untitled

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, NO. 21, NOVEMBER 1, 2014 5565

Direction of Arrival Estimation Using Co-Prime

Arrays: A Super Resolution Viewpoint

Zhao Tan, Student Member, IEEE,YoninaC.Eldar, Fellow, IEEE, and Arye Nehorai, Fellow, IEEE

Abstract—We consider the problem of direction of arrival

(DOA) est

imation using a recently proposed structure of nonuni-

form linear arrays, referred to as co-prime arrays. By exploiting

the second order statistical information of the received signals,

co-pr

ime arrays exhibit

degrees of freedom with only

sensors. A sparsity-based recovery algorithm is pro-

posed to fully utilize these degrees of freedom. The suggested

met

hod is based on the developing theory of super resolution,

which considers a continuous range of possible sources instead of

discretizing this range onto a grid. With this approach, off-grid

ffects inherent in traditional sparse recovery can be neglected,

thus improving the accuracy of DOA estimation. We show that

in the noiseless case it is theoretically possible to detect up to

sources with only sensors. The noise statistics of

co-prime arrays are also analyzed to demonstrate the robustness

of the proposed optimization scheme. A source number detection

method is presented based on the spectrum reconstructed from

the sparse method. By extensive numerical examples, we show the

superiority of the suggested algorithm in terms of DOA estimation

accuracy, degrees of freedom, and resolution ability over previous

techniques, such as MUSIC with spatial smoothing and discrete

sparse recovery.

Index Terms—Co-prime arrays, continuous sparse recovery,

direction of arrival estimation, source number detection, super

resolution.

I. INTRODUCTION

N the last few decades, research on direction of arrival

(DOA) esti

mation using array processing has focused

primarily on uniform linear arrays (ULA) [1]. It is well k now n

that using a ULA with

sensors, the n umber of sources that

can be res

olved by MUSIC-like algorithm s is

[2].

New geometries [3], [4] of non-uniform linear arrays have

been recently proposed to increase the degrees of freedom of

Manuscript received December 17, 2013; revised May 27, 2014 and August

25, 2014; accepted August 26, 2014. Date of publication September 04, 2014;

date of current version October 02, 2014. The associate editor coordinating the

review of this manuscript and approving it for publication was Dr. Chong-Yung

Chi. The work of Z. Tan and A. Nehorai was supported by the AFOSR Grant

FA9550-11-1-0210, and ONR Grant N000141310050. The work of Y. C. Eldar

was supported in part by the Israel Science Foundation under Grant no. 170/10,

in part by the Ollendorf Foundation, and in part by a Magneton from the Israel

Ministry of Industry and Trade.

Z. Tan and A. N ehorai are with the Preston M. Green Department of

Electrical and Systems E n gineering Department, Washington University

in St. Lou is, St. Louis, MO 63130 USA (e-mail: [email protected]. edu ;

[email protected]).

Y. C. Eldar is with the Departmen t of Electrical Engineering, Tech-

nion—Israel Institute of Technology, Haifa 32000, Israel (e-mail: yonina@

ee.technion.ac.il).

Color versions of one or more of the ﬁgures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Object Identiﬁer 10.1109/TSP.2014.2354316

the array by exploiting t he covariance matrix of the received

signals. Vectorizing the covari ance m atrix, the system model

can be view

ed as a v irtual array w ith a wider aperture. In [3],

a nested array structure was proposed to increase the degrees

of freedom from

to ,withonly sensors.

However,

some of the sensors in this structure are closely

located, which leads t o mutual coupling among these sensors.

To overco me this shortcomin g, co-prime arrays were prop osed

in [4]. S

uch arrays consist of two subarrays with

and

sensors respectively. It was shown th at by using

number of sensors, this structure can achieve degrees

of free

dom. In this paper we f ocu s o n co-prim e arrays.

The increased degrees of freedom provided by the co-prim e

structure can be utilized to improve DOA estimation. To this

end, two

main methodologies have been proposed to utilize t his

increased degrees of freedom for c o-prime arrays. The ﬁrst are

subspace methods, such as the MUSIC algorithm . In [5], a spa-

tial sm

oothing technique was impl emented prior to the appli -

cation of M USIC, and the authors showed that an increased

number of sources can be detected. However, the application

of spat

ial smoothin g reduces the obtained virtual array aperture

[6]. The second approach uses sparsity-based recovery to over-

come these d isadvantages of subspace m etho ds [6]–[9]. Tradi-

tiona

l sparsity techniques discretize the range of interest on to a

grid. Off-grid targets can lead to mismatches in the model and

deteriorate the performance signiﬁcan tly [10]. In [11], [12] the

grid m

ismatches are estimated simultaneously with the origin a l

signal, leading to improved performance over traditional sparse

recovery methods. In [13], the joint sparsity between the orig-

inal

signal and the mismatch is exploited d uring D OA estim a -

tion. Due to the ﬁrst-order approximation used in [13], the es-

timation perform a nce is still li mi ted by higher-order modeling

mism

atches.

To overcome grid mismatch of traditional sparsity-based

methods, in this paper we apply the recently developed

mathe

matical theory of continuous sparse recovery for super

resolution [14]–[16] to DOA estimation with co-prime ar ray s.

The term “super resolution” in this paper is related to the

off-

grid problem and is different from the tradition al deﬁnition

commonly used in DOA estimation. In [14], [1 5] it was shown

that assuming a signal co nsists of spikes, the high frequency

cont

ent of the signal’s spectrum can be perfectly recovered in

a robust fashion by sampling only the low end of its spectru m,

when the minimum distance between spikes satisﬁes certain

req

uirements. In [16], the author provides performance guar-

antees on the r ecov ered support set of the sparse signal. One

merit of this theory is that it considers all possible locations

wit

hin the desired range, and thus does not suffer from mod el

mismatches.

1053-587X © 20 14 IEEE. Personal use is permitted, but re pu b lication/redistribution requ ires IEEE permission.

See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

5566 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

Here we extend the mathematical theo ry of super resolution

to DOA estimation with co-prime arrays under Gaussian noise.

The effective no ise resulting from the usage of co-prime arrays

consists of a term with a known structur e and another term con-

taining quadratic combinations of Gaussian noise. Therefore,

we modify the reconstruction m etho d to ﬁt t hese pa rticular noise

properties and prove the robustn ess of our approach by ana-

lyzing the noise statistics. We also prove that with

sen-

sors in a co-prime array, it is possible to detect up to

sources robustly. Previous identiﬁability research using tradi-

tional com pressed seining for co-prime arrays [9] was based on

the idea of mutual coherence [17]. Using mutual coherence it

can be shown that co-prime arrays increase the number of de-

tected sources from

to , but this analysis is

valid only for very small values of the number of sources.

Source number detection i s another main application of array

processing. Various methods have been proposed over the years

based on the eigenvalues of the signal space, such as the Akaike

information criterio n [18], second-o rder statistic of eigenvalues

(SORTE) [19], and the predicted eigen-threshold approach [20].

The a uth ors of [21] showed that among these m ethods, S ORTE

often leads to better detection performance. Here we combine

the SORTE approach with the spectrum reconstructed f rom the

proposed DOA estimation algorithm to determine the numb

of sources. Through this source num ber detection, we identify

which reconstructed spikes are true detections and which are

false alarms.

The paper is organized as follows. In Section II, we int rod uce

the DOA estimation model and explain how co-prime arrays

can increase the degrees of freedom. In Section III, w

eadapt

the theory of super resolution to co-pr ime a r ray s, and analyze

the robustness of this ex tension by studying the statistics of t he

noisepatterninthemodel.Weproposeanumerica

l method to

perform DOA estimation for co-prime arra ys in Section IV. We

then extend th is approach to detect the number of sources in

Section V. Section V I presents extensive numer

ical simulations

demonstrating the advantages of our method in terms of estima-

tion accuracy, degrees of freedom, and resolution ability.

Throughout the paper, we use capital italic bold

letters to

represent matrices and operators, and lowercase italic bold let-

ters to represent vectors. For a given matrix

, denotes the

conjugate transpose matrix,

denotes the t ra

nspose,

rep-

resents the conjugate matrix witho ut transpose, and

de-

notes the

th element of .Weuse to denote the Kro-

necker product of two matrices. For a given op

erator

, de-

notes the conjugate op erato r of

. Given a vector ,weuse

and for the and norms; and are both

used to represent the

th element of .Give

n a function

are its norms.

II. D

IRECTION OF ARRIVAL ESTIM ATION AND

CO-PRIME ARRAYS

Consider a linear sensor array with sensors which may

be non-uniformly lo cated. Assume that there are

narrow

band sources located at

with signal powers

. The steering vector for the th source located

is with th element ,

in which

is the location of the th sensor and is the

wavelength. The data collected by all sensors at time

can be

expressed as

(1)

for

,where

is an i.i.d. white Gaussian noise ,

,and

represents the source

signal vector w ith

distributed as . We assum e

that the sources are temporally uncorrelated.

The correlation matrix of the data can be expressed as

(2)

in which

is a diagonal matrix with diagonal elem ents

. After vectorizing the correlation matrix ,

we have

(3)

where

(4)

,and with

denoting a vector with all zero elements, except for the th ele-

ment, which equals one.

Comparing (1) with (3), we see that

behaves like a coherent

source and

becomes a deterministic noise term. The dis-

tinct rows in

act as a larger virtual array with sensors located

,with . Traditional DOA estimation al-

gorithms can be implemented to detect m ore sources when the

structure of the sensor array is properly designed. Following this

idea, nested arrays [3] and co-prime arrays [4] were introduced,

and then shown to increase the degrees of freedom from

to , and from to respectively. In the

following, we focus o nly on co-prime arrays; the resul ts follow

naturally for nested arrays.

Consider a co-prime array structure consisting of two arrays

with

and sensors respectively. Th e location s of the

sensors are in the set , and the locations

of the

sensors are in the set as

illustrated in Fig. 1. The ﬁrst sensors of these two arrays are

collocated. The geometry of such a co-prime array is shown in

Fig. 1. The locations of the virtual sensors in

from (3) are

given by the cross difference set

and the two self difference sets.

In order to implement spatial smoothing of MUSIC, or to use

other popular DOA estimation techniques, we are interested in

generating a co nsecutive range of virtual sensors. It was shown

TAN et al.: A SUPER RESOLUTION VIEWPOINT 5567

Fig. 1. Geometry of co-prime arrays.

in [5] that when and are co-prime numbers, a consecutive

range can be created from

to , with

taken from the cross difference set and taken from any one

of the self d ifference sets.

By removing repeated rows of (3) and sorting the remaining

rows from

to , we have the linear m odel rear-

ranged as

(5)

Itiseasytoverifythat

is a vector whose

elements all equal zero, except t he

th element, which

equals one. The matrix

is given by

which is the steering matri x of a ULA with sen-

sors. Therefore, (5) can be regarded as a ULA detecting a co-

herent source

with determ ini stic noise term . By applying

MUSIC with spatial smoothing, the authors in [5] showed th at

sources can be detected, using this approach.

III. DIRECTION OF ARRIVAL ESTIMATION WITH SUPER

RESOLUTION RECOVERY

In this section we ﬁrst assume that the signal model (3) is

accurate, which means that the number of samples

is inﬁ-

nite, and also that the noise power

is known a priori. The

super resolution theory developed in [14] can then be applied to

co-prime arrays to demonstrate that we can detect up to

sources robustly as long as the distance between any two sources

is on the ord er of

. We then consider the case in which the

number of time samples

is limited a nd demonstrate the ro-

bustness of super resolution recovery via statistical analysis of

the noise structure.

A. Mathematical Theory of Super Resolution

Super resolution seeks to recover high frequency details from

the measurement of low frequency components. Mathem ati-

cally, given a measure

with , the Fourier series

coefﬁcients are recorded as

(6)

Using the operator

to denote the low frequency measuring

operator which transforms a signal from its con tinuous time do-

main into its discrete frequency domain, we can represent (6) as

,inwhich and

Suppose that the measure

is sparse, i.e., is a

weighted sum of several spikes:

(7)

in which

can be complex valued and for all .

Then

(8)

In order to recover

from the measurem ents ,total

variation minimization is introduced. This criterion encourages

thesparsityinthemeasure

,justas norm minimization

produces sparse signals in the discrete space. In the rest of the

paper, we will use

to denote the measure for simplicity.

The total variation for the complex measure

is deﬁned as

(9)

the supremum being taken over all partitions of the set

into countable coll ectio ns o f disjoint measurable sets .When

has the form ( 7 ), ,whichresemblesthe

discrete

norm.

The f ollow ing con vex optimization formula was proposed

in [14] to solve the super resolution problem which recovers a

sparse measure from

(10)

When the distance between any two

and is larger than ,

then the o ri ginal sparse s ignal

is the unique solution to the

above convex optimization [14 ]. Th e continu ous opti mization

(10) can b e solved via the dual problem [14]:

(11)

where

is a H er mi tian matrix and

is the Lagrangian multiplier for the constraint

. The primal solution is obtained through a combined

process of rooting ﬁnding and least-squares [14].

5568 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

B. DOA Estimation With TV- Norm Minimization

DOA estimation with co-prime arrays can be related to (8)

by a straightforward change of variables. Letting

for all , the linear model of (5) can be transformed

into

(12)

where

,and is a

sparse measure given in (7) with

. Note that the measure

is different from t he vector representation ,

and they are related by (7). The change of variables i s performed

to guarantee that

.Weuse to

denote the support set.

A theorem about the resolu tio n and degrees of freedom for

co-prime arrays can be directly derived using Theorem 1.2 in

[14]. Before introducing the theorem, we ﬁrst deﬁ ne the min-

imum distance between any tw o sources as

(13)

Theorem I II.1 : Consider a co-prime array consisting of

two linea r arrays with

and sensors respectively. The

distances between two consecutive sensors are

for the

ﬁrst array and

for the second array, where and are

co-prime numbers, and

. Sup pose we h ave sources

located at

. If the minimum distance follows the

constraint that

then by solving the convex optimization (10) with the signal

model

, one can recover the locations for

exactly. The number of sources that can be detected

With a co-prime array using sensors, the contin-

uous sparse recovery method can detect up to

sources

when

. The minimum distance constraint is a suf-

ﬁcient condition. In real applications we can expect a more re-

laxed distance condition for the sources. We will conﬁrm this

point in the numerical results. With the utilization of co-prime

arrays, the same number of sensors can detect

sources

as indicated by traditional M USIC theory [5]. We will show in

the numerical examples that implementing the super resolution

framework provides more degrees of freedom and ﬁner reso-

lution a bility than those of MUSIC. This is because the spatial

smoothing in MUSIC reduces the o btained virtual array aper-

ture. F or the noiseless case, other methods, such as Prony’s

method [22] and matrix pencil [23] can be used for exact re-

covery of

sources. However, they require prior infor-

mation about the system order, which we do n ot require here.

Furthermore, these methods are gener ally sensitive to noise i n

the model and therefore do not offer robustness guarantees.

C. Noisy Model for Sparse Recovery

In practice, the covariance m atrix

in (2) is typically un-

known, and cannot be estim a ted exactly unless the number of

samples

goes to inﬁnity. Typically the covariance matrix is

approximated by the sam ple covariance:

(14)

Subtracting the noise covariance matrix from both sides, we

obtain

(15)

Here

is a diagonal matrix w ith -th diagonal elem ent

(16)

and the

th element of isgivenby(see(1))

(17)

For simplicity of an a lysi s, we assume that

and

Similar to the operation in (3), vector izing (15) leads to

(18)

where

and . For co-prime ar-

rays, by removing repeated rows in (18), and sorting them as

consecutive lags from

to ,weget

(19)

in which

,and are deﬁned in (5). The vector is obtain ed

after rearranging

, a nd only one element from corresponds

to the diagonal element from

. Applying the transformatio n

technique in (12), we have

(20)

where

,and is the measure deﬁnedin(7)

with

. Thus we can formulate the following continuous

sparse recovery problem, which c onsiders the noise:

(21)

This optimization can be solved by ﬁrst solving the dual

problem [15]:

(22)

TAN et al.: A SUPER RESOLUTION VIEWPOINT 5569

As before, the primal solution is obtained through a combined

process of root ﬁnding and least-squares [15].

In order to analyze the robustness of the proposed approach

for co-prime arrays, we introduce a lemma that shows that the

probability of every element in

being larger than a constant is

upper bounded. The proof can be found in the appendix.

Lemma III.1: Let

be given in (17) and assume that

and .Thenfor ,wehave

When ,and ,weobtain

Here and are increasing functions of

The work of [16] provides an error boun d on the sup port

set estimation using (21) with noisy measurements. Com binin g

the result from [16] with Lemma III .1 , we have the following

theorem.

Theorem I II.2 : Consider a co-prime array consisting of

two linea r arrays with

and sensors respectively. The

distances between two consecutive sensors are

for the

ﬁrst array and

for the second array, where and are

co-prime numbers, and

. Assume sample points are

collected for each receiver. Suppose we have

sources lo-

cated at

. The minimum distance Let

with and .

Consider app lyin g the transformation in (12) and solving the

optimization (21) with

, and denote

as the optim al solution, so th at

(23)

Then, for every

(24)

(25)

and

(26)

with probability at least

,where is an in-

creasing function of

.Here and are positive con-

stants,

,and is the support

set of the original measure

Proof: Since

,wehavethat for all after

transformation (12 ). It was show n in [16] that in order to obtain

(24)–(26) we only need to show that

with a certain

probability in (21). Thus the statistical behavior of

in (20) is

analyzed ﬁrst.

Note that

(27)

which leads to the inequality

(28)

The equality follow s from the fact that

ac-

cording to (19) and (20). Recall that

elements of are

taken from

when , and one element of is taken

from

when . Therefore, by applying the results of

Lemma III.1, we can show that

with

probability at least

and is a increasing func-

tion of

Equations (24) and (25) show that the estimated support set

clusters tightly around the true support, while (2 6) indicates that

the false peaks in the estimated set

have small amplitudes.

A nu mer ical method is proposed in the next section to further

reﬁne the e sti mat ion, using a discrete sparse recovery method

after obtaining

When both DOAs and signal powers are of interest, we com-

bine the statistical analysis of the noise structure in co-prime

arrays with the super resolution resul ts in [15] to give a perfor-

mance guarantee on the reconstruction of the sparse measure

Since

is a sparse m easure, there is no point in bounding

directly. Instead , which is a low pass ﬁlter with cut-off fre-

quency

, is introduced. This kernel is referred to as

the Fejér kernel, and is given by

(29)

The cut-off frequency

can be much higher than . Thus

using

, we can sh ow that by solving t he convex optimiza-

tion problem in (21) the high resolution details of the original

measure

can be recovered with high prob-

ability, even though the sample size

is ﬁnite.

Theorem III.3: Let the co-prime arrays and the locations of

the sou rces have the same setup as in Theorem III.2. The solu-

tion of the convex optimization (21) satisﬁes

(30)

with probability at least when

,where is a increasing

function of

.Here is a positive co nstant n umb er.

5570 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

The proof can be obtained by combining Lemma III.1 with

the techn iques in [15]. Theorem III.3 allows to choose the

cut-off frequency

as large as one wants in order to boun d

the reconstructio n error up to a certain re solution. However,

this will entail an increase in the reconstruction error which is

proportional to

. This theorem also show s that the reconstruc-

tion of

is stable i n the presence of noise. T he probability of

successful reconstruction goes to one exponentially fast as the

number of samples

goes to .Whenﬁxing the probability

of a stable reconstruction, by increasing the number of samples

we can allow for a decreased since is an increasing

function. Therefore we can have a larger

without increasing

the error bound in (30). By collecting m ore samples, one can

stably reconstruct the measure

asifwehadanevenwider

aperture

IV. DOA E

STIMATION VIA SEMIDEFINITE

PROGRAMMING AND ROOT FINDING

We now derive an optimization framework to reconstruct

for co-prime arrays. Since the optimization is performed on a

continuous domain, we will refer to the proposed algorithm as

the continuous sparse recov ery in the rest of this paper.

For DOA estimation the noise power

is often unknown.

Therefore, the optimization must be modiﬁed to include this

effect. A more realistic optimization is reformulated as

(31)

in which

,and is deﬁned in (5). The dual

problem takes on the f orm

(32)

The derivation of (32) is given in the Appendix. Since

a feasible solution, strong duality holds according to the general

Slater condition [24].

Due to the ﬁrst constraint in (32), the prob lem itself is still an

inﬁnite dimensional optimization . It was shown in [ 14] that the

ﬁrst constraint can be recast as a semideﬁnite matrix constraint.

Thus the inﬁnite dimensional dual problem is equivalent to the

following semideﬁnite program (SDP):

(33)

Here

is a Hermitian matrix. This

optimization problem can be easily solved, for example b y using

the CVX package [24], t o yield t he o pti mal dual solution.

The following lemma is introduced to link the solutions of

the primal and dual problems.

Lemma IV.1: Let

and be the optimal

solutions of the primal problem (31) and dual problem (33) re-

spectively. Then

(34)

for al l

such that Here is the ad joint operator

, and it transforms a vector into a continuous signal by

taking the inverse Fourier transform.

Proof: Let

be the noise power estimated in the primal

problem. Since strong duality holds, we hav e

(35)

The ﬁrst inequality follows from the C auch y-Schwarz in-

equality and the fact that

.The

second inequality results from

. In addition, we

also have

(36)

where we used the fact that

. Combining (35)

and (36) leads to

, which implies

(34).

According to Lemma IV.1, the supports of satisfy

(34), and thus can be retr

ievedbyroot-ﬁnding based on the

trigonometric p olynomial

.Let deno te

the recovered set of roots of this po lynomial with cardinality

,andlet denote ele

ments in

with

Amatrix can then be formulated, w ith

measurement

expressed as

(37)

in which

and

Due to numerical issues in the root ﬁnding process, the car-

dinality of

is normally larger than the cardinality of ,i.e.,

. It is p ossible in some cases that ,

which would lead to an ill- cond iti oned linear system (37). Spar-

sity can then be exploited on

. A co nvex optimization in the

discrete dom ain can be formulated as

(38)

We choose

in (38) to be larger than in (31) since the noise

level is expected to be higher in (37) due to inevitable error in-

troduced in the root ﬁnding process. Assuming that the solutio n

TAN et al.: A SUPER RESOLUTION VIEWPOINT 5571

of (38) is , the estimation of the measure in

the continuo us domain can be represented a s

(39)

V. E

XTENSION:SOURCE NUMBER DETECTION

Conventional source number detection for array processing is

typically performed b y exp loi ting eigenvalues from the sample

covariance matrix. For co-prime arrays, this covariance matrix

can be obtained by performing spatial smoothing on

in (5).

The same idea can also be implemented on the sparse signal

recovered from the previous section. Ideally, after sorting

its elements in a descending order, the signal

reconstructed

from (38) should follow

(40)

The SORTE algorithm can be applied to this series. The dif-

ference of the elements from

(41)

The gap measure in SORTE is given as

(42)

where

(43)

The number of sources can be estimated as

(44)

This approach requires

due to the deﬁnition of

in (4 2). W hen ,since is obtained

from the rooting ﬁnding p rocess b ased on the continuous

sparse recovery, we simply l et

. We will refer to this

continuous sparse recovery based SORTE as CSORTE.

VI. N

UMERICAL RESULTS

In this section, we present several numerical examples to

show the merits of im pl emen ting our continuous sparse re-

covery techniques to co-prime arrays.

We consider a co-prime array with 10 sensors. One set of sen-

sors is located at positions

, and the s econd set

is located at

,where is taken as half of

the wavelength. The ﬁrst sensors from both sets are collocated.

It is easy to show that the correlation matrix generates a vir-

tual arr a y with lag s from

to . We compare continuous

sparse recovery (CSR) techniques with MUSIC and also with

discrete sparse recovery method (DSR) considering grid mis-

matches [13]. In [1 3], a LASSO formulation is used to perform

the DOA estimation. Here we implement an equivalent form

of LASSO, i.e., Basis Pursuit, to perform the comparison. The

Fig. 2. Normalized spectra for CSR, MUSIC, and DSR, with and

MUSIC method in this simulatio n follows the spatial smoothing

technique in [5]. For the discrete sparse recovery method, we

take the grid from

to 1, with step size 0.005 for .The

noise levels

in the optimization formulas are chosen by cross

validation. We consider 15 narrow band signals located at

We show that continuo us sparse recovery yields better results in

terms of detection ability, resolution, and e stimation accuracy.

A. Degrees of Freedom

In t h is ﬁrst num erical example, we verify that the proposed

continuous sparse recovery increases the degrees of freedom to

by implementing the co-prime arrays’ structure. The

number of tim e samples is 500 and the SNR is chosen to be

.The for CSR is taken as 5, and is taken as 10 while

DSR uses

.InFig.2,weuseadashedlinetorepresent

the true dir ections of arrival. T h e CPU time for running CSR

was 7.30 seconds. DSR took 7.82 seconds, whereas MUSIC al-

gorithm took only 0.81 seconds. In MUSIC, we implement a

root MUSIC algorithm to estimate the location of each source,

where the number of sources is assumed to be given. T he av-

erage estim ation errors for CSR, DSR, and root MUSIC are

0.23%, 0.26%, and 0.42% respectively. We can see that all three

methods achieve

. In the following subsectio n, we test

the estimation accuracy of these three methods via Monte Carlo

simulations.

B. Estimation Accuracy

In this section, we compare CSR, DSR and MUSIC via Monte

Carlo simulations. Since traditional MUSIC does not yield the

DOA of each source directly, we consider the Root MUSIC al-

gorithm instead. For simplicity, we will still refer to it as MUSIC

in this section. The number of sou rces is assumed to be known

for the M USIC algor ithm in th is simulation, whereas sparse

5572 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

Fig. 3. DOA estimation errors for CSR, MUSIC, and D SR, with .

methods do not assume this a priori. The values of and are

chosen to be 5 and 10, while discrete SR uses

Fig. 3 shows the DOA estimation error as a function of SNR

after 50 Monte Carlo simulatio ns. The estimation error is calcu-

lated based on the sine function of the DOAs. The average CPU

timesforrunningCSR,DSRandMUSICare6.93s,9.30s,and

1.46 s respectively. We can see that CSR performs better than

DSR uniformly with less computing time. Both sparse recovery

methods achieve better DOA estimation accuracy than MUSIC.

The accuracy of DSR can be further improved by taking a ﬁner

grid with a smaller step-size. However, this will slow dow n DS R

further.

In Fig. 4 we show that with a varying n umber of sn apshots the

proposed CSR also exhibits better estimation accuracy than ei-

ther DSR or MUSIC. The average CPU times for running C SR,

DSR and M USIC are 6.50 s, 7.91 s, and 1.43 s respectively. The

performance of MUSIC and DSR approaches the perform ance

of CSR when the num ber of snapshots is close to 5000. We can

see that implem ent ing CSR can save sampling time by taking a

small number of snapshots to achieve the sam e estimation ac-

curacy as the MU SIC algorithm. The parameters

and are

equal to 5 and 10 in this simulation.

C. Source Number Detection Performance Comparison

We now compare the source number detection performance

of the proposed CSORT E with that o f traditional SORT E ap-

plied to the covariance matrix after spatial smoothing. The SNR

is set to 0 dB while the number of snapshots is 3000. We vary

the number of sou rces from 11 to 17. Since this co-prime array

structure yields consecutive lags from

to ,17isthe

maximum number of sources that can be detected theoretically

via techniques based on the covariance matrix.

Fig. 7 shows the probability o f detection with respect to the

number of sources after 50 Monte Car lo simulatio ns. In CSR,

is chosen to be ,and is set to be . When the number of

sources is less than 15, CSORTE and SORTE yield comparable

result. However, SORTE fails after the number of sources is

larger than 15, while CSORTE provides stable performance and

also exhibits perfect detectio n even when the numb er of sources

reaches the theoretical limit of 17. DSR can also be combined

Fig. 4. DOA estimation error for CSR, MUSIC, and DSR, with

Fig. 5. Source number detection using CSORTE and SO RTE, with

, .

with SORTE to perform source number detection. H owever, the

detection accuracy is jeopardized by the spurious signal from

the reconstru cted signals using DSR. Theref or e SORTE based

on DSR is not included here.

D. Resolutio n Ability

Finally we c ompare the resolution abili ties of CSR and

MUSIC, and show that CSR is capable of resolving very

closely located signals. In the ﬁrst simulation, two sources are

closely located at

and . The value of is chosen

to be

and is set to be in CSR, where is the noise

power.

Fig. 6 shows a numerical exam ple in which the SNR is 0

dB and the number of snapshots is 500 . Norm a lized spectra

are plotted f or three methods. MUSIC method A is the MUSIC

algorithm with the assump tion that the number of sources is

known while the MUSIC m eth od B is MUSIC relying on tra-

ditional SORTE to provide the estimated number of sources.

We can see that MUS I C method B f ails to resolve these two

TAN et al.: A SUPER RESOLUTION VIEWPOINT 5573

Fig. 6. Source num ber detection using CSR and the MUSIC algorithm, with

, .

Fig. 7. Source number detection using CSR and MUSIC algorithm, with

, .

targets because traditional S ORTE fails to estimate t he number

of sources correctly. CSR resolves the two sources successfully

even though a priori information about the number of so urces is

notassumedtobegiven.InFig.7,welowertheSNRto

and we notice that even given the number of sources, MUSIC

fails to resolve the two closely located sources wh ile CSR re-

solves them successfully.

Note, that while a separation of

is sufﬁcient for The-

orem III.1 to hold, in real applications, we expect to observe

a better result. Thus we intentionally chose two sources which

are more closely lo cated, t o sho w that the proposed method still

worksevenwithastronger constraint.

Finally w e conduct a simulation based on Monte Carlo runs

to comp are the resolution ability of CS ORTE and the tradi -

tional SORTE algorithm. Fig. 8 shows the resolution perfor-

mance i n detecting two sources located at

and ,using

CSORTE and SORTE after 50 Mon te Carlo runs. The parameter

is chosen to be ,and is set to be in CSR. We can see

that CSORTE outperforms trad itional SO RTE when detecting

the two closely located sources.

Fig. 8. Comparison of resolution performance of CSORTE and SORTE, with

VII. CONCL USIONS AND FUTURE WORK

In this work, we extended the mathem atical theory of super

resolution to DOA estimatio n using co-prime arrays. A primal-

dual approach was utilized to transform the original inﬁnite

dimensional optim ization problem to a solvable sem ideﬁnite

program. After estimating the candidate supp ort sets by root

ﬁnding, a small scale sparse recovery problem is solved. The

robustness of the prop osed super resolution approach was veri-

ﬁed by performing statistical analysis of the noise inherent in

co-prime array processing. A source number detection algo-

rithm w as then pr oposed by combining the existing SORTE

algorithm with the reconstructed spectrum from convex o pti-

mization. Via num erical exam ples, we showed that the proposed

method achieves a more accurate DOA estimation while pro-

viding more degrees of freedom , and also exhibits improved res-

olution ability over traditional MUSIC with spatial smoot hing.

Although implementing the continuous sparse recovery

method sav es sampling time in obt aining a certain estimation

accuracy compared with MU SIC, one shortcom ing of this

approach is that solving the semideﬁnite program is more tim e

consuming than MUSIC. Fast algorith m dev elop men t could

be an interest ing topic for f uture work. It is a lso of interest to

developasystematicwaytochoose

and in the optimization

formulas. One m ajor assumption made in current research on

co-prime arrays research is that the sources are uncorrelated.

Incorporating correlations among sources is another important

topic for future work.

PPENDIX

To derive the statistical behavior of each element in in

Lemma III.1 we rely on two lemmas regarding the concentration

behavior of complex Gaussian rando m variables. Their proofs

are based on results from [25].

Lemma A.1: Let

and be sequ ences of

i.i.d., c ircularly-symmetric complex normal variables with zero

5574 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

mean and variances equal to and re spectively. That is

and .Then

Proof: First we have

Following the same procedure used in the proof of Lemma III.1,

we have

Applying Lemma 6 from [25] concludes the proof.

Before introducing the next lemma, we need to show that

thesquaresumso

f i.i.d G aussian random variables concentrate

around the sum of their variances. The results below rely on

Lemma 7 fr om [25].

Lemma A .2: Let

be a sequence of i.i.d.

Gaussian random variables with zero mean and variance equal

,i.e., .Then

for .

Proof: From the resu lts in [25], for any positive

,wehave

the asymmetric bounds

When ,weobtain

Combing t he above two inequalities leads to

which yie lds the result by replacing with while main-

taining

Lemma A.3: Let be a se-

quence of i.i.d., circularly-symmetric complex normal random

variable. When

, we have

Proof: We begin by noting that

Therefore

Applying Lemma A.2, we establish the result.

ProofofLemmaIII.1: We use ,and to denote the

ﬁrst three terms in (17). The last two term s are denoted by

Then

which leads to the inequality

(45)

TAN et al.: A SUPER RESOLUTION VIEWPOINT 5575

We also have

(46)

The last inequality follows from the fact that

for all

.Thus

Clearly

for some with .UsingLemmaA.1

(47)

with

For the second term ,wehave

(48)

Following similar arguments as for

, we obtain that

Applying Lemma A.1, we have

(49)

with

For the third term, we have the same results as the second

one, given as

(50)

When

,thelastterm , and by

Lemma A.1,

(51)

with

.When , the last term is given

, thus the probability is bounded

(52)

where

and according to Lemma A .3.

Applying the results from (47), (49), (50), (51) and (52) to in-

equality (45), we obtain the desired result.

A. Derivation of the Dual Problem in Section IV

By introducin g the variable

, the original prim al

problem is equivalent to the following opti mi zation:

With the Lagrangian multiplier and ,the

Lagrangian fu nction is given as

The dual function is given as

The Lagrang ian multipliers and in the domain of the dual

function have to satisfy the following three constraints:

From the third constraint, we have , resulting in the

dual problem stated in (33).

EFERENCES

[1] H.L.V.Trees, Optimum Array Processing: Part IV of Detection, Es-

timation and Modulation Theo r y. NewYork,NY,USA:WileyIn-

tersci., 2002.

[2] R. O. Schmidt, “M u ltiple emitter location an d signal parameter esti-

mation,” IEEE Trans. Antennas Propag., vol. 34, no. 3, pp. 276–280,

1986.

[3] P.PalandP.P.Vaidyanathan,“Nested arrays: A novel approach to

array processing with enhanced degrees of freedom,” IEEE Trans.

Signal Process., vol. 58, no. 8, pp. 4167–4181, 2010.

[4] P . P. Vaidyanathan and P. P al, “Spa rse sensing with co-prime sam plers

and arrays,” IEEE Trans. Signal Process., vol. 59, no. 2, pp. 573–586,

2011.

[5] P. Pal and P. P. Vaidyanathan, “Coprime sampling and the m usic al-

gorithm,” in Proc. IEEE D igit. Signal Process. Workshop and IEEE

Signal Process. Educ. Workshop (DSP/SPE), 2011, pp. 289–294.

[6] Y.D.Zhang,M.G.Amin,andB.Himed,“Sparsity-basedDOAestima-

tion using co-prime array s ,” in Proc. IE EE Int. Conf. Acoust, Speech,

Signal Process., Vancouver, Canada, May 2013, pp. 3967–3971.

[7] P. Pal and P. P. Vaidyanathan, “Correlation-aware techniques for sparse

support recovery,” in Proc. IEEE Statist. Signal Process. Workshop

(SSP), 2012, pp. 53–56.

[8] P. Pal and P. P. Vaidyanathan, “On application of LASSO for s parse

support recovery with imperfect correlation a ware ness,” in Proc. Conf.

Rec. 46th Asilomar Conf. Signals, Syst. Comput. (ASILOMAR), 2012,

pp. 958–962.

5576 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 62, N O. 21, NOVEMBER 1, 2014

[9] P.PalandP.P.Vaidyanathan,“Correlation-aware sparse support re-

covery: Gaussian sources,” in Proc. IEEE Int. Conf. Acoust., Speech

Signal Process. (ICASSP), 2013, pp. 5880–5884.

[10] Y. Chi, L. L. Scharf, A. Pezeshki, and A. R. Calderbank, “Sensitivity to

basis mismatch in compressed sensing,” IEEE Trans. Signal Process.,

vol. 59, no. 5, pp. 2182–2195, May 2011.

[11] Z. Tan, P. Yang, and A. Nehorai, “Joint-sparse recovery in compressed

sensing with dictionary mismatch,” in Proc. IEEE 5th IEEE I nt. Work-

shop Computat. Adv. Multi-Sens . Adapt . Process. (CAMSAP), 2013,

pp. 248–251.

[12] Z. Yang, C. Zhang, and L. Xie, “Robustly stable signal recovery in

compressed sensing with structured matrix perturbation,” IEEE Trans.

Signal Process., vol. 60, no. 9, pp. 4658–4671, 2012.

[13] Z. Tan and A . Nehorai, “Spar s e direction of arrival estimation using

co-prime a rrays with off-grid targets,” IEEE Signal Process. Lett., vol.

21, no. 1, pp. 26–29, 2014.

[14] E. J. Candès and C. Fernandez-Granda, “To wards a mathematical

theory of super-reso lution,” Commun. Pure Appl. Math., vol. 67, no.

6, pp. 906–956.

[15] E. J. Candès and C. Fernandez-Granda, “Super-resolution from noisy

data,” J. Fourier Anal. Appl., vol. 19, no. 6, pp. 1229–1254, Aug. 2013.

[16] C. Fernandez-Granda, “Support detection in super-resolution,” in Proc.

10th Int. Conf. Sampling Theory Appl., 2013, pp. 145–148.

[17] J. A. Tropp, “Just relax: Convex programming methods for identifying

sparse signals in noise,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp.

1030–1051, 2006.

[18] H. Akaike, “A new look at the statistical model identiﬁcation,” IEEE

Trans. Au tom. Control, vol. 19, no. 6, pp. 716–723, 1974.

[19] Z. He, A. Cichocki, S. Xie, and K. Choi, “Detecting the number of

clusters in n-way probabilistic clustering,” IEEE Trans. P attern Anal.

Mach. Intell., vol. 32, no. 11, pp. 2006–2021, 2010.

[20] W. Chen, K. M. Wong, and J. P. Reilly , “Detection of the number of

signals: A predicted eigen-threshold approach,” IEEE Trans. Signal

Process., vol. 39, no. 5, pp. 1088–1098, 1991.

[21] K. Han and A. Nehorai, “Improved source number detection and direc-

tion estimation with nested arrays and ulas using jackkniﬁng,” IEEE

Trans. Signal Process., vol. 61, no. 23, pp. 6118–6128, 2013.

[22] R. Prony, “Essai expérimental et analytique: Sur les lois de la dilata-

bilité d e ﬂuidesélastique et sur celles de la force expansive de la vapeur

de l’alkool,à diérentes températures,” J. de l’Ecole Polytechn.,vol.1,

no. 2, pp. 24–76.

[23] Y. Hua and T. K. Sarkar, “Matrix pencil method for estimating param-

eters of exp onentially damped/undamped s inusoids in noise,” IEEE

Trans. Acoust., Speech Signal Process., vol. 38, no. 5, pp. 814–824,

May 1990.

[24] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge,

U.K.: Cambridge U niv. Press, 2004.

[25] J. Haupt, W. U. Bajwa, G. Raz, and R. Nowak, “Toeplitz compressed

sensing matrices with applications to sparse channel estimation,” IEEE

Trans. Inf. Theory, vol. 56, no. 11, pp. 5862–5875, 2010.

Zhao Tan (S’12) received the B.Sc. degree in

electronic information science and technology from

Fudan University of China in 2010. He received

M.Sc. degree in electrical engineering from Wash-

ington University in St. Louis in 2013.

He is currently working tow ards a Ph.D. degree

with the Preston M. Green Department of Electrical

and Systems Engineering at Washington University

under the guidance of Dr. A. Nehorai. His research

interests are mainly in the areas of optimization al-

gorithms, compressed sensing, sensor arrays, radar

signal processing, and state estimation and scheduling in smart grid.

Yonina C. Eldar (S’98–M’02–SM’07–F’12) re-

ceived the B.Sc. degree in physics and the B.Sc.

degree in electrical engineering both from Tel-Aviv

University (TAU), Tel-Aviv, Israel, in 199 5 and

1996, respectively, and the Ph.D. degree in electrical

engineering and computer science from the Massa-

chusetts Institute of Technology (MIT), Cambridge,

in 2002.

From January 2002 to July 2002, she was a

Postdoctoral Fellow at the Dig ital Signal Processing

Group at MIT. She is currently a Professor in the

Department of Electrical Enginee rin g at the Technion—Israel I nstitute o f

Technology, Haifa, and holds The Edwards Chair in Engineering. She is also a

Research Afﬁliate with the Research Laboratory of Electronics at MIT and a

Visiting Professor at Stanford University, Stanford, CA. Her research interests

are in the broad areas of statistical signal processing, sampling theory and

compressed sensing, optimizatio n me thods, and their applications to biology

and optics.

Dr. Eldar was in the program for outstanding students at TAU from 1992 to

1996. In 1998 , she held the Rosenblith Fello wship for study in electrical engi-

neering at MIT, and in 2000, she held an IBM Research Fellowship. From 2002

to 2005, she was a Horev Fellow of the Leaders in Science and Technology

program at the Technion and an Alon Fellow. In 2004, she was awarded the

Wolf Fo un dation Krill Prize f or Excellence in Scientiﬁc Research, in 2005 the

Andre and Bella Meyer L ectureship, in 2007 the Henry Taub Prize for Excel-

lence in Research, in 2008 the Hershel Rich Innovation Award, the Award for

Women with Distinguished Contributions, the Muriel & David Jacknow Award

for Excellence in Teaching, and the Technion Outstanding Lecture Award, in

2009 the Technion’s Award for Excellence in Teaching, in 2010 the Michael

Bruno Memorial Award from the Rothschild Foundation, and in 2011 the Weiz-

mann Prize for Exact Sciences. In 2012, she was elected to the Young Israel

Academy of Science and to the Israel Comm ittee for Higher Educatio n , and

elected an IEEE Fellow. In 2013, she received the Technion’s Award for E xce l-

lence in Teaching, the Hershel Rich Innovation Award, and the IEEE Signal Pro-

cessing Technical Achievement Award. She received several Best Paper awards

together with her research students and colleagues. She is a Signal Processing

Society Distinguished Lecturer, and Ed itor-in-Chief of Foundations and Trends

in Signal Processing. In the past, she was a member of the IEEE Signal Pro-

cessing Theory and Methods and Bio Imaging Signal Processing technical com-

mittees, and served as an Associate Editor for the IEEE T

RANSACTIONS ON

SIGNAL PROCESSING, the EURASIP Journal of Signal Processing,theSIAM

Journal on M atrix Analysis and Applications,andtheSIAMJournal on Imaging

Sciences.

Arye Nehorai (S’80–M’83–SM’90–F’94) received

the B.Sc. and M.Sc. degrees from the Technion, Is-

rael, and the Ph.D. from Stanford University, CA.

He is the Eugene and Martha Lohman Professor

and Chair of the P reston M. Green Department of

Electrical and Systems Engineering (ESE), Pro-

fessor in the Department of Biomedical Engineering

(by courtesy) and in the Division of Biolo gy and

Biomedical Studies (D BBS) at Washington Univer-

sity, St. Louis (WUSTL), MO. He serves as Director

of the Center for Sensor Signal and Information

Processing at WUSTL. Under his leadership as department chair, the under-

graduate enrollment has mor e than tripled in the last four years. Earlier, he was

a faculty member at Yale University and the University of Illinois at Chicago.

Dr. Nehorai served as Ed itor -in -Chief of the IEEE T

RANSACTIONS ON SIGNAL

PROCESSING from 2000 to 2002. From 2003 to 2005, he w as the Vice President

(Publications) of the IEEE Signal Processing Society (SPS), the Chair of the

Publications Board, and a memb er of the Executive Committee of this Society.

He was the founding editor of the special columns on Leadership R eﬂecti ons in

IEEE S

IGNAL PROCESSING MAGAZINE from 2003 to 2006. He received the 2006

IEEE SPS Technical Achievement Award and the 2010 IEEE SPS Meritorious

Service Award. He was elected Distinguished Lecturer of the IEEE SPS for

a term lasting from 2004 to 2005. He received several best pape r awards in

IEEE journals and conferences. I n 2001, he was named University Scholar of

the U niv ersity of Illinois. He has been a Fellow of th e Royal Statistical Society

since 1996 and a Fellow of AAAS since 2012.