IEEE Signal Processing - July 2018 - 26

exploiting the shift-invariance property embedded in the structure of complex harmonics. This is done by constructing an n 1 by-(n - n 1 + 1) Hankel matrix spanned by the signal vector
x ! C n as
R
V
S x1 x2
W
S x2
i W
W,
H (x) = S
i
Sh
W
Sx n 1 x n 1 + 1 g x nW
T
X

(G L) i, l = D n 1 (z i - z l), 1 # i, l # r ,

The incoherence parameter is then defined as follows.

H (x) = Vn 1 CV Tn - n 1 + 1 ,

g 1 VW
g zr W
,
h
h W
W
g z nr 1 - 1WX

(33)

C = diag [c 1, c 2, f, c r], and Vn - n 1 + 1 is defined in a way similar to (33). This decomposition shows that rank (H (x)) # r, and
equality holds when all the poles are distinct. This representation
of x as a structured low-rank matrix can be leveraged to facilitate recovery of the unmeasured entries of x. In particular, one
can try to recover the missing measurements by seeking a Hankel matrix with the smallest nuclear norm and consistent with
the available measurements. This idea gives rise to the following
algorithm, termed enhanced matrix completion (EMaC) [80]:
min H ( g)

*

subject to PX ( g) = PX (x) .

(34)

Figure 4(a) illustrates the observation pattern in a Hankel matrix
recovery problem, which is highly structured.
Under the parametric model (29), we define a new notion of
incoherence that bears an interesting physical interpretation. Let
the Dirichlet kernel be
n1
D n 1 (z) : = 1 c 1 - z m,
n1 1 - z

(a)

Definition 4 (incoherence)

The incoherence parameter of a signal x of the form (29) is
defined as the smallest number n satisfying the bounds
v min ^ G L h $

(32)

where

g ! Cn

(G R) i, l = D n - n 1 + 1 (z i - z l), 1 # i, l # r.

(31)

where n 1 is commonly selected as 6n/2@ to make the matrix
H (x) as square as possible. The important observation is that
H (x) admits the following low-rank decomposition:

R 1
1
S
z
z
2
S 1
Vn 1 = S
h
h
SS n 1 - 1 n 1 - 1
z2
Tz 1

whose absolute value decays inverse proportionally with respect
to z . Given r poles, one can construct two r # r Gram matrices
G L and G R, corresponding to the column space and row space of
H (x), where the entries of these matrices are specified by

(35)

1
n

and

v min ^ G R h $

1,

n

(36)

where v min ^G Lh and v min ^G Rh denote the smallest singular
values of G L and G R, respectively.
If all poles are well separated by 2/n, the incoherence parameter n can be bounded by a small constant [83]. As the poles get
closer, the Gram matrices become poorly conditioned, resulting
in a large n. Therefore, the incoherence parameter provides a
measure of the hardness of the recovery problem in terms of the
relative positions of the poles. Theorem 8 summarizes the performance guarantees of the EMaC algorithm [80].

Theorem 8 (structured matrix completion)
Suppose that each entry of x is observed independently with
probability p. As long as
4

p$C

nr log n

n

,

for some sufficiently large constant C, the signal x can be
exactly recovered with high probability via EMaC.
Theorem 8 suggests that a Hankel-structured low-rank
matrix can be faithfully recovered using a number of measurements much smaller than its dimension n. Recently it has
been shown that Hankel matrix completion can also be efficiently solved using the nonconvex Burer-Monteiro factorization and projected gradient descent approach described in
the section "Provable and Fast Low-Rank Matrix Estimation

(b)

(c)

(d)

Figure 4. An illustration of structured matrices considered in the section "Tructured Low-Rank Matrix Estimation." (a) The observation pattern in a Hankel matrix completion problem. (b) The cluster matrix. (c) The affinity matrix in a cluster matrix recovery problem, when the nodes are ordered according
to the cluster structure. (d) The affinity matrix in (c), where the nodes are randomly permuted.

26

IEEE Signal Processing Magazine

|

July 2018

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