1

Detection Estimation and Grid matching of Multiple
Targets with Single Snapshot Measurements

arXiv:1705.07561v1 [stat.AP] 22 May 2017

Rakshith Jagannath

Abstract—In this work, we explore the problems of detecting
the number of narrow-band, far-field targets and estimating their
corresponding directions from single snapshot measurements.
The principles of sparse signal recovery (SSR) are used for the
single snapshot detection and estimation of multiple targets. In
the SSR framework, the DoA estimation problem is grid based
and can be posed as the lasso optimization problem. However,
the SSR framework for DoA estimation gives rise to the grid
mismatch problem, when the unknown targets (sources) are not
matched with the estimation grid chosen for the construction
of the array steering matrix at the receiver. The block sparse
recovery framework is known to mitigate the grid mismatch
problem by jointly estimating the targets and their corresponding
offsets from the estimation grid using the group lasso estimator.
The corresponding detection problem reduces to estimating the
optimal regularization parameter (τ ) of the lasso (in case of
perfect grid-matching) or group-lasso estimation problem for
achieving the required probability of correct detection (Pc ). We
propose asymptotic and finite sample test statistics for detecting
the number of sources with the required Pc at moderate to high
signal to noise ratios. Once the number of sources are detected,
or equivalently the optimal τ̂ is estimated, the corresponding
estimation and grid matching of the DoAs can be performed by
solving the lasso or group-lasso problem at τ̂ .
Index Terms—Sparse Signal Recovery, Multiple Hypothesis
Testing, Test Statistics, Probability of Correct Detection, Threshold, Single Snapshot, Grid Matching, Direction of Arrival Estimation, Lasso, Group Lasso

I. I NTRODUCTION
Detection, estimation and tracking of targets are the primary functions of radar-based localization systems. A main
challenge frequently faced by these systems is the problem of
restricted measurements due to limited availability of sensors.
In such cases, it is essential to exploit the sparsity of targets
in the array manifold (spatial domain) for the purpose of
detection and estimation with as few sensors as possible. In
this work, we focus on the problems of detecting the number
of narrow-band, far-field targets and estimating their corresponding direction of arrivals (DoAs) from single snapshot
measurements.
The signal model used for detection and estimation in single
snapshot DoA problem models the observed measurements
as a continuous and non-linear function of the DoAs [1].
As the DoAs are sparse in the spatial domain, sparse signal
recovery (SSR) based techniques can be used for detection
and estimation. In the SSR framework, the continuous DoA
signal model can be approximated into three classes, namely,
on-grid, off-grid and grid-less [2].
The author is with the Department of Electrical Engineering, I.I.T Madras,
Chennai, India (e-mail:ee13d005@ee.iitm.ac.in)

In the on-grid SSR framework, the signal model for estimation is obtained by the discretization of the continuous DoAs
over a selected interval to construct the array steering matrix
over an estimation grid of DoAs. The true DOA targets are
then assumed to lie on the estimation grid and SSR based
estimators have been proposed for DoA estimation. These
estimators essentially use the lasso estimator in its various
forms for estimation of the DoAs [3]. However, the lasso
regularization parameter (τ ), which controls the number of
sources that are estimated is usually chosen empirically. In
the case of sparse greedy algorithms like orthogonal matching
pursuit (OMP) and its variants, the number of sources is
assumed to be known apriori and then the estimation is
performed [4].
For the case of a single source in noise model in the
on-grid SSR framework,
the estimate of the regularization
p
parameter, τ̂ = σ − ln(Pf ) for a given probability of
false alarm Pf and noise variance σ, was obtained in [5]
using the generalized likelihood ratio test (GLRT). However,
for multiple targets, it is well-known that the GLRT selects
the largest model [6]. Algorithms based on cross-validation
and information criteria principles like Bayesian information
criteria and minimum description length have been proposed
in [7], [8], [9], [10]. But, these algorithms are known to suffer
in detection performance for small number of snapshots and
are mostly not even applicable for the single snapshot case
[11]. Also, the relationship between τ and the probability
of correct detection, Pc (or Pf ) have not been obtained
for these algorithms. A number of asymptotic results (for
large measurements) which are the SSR counterparts to the
martingale stability theorem [12] derived for maximum likelihood estimation framework exist in the literature [13], [14],
wherein the optimal regularization parameter (τ̂ ) is derived
to minimize the lasso estimation error. But, small estimation
errors does not necessarily mean that sparsity and support
of the estimate is same as the original parameter, which is
required to control Pc (or Pf ) in the detection framework. In
the related framework of sequential hypothesis testing, familywise error rate control procedures and the Benjamini-Hojberg
procedure and its variants have been used for controlling
the false discovery rates and p-values (these quantities can
be related to Pc ). However, to our knowledge, most of the
results are asymptotic in measurements and offer average rate
control with respect to (w.r.t) p-values for large measurements.
Hence these are useful mostly for the multiple snapshot DoA
detection and estimation. In [15], the co-variance test statistics
has been proposed for real measurements to obtain the optimal
τ . However, the authors obtain an asymptotic (in the number of

2

measurements) distribution for the co-variance test statistics,
which can then be used to obtain the optimal τ for an
approximate Pc .
The on-grid SSR framework for DoA estimation gives rise
to the grid mismatch problem when the unknown targets
(sources) do not lie in the estimation grid, chosen for the
construction of the array steering matrix at the receiver. The
block sparse recovery framework is known to mitigate the
grid mismatch problem by jointly estimating the targets and
their corresponding off-sets from the estimation grid using
the group-lasso estimator or its variants. The corresponding
detection problem reduces to estimating the optimal regularization parameter (τ ) of the group-lasso estimation problem for
achieving the required probability of correct detection (Pc ).
A number of estimation algorithms have been proposed for
joint DoA estimation and grid matching in the block sparse
recovery framework using second order cone programming,
semi-definite programming and greedy algorithms [16], [17],
[18]. But to our knowledge, the problem of detection of the
number of sources has not been sufficiently explored.
The grid-less methods for DoA estimation such as MUSIC and ESPRIT traditionally require the knowledge of the
number of sources for estimation of DoAs and an estimate of
the measurement co-variance matrix, which in-turn requires
multiple snapshots. Hence, these cannot be used for detection
and estimation of DoAs with single snapshot measurements.
Recently, other sub-space based algorithms for single snapshot
DoA estimation have been proposed in [2], [19], [20], but they
all require the knowledge of the number of sources and hence
do not detect the number of sources from the measurements.
Since we work with single snapshot measurements, beamformers can be used only for detecting a single source, but
these techniques cannot be used for detecting multiple sources
with adequate performance [21].
In this work, we explore the problem of finding the relationship between τ and the detection performance metrics like
the probability of correct detection (Pc ), the probability of
mis-detection (Pm ) and the probability of false alarm (Pf ).
Specifically, we propose finite sample and asymptotic test
statistics which can be used at moderate to high SNRs to
obtain the optimal τ for a given Pc with varying degrees
of performance. This is accomplished by comparing the test
statistics to a threshold which is obtained by inverting the
cumulative distribution function (c.d.f) of the proposed test
statistics. Finally, we compare the performance of all these
tests through simulations and discuss their merits.
Organization and Notations: We use bold lower case letters
to denote vectors (x) and bold upper case letters to denote
matrices (A). kxk∞ , kxk1 and kxk2 denote the l∞ , l1 and l2
norms of a vector x respectively. xH denotes the Hermitian
of x. D(x) denotes a diagonal matrix with entries of x
as the diagonal elements, P(.) denotes probability and E(.)
denotes expectation. x ⊙ y represents the Hadamard product
(entry-wise product) of two vectors x and y. The rest of
this work is organized as follows. Section-II describes the
DoA signal model used in this work. Section-III describes
the main content, wherein we propose algorithms for joint
detection, estimation and grid matching of DoAs from single

snapshot measurements. Simulation results for evaluating the
performance of the algorithm are presented in section IV. We
conclude the paper in section V followed by references. Proofs
of some of the theorems are provided in the Appendix.
II. S IGNAL M ODEL
We consider an array of M elements, impinged by an
unknown number (S) of sources. The measurements at each
element can be expressed as a superposition of S elementary waveforms (a(αi , d), i = 1, 2, . . . , S), each containing
unknown angles αi ∈ [κ1 , κ2 ] as,
b̃(d) =

S
X

si a(αi , d) + v(d),

i=1

where v(d) is a white Gaussian noise process with zero
mean and variance σ 2 , si are the weights and b̃(d) are the
measurements over the spatial variable d = 1, 2, . . . , M .
The recovery problem now reduces to detecting the number
of sources S, estimating their corresponding weights si and
parameters αi , which is non-linear [22].
In the grid based signal model for detection and estimation,
the interval [κ1 , κ2 ] is discretized into N bins, each of size r
to obtain the estimation grid, ρ1 , . . . , ρN . Let xk denote the
weight, corresponding to the source in k th bin. The discrete
model approximation for b̃(d) is then given by [22], [23], [24],
b(d) =

N
X

xk a(ρk , d) + v(d).

k=1

The above equation can be expressed in vector form as:
b(d) = aT (d)x + v(d),
where x = [x1 , x2 , . . . , xN ]T and a(d) = [a(ρ1 , d), . . . ,
, a(ρN , d)]T . Stacking the measurements, we obtain
bM×1 = AM×N xN ×1 + vM×1 ,

(1)

where b is the measurement vector, A = [a(0), a(1), . . . ,
, a(M − 1)]T is the array steering matrix (with M ≤ N ), and
x is the signal of interest which has a sparse or almost sparse
representation under the basis of A.
This discretization of the estimation grid into discreet bins
is the cause of grid mismatch [25]. If the bin size is made too
small, then there is also the risk of columns of A becoming
correlated, thus reducing the incoherence of A. Classical
grid based estimation methods recover the desired signal
without any ambiguities only if the signal is placed exactly
on the corresponding grid cells. Any grid mismatch leads to
ambiguities in estimation due to the leakage of source power
over all the grid cells. The source power leakage depends
on the kernel used for the construction of the array steering
matrix, A. In the SSR framework, it may also mean that the
signal is less or even no longer sparse in the basis domain
[25]. Hence, it is necessary to account for grid mismatch in
DoA detection and estimation.

3

A. Modeling Grid Mismatch
The earliest model proposed for grid matching is the errors
in variables (EIV) model, which treats the grid mismatch effect
as an additive error matrix, E as shown below in (2) [23], [26],
b = Âx + v,

Â = A + E

(2)

The performance of the model in (2) characterized by its
Cramer-Rao bound, derived in [27]. However, the model
described by (2) does not exploit the inherent Vandermonde
structure of the array steering vectors in the DoA signal
model, hence making the detection and estimation of DoAs
complicated.
A special case of the EIV model, which preserves the
Vandermonde structure of DoAs, is obtained by the Taylor
series based interpolation model. This model is obtained by
an interpolation of the array steering matrix, A w.r.t the
parameters of interest as described below [24].
We note that the grid mismatch problem occurs if a particular parameter of interest, αi is not present on the estimation
grid. Hence, to add αi to the estimation grid, a Taylor series
interpolation of a(ρ, d) over the nearest ρk is given by [24],
∂a(ρ, d)
pk .
∂ρ
ρ=ρk
Here pk gives the perturbation on ρk to add αi to the grid,
and it is assumed real and unknown. It can be seen that the
misaligned grid can become an aligned grid if pk can be
estimated correctly. Thus, the grid-mismatch problem can be
converted into an estimation problem with interpolation over
the estimation grid.
Including the Taylor series approximation, the measurements, b(d) can be approximated as,
a(ρk + pk , d) ≈ a(ρk , d) +

b(d) =

N
X

xk a(ρk , d) +

k=1

N
X

k=1

∂a(ρ, d)
xk pk
∂ρ

ρ=ρk

+v(d).

The above equation can be expressed in vector form as,
T

b(d) = aT (d)x + a′ (d)Px + v(d),
iT
h
and P =
, . . . , ∂a(ρ,d)
where a′ (d) = ∂a(ρ,d)
∂ρ
∂ρ
ρ=ρ1

ρ=ρN

D(p), where p = [p1 , . . . , pN ]T represents the grid mismatch
of the estimation grid.
Stacking the measurements, the above equation can be
expressed in the matrix-vector form as,
b = Ax + A1 Px + v,
′

′

′

(3)
T

where A1 = [a (0), a (1), . . . , a (M − 1)] . So writing
A1 P = E, the interpolation model for grid mismatch becomes
a special case of the EIV model in (2). The model in (3) has
been used for deriving the Cramer-Rao bound in [24], which
evaluates the accuracy of the model for grid matching and
hence, justifies its use.
The model in (3) can be equivalently expressed as,




x
+ v,
b = A|A1
p⊙x


x
= Φy + v;
y=
.
(4)
p⊙x

Here, it should be noted that, in the above equation if xj = 0,
for some j ∈ {1, 2, . . . , N } then pj has no contribution to b,
i.e.,, by definition pj 6= 0 only if xj 6= 0. The model in (4) has
been used for estimation of the weights x and grid matching
(or estimation of p), with the knowledge of the number sources
(S) in the measurements [24]. In this work, we also have the
additional problem of detecting the number of sources S from
the measurements.
We consider another equivalent model by noting that the
Vandermonde structure of the array steering vectors gives
A1 P = DAC, where D = D([1, 2, . . . , M ]) and C = D(c),
where the entries of c depend on the geometry of the DoA
problem. For the case of uniform linear array (ULA), c =
[j2π∆ cos(θ1 )p1 , j2π∆ cos(θ2 )p2 , . . . , j2π∆ cos(θM )pM ].
From the above discussions we have,


b = A|DA




x
+ v.
c⊙x

(5)

We observe that any source DoA αi can be expressed as
the sum ρi + pi , where ρi lies on the estimation grid and
hence can be estimated for any choice of the estimation grid.
Now, we select the estimation grid (ρ) of A in such a way
that the array steering matrix is constrained to be orthogonal,
i.e, AH A = I. This choice of the estimation grid makes A
maximally incoherent and hence is the best for SSR and also
has computational advantages. We now pre-multiply (5) by
AH to obtain,


AH b = I|AH DA y + AH v,




x
b = I|G y + v,
y=
,
c⊙x

(6)

where, G = AH DA, b = AH b, v = AH v. The model in (6)
will be used for detection (finding S), estimation (estimating
ρ) and grid matching (estimating p) of DoAs. In the case of
multiple snapshot measurements, an extension of (6) gives a
nice structure which can be used for estimation of DoAs using
the techniques described in [28].
Let α be the vector representing S source locations (actual
DoAs) and let ρ̂ represent the Ŝ location estimates of the
sources. We define the probability of correct detection (Pc )
as the probability that all the sources and their locations
are detected correctly, i.e., Pc = P{ρ̂ = α}, similarly the
probability of miss (Pm ) is defined as the probability that
one or more sources is not detected, i.e., Pm = P{Ŝ <
S, ρ̂i = αi , i = 1, 2, . . . , Ŝ} and the probability of false alarm,
Pf = 1 − Pc − Pm . We define the signal to noise ratio, SNR
as E{kAxk22 }/E{kvk22 }.
Problem Description: Given the measurements b, the array
steering matrix A, SNR and the required probability of correct
detection Pc . The goal is to propose test statistics to detect
the number of sources Ŝ, their corresponding locations ρ̂i on
the estimation grid and estimate the grid mismatch error pi to
match the grid. The proposed tests should achieve the required
probability of correct detection Pc .

4

III. J OINT D ETECTION E STIMATION AND G RID M ATCHING
FOR M ULTIPLE TARGETS
In this section, we briefly review the lasso estimator, the
lasso path and propose tests for joint detection, estimation and
grid matching of DoAs from single snapshot measurements.
The Lasso Estimator: The lasso estimator for the DoA
model in (1) is given by the solution of the following optimization problem.
1
x̂(τ ) = arg min kb − Axk22 + τ kxk1 ,
2
x

(7)

where x̂(τ ) is the estimate of x and τ ∈ [0, ∞) is the
regularization parameter which controls the sparsity of x̂.
Applying KKT conditions to (7), the lasso solution can be
characterized as follows,
Theorem 1. For a certain value of τ , the solution to (7) is
characterized by
x̂i
|x̂i |
|aH
i (b − Ax̂)| < τ

aH
i (b − Ax̂) = τ

∀x̂i 6= 0,

(8)

∀x̂i = 0,

(9)

where x̂j , j = 1, 2, . . . , M is the j th entry of x̂ and aj is the
j th column of A. The singular points (knot points) occur when
the second condition is changed to τ = max |aH
i (b−Ax̂)|.
{i|x̂i =0}

Proof. See [3, Theorem 1].
We observe that the lasso solution for the special case of
orthogonal array steering matrix (AH A = I) reduces to the
following thresholding estimator,
(
x̂j
if |aH
aH
j b| > τ,
j b − τ |x̂j |
(10)
x̂j (τ ) =
0
if |aH
j b| ≤ τ.
We now discuss the behavior of x̂ for variations in τ , which
is called the lasso path. The lasso path can be obtained using
the iterative algorithm described in [3].
Lasso Path: The lasso estimator x̂(τ ) is a continuous and
piecewise linear function of τ . The points τk with τ1 ≥ . . . ≥
τk . . . ≥ τr , where the slope of the function x̂(τ ) changes are
called knots (or singular points) [3]. For all τ ≥ kAH bk∞ ,
the lasso estimate x̂(τ ) = 0. For decreasing τ , each knot
τk marks the entry or removal of some variable from the
current active set (J), which is the index set corresponding
to non-zero entries of x̂(τk−1 ). Hence, the active set remains
constant in between the knots. For a matrix A satisfying the
special positive cone condition (example orthogonal matrices),
no variables are removed from the active set as τ decreases
and hence there are always M knots in the lasso path.
We observe that the sparsity changes only at the knots.
The estimation algorithm of [3] sequentially iterates over the
knot points, τk , k = 1, 2, . . . , r and calculates x̂(τk ). So, we
propose tests at the knot points to obtain a stopping condition
for the iterative algorithm as the lasso solution varies from
x̂(τ1 ) to x̂(τS ). Once, the tests detect the number of sources Ŝ
or equivalently τŜ , the DoAs can then be estimated by solving
lasso at τ = τŜ .

A. Orthogonal Models
Here we assume that the array steering matrix is orthogonal (AH A = I) and the sources lie on the estimation
grid (perfect grid matching). These assumptions make the
analysis of the test statistics simpler for evaluating thresholds.
Specifically, the components of the lasso estimate, x̂ in (10)
are independent. Although, this scenario is not practical as it
occurs only for antennas with infinite apertures, the insights
obtained here are helpful in proposing tests while working with
non-orthogonal (over-sampled) and grid matching models. In
the following, we propose the covariance test, test-A, testB and test-C. The first three tests also require the additional
knowledge of noise variance.
Covariance Test: The covariance test statistics is defined at
the knots of the lasso path. At the k th knot, the covariance
test statistics is defined as [15],

1 
(11)
Tk = 2 bH Ax̂(τk+1 ) − bH AJ x̃J (τk+1 ) ,
σ
where J is the active set just before τk , x̃(τk+1 ) is the solution
of the lasso problem using only the active model AJ (columns
of A belonging to J), with τ = τk+1 , i.e.,
1
x̃J (τk+1 ) = arg min kb − AJ xJ k22 + τk+1 kxJ k1 .
2
|J|
x∈ℜ

(12)

Intuitively, the covariance test statistics defined in (11) is a
function of the difference between Ax̂ and AJ x̃J , which
represents the fitted values of the model by including and
leaving out the next x̂j (corresponding to the knot at τk+1 ),
respectively. For the case of orthogonal A, it can be shown
[15, Lemma 1] that the covariance test statistics reduces to
Tk = τk (τk − τk+1 )/σ 2 , k = 1, 2, . . . , M − 1,

(13)

where, the M knots of the lasso estimator x̂(τ ) are given by
[I, τ ] =sort(|AH b|). The function sort(u) sorts the entries
of u in the descending order, I is the collection of the
corresponding indices of |AH b| and τ is the vector of M
knot points.
Now, let the number of non zero entries in the actual
parameter x be S. We define B as the event that the S sources
are added to the estimate x̂ at the first S knot points of the
lasso path:
o
n
(14)
B = min τj > max τj .
j∈T̃

j∈
/ T̃

For the case of orthogonal models, event B reduces to
n
o
H
B = min |aH
j b| > max |aj b| ,
j∈T̃

(15)

j∈
/ T̃

where T̃ is the support of the original parameter x (columns
of A corresponding to non-zero entries of x).
Remark-1: Event B is defined to ensure that S active
parameters (S sources) are added to the estimate x̂ in the first
S knots, then the test statistics at (S + 1)th knot and beyond
would depend only on the truly inactive variables (noise). The
detection tests proposed below are conditioned on event B.
Hence, P (B) = 1 is a sufficient condition for the detection
tests to provide rate control (P̂c = Pc ). However, we show in
Lemma 1 that P (B) → 1, whenever the power of the weakest

5

source is large compared to the noise power or whenever the
detection is performed in the moderate to high SNR regime
[15, Theorem-1]. Hence, detection at moderate to high SNR
is a sufficient condition for P (B) → 1 and hence is also a
sufficient condition for the tests to provide rate control for a
given Pc .
Lemma 1. For orthogonal models, P (B) → 1 at moderate
to high SNRs.

We observe that although the asymptotic distribution of
TS+1 is tractable, it converges very slowly (2 log M ), hence
offering lesser control in-terms of Pc . So we now propose
other tests which are both easy to evaluate and exact.
Test-A: We note that, if event B is satisfied and there
are S sources, then Ak = τS+k
σ , k = 1 . . . , M − S are the
order statistics of Rayleigh random variables. We define the
Rayleigh test statistics as
Ak =

Proof. See Appendix-VI-E

τk+S
.
σ

(17)

From the above discussions, we conclude that it suffices to
stop at the (S+1)th knot for providing rate control at moderate
to high SNR regime. This requires the evaluation of c.d.f of
TS+1 conditional on event B, given by

We note that τS+1 is the first knot point corresponding to
noise, conditional on event B. Hence, Pc can be controlled
by accurately detecting A1 . The threshold for controlling Pc
requires the c.d.f of A1 which is given by,

Theorem 2. The c.d.f of TS+1 , conditional on event B is,

Theorem 4. The c.d.f of A1 conditional on event B is,


n−1
Z∞
−(y−η/y)2
2
2
FTS+1 (η) = 1 − n ye(−y /2) 1 − e
dy,
√
η

where n = M − S.
Proof. See Appendix-VI-A
Now, with the knowledge of the c.d.f of TS+1 conditional
on event B, the problem of finding the number of sources S
reduces to the following hypothesis testing problem.
Ho = Tk is distributed as FTS+1 .
Ha = Tk is not distributed as FTS+1 .
The idea is to evaluate the test statistics at each knot in
the increasing order (from τM to τ1 ) and compare the value
to a threshold, η. The first instance, where Tk > η is the
stopping point, because conditional on B, the stopping point
corresponds to the knot τS , where all the sources have been
added to the lasso estimate x̂. The threshold, η is obtained
from the tail probability of the c.d.f of TS+1 by fixing the
required probability of correct detection, Pc
Pc = P{Tk ≤ η} = FTS+1 (η).

(16)

We observe that the c.d.f of the covariance test, though an
exact (non-asymptotic) distribution, requires numerical integration for evaluating the threshold at each knot, hence making
the test complicated. In [15], the asymptotic c.d.f of Tk , k > S,
conditional on event B is derived for real measurement model.
The extension to complex measurement model is given by the
following theorem,
Theorem 3. Let the magnitude of the smallest nonzero entry
of x be large compared to σ. Then event B is satisfied, i.e.,
P(B) → 1 and furthermore, for each fixed l ≥ 0


1
1
d
[TS+1 , TS+2 , . . . , TS+l] −
→ Exp(1), Exp( ), . . . , Exp( ) ,
2
l
conditional on B, i.e., the lth statistics after S converges
independently to exponential distribution with mean 1/l.
Proof. See Appendix-VI-D

FA1 (x) = (1 − exp(−x2 /2))M−S .

(18)

Proof. A1 is the maximum of the i.i.d Rayleigh random
variables and hence its c.d.f is obtained by (18).
The problem of finding S sources reduces to comparing
Ak with a threshold (η) at each knot point. The threshold is
obtained from the c.d.f (18) by fixing FA1 to the required Pc .
Test-B: Let us consider the random variables Ei = A2i , i =
1, 2, . . . , n. Then Ei are the order statistics of the standard
exponential distribution, conditional on event B. Now, we
define the Exponential test statistics Bn = En − En−1 . The
c.d.f of BS+1 , conditional on event B is required for detection
of S sources, which is given by,
Theorem 5. The c.d.f of BS+1 conditional on event B is,
FBS+1 (x) = 1 − exp(−x).

(19)

Proof. Ei are the order statistics of the standard exponential
distribution. The c.d.f of BS+1 can now be obtained as follows.
The joint pdf of Bn and En is,
fBn ,En (g, y) = C{F (y − g)}n−2 f (y − g)f (y).
Hence the pdf of the test statistics Bn is
Z ∞
C{F (y − g)}n−2 f (y − g)f (y)dy.
fBn (g) =
0

The cdf of the test statistics G is given by
Z ηZ ∞
FBn (η) =
C{F (y − g)}n−2 f (y − g)f (y)dydg
0

0

= 1 − exp(−η), n = S + 1, . . . , M.

Again, the problem of finding S sources reduces to comparing Bk with a threshold (η) at each knot point. The threshold
is obtained from the c.d.f (19) by fixing FBS+1 to required Pc .

6

1) Unknown noise variance: Here, we propose a test statistics for the case when the noise variance is unknown and needs
to be estimated. We retain the orthogonality and perfect grid
matching assumptions discussed at the beginning.
Test-C: We choose the estimate of the noise variance as
σ̂ 2 = kb−Ax̂I k22 , where x̂I is the least-square estimate using
the model after (M − 1) steps of Algorithm-1. The reason for
the choice of using (M − 1) supports for estimating variance
is that it is well known that an antenna array of M elements
can recover at-most (M − 1) sources [29], hence the effect
of all the sources impinging the array is removed from the
measurements after M − 1 steps. Now, we propose the test
statistics at the k th knot as,
τ2
A2
= 2 k 2 , k = 1, . . . , l − 1,
Ck = k+S
2
σ̂
σ̂ /σ

(20)

where l = M − S. The distribution of C1 conditional on event
B is required for detecting the S sources and is given by,
Theorem 6. The c.d.f of C1 , conditional on event B is,
 
l
X
−1
r l
(1 + rη) .
(21)
(−1)
FC1 (η) =
r
r=0
2

σ̂
2
Proof. We observe that 2σ
random variable with 2
2 is a χ
degrees of freedom for all k, i.e., σ̂ 2 ∽ χ22 and Rk2 /2, k =
1, 2, . . . , l − 1 are the order statistics of a χ2 random variable
with 2 degree of freedom. Hence, C1 is the maximum of F
random variables with equal correlations, whose distribution
is given by [30], [31],
 
k
X
k
(1 + rη)−1
(−1)r
FC1 (η) =
r
r=0

Again, the problem of finding S sources reduces to comparing Ck with a threshold (η) at each knot point. The threshold
is obtained from the c.d.f (21) by fixing FC1 to required Pc .
We note that test-C proposed here is very similar to the to F
test used in the least squares regression for selecting the best
model. However, the main difference is that the threshold in
the least squares regression setup is evaluated by observing
the degree of the F random variable at each step, whereas
here we show that the maximum of equicorrelated F random
variables is a better test statistics for evaluating the threshold.
We summarize the steps for detection and estimation of DoAs
with orthogonal measurement model in Algorithm-1 using
test-A as an example. All the other tests described earlier can
be implemented by evaluating the corresponding test statistics
in step-3 of the algorithm.
Algorithm 1 Algorithm for Detection and Estimation
1:
2:
3:
4:
5:
6:

Inputs: b, A, η (obtained by inverting the c.d.f).
Initialize: Set i = M − 1, Ŝ = 0, [I,τ ] = sort(|AH b|).
Evaluate: Evaluate the test statistics Ai .
Decision: If Ai ≥ ηi go to step 6
Iterate: Decrease i by 1 and iterate from step 3.
Outputs: Ŝ = i, T̂ =I(1,2,...,Ŝ), τ̂ = τ (Ŝ), ρ̂ = ρ(T̂ ).

2) Low SNR scenarios: We observe that the tests proposed
for orthogonal models require the probability of event B to
be close to 1 (i.e., P (B) → 1) for obtaining rate control w.r.t
Pc . For orthogonal models, it was shown that moderate to
high SNR scenarios are sufficient for P (B) → 1. Here, we
make some comments on low SNR scenarios and explain the
difficulty for proposing tests at low SNR scenarios.
We observe that the tests discussed above depended on some
functions of the p.d.f of the estimator, x̂. For e.g., the knot
points correspond to singularities of x̂. So it would be useful
to consider the p.d.f. of the lasso estimator. For a real linear
model in real Gaussian noise we have,
Theorem 7. The p.d.f of the lasso estimator, x̂ for orthogonal
models (AH A = I) is given by,
(
−xk )2 
√ 1
if x̂k > 0,
exp − (x̂k +τ
2
2σ2
2πσ
fx̂k (x̂k ) =
(x̂k −τ −xk )2 
1
√
exp −
if x̂k < 0.
2σ2
2πσ2
(22)
Proof. See [32].
We observe from (22) that the p.d.f of the lasso estimator
is continuous function of x̂k except for the discontinuities at
the knot points (when x̂k = 0 or τ = τk = |aH
k b|). In order
to understand the problems for proposing tests at low SNR,
we study the expression for probability of error Pe given by,
Pe = Pm + Pf
= P(x̂k = 0|xk 6= 0) + P(x̂k 6= 0|xk = 0)
−τ − xk
τ − xk
) − Φ(
) + G(τ ),
= Φ(
2σ
2σ
where, Φ(.) denotes the cdf of normal random variable and
G(.) is a function of τ only. In the above expression, we
observe that Pm is a function of both xk (unknown) and τ ,
whereas Pf is only a function of τ . This dependence of Pe
(obtained from p.d.f of x̂k ) on the unknown parameter xk
makes it difficult for proposing test statistics to control Pc .
Hence, conditioning tests over event B translates to assuming
that Pm → 0 as σ → 0 (or moderate to high SNR), which is a
good assumption for orthogonal models. We also observe that
there is still complete control over Pf for orthogonal models,
which is usually the main objective in classical hypothesis
testing. Finally, we note that controlling Pm requires the prior
knowledge of xk , which is possible in communication scenario
wherein x are symbols transmitted from a predefined codebook. Hence, in a communication scenario, it may be possible
to calculate exact expressions for Pm (and Pc ).
B. Non-Orthogonal Models
We now obtain tests for the case where the estimation grid
is over-sampled to N >> M bins to obtain a fat array
steering matrix (A). We retain the assumption that all the
source locations are perfectly matched to the estimation grid.
From the discussions on orthogonal models, we observed that
test statistics to control Pc can be proposed at knot points.
Hence, we will first study the knot points of the lasso for
a fat matrix A. The first knot point of the lasso occurs at

7

τ1 = max |aH
k b|. The process of finding the subsequent knots
k
is summarized in Algorithm-2.
Remark-2: For non-orthogonal model, we observe from
simulations (section-IV) that the following two sufficient conditions are required for P(B) → 1. Firstly, the power of the
weakest source should be large compared to the noise power
or the detection should be performed in the moderate to high
SNR regime. Secondly, the sources should be well separated.
We now propose a test at the knot points. The goal of the
proposed test is to detect the (S + 1)th knot point (where S
is unknown), conditional on event B.
Test-D: The D test statistics at the k th knot is defined as,
τk2
.
(23)
σ2
Again, assuming event B is true (i.e., P (B) → 1), we need
to make a decision at (S + 1)th knot. Hence, we require the
c.d.f of D1 , given by

grid of A. However, as discussed in Section-II, it has been
shown in [25] that fine sampling of the estimation grid does
not necessarily guarantee perfect grid matching. There is
always a non-zro probability that all the sources are not
aligned on the estimation grid. Moreover, there is also the
problem of columns of A becoming correlated, thus reducing
its incoherence. This also means that the signal is less sparse or
even no longer sparse in the spatial domain [25], [26]. Hence,
the grid matching model discussed in Section-II may be used
for detection and estimation of off-grid sources.
The block sparse estimator for parameter estimation and
grid matching can be formulated as the following group lasso
optimization problem,

Dk =

Theorem 8. The c.d.f of D1 , conditional on event B is,
FD1 (η) =

M−S
Y

(1 − e−η/̺i ),

(24)

i=1

ŷ = arg min
y

Theorem 9. The solution of the group-lasso estimator satisfies
the following K.K.T conditions
ŷg
kŷg k2
H
kPg (b − Pŷ)k2 ≤ τ

PH
g (b − Pŷ) = τ

Proof. See Appendix-VI-B

Algorithm 2 Algorithm for Detection and Estimation
1:
2:
3:
4:

Inputs: b, A, η (obtained by inverting the c.d.f).
Initialize: Set k = 1, Ŝ = 0, τ1 = max |aH
k b|.
k

The active set J = {j1 , j2 , . . . , jn } is determined by
solving (8) at τk .
For each k ∈
/ J, solve the following system of equations
for a vector x̂ = [x̂1 , . . . , x̂n ] and a set Λk .
n

x̂l
, |aH
x̂)
=
Λ
aH
(b
−
A
k
J
j (b − AJ x̂)| = Λk
jl
|x̂l | l=1

7:

If the system is infeasible, we put Λj = 0.
Evaluate: Evaluate the test statistics Dk .
Decision: If Dk ≥ ηi go to step 8
Iterate: The next knot is given by, τk+1 = max Λj .

8:

Outputs: Ŝ = i,

5:
6:

∀ŷg = 0.

(27)

We can immediately notice that the first knot point is
given by max kPH
g bk2 . The process of finding the knots is
g

summarized in Algorithm-3.
Remark-3: For grid matching model, we observe from
simulations (section-IV) that P (B) → 1 if the sufficient
conditions mentioned in Remark-2 are satisfied.
Algorithm 3 Algorithm for Detection and Estimation
1:
2:

Inputs: b, A, η (obtained by inverting the c.d.f).
Initialize: Set k = 1, Ŝ = 0, τ1 = max kPH
jk bk2 .

3:

The active groups J = {j1 , j2 , . . . , jn } is determined by
solving (26) at τk .
For each k ∈
/ J solve the following system of equations
for the blocks ŷ = [ŷ1 , . . . , ŷn ] and a set Λk .
n

ŷl
, kPH
ŷ)
=
Λ
PH
(b
−
P
k
J
j (b−PJ ŷ)k = Λk
jl
kŷl k l=1

4:

k

6:
7:

If the system is in-feasible, we put Λj = 0.
Evaluate: Evaluate the test statistics Ek .
Decision: If Ek ≥ ηi go to step 8
Iterate: The next knot is given by, τk+1 = max Λk .

8:

Outputs: Ŝ = i,

5:

For accurate detection and estimation of sources, we require
the source locations to be matched with the estimation grid.
The popular way to deal with the grid-mismatch problem in
practice is to over-sample the estimation grid into N >> M
bins to obtain a fat array steering matrix, A and hope that all
the source locations are perfectly matched to the estimation

(26)

Proof. See [33]

τ̂ = τ (Ŝ), ρ̂ = ρ(T̂ ).

C. Grid Matching

∀ŷg 6= 0,

where Pg = [eg |gg ], eg and gg are g th column of I and G.

k

T̂ =I(1,2,...,Ŝ),

(25)

where yg = [xg , pg xg ]T , g = 1, 2, . . . , N and P = [I|G]. We
now obtain the optimality conditions for the above optimization as,

where ̺i are the M − S non-zero eigen values of the matrix
QM −S , whose construction is described in the proof.

Similar to other tests, the problem of finding S sources
reduces to comparing Dk with a threshold (η) at each knot
point. The threshold is obtained from the c.d.f (24) by fixing
FD1 to the required Pc .

N
X
1
kb − Pyk22 + τ kyg k2 ,
2
g=1

k

T̂ =I(1,2,...,Ŝ),

τ̂ = τ (Ŝ), ρ̂ = ρ(T̂ ).

We now propose a test at the knot points of the group-lasso
path. The goal of the proposed test is to detect the (S + 1)th
knot point (where S is unknown), conditional on event B.

8

Test-E: The E test statistics at the k th knot is defined as,
Ek =

τS+1
, k = 1, 2, . . . , M − S − 1,
σ2

(28)

Again, assuming event B is true (i.e.,, P (B) → 1), we need
to make a decision at (S + 1)th knot. Hence, we require the
c.d.f of ES+1 , given by
Theorem 10. The c.d.f of E1 , conditional on event B is,
M−S
Y

̺i
εi
(1 − e−η/̺i ) −
(1 − e−η/εi ),
̺
−
ε
̺
−
ε
i
i
i
i
i=1
(29)
where ̺i ≥ εi , i = 1, 2, . . . , M − S are the M − S nonzero eigen values corresponding to the χ2 random variables
as described in the proof.
FE1 (η) =

Proof. See Appendix-VI-C.
Similar to other tests, the problem of finding S sources
reduces to comparing Ek with a threshold (η) at each knot
point. The threshold is obtained from the c.d.f (29) by fixing
FE1 to the required Pc .

IV. N UMERICAL S IMULATIONS
In this section, we evaluate the performance of the proposed
joint detection, estimation and grid matching algorithms discussed in the previous section. In the following, we will first
discuss the simulation set-up, present the results obtained by
the algorithms and interpret the results.

A. Simulation Setup
The simulation setup consists of a uniform linear array
(ULA) with M = 8 antennas, which is receiving signal
from S sources [1]. The sources are chosen such that the
total source power, E{kxk22 } = 1. In the case of multiple
sources, all the sources are assumed to have equal power.
We generate the estimation grid ρ by uniformly sampling the
interval [−π/2, π/2] into N = 8 bins for orthogonal and grid
matching models and N = 16 bins for the non-orthogonal
model. The array steering matrix, A of size M × N is then
generated as explained in section II. A is further normalized
to avoid gain at the receiver. The Gaussian noise is generated
by selecting the noise variance based on the given value of
SNR (defined in section II).
The sources are detected and estimated as described in
Algorithm-1 to Algorithm-3. Grid matching is also performed
while simulating the grid matching scenario using Algorithm3. The threshold for all the simulations is set to maintain the
required probability of correct detection of Pc = 0.99. In the
following, we use Monte-Carlo simulations for L = 105 noisy
realizations to evaluate the performance. We also calculate
P(B) for different scenarios by checking if the knot points
corresponding to the sources occur first in the lasso path.

B. Orthogonal Models
In the simulations for the single source scenario, the source
impinges the ULA from the angle ρ(5). Similarly, sources
impinge ULA from angles ρ(3, 6) for two source scenario. For
three and four source scenarios the sources impinge the ULA
from ρ(2, 4, 6) and ρ(2, 4, 6, 7) angles respectively. Figure1 shows the plot of P(B) vs SNR. Tables (I-V) show the
P̂c obtained by Algorithm-1 based on tests mentioned in
the caption of the table (Asymptotic covariance test, Exact
covariance test, Test-A, Test-B, Test-C). For Test-C, the noise
variance is unknown and is estimated as described earlier.
The number of sources (S) received are indicated in the subcaption. The following observations can be made from Fig. 1
and Tables-(I-V).
1) Fig. 1 shows that P(B) → 1 for SNR > 10, 15, 20, 20
dB for one, two, three and four source scenarios.
2) None of the proposed tests provide rate control (i.e.,
P̂c < Pc ) for SNR< 15 dB for single source, SNR< 20
dB for two source and three source, and SNR< 25dB
for four source scenarios respectively. The reason for
this behaviour is that P (B) 6= 1 in these scenarios, so
the tests fail when SNR is low.
3) All the finite sample tests (Ak , Bk and Tk (Finite)) give
perfect rate control (P̂c = Pc ) independent of SNR
whenever SNR≥ 15, SNR≥ 20, SNR≥ 20 dB and
SNR≥ 25 dB for single, two, three and four source
scenarios respectively.
4) The asymptotic covariance test (Tk (Asymp)) does not
give rate control (i.e., P̂c < Pc ) even at high SNRs.
5) Test-C (Ck ) also provides rate control for high SNRs
for all the scenarios.
6) Pf ≤ 0.01 for exact covariance test, Test-A and Test-B
at moderate to high SNRs.
7) The Algorithm also outputs the correct DoA(s) for 99%
(Pc ) of the trials at moderate to high SNRs.
From the observations, we can conclude that P(B) → 1 at
moderate to high SNRs for orthogonal models, thus verifying
Lemma-1. We also conclude that the proposed finite sample
tests maintain rate control (P̂c = Pc ) at moderate to high
SNRs, where P(B) → 1. Whenever the source is detected
correctly, the estimation error is zero because of perfect grid
matching. We note that the evaluation of threshold (η) for the
finite sample covariance test requires numerical integration,
which makes it the most complex test. But, there is no gain
in-terms of rate control compared to the other finite sample
tests. We also note that although the tests have been performed
for Pc = 0.99, the rate control for higher values of Pc was
also observed and upto 7 sources could be detected.
C. Non-Orthogonal Models
In the simulations for the single source scenario, the source
impinges the ULA from the angle ρ(9). Similarly, sources
impinge ULA from angles ρ(7, 10) for two source scenario.
For three and four source scenarios the sources impinge the
ULA from ρ(6, 9, 12) and ρ(5, 8, 11, 14) angles respectively.
Fig. 2 shows the plot of P(B) vs SNR. Table-VI shows the
P̂c obtained by Algorithm-2 based on Test-D. The number

9

D. Grid Matching

1
S
S
S
S

P(B)

0.8
0.6

=
=
=
=

1
2
3
4

0.4
0.2
0

0 5 10 15 20 25 30 35 40 45 50
SNR in dB

Fig. 1: P(B) vs SNR for orthogonal model
of sources (S) received are indicated in the sub-caption. The
following observations are made from Fig. 2 and Table-VI,
1) Fig. 2 shows that P(B) → 1 for SNR > 15, 20, 25, 35
dB for one, two, three and four source scenarios.
2) Test-D does not provide rate control (i.e., P̂c < Pc ) for
SNR< 15 dB for single source, SNR< 22 dB for two
source, SNR< 25 dB for three source, and SNR< 35dB
for four source scenarios respectively. The reason for
this behaviour is that P (B) 6= 1 in these scenarios, so
the tests fail when SNR is low and sources are not well
separated.
3) The test gives perfect rate control (P̂c = Pc ) independent
of SNR whenever SNR≥ 15, SNR≥ 22, SNR≥ 25 dB
and SNR≥ 35 dB for single, two, three and four source
scenarios respectively.
4) Test-D maintains Pf ≤ 0.01 at moderate to high SNRs.
5) The Algorithm also outputs the correct DoA(s) for 99%
(Pc ) of the trials at moderate to high SNRs.
From the observations, we can conclude that P(B) → 1 for
well separated sources at moderate to high SNRs . We also
conclude that Test-D maintains rate control (P̂c = Pc ) at
moderate to high SNRs for well separated sources, where
P(B) → 1. Whenever the source is detected correctly, the
estimation error is zero because of perfect grid matching.
We note that although the tests have been performed for
Pc = 0.99, the rate control for higher Pc was also observed.
1
S
S
S
S

P(B)

0.8
0.6

=
=
=
=

1
2
3
4

0.4

V. C ONCLUSIONS

0.2
0

In the simulations for the single source scenario, the source
impinges the ULA from the angle ρ(5). Similarly, sources
impinge ULA from angles ρ(3, 6) for two source scenario. For
three and four source scenarios the sources impinge the ULA
from ρ(2, 4, 6) and ρ(1, 3, 5, 7) angles respectively. For P(B)
simulations, the offset error was maintained at pi = 0.24r for
all the sources, where r is the resolution of the grid. Fig. 3
shows the plot of P(B) vs SNR. We note that P(B) depends
on the grid mismatch error pi . For four source scenario and pi
to 0.24r for all the sources, P(B) is always zero irrespective of
SNR (green curve with diamond marker). Reducing pi = 0.1r
for S = 4 sources, we find that P(B) → 1 for high SNRs.
Table-VII shows the P̂c obtained by Algorithm-3 based on
Test-E. The number of sources (S) received are indicated in the
sub-caption. Fig. 4 shows the square root of the Cramer-Rao
bound (SCRB) vs SNR for the model for S sources. For S = 3
sources, the root of the mean-square error (RMSE) vs SNR is
also plotted with pi = 0.24r for all sources. The average for
the RMSE plot is taken over correctly detected sources which
account for Pc . Hence, the RMSE is not calculated for SNR
< 30dB where Pc is small. The following observations can be
made from Fig. 3, Fig. 4 and Table-VII.
1) Fig. 3 shows that P(B) → 1 for SNR > 20, 35, 35 dB
for one, two and three source scenarios.
2) Test-E does not provide rate control (i.e., P̂c < Pc )
for SNR< 20 dB for single source, SNR< 40 dB
for two source and SNR< 40 dB for three source
scenarios respectively. The reason for this behavior is
that P (B) 6= 1 in these scenarios, so the tests fail when
SNR is low and sources are not well separated.
3) The test gives perfect rate control (P̂c = Pc ) independent
of SNR whenever SNR≥ 25, SNR≥ 40 and SNR≥ 40
dB for single, two and three source scenarios.
4) Test-E maintains Pf ≤ 0.01 at moderate to high SNRs.
5) The Algorithm also outputs the correct DoA(s) for 99%
(Pc ) of the trials at high SNRs.
6) Fig. 4 shows that the RMSE for S = 3 is close to the
SCRB for SNR≥ 30dB.
From the observations, we can conclude that P(B) → 1 for
well separated sources at moderate to high SNRs. We also
conclude that Test-E maintains rate control (P̂c = Pc ) at high
SNRs for well separated sources, where P(B) → 1. Whenever
the source(s) are detected correctly, the estimation error and
is close to the SCRB for the grid mismatch model. We note
that although the tests have been performed for Pc = 0.99,
the rate control for higher Pc was also observed.

5 10 15 20 25 30 35 40 45 50
SNR in dB

Fig. 2: P(B) vs SNR for non-orthogonal model

In this work, we propose tests for joint detection and
estimation of multiple targets using single snapshot measurements at moderate to high SNR. These tests can also be
interpreted as stopping criterion for homotopy based (group)
lasso estimators, since they provide a stopping criteria as
the (group) lasso estimator travels the (group) lasso path.
The proposed algorithms offer control over the probability of
correct detection of the sources by choosing the appropriate

10

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.2131
0.8220
0.9683
0.9693
0.9694
0.9693
0.9701
0.9696
0.9695
0.9695

P̂f
0.0179
0.0290
0.0317
0.0307
0.0306
0.0307
0.0299
0.0304
0.0305
0.0305

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(a) S = 1

P̂c
0.2131
0.8220
0.9683
0.9693
0.9694
0.9693
0.9701
0.9696
0.9695
0.9695

P̂f
0.0179
0.0290
0.0317
0.0307
0.0306
0.0307
0.0299
0.0304
0.0305
0.0305

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂c
0.0003
0.0309
0.6992
0.9658
0.9656
0.9663
0.9659
0.9658
0.9658
0.9660

P̂f
0.0158
0.0815
0.1759
0.0342
0.0344
0.0337
0.0340
0.0342
0.0342
0.0340

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(c) S = 3

P̂c
0
0.0042
0.3821
0.9616
0.9631
0.9624
0.9632
0.9620
0.9620
0.9621

P̂f
0.0077
0.0041
0.0233
0.0379
0.0369
0.0376
0.0368
0.0380
0.0380
0.0379

(d) S = 4

TABLE I: Asymptotic Covariance Test

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.1382
0.7557
0.9903
0.9907
0.9902
0.9907
0.9902
0.9901
0.9906
0.9901

P̂f
0.0046
0.0085
0.0097
0.0093
0.0098
0.0093
0.0098
0.0099
0.0094
0.0099

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(a) S = 1

P̂c
0.0022
0.1164
0.9233
0.9909
0.9906
0.9902
0.9904
0.9911
0.9907
0.9908

P̂f
0.0026
0.0025
0.0089
0.0091
0.0094
0.0098
0.0096
0.0089
0.0093
0.0092

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂c
0
0.0089
0.5525
0.9899
0.9898
0.9900
0.9902
0.9902
0.9905
0.9904

P̂f
0.0028
0.0012
0.0074
0.0100
0.0103
0.0100
0.0098
0.0098
0.0095
0.0096

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(c) S = 3

P̂c
0
0
0.2118
0.9868
0.9891
0.9890
0.9897
0.9892
0.9891
0.9898

P̂f
0.0022
0
0.0043
0.0107
0.0109
0.0110
0.0103
0.0108
0.0109
0.0102

(d) S = 4

TABLE II: Exact Covariance Test

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.1629
0.8168
0.9901
0.9906
0.9903
0.9897
0.9903
0.9898
0.9901
0.9903

P̂f
0.0092
0.0097
0.0099
0.0094
0.0097
0.0103
0.0097
0.0102
0.0098
0.0097

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(a) S = 1

P̂c
0.0025
0.1424
0.9564
0.9896
0.9902
0.9905
0.9905
0.9901
0.9904
0.9895

P̂f
0.0074
0.0065
0.0097
0.0104
0.0098
0.0095
0.0095
0.0099
0.0096
0.0106

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂c
0
0.0083
0.6575
0.9896
0.9904
0.9895
0.9897
0.9908
0.9902
0.9896

P̂f
0.0061
0.0068
0.0097
0.0104
0.0096
0.0105
0.0103
0.0092
0.0098
0.0104

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(c) S = 3

P̂c
0
0
0.2669
0.9892
0.9900
0.9896
0.9895
0.9901
0.9905
0.9896

P̂f
0.0051
0.0053
0.0075
0.0101
0.0100
0.0104
0.0105
0.0098
0.0095
0.0104

(d) S = 4

TABLE III: Test-A

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.1475
0.7775
0.9900
0.9896
0.9902
0.9897
0.9901
0.9900
0.9900
0.9901

P̂f
0.0050
0.0089
0.0100
0.0104
0.0098
0.0103
0.0099
0.0100
0.0100
0.0099

(a) S = 1

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.0027
0.1249
0.9364
0.9904
0.9899
0.9899
0.9898
0.9902
0.9900
0.9901

P̂f
0.0039
0.0030
0.0094
0.0094
0.0101
0.0101
0.0102
0.0098
0.0100
0.0099

(b) S = 2

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0
0.0083
0.5975
0.9900
0.9900
0.9897
0.9901
0.9901
0.9897
0.9895

P̂f
0.0033
0.0014
0.0074
0.0100
0.0100
0.0103
0.0099
0.0098
0.0103
0.0105

(c) S = 3

TABLE IV: Test-B

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0
0
0.0707
0.9905
0.9900
0.9897
0.9901
0.9901
0.9897
0.9895

P̂f
0
0
0.0002
0.0016
0.0100
0.0103
0.0099
0.0098
0.0103
0.0105

(d) S = 4

11

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.0254
0.1345
0.5467
0.9653
0.9896
0.9897
0.9901
0.9899
0.9905
0.9896

P̂f
0.0103
0.0098
0.0100
0.0110
0.0104
0.0103
0.0099
0.0101
0.0095
0.0104

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.0024
0.0212
0.1660
0.6900
0.9886
0.9920
0.9928
0.9923
0.9920
0.9926

(a) S = 1

P̂f
0.0075
0.0071
0.0071
0.0084
0.0078
0.0080
0.0072
0.0077
0.0080
0.0074

P̂c
0
0.0085
0.0956
0.5469
0.9754
0.9900
0.9897
0.9898
0.9899
0.9900

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂f
0.0196
0.0299
0.0873
0.1236
0.0176
0.0100
0.0103
0.0102
0.0101
0.0100

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(c) S = 3

P̂c
0
0.0039
0.0544
0.4096
0.9503
0.9908
0.9907
0.9911
0.9909
0.9906

P̂f
0.0248
0.0120
0.0092
0.0096
0.0092
0.0092
0.0094
0.0089
0.0091
0.0094

(d) S = 4

TABLE V: Test-C
SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0.1337
0.7653
0.9893
0.9894
0.9903
0.9900
0.9900
0.9898
0.9902
0.9901

P̂f
0.0388
0.0502
0.0107
0.0106
0.0097
0.0100
0.0100
0.0102
0.0098
0.0099

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0
0.0709
0.8419
0.9885
0.9898
0.9899
0.9901
0.9899
0.9893
0.9901

(a) S = 1

P̂f
0.0473
0.1228
0.0629
0.0114
0.0102
0.0101
0.0099
0.0101
0.0107
0.0099

P̂c
0
0.0024
0.3574
0.9435
0.9893
0.9901
0.9895
0.9899
0.9893
0.9899

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂f
0.0612
0.2130
0.5186
0.0523
0.0107
0.0099
0.0105
0.0101
0.0107
0.0101

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(c) S = 3

P̂c
0
0
0.0602
0.6308
0.8715
0.9701
0.9903
0.9906
0.9904
0.9908

P̂f
0.0828
0.2317
0.5768
0.3680
0.1285
0.0299
0.0097
0.0094
0.0096
0.0092

(d) S = 4

TABLE VI: Test-D
SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

P̂c
0
0.0112
0.4334
0.8773
0.9902
0.9890
0.9905
0.9900
0.9907
0.9908

P̂f
0
0.0105
0.3841
0.0980
0.0098
0.0101
0.0095
0.0100
0.0093
0.0092

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(a) S = 1

P̂c
0
0
0.1365
0.6156
0.7706
0.8634
0.9626
0.9900
0.9899
0.9903

P̂f
0.0012
0.0340
0.4188
0.3751
0.2294
0.1366
0.0374
0.0100
0.0101
0.0097

SNR
5 dB
10 dB
15 dB
20 dB
25 dB
30 dB
35 dB
40 dB
45 dB
50 dB

(b) S = 2

P̂c
0
0
0.0694
0.5222
0.7118
0.8711
0.9691
0.9898
0.9902
0.9898

P̂f
0.0085
0.1071
0.5859
0.4733
0.2878
0.1289
0.0309
0.0102
0.0098
0.0102

(c) S = 3

TABLE VII: Test-E

1
S
S
S
S
S

0.6

=
=
=
=
=

1
2
3
4
4

5
4

0.4
SBCRB

P(B)

0.8

0.2
0

3

·10−2
S=1
S=2
S=3
√
S = 3, MSE
S=4

2

5 10 15 20 25 30 35 40 45 50
SNR in dB

1

Fig. 3: P(B) for grid matching model
0

5 10 15 20 25 30 35 40 45 50
SNR in dB

threshold. Although we have applied the algorithm only for
the DoA problem, the algorithm can be used for any linear
model with Gaussian noise problem.

Fig. 4: SBCRB vs SNR for grid matching model

12

R EFERENCES
[1] H. L. Van Trees, Detection, estimation, and modulation theory. Part IV.
, Optimum array processing. New York: Wiley-Interscience, 2002.
[2] Z. Yang, J. Li, P. Stoica, and L. Xie, “Sparse Methods for Direction-ofArrival Estimation,” ArXiv e-prints, Sep. 2016.
[3] A. Panahi and M. Viberg, “Fast candidate points selection in the lasso
path,” IEEE Signal Processing Letters, vol. 19, no. 2, pp. 79–82, Feb
2012.
[4] P. Gerstoft, A. Xenaki, and C. F. Mecklenbruker, “Multiple and single
snapshot compressive beamforming,” The Journal of the Acoustical
Society of America, vol. 138, no. 4, pp. 2003–2014, 2015.
[5] J. Fuchs, “The generalized likelihood ratio test and the sparse representations approach,” in Image and Signal Processing, ser. Lecture Notes
in Computer Science. Springer Berlin / Heidelberg, 2010, vol. 6134,
pp. 245–253.
[6] S. M. Kay, Fundamentals of Statistical Signal Processing, Volume 2:
Detection Theory. New Jersey: Prentice-Hall Inc, 1993.
[7] P. Boufounos, M. F. Duarte, and R. G. Baraniuk, “Sparse signal reconstruction from noisy compressive measurements using cross validation,”
in IEEE/SP 14th Workshop on Statistical Signal Processing, 2007.
IEEE, 2007, pp. 299–303.
[8] C. D. Austin, R. Moses, J. Ash, and E. Ertin, “On the relation
between sparse reconstruction and parameter estimation with model
order selection,” IEEE Journal of Selected Topics in Signal Processing,
vol. 4, no. 3, pp. 560–570, 2010.
[9] A. Panahi and M. Viberg, “Maximum a posteriori based regularization
parameter selection,” in 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).
[10] E. Fishler and H. Messer, “On the use of order statistics for improved
detection of signals by the mdl criterion,” IEEE Transactions on Signal
Processing, vol. 48, no. 8, pp. 2242–2247, Aug 2000.
[11] B. M. Radich and K. M. Buckley, “Single-snapshot DOA estimation and
source number detection,” IEEE Signal Processing Letters, vol. 4, no. 4,
pp. 109–111, April 1997.
[12] T. L. Lai and C. Z. Wei, “Least squares estimates in stochastic regression
models with applications to identification and control of dynamic
systems,” Ann. Statist., vol. 10, no. 1, pp. 154–166, 03 1982.
[13] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition
by basis pursuit,” SIAM Rev., vol. 43, no. 1, pp. 129–159, Jan. 2001.
[Online]. Available: http://dx.doi.org/10.1137/S003614450037906X
[14] B. N. Bhaskar, G. Tang, and B. Recht, “Atomic norm denoising with
applications to line spectral estimation,” IEEE Transactions on Signal
Processing, vol. 61, no. 23, pp. 5987–5999, Dec 2013.
[15] R. Lockhart, J. Taylor, R. J. Tibshirani, and R. Tibshirani, “A significance
test for the lasso,” Annals of statistics, vol. 42, no. 2, pp. 413–468, 2014.
[16] R. Arablouei, “Fast reconstruction algorithm for perturbed compressive
sensing based on total least-squares and proximal splitting,” Signal
Process., vol. 130, no. C, pp. 57–63, Jan. 2017.
[17] G. Tang, B. Bhaskar, P. Shah, and B. Recht, “Compressed sensing off
the grid,” Information Theory, IEEE Transactions on, vol. 59, no. 11,
pp. 7465–7490, Nov 2013.
[18] O. Teke, A. C. Gurbuz, and O. Arikan, “A robust compressive sensing
based technique for reconstruction of sparse radar scenes,” Digit.
Signal Process., vol. 27, pp. 23–32, Apr. 2014. [Online]. Available:
http://dx.doi.org/10.1016/j.dsp.2013.12.008
[19] D. Malioutov, M. Cetin, and A. S. Willsky, “A sparse signal reconstruction perspective for source localization with sensor arrays,” IEEE
Transactions on Signal Processing, vol. 53, no. 8, pp. 3010–3022, Aug
2005.
[20] W. Liao and A. Fannjiang, “{MUSIC} for single-snapshot spectral
estimation: Stability and super-resolution,” Applied and Computational
Harmonic Analysis, vol. 40, no. 1, pp. 33 – 67, 2016. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/S1063520314001432
[21] P. Häcker and B. Yang, “Single snapshot DOA estimation,” Advances
in Radio Science, vol. 8, pp. 251–256, 2010.
[22] C. Ekanadham, D. Tranchina, and E. Simoncelli, “Recovery of sparse
translation-invariant signals with continuous basis pursuit,” IEEE Transactions on Signal Processing, vol. 59, no. 10.
[23] H. Zhu, G. Leus, and G. Giannakis, “Sparsity-cognizant total leastsquares for perturbed compressive sampling,” IEEE Transactions on
Signal Processing, vol. 59, no. 5, pp. 2002 –2016, may 2011.
[24] R. Jagannath and K. V. S. . Hari, “Block sparse estimator for grid
matching in single snapshot DoA estimation,” Signal Processing Letters,
IEEE, vol. 20, no. 11, pp. 1038–1041, Nov 2013.

[25] Y. Chi, A. Pezeshki, L. Scharf, and R. Calderbank, “Sensitivity to basis
mismatch in compressed sensing,” in IEEE International Conference on
Acoustics Speech and Signal Processing (ICASSP), 2010, march 2010,
pp. 3930 –3933.
[26] M. Herman and T. Strohmer, “General deviants: An analysis of perturbations in compressed sensing,” IEEE Journal of Selected Topics in
Signal Processing, vol. 4, no. 2, pp. 342 –349, april 2010.
[27] S. Bernhardt, R. Boyer, S. Marcos, and P. Larzabal, “Compressed
sensing with basis mismatch: Performance bounds and sparse-based
estimator,” IEEE Transactions on Signal Processing, vol. 64, no. 13,
pp. 3483–3494, July 2016.
[28] A. Beck and A. Ben-Tal, “A global solution for the structured total least
squares problem with block circulant matrices,” SIAM Journal on Matrix
Analysis and Applications, vol. 27, no. 1, pp. 238–255, 2005.
[29] H. L. Van Trees, “Optimum array processing (detection, estimation, and
modulation theory, part IV),” Wiley-Interscience.
[30] S. S. Gupta and M. Sobel, “On the smallest of several correlated f
statistics,” Biometrika, vol. 49, no. 3/4, pp. 509–523, 1962. [Online].
Available: http://www.jstor.org/stable/2333984
[31] D. H. Young, “Recurrence relations between the p.d.f.’s of
order statistics of dependent variables, and some applications,”
Biometrika, vol. 54, no. 1/2, pp. 283–292, 1967. [Online]. Available:
http://www.jstor.org/stable/2333871
[32] R. Jagannath and N. S. Upadhye, “The LASSO Estimator: Distributional
Properties,” ArXiv e-prints, May 2016.
[33] M. Yuan and Y. Lin, “Model selection and estimation in regression
with grouped variables,” Journal of the Royal Statistical Society: Series
B (Statistical Methodology), vol. 68, no. 1, pp. 49–67, 2006. [Online].
Available: http://dx.doi.org/10.1111/j.1467-9868.2005.00532.x
[34] B. Arnold, N. Balakrishnan, and H. Nagaraja, A First Course in Order
Statistics, ser. Classics in Applied Mathematics. SIAM.
[35] R. K. Mallik, “On multivariate rayleigh and exponential distributions,”
IEEE Transactions on Information Theory, vol. 49, no. 6, pp. 1499–
1515, June 2003.
[36] L. de Haan and A. Ferreira, Extreme Value Theory: An Introduction,
ser. Springer Series in Operations Research and Financial Engineering.
Springer New York, 2006.
[37] I. Weissman, “Estimation of parameters and large quantiles based on
the k largest observations,” J. Amer. Statist. Assoc., vol. 73, no. 364, pp.
812–815, 1978.

VI. A PPENDIX
A. Proof of Theorem-2
In the moderate SNR regime, τσj ,j=S+1,S+2,...,M are the
order statistics of Rayleigh random variable with p.d.f f (x)
and c.d.f F (x) = 1 − exp(−x2 /2). Defining M − S = n
and Vj = τS+j /σ, we have Vn ≤...≤Vj ≤...V1 . Defining Vj =
Xn+1−i , we have X1 ≤...Xi ≤...≤Xn .
We first require the joint pdf of V1 , V2 or Xn , Xn−1 . The
joint pdf of consecutive order statistics is [34, Chapter-2]
fXk ,Xk+1 (x, y) = C0 {F (x)}k−1 {1 − F (y)}n−k−1 f (x)f (y),
where C0 =

n!
(k−1)!(n−k−1)! .

Substituting k = n − 1,

fXn−1 ,Xn (x, y) = C{F (x)}n−2 f (x)f (y), 0 < x < y < ∞,
where

n!
.
C= (n−2)!

The joint pdf of Xn and

W =Xn −Xn−1

is,

fW,Xn (w, y) = C{F (y − w)}n−2 f (y − w)f (y), 0 < w < y < ∞.

Now, the joint p.d.f of Xn and TS+1 = Xn W is,
fTS+1 ,Xn (t, y) = C{F (y − t/y)}n−2 f (y − t/y)f (y) y1 , 0 < t < y 2 < ∞.

Finally the p.d.f of TS+1 is obtained by integration of the
above equation w.r.t. y. Hence,
Z ∞
1
fTS+1 (t) = √ C{F (y − t/y)}n−2 f (y − t/y)f (y) dy.
y
t

13

Now the cdf of the co-variance test statistics is,
ZηZ∞
1
FTS+1 (η) =
C{F (y − t/y)}n−2 f (y − t/y)f (y) dydt,
y
√
0

=

√
2
Z ηZ y

t

1
C{F (y − t/y)}n−2 f (y − t/y)f (y) dtdy,
y

Now, at the (S + 1)st knot point, τS+1 = max Λk , Λk =
k∈J
/

c
kPH
k (b − Pji ŷJ )k2 for all ji ∈ J and for some k ∈ J
H
and ŷJ satisfies Λk = kPJ (b − PJ ŷJ )k2 , for the chosen k.
Hence, we obtain the following set of equations for ŷ

H
c
kPH
k (b − PJ ŷJ )k2 = kPji (b − AJ ŷJ )k2 ∀ji ∈ J, k ∈ J .

0 0

Z∞Zη
1
+
C{F (y − t/y)}n−2 f (y − t/y)f (y) dtdy,
y
√
η0

Z∞
−(y − η/y)2 n−1
= 1 − n y exp(−y 2 /2){1 − exp
}
dy.
2
√
η

B. Proof of Theorem-8
Assuming event B is true and S sources. Let J =
{j1 , . . . , jS } be the the active set, after S knot points. Now,
at the (S + 1)st knot point, τS+1 = max Λk , Λk = |aH
k (b −
k∈J
/

AJ x̂J )| for some k ∈ J c and x̂J satisfies Λk 1 = |AH
J (b −
AJ x̂J )|, k ∈ J c . Hence, we obtain the following set of |J|
equations for x̂
c
H
|aH
k (b − AJ x̂J )| = |aji (b − AJ x̂J )| ∀ji ∈ J, k ∈ J . (30)

Solving for x̂ from the above equations and substituting back
in the expression for Λr , we obtain Λr = |aH
r QM−S v|, r ∈
J c , where QM−S is a projection matrix with S zero eigen
values. Since, v is a complex Gaussian random variable
with zero mean and variance σ 2 , each Λ2r /σ 2 are correlated
χ2 random variables. Hence, the test D1 is a maximum of
correlated χ2 random variables whose c.d.f is given by,


= FD1 (η) = P(D1 ≤ η) = P maxc Λ2r /σ 2 ≤ η ,
r∈J

Zη
2
2
2
2
= P(Λ1 /σ ≤ η, . . . , Λ|J|c /σ ≤ η) = fu (u)d(u),
0

Z∞
Z∞
M−S
Y (1 − e−jηzi )
(b)
dz,
= fu (u)I(u, η)d(u) = fˆz (z)
jzi
i=1

(a)

0

0

Z∞
M−S
Y (1 − e−jηzi )
dz,
= (det(I − jDiag(z)RM −S ))−1
jzi
i=1
=

0
∞
M−S
Y Z

i=1z =0
i

M−S
Y
(1 − e−jηzi )
(1 − e−η/̺i ).
dzi =
jzi (1 − j̺i zi )
i=1
M−S

In the above equations, I(u, η) = [0, η]
, fu denotes the
joint p.d.f of Λr , r ∈ J c in (a) and is degenerate because
QM −S is singular. Hence, we use the Parseval theorem to
obtain (b) and then the characteristic function of correlated
χ2 random variables from [35] to evaluate the c.d.f.
C. Proof of Theorem-10
Assuming event B is true and S sources. Let J =
{j1 , . . . , jS } be the the active group, after S knot points.

Solving for ŷ from the above equations and substituting back in the expression for Λr , we obtain Λr =
c
kPH
r Q2(M−S) vk, r ∈ J , where Q2(M−S) is a projection
matrix with 2S zero eigen values. Since, v is a complex
Gaussian random variable with zero mean and variance σ 2 ,
each Λ2r /σ 2 is a correlated χ2 random variable. Hence, the test
E1 is a maximum of correlated χ2 random variables whose
c.d.f is given by,
= FE1 (η) = P(E1 ≤ η) = P(maxc Λ2r /σ 2 ≤ η),
r∈J

=

P(Λ21 /σ 2

≤

η, . . . , Λ2|J|c /σ 2

Zη
≤ η) = fu (u)d(u),
0

Z∞
Z∞
M−S
Y (1 − e−jηzi )
(b)
(a)
dz,
= fu (u)I(u, η)d(u) = fˆz (z)
jzi
i=1
0

0

Z∞
= (det(I − jDiag(z)RM −S )−1 (det(I − jDiag(z)TM −S )−1
0

×

=

M−S
Y

i=1
∞
Z
M−S
Y
i=1z =0
i

(1 − e−jηzi )
dz
jzi

(1 − e−jηzi )
dzi
jzi (1 − j̺i zi )(1 − jεi zi )

In the above equations I(u, η) denotes a unit box from 0 to η,
fu denotes the joint p.d.f of Λr , r ∈ J c in (a) and is degenerate
because QM −S is singular. Hence, we use the Parseval theorem
to obtsin (b) and then the characteristic function of correlated
χ2 random variables from [35] to evaluate the c.d.f.

D. Proof of Theorem-3
We note that Rayleigh random variables (Vi ) satisfy the
Von-Misespcondition. Hence ∃ constants aM =pF −1 (1 −
2 log(M ) and bM = pF ′ (aM ) =
2 log(M )
1/M ) =
d
V1
→ − log(E0 ), where − log E0 has type
s.t. bM ( σ − aM ) −
I extreme value distribution [15], [36]. From [37], for any
V
fixed l ≥ 1, the random variables W0 = bM ( l+1
σ − aM )
(Vi −Vi+1 )
),
i
=
1,
.
.
.
,
l
converge
jointly
and Wi = bM (
σ
d
as (W0 , W1 , W2 , . . . , Wl ) −
→ (log G0 , E1 /1, E2 /2, . . . , El /l),
where G0 , E1 , . . . , El are independent and G0 is Gamma
distributed with scale parameter 1 and shape parameter l, and

14

E1 , . . . , El are standard exponentials. We have,
TS+k

l
W0 X Wj
aM +
+
bM
bM
j=k
!
l
X
Wj Wk ,
W0 +

Vk
= 2 (Vk − Vk+1 ) =
σ
=

aM
1
Wk + 2
bM
bM

!

Wk
,
bM

j=k

!
l
X
1
W0 +
Wj Wk .
= Wk +
2 log(M )
j=k

Hence TS+k converges pointwise to Wk which converges in
distribution to Exp(1/k) as M → ∞.
E. Proof of Lemma-1
Here we show that P(B) → 1 holds in the moderate to high
SNR regime (when θ = min xj ≫ σ). We choose ǫ s.t. ǫ ≫ σ
j∈Te

and θ ≫ ǫ. Now, the knots τk , k = 1, 2, . . . S are independent
Rician random variables. Hence,
S 
S

 Y
 Y
θ η
P min τk ≥ ǫ =
P τk ≥ ǫ ≥
Q1 ,
σ σ
k∈Te
k=1
k=1


Where, Q1 σθ , σǫ is the Marcum Q function, which tends


to 1 as θǫ tends to infinity. Hence P mink∈Te τk ≥ η → 1

for large ηθ . Also simultaneously, we note that τk , k = S +
1,S + 2, . . . M arei.i.d. Rayleigh random variables, hence
2
M−S
which tends to
P maxk∈/ Te τk ≤ η = (1 − exp( −η
2 ))
2σ


1 as ση → ∞. Hence, P maxk∈/ Te τk ≤ η → 1 for large ση .
So, we can conclude that P(B) → 1 for large

θ
σ.

