IEEE Signal Processing - July 2018 - 69

0.8

0.8

0.6

0.6
pe

1

pe

1

0.4

0.4

0.2

0.2

0
100

101

102

103

0
100

104

101

102

L

L

(a)

(b)
ML Detector

Upper Bound

103

104

SBL

Figure 6. The probability of error for the ML detector and SBL algorithm as a function of L. Here, M = 5, N = 20. (a) D = 11 2 M and (b) D = 4 1 M.

where R i denotes the covariance matrix of Y characterized
by the ith candidate support, i.e., R i = S i C i S Ti + v 2w I, where
S i ! C M # D consists of the D columns of S indexed by the
ith candidate support and C i ! R D # D consists of the corresponding entries of C. The authors in [90] considered a ML
support detector
t (Y) = arg max P ^Y H ih .
}
1#i#Q

Upper bound on the probability of error for this detector was
derived in [90], which provably converges to zero as L " 3 provided D 1 M. However, in recent work, this result has been
considerably strengthened and extended to the regime D 2 M,
by exploiting the Khatri-Rao product of S [91]. In particular, it is
shown that the probability of error p e of the above detector is
upper bounded by
p e # e D log (eN/D) - aL .

(40)

The quantity a is given by a = min i ! j a i, j where

/ log f
M

a i, j =

k= 1
(i, j)

(i, j)

mk

+

1
(i, j)

mk

2

p.

(41)

Here m k is the kth eigenvalue of the matrix R 1i /2 R -j 1 R 1i /2 . It
can be verified [91] that the quantity a that controls the error
exponent in (40) is strictly greater than zero as long as
D 1 (1/2) Kruskal-rank (S ) 9 S). Since Kruskal-rank (S ) 9 S)
can be O (M 2), this result decisively shows that when M and N
are held constant, it is possible to recover supports of size
D 2 M with exponentially vanishing probability of error with
respect to L. Figure 6 shows the probability of error for both the
ML detector and the SBL algorithm as a function of L along

with the aforementioned upper bound for the ML detector. Here,
the measurement matrix S is generated as a specific realization
of an i.i.d. Gaussian random matrix and held fixed throughout
the simulations. It can be seen that both detectors are capable of
resolving supports of size larger than M.

Summary and conclusions
In this review article, we studied the role of correlation awareness in low-rank measurement models and demonstrated how
the design of efficient samplers can overcome long-standing bottlenecks in the number of identifiable parameters. In particular,
we focused on the role of difference sets and coarrays in source
localization and showed that nonuniform arrays are necessary to
unambiguously identify parameters in underdetermined models.
We also demonstrated optimal sampling techniques that maximally exploit the low-rank structure of Toeplitz covariance
matrices, and showed that deterministic sampling (GNS) outperforms random sampling in this case. These ideas naturally
extend to Bayesian sparse signal recovery techniques (such as
SBL), which implicitly translates sparsity of the unknown signals into suitable low-rank representations of the covariance
matrix. Finally, we studied recent breakthroughs in understanding fundamental limits of underdetermined parameter estimation, where the number of sources can exceed the number of
sensors. In this case, nonnuniform sampling becomes essential
to guarantee existence of consistent estimators. Spatial and temporal measurements play distinct roles in characterizing the
CRB, which exhibits unique saturation effects that only arise in
the underdetermined setting.

Acknowledgment
This work was supported in parts by the NSF CAREER Award
ECCS 1553954, NSF CPS Synergy 1544798 and the University
of California, San Diego.

IEEE Signal Processing Magazine

|

July 2018

|

69
Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018
