1

Compressed sensing radar

Matthew Herman and Thomas Strohmer
Department of Mathematics, University of California
Davis, CA 95616-8633, USA
e-mail: {mattyh,strohmer}@math.ucdavis.edu

Abstract—A stylized compressed sensing radar is proposed in When f = g we have the (self) ambiguity function Af (τ, ω).
which the time-frequency plane is discretized into an N by N The shape of the ambiguity surface |Af (τ, ω)| of f is bounded
grid. Assuming that the number of targets K is small (i.e., above the time-frequency plane (τ, ω) by |Af (τ, ω)| ≤
K  N 2 ), then we can transmit a sufficiently “incoherent” pulse
and employ the techniques of compressed sensing to reconstruct Af (0, 0) = kf k22 .
the target scene. A theoretical upper bound on the sparsity K is The radar uncertainty principle [2] states that if
presented. Numerical simulations verify that even better perfor- ZZ
mance can be achieved in practice. By comparing traditional
uncertainty principles with those of compressed sensing, this |Af g (τ, ω)|2 dτ dω ≥ (1 − ε) kf k22 kgk22 (3)
novel approach reveals great potential for better resolution over U
classical radar.
for some support U ⊆ R2 and ε ≥ 0, then |U | ≥ (1 − ε).
Index Terms—Compressed sensing, sparse recovery, Alltop Informally, this can be interpreted as saying that the area of an
sequence.
ambiguity function’s “footprint” on the time-frequency plane
can only be made so small.
I. I NTRODUCTION
In classical radar, the ambiguity function of f is the main
Radar, sonar and similar imaging systems are in high de- factor in determining the resolution between targets [3]. There-
mand in many civilian, military, and biomedical applications. fore, the ability to identify two targets in the time-frequency
The resolution of these systems is limited by classical time- plane is limited by the essential support of Af (τ, ω) as dictated
frequency uncertainty principles. Using the concepts of com- by the radar uncertainty principle. The primary result of this
pressed sensing (CS), we propose a radically new approach to paper is that, under certain conditions, CS radar achieves better
radar. In this simplified version of a monostatic, single-pulse target resolution than classical radar.
radar system we assume that the targets are radially aligned
with the transmitter and receiver.
There are three key points to be aware of: (1) The transmit- II. C OMPRESSED S ENSING
ted signal must be sufficiently “incoherent.” Our results rely on
the use of a deterministic signal (the Alltop sequence), how- Recently, the signal processing/mathematics community has
ever, transmitting white noise would yield a similar outcome. seen a paradigmatic shift in the way information is represented,
(2) This approach does not use a matched filter. (3) The target stored, transmitted and recovered [4], [5], [6]. This area is
scene is recovered by exploiting the sparsity constraints. often referred to as Sparse Representations and Compressed
This report is a first step in formalizing the theory of CS Sensing. Consider a discrete signal s of length M (note,
radar and contains many assumptions. In particular, analog to boldface variables denote vectors and matrices). We say that
digital (A/D) conversion and related implementation details it is K-sparse if at most K  M of its coefficients are
are ignored. nonzero (perhaps under some appropriate change of basis).
Throughout this discussion we only consider functions With this point of view the true information content of s
with finite energy; that is, if f ∈ L2 (R), then kf k22 = lives in at most K dimensions rather than M . In terms of
|f (t)|2 dt < ∞. The cross-ambiguity function for two
R
R signal acquisition it makes sense then that we should only
functions f, g ∈ L2 (R) is defined as [1] have to measure a signal N ∼ K times instead of M . We do
Z
this by observing N non-adaptive, linear measurements in the
Af g (τ, ω) = f (t + τ /2)g(t − τ /2)e−2πiωt dt (1)
R form of y = Φs, where Φ is a dictionary of size N × M .
where · denotes complex conjugation, and the upright Roman If Φ is sufficiently “incoherent,” then the information of s
√
letter i = −1. The short-time Fourier transform (STFT) of f will be embedded in y such that it can be perfectly recovered
with respect to g is Vg f (τ, ω) = R f (t)g(t − τ )e−2πiωt dt. A with high probability. Current reconstruction methods include
R

simple change of variable reveals that within a complex factor, using greedy algorithms such as orthogonal matching pursuit
the cross-ambiguity function is equivalent to the STFT (OMP) [6], and solving the convex problem: min ks0 k1 such
that Φs0 = y. The latter program is often referred to as Basis
Af g (τ, ω) = eπiωτ Vg f (τ, ω). (2) Pursuit (BP) [4], [5]. A new algorithm, regularized orthogonal
This work was partially supported by NSF Grant No. DMS-0511461 and matching pursuit (ROMP) [7], has recently been proposed
NSF VIGRE Grant No. DMS-0135345. which combines the advantages of OMP with those of BP.

1-4244-1539-X/08/$25.00 ©2008 IEEE

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.
 2

III. M ATRIX I DENTIFICATION VIA C OMPRESSED S ENSING C. The Basis of Time-Frequency Shifts

A. Problem Formulation Let the N × N matrices T and M respectively

0
denote the unit shift and modulation operators where
Consider an unknown matrix H ∈ CN ×N and an or- T (f0 , . . . , fN −2 , fN −1 )T = (fN −1 , f0 , . . . , fN −2 )T , M =
0
N −1
thonormal basis (ONB) (H i )i for CN ×N . Then there exist diag{ωN 0
, . . . , ωN }, and ωN = e2πi/N is the N th root of
coefficients (si )i such that unity. The ith time-frequency basis element is defined as

N 0 −1
NX H i = M i mod N · T bi/N c (7)
H = si H i . (4)
i=0
where b·c is the floor function. A simple calculation shows
2
−1
that the family (H i )N
i=0 forms an ONB with respect to the
Our goal is to identify/discover the coefficients (si )i . Since Frobenius norm. Furthermore, under this basis it is known that
the basis elements are fixed, identifying (si )i is tantamount to some practical systems H with meaningful applications have a
discovering H. We will do this by designing a test function sparse representation s [11], [12], [13]. This fact complements
0
f = (f0 , . . . , fN 0 −1 )T ∈ CN and observing Hf ∈ CN . the theorems developed in the subsequent sections.
Here, ( · )T denotes the transpose of a vector or a matrix. A finite collection of length-N vectors which are time-
Figure 1 depicts this from a systems point of view where H frequency shifts of a generating vector, and which spans
is an unknown “block box.” Systems like this are ubiquitous the space CN is called a (discrete) Gabor frame [2].
2
−1
in engineering and the sciences. For instance, H may repre- Since (H i )N
i=0 forms an ONB, it follow that our dictio-
sent an unknown communication channel which needs to be nary Φ is a Gabor frame. Without loss of generality assume
identified for equalization purposes. kf k2 = 1. Because each H i is a unitary matrix we have that
kϕi k2 = 1 for i = 0, . . . , N 2 − 1. We can also express Φ as
f −→ H −→ y = Hf the concatenation of N blocks
Black Box
 
Φ = Φ(0) | Φ(1) | · · · | Φ(N −1) (8)
Fig. 1. Unknown system H with input probe f and output observation y.
where the kth block Φ(k) = D k · WN with D k =
pq N −1
diag{fk , . . . , fN −1 , f0 , . . . , fk−1 } and WN = (ωN )p,q=0 .
For simplicity, from now on assume that N 0 = N . The
observation vector can be reformulated as
2 2
D. The Probing Test Function f
NX −1 NX −1
y = si H i f = si ϕi = Φs (5) We now introduce a candidate probe function f which
i=0 i=0
results in remarkable incoherence properties for the dictio-
N −1
nary Φ. Consider the Alltop sequence fA = (fn )n=0 for some
where the ith atom ϕi = H i f is a column vector of length N , prime N ≥ 5 where [14]
the concatenation of the atoms Φ = ( ϕ0 | ϕ1 | · · · | ϕN 2 −1 )
1 3
is an N × N 2 matrix, and s = ( s0 , s1 , · · · , sN 2 −1 )T is a fn = √ e2πin /N . (9)
column vector of length N 2 . The system of equations in (5) is N
clearly highly underdetermined. If s is sufficiently sparse, then Let ΦA denote the Gabor frame generated by the Alltop
there is hope of recovering s from y. To use the reconstruction sequence (9). Since its atoms are already grouped into N × N
methods of CS we need to design f so that the dictionary Φ blocks in (8), we will maintain this structure by denoting the
is sufficiently incoherent. (k)
jth atom of the kth block as ϕj . Note that kfA k2 = 1, so we
(k) (k0 )
have 0 ≤ |hϕj , ϕj 0 i| ≤ 1 for any j, j 0 , k, k 0 = 0, . . . , N −1.
Within the same block (i.e., k = k 0 ) we have
B. The Coherence of a Dictionary
0, if j 6= j 0

(k) (k)
We are interested in how the atoms of a general dictionary Property 1: |hϕj , ϕj 0 i| =
1, if j = j 0 .
Φ = (ϕi )i ∈ CN ×M (with N ≤ M ) are “spread out” in CN .
This can be quantified by examining the magnitude of the inner Thus, each Φ(k) is an ONB for CN . Moreover, for different
product between its atoms. The coherence µ(Φ) is defined blocks (i.e., k 6= k 0 ) we have
as the maximum of all of the distinct pairwise comparisons
(k) (k0 ) 1
µ(Φ) = maxi6=i0 |hϕi , ϕi0 i|. Assuming that each kϕi k2 = 1 Property 2: |hϕj , ϕj 0 i| = √
the coherence is bounded [8], [9] by N
s for all j, j 0 = 0, . . . , N − 1. This means that there is a mutual
M −N incoherence between the √ atoms of different blocks Trivially, it
≤ µ(Φ) ≤ 1. (6) 2
N (M − 1) follows that µ(ΦA ) = 1/ N . Furthermore, √ with M = N in
(6) we see that the lower bound of 1/ N + 1 is practically
When a dictionary can be expressed as
√the union of 2 or more attained. (See [15] for more details on this, mutually unbiased
ONBs, this lower bound becomes 1/ N [10]. bases (MUBs), and equiangular line sets.)

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.
 3

E. Identifying Matrices via Compressed Sensing: Theory Furthermore, the overly strict constraint of Theorem 1 can
Having established the incoherence properties of the be seen√by the lower dash-dotted, blue line representing
dictionary ΦA we can now move on to apply the concepts K = 12 ( N + 1).
and techniques of CS. It is worth pointing out that most CS
scenarios deal with a K-sparse signal s (for some fixed K),
and one is tasked with determining how many observations
are necessary to recover the signal. Our situation is markedly
different. Due to the fact that ΦA is constrained to be N ×N 2 ,
we know y = ΦA s we will contain exactly N observations.
With N fixed, our CS dilemma is to determine how sparse s
should be such that it can be recovered from y. We hope to
recover any K-sparse signal s with K ≤ C · N/ log N for
some C > 0. The following two theorems [15] summarize
the recovery of N × N matrices via CS when identified with
the Alltop sequence with prime N ≥ 5.
Theorem 1: Suppose H = i si H i ∈ CN ×N has a K-
P
sparse representation
√ under the time-frequency ONB, with
K < 21 ( N + 1), and that we have observed y = HfA .
Then we are guaranteed to recover s either via BP or OMP.
The sparsity condition in Theorem 1 is rather strict. Instead
of the requirement of guaranteed perfect recovery, we can ask Fig. 2. Matlab simulation of solving min ks0 k1 s.t. ΦA s0 = ΦA s where s
to achieve it with only high probability. This more modest is random. The solid, gray-black lines are the contours of the error ks − s0 k2
expectation provides us with a much more realistic sparsity vs. the N -K domain. The dashed, red line shows that Theorem 2 is overly
pessimistic. The region below this is the zone of “perfect reconstruction.” The
condition. Throughout this paper a random signal refers lower dash-dotted, blue line illustrates how Theorem 1 is too strict.
to a vector or matrix with nonzero coefficients which are
independent with a Gaussian distribution of zero mean and
unit variance, and which are located according to a uniform
distribution. IV. R ADAR
N ×N A. Classical Radar Primer
P
Theorem 2: Suppose random H = i si H i ∈ C
has a K-sparse representation under the time-frequency
√ ONB Consider the following simple (narrowband) 1-dimensional,
where K ≤ N/16 log (N/ε) with ε ≤ 1/ 2, and that monostatic, single-pulse radar model. Monostatic refers to
we have observed y = HfA . Then BP will recover s with the setup where the transmitter (Tx) and receiver (Rx) are
probability
p greater than 1 − 2ε2 − K −ϑ for some ϑ ≥ 1 s.t. collocated. Suppose a target located at range x is traveling
ϑ log N/ log (N/ε) ≤ c where c is an absolute constant. with constant velocity v and has reflection coefficient sxv .
Figure 3 shows such a radar with one target. After transmitting
F. Identifying Matrices via Compressed Sensing: Simulation signal f (t), the receiver observes the reflected signal
Numerical simulations were performed and indicate that the r(t) = sxv f (t − τx )e2πiωv t (10)
theory above is actually quite pessimistic. The simulations
were conducted as follows. The values of prime N ranged where τx = 2x/c is the round trip time of flight, c is the
from 5 to 127, and the sparsity K ranged from 1 to N . For speed of light, ωv ≈ −2ω0 v/c is the Doppler shift, and ω0 is
each ordered pair (N, K) a K-sparse vector s of length N 2 the carrier frequency. The basic idea is that the range-velocity
was randomly generated. With this random s the observation information (x, v) of the target can be inferred from the
y = ΦA s was generated. Then, y and ΦA were input to a observed time delay-Doppler shift (τx , ωv ) of f in (10). Hence,
linear program [16] to solve min ks0 k1 s.t. ΦA s0 = y. This a time-frequency shift operator basis is a natural representation
procedure was repeated 15 times and averaged. for radar systems [17].
Figure 2 shows how the numerical simulations compare
to Theorems 1 and 2. The error ks − s0 k2 as a function f
of (N, K) is shown as solid, gray-black contour lines. The - L

|= m
dashed, red line represents K = N/ log N . The zone of r
“perfect reconstruction” lies below this line. In this region Tx/Rx Target
random N × N matrices with 1 ≤ K ≤ N/ log N nonzero
entries can be perfectly recovered with high probability. This is Fig. 3. Simplified radar model. Tx transmits signal f , and Rx receives the
reflected (or echoed) signal r according to (10).
empirical evidence that the denominator of K in Theorem 2
can be relaxed from log (N/ε) to just log N , and that the
proportionality constant C = 1. However, it is still an open Using a matched filter at the receiver, the reflected signal r
mathematical problem to prove this for the Alltop sequence. is correlated with a time-frequency shifted version of the

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.
 4

N −1
transmitted signal f via the cross-ambiguity function (1)

Z
|Arf (τ, ω)| = r(t)f (t − τ )e−2πiωt dt
R • 
= |sxv Af (τ − τx , ω − ωv )|. (11)  •
↑ •
From this we see that the time-frequency plane consists of  
ω 
the ambiguity surface of f centered at the target’s “loca-
•
tion” (τx , ωv ) and scaled by its reflection coefficient |sxv |. •

Extending (11) to include multiple targets is straightforward. 
Figure 4 illustrates an example of the time-frequency plane
with five targets; two of these have overlapping uncertainty
regions. The uncertainty region is a rough indication of the 0 N −1
essential support of Af in (3). Targets which are too close τ→
will have overlapping ambiguity functions. This may blur the
Fig. 4. The time-frequency plane discretized into an N × N grid. Shown are
exact location of a target, or make uncertain how many targets five targets with their associated uncertainty regions. Classical radar detection
are located in a given region in the time-frequency plane. Thus, techniques may fail to resolve the two targets whose regions are intersecting.
the range-velocity resolution between targets of classical radar In contrast, CS radar will be able to distinguish them as long as the total
number of targets is much less then N 2 .
is limited by the radar uncertainty principle.

B. Compressed Sensing Radar C. Compressed Sensing and Classical Radar Simulations

We now propose our stylized CS radar which under ap-
Figures 5 and 6 show the result of Matlab radar simulations.
propriate conditions can “beat” the classical radar uncertainty
For purposes
√ of normalization the grid spacing in these figures
principle! Consider K targets with unknown range-velocities
is 1/ N . Hence, √ the numbers shown on the axes represent
and corresponding reflection coefficients. Next, discretize the
multiples of 1/ N . A random time-frequency scene with
time-frequency plane into an N × N grid as depicted in
K = 10 targets and N = 47 is presented in Figure 5(a).
Figure 4. Recognizing that each point on the grid represents
Targets which are darker indicate a larger reflection coefficient.
a unique time-frequency shift H i (7) (with a corresponding
The CS radar simulation [16] used the Alltop sequence to
reflection coefficient si ), it is easy to see that every possible
identify the targets. In Figure 5(b) it is clear that CS was
target scene can be represented by some matrix H (4). If the
able to perfectly reconstruct the target scene when there was
number of targets K  N 2 , then the time-frequency grid
no added noise. Based on the grid of the discretized time-
will be sparsely populated. By “vectorizing” the grid, we can
frequency plane in Figure 5 it is obvious that we can resolve
represent it as an N 2 × 1 sparse vector s.
targets located at adjacent
√ grid points. Thus, CS radar has a
Assume that the Alltop sequence is sent by the transmitter1 .
resolution of 1/2 N .
The received signal now is of the form in (5). If the number of
Figure 5(c) illustrates how CS starts to suffer in the presence
targets obey the sparsity constraints in Theorems 1 and 2, then
of additive white Gaussian noise (AWGN). Here the signal-
we will be able to reconstruct the original target scene using
to-noise ratio (SNR) is 15 dB. Some faint false positives have
CS techniques. In reality, we are not actually “beating” the
appeared, yet the target scene has still been identified. The
classical uncertainty principle as claimed above. Rather, we
performance with 5 dB SNR is shown in Figure 5(d). Several
are just transferring to a different mathematical perspective.
targets were lost and many false positives have appeared,
The new CS uncertainty principle is dictated by the sparsity
which is clearly undesirable. It remains an open problem in
constraints of Theorems 1 and 2.
the CS community how to deal with such noisy situations.
It is interesting to note that Alltop specifically mentions
As a comparison to CS Figure 6 presents classical radar
the applicability of his sequence to spread-spectrum radar.
reconstruction (which uses a matched filter as described
The cubic phase in (9) is known in classical radar as a
in Section IV-A) with two different transmitted pulses. The
discrete quadratic chirp, which is similar to what bats use
ambiguity surfaces associated with these two waveforms
to “image” their environment (although bats use a continuous
demonstrate, in some sense, two extremes of traditional radar
sonar chirp). The use of a chirp is an effective way to transmit
performance. In the first case, the ambiguity surface is a
a wide-bandwidth signal over a relatively short time duration.
relatively wide Gaussian pulse, whereas in the second case
However, here in CS radar we make use of the incoherence
the ambiguity surface is a highly concentrated “thumbtack”
property of the Alltop sequence, which is due to specific
function. We stress that these are not necessarily the final
properties of prime numbers. Recall the three key points of this
results of traditional target reconstruction, and are included
novel approach: (1) the transmitted signal must be incoherent,
only for rough comparison. In practice, radar engineers use
(2) there is no matched filter, (3) instead, CS techniques are
extremely advanced techniques to determine target range and
used to recover the sparse target scene.
velocity.
1 The transmitter in Fig. 3 sends analog signals. We assume here that there Figures 6(a), 6(c), and 6(e) show the original target scene
exists a continuous signal which when discretized is the Alltop sequence (9). of Figure 5(a) reconstructed using a Gaussian pulse. The (self)

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.
 5

Fig. 5. Radar simulation with K = 10 targets on a 47 × 47 time-frequency

grid. (a) Original target scene. CS reconstruction of original target scene with
SNR: (b) ∞ dB, (c) 15 dB, (d) 5 dB. Notice CS perfectly recovers (a) in the
case of no noise (b).

ambiguity function associated with a Gaussian pulse is a two-

dimensional Gaussian pulse as a result of the STFT in (2).
Therefore, according to (11) we see that the radar scenes in
these figures consist of a 2D Gaussian pulse centered at each
Fig. 6. Traditional radar reconstruction of Fig. 5(a)’s original target scene.
target in the time-frequency plane. In each of these it is clear With no noise: (a) Gaussian pulse, (b) Alltop sequence. With SNR = 15 dB:
that some of the targets are contained within the Heisenberg (c) Gaussian pulse, (d) Alltop sequence. With SNR = 5 dB: (e) Gaussian
boxes of neighboring targets. Depending on the sophistication pulse, (f) Alltop sequence.
of subsequent algorithms some of the targets (e.g., the two
closest in the center) may be unresolvable. It is also clear
that Figures 6(c) and 6(e) suffer from added noise, and this surface has this thumbtack feature. Other thumbtack-like am-
compounds the problem of accurate resolution [3]. biguity surfaces include those associated with the waveforms
As a consequence of the grid spacing, the Heisenberg box which generate the equiangular line sets found in [18].
associated with the Gaussian pulse’s ambiguity surface has Figures 6(b), 6(d), and 6(f) depict the original target scene
been normalized to a square of unit area. This is empirically traditionally reconstructed using the Alltop sequence. Take
verified in Figures 6(a), 6(c), and 6(e) where we see that the note of the distinction with compressed sensing radar pre-
diameter of the uncertainty region around each target spans√ap- sented in Section IV-B which also uses this function. Here, the
proximately seven grid points. Since the grid spacing is 1/ N classical approach transmits the Alltop sequence, and then uses
we confirm that the base and √ height of the Heisenberg box a matched filter to correlate the received signal with a time-
are each approximately 7/ 47 ≈ 1. Therefore, we have a frequency shifted Alltop sequence as in (11). The radar scene
rough measure of the target resolution of a Gaussian pulse: will now consist of a thumbtack function centered at each
here classical radar yields a resolution of 1/2. Comparing target. In theory, this radar would provide target resolution
the resolution
√ of classical radar with that of CS we see that similar to our CS version (i.e., the target is represented as
1/2 > 1/2 N for N ≥ 2. Thus, we claim that CS radar a point source in time-frequency plane rather than a “spread
can achieve better resolution than classical radar. Moreover, out” uncertainty region).
by increasing N the time-frequency plane will be discretized However, the situation is not so simple. The non-zero
into a finer grid and this will increase CS’s resolution. Of portions of the ambiguity function can accumulate to create
course, there are practical limits on how large N can be (e.g., undesirable effects. This is shown in Figure 6(b) where it is
implementation details such as A/D conversion and related apparent, even in the ideal case of no added noise, that there
hardware issues which we ignore in this paper). is a great deal of interference. Moreover, this type of “noise”
In contrast to a Gaussian pulse we now examine a waveform is deterministic and cannot be remedied by averaging over
whose associated ambiguity surface is thumbtack-like. A func- multiple observations. Notice that the interference seems to be
tion is “thumbtack-like” if all of its values are are close to zero distributed over a wide range of amplitudes. In fact, referring
except for a unique large spike. Due to Properties 1 and 2 of to the original target scene in Figure 5(a), it appears that some
the Alltop sequence in Section III-D we see that its ambiguity of of the weaker targets have been buried in this noise. Even

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.
 6

if a reasonable threshold could be determined, perhaps only the context of CS. There is also the possibility of combining
the four or five strongest targets would be detected and many classical radar techniques with `1 recovery. Initial tests show
false positives would remain. that while we get good reconstruction, the results are not
We present these results to emphasize that naive application guaranteed, even in the case of no noise.
of traditional radar techniques with the Alltop sequence will Narrowband radar is by no means the only application to
fail if the radar scene contains more than just a few strong which the techniques presented here can be used. Wideband
targets. The outcome will be similar if other low-correlation radar admits a received signal which is well-represented by
sequences are used. a wavelet basis, and the dictionary Φ could be reformulated
Regardless of whether a transmitted waveform has an am- accordingly. There are also applications to many other linear
biguity surface which is spread or narrow, interference from time-varying systems such as sonar, estimation of underwa-
adjacent targets will necessarily occur in classical radar, and ter acoustic communication channels [12], and blind source
this will result in undesirable effects. In contrast, CS radar does separation [13].
not experience this interference since it completely dispenses
with the need for a matched filter. Therefore, there are no R EFERENCES
issues with the ambiguity function of the transmitted signal. [1] R. E. Blahut, “Theory of remote surveillance algorithms,” in Radar and
Sonar, Part I, ser. IMA Volumes in Mathematics and its Aplications,
R. E. Blahut, W. Miller Jr., and C. H. Wilcox, Eds. NY: Springer-
V. D ISCUSSION Verlag, 1991, vol. 32, pp. 1–65.
[2] K. Gröchenig, Foundations of time-frequency analysis. Boston:
We have provided a sketch for a high-resolution radar Birkhäuser, 2001.
system based on CS. Assuming that the number of targets [3] A. W. Rihaczek, High-Resolution Radar. Boston: Artech House, 1996,
obey the sparsity constraint in Theorem 2, the Alltop sequence (originally published: McGraw-Hill, NY, 1969).
[4] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52,
will perfectly identify the radar scene with high probability no. 4, pp. 1289–1306, 2006.
using CS techniques. Numerical simulations confirm that this [5] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertaitny principles:
sparsity constraint is too strict and can be relaxed to K ≤ Exact signal reconstruction from highly incomplete frequency informa-
tion,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb. 2006.
N/ log N , although this has yet to be proven mathematically. [6] J. A. Tropp, “Greed is good: Algorithmic results for sparse approxima-
It must be emphasized that our model presents radar in an tion,” IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2231–2242, Oct.
overly simplified manner. In reality, radar engineers employ 2004.
[7] D. Needell and R. Vershynin, “Uniform uncertainty principle and
highly sophisticated methods to identify targets. For example, signal recovery via regularized orthogonal matching pursuit,” July 2007,
rather than a single pulse, a signal with multiple pulses is often preprint.
used and information is averaged over several observations. [8] R. A. Rankin, “The closest packing of spherical caps in n dimensions,”
Proc. Glasgow Math. Assoc., vol. 2, pp. 139–144, 1955.
We also did not address how to discretize the analog signals [9] L. R. Welch, “Lower bounds on the maximum cross-correlation of
used in both CS and classical radar. A more detailed study signals,” IEEE Trans. Inf. Theory, vol. 20, no. 3, pp. 397–399, 1974.
addressing these issues is the topic of another paper. [10] P. Delsarte, J. M. Goethals, and J. J. Seidel, “Bounds for systems of
lines and Jacobi poynomials,” Philips Res. Repts, vol. 30, no. 3, pp.
Related to the discretization issue is the fact that CS radar 91∗ –105∗ , 1975, issue in honour of C.J. Bouwkamp.
does not use a matched filter at the receiver. This will directly [11] P. A. Bello, “Characterization of randomly time-variant linear channels,”
impact A/D conversion, and has the potential to reduce the IEEE Trans. on Comm., vol. 11, no. 4, pp. 360–393, Dec. 1963.
[12] W. Li and J. C. Preisig, “Estimation and equalization of rapidly varying
overall data rate and to simplify hardware design. These sparse acoustic communication channels,” Proc. IEEE OCEANS 2006,
matters are discussed in [19], although it does not consider pp. 1–6, Sept. 2006.
the case of moving targets. In our study the major benefit of [13] Z. Shan, J. Swary, and S. Aviyente, “Underdetermined source separation
in the time-frequency domain,” Proc. IEEE ICASSP 2007, pp. 945–948,
relinquishing the matched filter is to avoid the target uncer- April 2007.
tainty and interference resulting from the ambiguity function. [14] W. O. Alltop, “Complex sequences with low periodic correlations,” IEEE
Trans. Inf. Theory, vol. 26, no. 3, pp. 350–354, May 1980.
Since many of the implementation details of our CS radar [15] M. Herman and T. Strohmer, “High-resolution radar via compressed
have yet to be determined, and since classical radar can also be sensing,” Sub. to IEEE Trans. Sig. Proc., Oct. 2007.
implemented in many ways we were only able to make a rough [16] M. Grant, S. Boyd, and Y. Ye, “cvx: Matlab software
for disciplined convex programming.” [Online]. Available:
comparison between their respective resolutions. Regardless, http://www.stanford.edu/∼boyd/cvx/
the radar uncertainty principle lies at the core of traditional [17] L. Auslander and R. Tolimieri, “Radar ambiguity functions and group
approaches and limits their performance. We contend that CS theory,” SIAM Journal on Mathematical Analysis, vol. 16, no. 3, pp.
577–601, 1985.
provides the potential to achieve higher resolution between [18] S. D. Howard, A. R. Calderbank, and W. Moran, “The finite Heisenberg-
targets. The radar simulations presented confirm this claim. Weyl groups in radar and communications,” EURASIP Journal on
It must be stressed again that the success of this stylized CS Applied Signal Processing, vol. 2006, pp. 1–12, article ID 85685.
[19] R. Baraniuk and P. Steeghs, “Compressive radar imaging,” Proc. 2007
radar relied on the incoherence of the dictionary ΦA resulting IEEE Radar Conf., pp. 128–133, Apr. 2007.
from the Alltop sequence. There exist other probing functions [20] G. E. Pfander, H. Rauhut, and J. Tanner, “Identification of matrices
with similar incoherence properties. Numerical simulations having a sparse representation,” preprint June 2007.
with f as a random Gaussian signal, as well as a constant-
envelope random-phase signal indicate similar behavior to
what we have reported for the Alltop sequence. At the time
of writing this paper we became aware of a similar study
[20] where the properties of these functions are analyzed in

Authorized licensed use limited to: Universitat Wien. Downloaded on November 26, 2009 at 07:31 from IEEE Xplore. Restrictions apply.