Separation-Free Super-Resolution from Compressed
Measurements is Possible: an Orthonormal Atomic Norm
Minimization Approach

arXiv:1711.01396v1 [] 4 Nov 2017

∗

Weiyu Xu†

Jirong Yi‡
Mathews Jacob

Soura Dasgupta§
k

Jian-Feng Cai¶

Myung Cho

∗∗

November 7, 2017

Abstract
We consider the problem of recovering the superposition of R distinct complex exponential
functions from compressed non-uniform time-domain samples. Total Variation (TV) minimization or atomic norm minimization was proposed in the literature to recover the R frequencies
or the missing data. However, it is known that in order for TV minimization and atomic norm
minimization to recover the missing data or the frequencies, the underlying R frequencies are
required to be well-separated, even when the measurements are noiseless. This paper shows that
the Hankel matrix recovery approach can super-resolve the R complex exponentials and their
frequencies from compressed non-uniform measurements, regardless of how close their frequencies are to each other. We propose a new concept of orthonormal atomic norm minimization
(OANM), and demonstrate that the success of Hankel matrix recovery in separation-free superresolution comes from the fact that the nuclear norm of a Hankel matrix is an orthonormal
atomic norm. More specifically, we show that, in traditional atomic norm minimization, the
underlying parameter values must be well separated to achieve successful signal recovery, if
the atoms are changing continuously with respect to the continuously-valued parameter. In
contrast, for OANM, it is possible the OANM is successful even though the original atoms can
be arbitrarily close.
As a byproduct of this research, we provide one matrix-theoretic inequality of nuclear norm,
and give its proof from the theory of compressed sensing.
∗ The

first two authors contributed equally to this work.
of Electrical and Computer Engineering, University of Iowa, Iowa City, IA 52242. Email:
weiyu-xu@uiowa.edu.
‡ Department of Electrical and Computer Engineering, University of Iowa, Iowa City, IA 52242. Yi is co-first
author.
§ Department of Electrical and Computer Engineering, University of Iowa, Iowa City, IA 52242.
¶ Department of Mathematics, Hong Kong University of Science and Technology, Hong Kong.
k Department of Electrical and Computer Engineering, University of Iowa, Iowa City, IA.
∗∗ Department of Electrical and Computer Engineering, University of Iowa, Iowa City, IA.
† Department

1

1

Introduction

In super-resolution, we are interested in recovering the high-end spectral information of signals from
observations of it low-end spectral components [3]. In one setting of super-resolution problems, one
aims to recover a superposition of complex exponential functions from time-domain samples. In
fact, many problems arising in science and engineering involve high-dimensional signals that can be
modeled or approximated by a superposition of a few complex exponential functions. In particular,
if we choose the exponential functions to be complex sinusoids, this superposition of complex exponentials models signals in acceleration of medical imaging [18], analog-to-digital conversion [29],
and signals in array signal processing [24]. Accelerated NMR (Nuclear magnetic resonance) spectroscopy, which is a prerequisite for studying short-lived molecular systems and monitoring chemical
reactions in real time, is another application where signals can be modeled or approximated by a
superposition of complex exponential functions. How to recover the superposition of complex exponential functions or parameters of these complex exponential functions is of prominent importance
in these applications.
In this paper, we consider how to recover those superposition of complex exponential from linear
measurements. More specifically, let x ∈ C2N −1 be a vector satisfying
xj =

R
X

ck zkj ,

j = 0, 1, . . . , 2N − 2,

(1)

k=1

where zk ∈ C, k = 1, . . . , R, are some unknown complex numbers with R being a positive integer.
In other words, x is a superposition of R complex exponential functions. We assume R ≤ 2N − 1.
When |zk | = 1, k√= 1, . . . , R, x is a superposition of complex sinusoid. When zk = e−τk e2πıfk ,
k = 1, . . . , R, ı = −1, x can model the signal in NMR spectroscopy.
Since R ≤ 2N −1 and often R  2N −1, the degree of freedom to determine x is much less than
the ambient dimension 2N − 1. Therefore, it is possible to recover x from its under sampling [5,11].
In particular, we consider recovering x from its linear measurements
b = A(x),

(2)

where A is a linear mapping to CM , M < 2N − 1. After x is recovered, we can use the singlesnapshot MUSIC or the Prony’s method to recover the parameter zk ’s.
The problem on recovering x from its linear measurements (2) can be solved using Compressed
Sensing (CS) [5], by discretizing the dictionary of basis vectors into grid points corresponding to
discrete values of zk . When the parameters fk ’s in signals from spectral compressed sensing or
(fk , τk )’s from signals in accelerated NMR spectroscopy indeed fall on the grid, CS is a powerful
tool to recover those signals even when the number of samples is far below its ambient dimension
(R  2N − 1) [5, 11]. Nevertheless, the parameters in our problem setting often take continuous
values, leading to a continuous dictionary, and may not exactly fall on a grid. The basis mismatch
problem between the continuously-valued parameters and the grid-valued parameters degenerates
the performance of conventional compressed sensing [8].
In two seminal papers [3, 27], the authors proposed to use the total variation minimization or
the atomic norm minimization to recover x or to recover the parameter zk , when zk = eı2πfk
with fk taking continuous values from [0, 1). In these two papers, the author showed that the
TV minimization or the atomic norm minimization can recover correctly the continuously-valued
frequency fk ’s when there are no observation noises. However, as shown in [3, 26, 27], in order for
2

the TV minimization or the atomic norm minimization to recover spectrally sparse data or the
associated frequencies correctly, it is necessary to require that adjacent frequencies be separated
far enough from each other. For example, for complex exponentials with zk ’s taking values on the
complex unit circle, it is required that their adjacent frequencies fk ∈ [0, 1]’s be at least 2N2−1 apart.
This separation condition is necessary, even if we observe the full (2N − 1) data samples, and even
if the observations are noiseless.
This raises a natural question, “Can we super-resolve the superposition of complex exponentials
with continuously-valued parameter zk , without requiring frequency separations, from compressed
measurements?” In this paper, we answer this question in positive. More specifically, we show
that a Hankel matrix recovery approach using nuclear norm minimization can super-resolve the
superposition of complex exponentials with continuously-valued parameter zk , without requiring
frequency separations, from compressed measurements. This separation-free super-resolution result
holds even when we only compressively observe x over a subset M ⊆ {0, ..., 2N − 2}.
In this paper, we give the worst-case and average-case performance guarantees of Hankel matrix
recovery in recovering the superposition of complex exponentials. In establishing the worst-case
performance guarantees, we establish the conditions under which the Hankel matrix recovery can
recover the underlying complex exponentials, no matter what values the coefficients ck ’s of the complex exponentials take. For the average-case performance guarantee, we assume that the phases of
the coefficients ck ’s are uniformly distributed over [0, 2π). For both the worst-case and average-case
performance guarantees, we establish that Hankel matrix recovery can super-resolve complex exponentials with continuously-valued parameters zk ’s, no matter how close two adjacent frequencies or
parameters zk ’s are to each other. We further introduce a new concept of orthonormal atomic norm
minimization (OANM), and discover that the success of Hankel matrix recovery in separation-free
super-resolution comes from the fact that the nuclear norm of the Hankel matrix is an orthonormal
atomic norm. In particular, we show that, in traditional atomic norm minimization, for successful
signal recovery, the underlying parameters must be well separated, if the atoms are changing continuously with respect to the continuously-valued parameters; however, it is possible the OANM is
successful even though the original atoms can be arbitrarily close.
As a byproduct of this research, we discover one interesting matrix-theoretic inequality of nuclear
norm, and give its proof from the theory of compressed sensing.

1.1

Comparisons with related works on Hankel matrix recovery and
atomic norm minimization

Low-rank Hankel matrix recovery approaches were used for recovering parsimonious models in system identifications, control, and signal processing. In [19], Markovsky considered low-rank approximations for Hankel structured matrices with applications in signal processing, system identifications
and control. In [12, 13], Fazel et al. introduced low-rank Hankel matrix recovery via nuclear norm
minimization, motivated by applications including realizations and identification of linear timeinvariant systems, inferring shapes (points on the complex plane) from moments estimation (which
is related to super-resolution with zk from the complex plane), and moment matrix rank minimization for polynomial optimization. In [13], Fazel et al. further designed optimization algorithms to
solve the nuclear norm minimization problem for low-rank Hankel matrix recovery. In [6], Chen and
Chi proposed to use multi-fold Hankel matrix completion for spectral compressed sensing, studied
the performance guarantees of spectral compressed sensing via structured multi-fold Hankel matrix
completion, and derived performance guarantees of structured matrix completion. However, the

3

results in [6] require that the Dirichlet kernel associated with underlying frequencies satisfies certain
incoherence conditions, and these conditions require the underlying frequencies to be well separated
from each other. In [9, 30], the authors derived performance guarantees for Hankel matrix completion in system identifications. However, the performance guarantees in [9,30] require a very specific
sampling patterns of fully sampling the upper-triangular part of the Hankel matrix. Moreover, the
performance guarantees in [9, 30] require that the parameters zk ’s be very small (or smaller than
1) in magnitude. In our earlier work [2], we established performance guarantees of Hankel matrix
recovery for spectral compressed sensing under Gaussian measurements of x, and by comparison,
this paper considers direct observations of x over a set M ⊆ {0, 1, 2, ..., 2N − 2}, which is a more
relevant sampling model in many applications. In the single-snapshot MUSIC algorithm [17], the
Prony’s method [10] or the matrix pencil approach [15], one would need the full (2N − 1) consecutive samples to perform frequency identifications, while the Hankel matrix recovery approach can
work with compressed measurements. When prior information of the locations of the frequencies
are available, one can use weighted atomic norm minimization to relax the separation conditions
in successful signal recovery [20]. In [25], the authors consider super-resolution without separation
using atomic norm minimization, but under the restriction that the coefficients are non-negative
and for a particular set of atoms.

1.2

Organizations of this paper

The rest of the paper is organized as follows. In Section 2, we present the problem model, and introduce the Hankel matrix recovery approach. In Section 3, we investigate the worst-case performance
guarantees of recovering spectrally sparse signals regardless of frequency separation, using the Hankel matrix recovery approach. In Section 4, we study the Hankel matrix recovery’s average-case
performance guarantees of recovering spectrally sparse signals regardless of frequency separation.
In Section 5, we show that in traditional atomic norm minimization, for successful signal recovery,
the underlying parameters must be well separated, if the atoms are changing continuously with
respect to the continuously-valued parameters. In Section 6, we introduce the concept of orthonormal atomic norm minimization, and show that it is possible that the atomic norm minimization
is successful even though the original atoms can be arbitrarily close. In Section 7, as a byproduct
of this research, we provide one matrix-theoretic inequality of nuclear norm, and give its proof
from the theory of compressed sensing. Numerical results are given in Section 8 to validate our
theoretical predictions. We conclude our paper in Section 9.

1.3

Notations

We denote the set of complex numbers and real number as C and R respectively. We use calligraphic
uppercase letters to represent index sets, and use | · | to represent a set’s cardinality. When we use
an index set as the subscript of a vector, we refer to the part of the vector over the index set. For
example, xΩ is the part of vector x over the index set Ω. We use Cnr 1 ×n2 to represent the set of
matrices from Cn1 ×n2 with rank r. We denote the trace of a matrix X by Tr(X), and denote the
real part and imaginary parts of a matrix X by Re(X) and Im(X) respectively. The superscripts
T and ∗ are used to represent transpose, and conjugate transpose of matrices or vectors. The
Frobenius norm, nuclear norm, and spectral norm of a matrix are denoted by k · kF , k · k∗ and k · k2
(or k·k) respectively. The notation k·k represents the spectral norm if its argument is a matrix, and
represents the Euclidean norm if its argument is vector. The probability of an event S is denoted

4

by P(S).

2

Problem statement
The underlying model for spectrally sparse signal is a mixture of complex exponentials
xj =

R
X

ck e(ı2πfk −τk )j , j ∈ {0, 1, · · · , 2N − 2}

(3)

k=1

√
where ı = −1, fk ∈ [0, 1), ck ∈ C, and τk ≥ 0 are the normalized frequency, coefficients, and
damping factor, respectively. We observe x over a subset M ⊆ {0, 1, 2, ..., 2N − 2}.
To estimate the continuous parameter fk ’s, in [3, 27], the authors proposed to use the total
variation minimization or the atomic norm minimization to recover x or to recover the parameter
zk , when zk = eı2πfk with fk taking continuous values from [0, 1). In these two papers, the
author showed that the TV minimization or the atomic norm minimization can recover correctly
the continuously-valued frequency fk ’s when there are no observation noises. However, as shown
in [3,26,27], in order for atomic norm minimization to recover spectrally sparse data or the associated
frequencies correctly, it is necessary to require that adjacent frequencies be separated far enough
from each other. Let us define the minimum separation between frequencies as the following:
Definition 2.1. (minimum separation, see [3]) For a frequency subset F ⊂ [0, 1) with a group of
points, the minimum separation is defined as smallest distance two arbitrary different elements in
F, i.e.
dist(F) =

inf

fi ,fl ∈F ,fi 6=fl

d(fi , fl ),

(4)

where d(fi , fl ) is the wrap around distance between two frequencies.
As shown in [26], for complex exponentials with zk ’s taking values on the complex unit circle,
it is required that their adjacent frequencies fk ∈ [0, 1]’s be at least 2N2−1 apart. This separation
condition is necessary, even if we observe the full (2N −1) data samples, and even if the observations
are noiseless.
Following the idea the matrix pencil method in [15] and Enhanced Matrix Completion (EMaC)
in [6], we construct a Hankel matrix based on signal x. More specifically, define the Hankel matrix
H(x) ∈ CN ×N by
Hjk (x) = xj+k−2 ,
j, k = 1, 2, . . . , N.
(5)
The expression (3) leads to a rank-R decomposition:




1
...
1
1
 z1
 c1
.
.
.
z
R




.
.
..
H(x) =  ..
..
..  
  ..
 .

.
.
cR
1
N −1
z1N −1 . . . zR

z1 . . .
..
.
zR . . .


z1N −1
.. 
. 

N −1
zR

Instead of reconstructing x directly, we reconstruct the rank-R Hankel matrix H, subject to
the observation constraints. Low rank matrix recovery has been widely studied in recovering a
matrix from incomplete observations [4]. It is well known that minimizing the nuclear norm can
5

lead to a solution of low-rank matrices. We therefore use the nuclear norm minimization to recover
the low-rank matrix H. More specifically, for any given x ∈ C2N −1 , let H(x) ∈ CN ×N be the
corresponding Hankel matrix. We solve the following optimization problem:
min kH(x)k∗ ,
x

subject to A(x) = b,

(6)

where k · k∗ is the nuclear norm, and A and b are the linear measurements and measurement results.
When there is noise η contained in the observation, i.e.,
b = Ax + η,
we solve
min kH(x)k∗ ,
x

subject to kAx − bk2 ≤ δ,

(7)

where δ = kηk2 is the noise level.
It is known that the nuclear norm minimization (6) can be transformed into a semidefinite
program
1
(Tr(Q1 ) + Tr(Q2 ))
x,Q1 ,Q2 2
s.t. b = Ax,


Q1
H(x)∗
0
H(x)
Q2
min

(8)

which can be easily solved with existing convex program solvers such as interior point algorithms.
After successfully recovering all the time samples, we can use the single-snapshot MUSIC algorithm
(as discussed in [17]) to identify the underlying frequencies fk .
For the recovered Hankel matrix H(x), let its SVD be


Σ1 0
H(x) = [U1 U2 ]
[V1 V2 ]∗ , U1 , V1 ∈ CN ×R ,
(9)
0 0
and we define the vector φN (f ) and imaging function J(f ) as
φN (f ) = (eı2πf 0 , eı2πf 1 , ..., eı2πf (N −1) )T , J(f ) =

kφN (f )k2
, f ∈ [0, 1).
kU2∗ φN (f )k2

(10)

The single-snapshot MUSIC algorithm is given in Algorithm 1.
Algorithm 1 The Single-Snapshot MUSIC algorithm [17]
require: solution x, parameter R and N
form Hankel matrixZ ∈ CN ×N

Σ1 0
3: SVD Z = [U1 U2 ]
[V1 V2 ]∗ with U1 ∈ CN ×R and Σ1 ∈ CR×R
0 0
1:
2:

kφN (f )k2
,f
kU2∗ φN (f )k2

∈ [0, 1)

4:

compute imaging function J(f ) =

5:

get set F̂={ f : f corresponds to R largest local maxima of J(f )}

In [17], the author showed that the MUSIC algorithm can exactly recover all the frequencies by
finding the local maximal of J(f ). Namely, for undamped signal (3) with the set of frequencies F,
if N ≥ R, then “f ∈ F” is equivalent to “J(f ) = ∞.”
6

3

Worst-case performance guarantees of separation-free superresolution

In this section, we provide the worst-case performance guarantees of Hankel matrix recovery for
recovering the superposition of complex exponentials. Namely, we provide the conditions under
which the Hankel matrix recovery can uniformly recover the superposition of every possible R
complex exponentials. Our results show that the Hankel matrix recovery can achieve separationfree super-resolution, even if we consider the criterion of worst-case performance guarantees. Later
in Section 4.2, we further show that our derived worst-performance guarantees are tight, namely
we can find examples where R is bigger than the predicted recoverable sparsity by our theory, and
the nuclear norm minimization fails to recover the superposition of complex exponentials.
We let wi be the number of elements in the i-th anti-diagonal of matrix H, namely,
(
i, i = 1, 2, · · · , N,
(11)
wi =
2N − i, i = N + 1, · · · , 2N − 1.
Here we call the (2N − 1) anti-diagonals of H(x) from the left top to the right bottom as the
1-st anti-diagonal, ..., and the (2N − 1)-th anti-diagonal. We also define wmin as
wmin =

min

i∈{0,1,2,...,2N −2}\M

wi+1 .

(12)

With the setup above, we give the following Theorem 1 concerning the worst-case performance
guarantee of Hankel matrix recovery.
Theorem 1. Let us consider the signal model of the superposition of R complex exponentials (3),
the observation set M ⊆ {0, 1, 2, ..., 2N − 2}. We further define wi of an N × N Hankel matrix
H(x) as in (11), and define wmin as in (12). Then the nuclear norm minimization (6) will
uniquely recover H(x), regardless of the (frequency) separation between the R continuously-valued
(frequencies) parameters if
R<

wmin
.
2(2N − 1 − |M|)

(13)

Proof. We can change (6) to the following optimization problem:
min kBk∗ ,
B,x

subject to B = H(x), A(x) = b.

(14)

We can think of (14) as a nuclear norm minimization problem, where the null space of the linear
operator (applied to (B,x)) in the constraints of (14) is given by (H(z), z) such that A(z) = 0.
From [21, 22], we have the following lemma about the null space condition for successful signal
recovery via nuclear norm minimization.
Lemma 1. [21] Let X0 be any N ×N matrix of rank R, and we observe it through a linear mapping
A(X0 ) = b. Then the nuclear norm minimization (15)
min kXk∗ ,
X

subject to

7

A(X) = A(X0 ),

(15)

can uniquely and correctly recover every matrix X0 with rank no more than R if and only if, for all
nonzero Z ∈ N (A),
2kZk∗R < kZk∗ ,

(16)

where kZk∗R is the sum of the largest R singular values of Z, and N (A) is the null space of A.
Using this lemma, we can see that (14) or (6) can correctly recover x as a superposition of R
complex exponentials if kH(z)k∗R < kH(z)k∗ holds true for every nonzero z from the null space
of A.
Considering the sampling set M ⊆ {0, 1, 2, ..., 2N − 2}, the null space of the sampling operator
A is composed of (2N − 1) × 1 vectors z’s such that zi+1 = 0 if i ∈ M. For such a vector z, let
us denote the element across the i-th anti-diagonal of H(z) as ai , and thus Q = H(z) is a Hankel
matrix with its (i + 1) anti-diagonal element equal to 0 if i ∈ M. Let σ1 , · · · , σN be the N singular
values of H(z) arranged in a descending order. To verify the null space condition for nuclear norm
minimization, we would like to find the largest R such that
σ1 + · · · + σR < σR+1 + · · · + σN ,

(17)

for every nonzero z in the null space of A.
Towards this goal, we first obtain a bound for its largest singular value (for a matrix Q, we use
Qi,: to denote its i-th row vector):
σ1 =

=

=

≤

=

≤

≤

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

max

u∈CN ,kuk2 =1

s
=

kQuk2
v
uN
uX
t
|Qi,: u|2

(18)

(19)

i=1

v
u
uX
N
u
t

2

X

aj uj−i+1

(20)

i=1 j∈{j: i∈Ind(j),aj 6=0}

v

u
N
uX
u

t
i=1

v
u
u
u
t


X

|aj |2  

j∈{j:i∈Ind(j),aj 6=0}

|aj |2 

N
X



(21)


X


i=1

j∈{j:i∈Ind(j),aj 6=0}

j1 =1

|uj−i+1 |2 

j∈{j:i∈Ind(j),aj 6=0}


X

v


u
−1
u2N
uX 
t
|aj1 |2 


X

|uj−i+1 |2 

(22)

j∈{j:i∈Ind(j),aj 6=0}


X

X

|uj2 −i+1 |2 

(23)

i∈Ind(j1 ) j2 ∈{j:i∈Ind(j),aj 6=0}

v
u2N −1
uX
t
[|aj1 |2 (2N − 1 − M )]

(24)

j1 =1

X

|aj+1 |2 (2N − 1 − M ).

j∈{0,1,...,2N −2}\M

8

(25)

where (20) is obtained by looking at the rows (with Ind(j) being the set of indices of rows which
intersect with the j-th anti-diagonal and {j : i ∈ Ind(j), aj 6= 0} being the set of all non-zero
anti-diagonals intersecting with the i-th row), (21) is due to the Cauchy-Schwarz inequality, and
(24)
kuk2 = 1 and, for each i, |ui |2 appears for no more than (2N − 1 − M ) times in
P is because
P
2
i∈Ind(j1 )
j2 ∈{j:i∈Ind(j),aj 6=0} |uj2 −i+1 | .
Furthermore, summing up the energy of the matrix Q, we have
N
X

X

σi2 =

i=1

|ai+1 |2 wi+1 .

(26)

i∈{0,1,...,2N −2}\M

Thus for any integer k ≤ N , we have
PN

i=1
Pk
i=1

σi
σi

PN
≥

i=1

σi

kσ1
PN

2
i=1 σi
2
kσ1

≥

P
≥

i∈{0,1,...,2N −2}\M

k

P

j∈{0,1,...,2N −2}\M

|ai+1 |2 wi+1

|aj+1 |2 (2N − 1 − M )

mini∈{0,1,...,2N −2}\M wi+1
k(2N − 1 − M )
wmin
=
.
k(2N − 1 − M )
≥

(27)

So if
mini∈{0,1,...,2N −2}\M wi+1
> 2,
R(2N − 1 − M )

(28)

then for ever nonzero vector z in the null space of A, and the corresponding Hankel matrix Q =
H(z),
N
X

σi > 2

i=1

R
X

σi .

(29)

i=1

min
It follows that, for any superposition of R < 2(2Nw−1−M
) complex exponentials, we can correctly
recover x over the whole set {0, 1, ..., 2N − 2} using the incomplete sampling set M, regardless of
the separations between different frequencies (or between the continuously-valued parameters zk ’s
for damped complex exponentials).

On the one hand, the performance guarantees given in Theorem 1 can be conservative: for
average-case performance guarantees,even when the number of complex exponentials R is bigger
than predicted by Theorem 1, the Hankel matrix recovery can still recover the missing data, even
though the sinusoids can be very close to each other. On the other hand, the bounds on recoverable
sparsity level R given in Theorem 1 is tight for worst-case performance guarantees, as shown in the
next section.
9

3.1

Tightness of recoverable sparsity guaranteed by Theorem 1

We will show the tightness of recoverable sparsity guaranteed by Theorem 1 in Section 4.2, which
is built on the developments in Section 4.1.

4

Average-case performance guarantees

In this section, we study the performance guarantees for Hankel matrix recovery, when the phases
of the coefficients of the R sinusoids are iid and uniformly distributed over [0, 2π). For averagecase performance guarantees, we show that we can recover the superposition of a larger number of
complex exponentials than Theorem 1 offers.

4.1

Average-case performance guarantees for orthogonal frequency atoms
and the tightness of worst-case performance guarantees

Theorem 2. Let us consider the signal model of the superposition of R complex exponentials
(3) with τk = 0. We assume that the R frequencies f1 , f2 ,..., and fR are such that the atoms
(eı2πfi 0 , eı2πfi 1 , ..., eı2πfi (N −1) )T , 1 ≤ i ≤ R, are orthogonal to each other. We let the observation
set be M = {0, 1, 2, ..., 2N − 2} \ {N − 1}. We assume the phases of coefficients c1 , · · · , cR in
signal model (3) are independent and uniformly distributed over [0, 2π). Then the nuclear norm
minimization (6) will successfully and uniquely recover H(x) and x, with probability approaching 1
as N → ∞ if
p
(30)
R = N − c log(N )N ,
where c > 0 is a constant.
Proof. We use the following Lemma 2 about the condition for successful signal recovery through
nuclear norm minimization. This lemma is an extension of Lemma 13 in [21]. The key difference
is Lemma 2 deals with complex-numbered matrices. Moreover, Lemma 2 gets rid of the “iff” claim
for the null space condition in Lemma 13 of [21], because we find that the condition in Lemma 13
of [21] is a sufficient condition for the success of nuclear norm minimization, but not a necessary
condition for the success of nuclear norm minimization. We give the proof of Lemma 2, and prove
the null space condition is only a sufficient condition for nuclear norm minimization in Appendix
10.1 and Appendix 10.2 respectively.
Lemma 2. Let X0 be any M × N matrix of rank R in CM ×N , and we observe it through a
linear mapping A(X0 ) = b. We also assume that X0 has a singular value decomposition (SVD)
X0 = U ΣV ∗ , where U ∈ CM ×R , V ∈ CN ×R , and Σ ∈ CR×R is a diagonal matrix. Then the
nuclear norm minimization (31)
min kXk∗ ,
X

subject to

A(X) = A(X0 ),

(31)

correctly and uniquely recovers X0 if, for every nonzero element Q ∈ N (A),
−|Tr(U ∗ QV )| + kŪ ∗ QV̄ k∗ > 0,
where Ū and V̄ are such that [U Ū ] and [V V̄ ] are unitary.
10

(32)

We can change (6) to the following optimization problem
min kBk∗ ,

subject to B = H(x), A(x) = b.

B,x

(33)

We can think of (33) as a nuclear norm minimization, where he null space of the linear operator
(applied to B and x) in the constraints of (14) is given by (H(z), z) such that A(z) = 0.
Then we can see that (33) or (6) can correctly recover x as a superposition of R complex
exponentials if
|Tr(V U ∗ H(z))| < kŪ ∗ H(z)V̄ k∗ ,

(34)

hold true for any z which is a nonzero vector from the null space of A, where H(x) = U ΣV ∗ is
the singular value decomposition (SVD) of H(x) with U ∈ CN ×R and V ∈ CN ×R , and Ū and V̄
are such that [U , Ū ] and [V , V̄ ] are unitary.
Without loss of generality, let fk = sNk for 1 ≤ k ≤ R, where sk ’s are distinct integers between
0 and N − 1. Then
sR
s2
s1


  −ıθ1
eı2π N 0
···
eı2π N 0
eı2π N 0
e
0
···
0
sR
s1
s2
ı2π 1
 0
0 
e−ıθ2 · · ·
eı2π N 1
···
eı2π N 1
1 
 e N


U=√

 ,


.
.
..
..
..
.
.
.
.
.
.
.
.

 .
N 
.
.
.
.
.
.
.
s1

eı2π N (N −1)

s2

eı2π N (N −1)

···

sR

eı2π N

(N −1)

0

0

···

e−ıθR

(35)
and

1
V =√
N






s1

s2

e−ı2π N 0
s1
e−ı2π N 1
..
.

e−ı2π N 0
s2
e−ı2π N 1
..
.

s1

e−ı2π N (N −1)

eı−2π N (N −1)

s2

sR

e−ı2π N 0
sR
e−ı2π N 1
..
.

···
···
..
.
···

sR

e−ı2π N




 ,


(36)

(N −1)

and



Σ=N 


|c1 | 0 · · ·
0 |c2 | · · ·
..
..
..
.
.
.
0
0 ···

0
0
..
.




 ,


(37)

|cR |

where θk ’s (1 ≤ k ≤ R) are iid random variables uniformly distributed over [0, 2π).
When the observation set M = {0, 1, 2, ..., 2N − 2} \ {N − 1}, any Q = H(z) with z from the
null space of A takes the following form:


0 ··· 1


Q = a  ... . . . ...  , a ∈ C.
(38)
1

···

11

0

Thus





|Tr(V U ∗ Q)| = aTr U ∗

= |a|

=

1
√
N

 
1
..  V 
.  
0

···
.
..

0
 ..
 .
1

···
2 X
R N
−1
X

eıθi e−ı2π

si (N −1−t)
N

× e−ı2π

si (t)
N

R N −1
|a| X X ıθi −ı2π si (N −1)
N
e e
N i=1 t=0

= |a|

R
X

(39)

i=1 t=0

eıθi e−ı2π

si (N −1)
N

(40)

.

(41)

i=1
si (N −1)

Notice that random variable eıθi e−ı2π N
are mutually independent random variables uniformly distributed over the complex unit circle. We will use the following lemma (see for examsi (N −1)
ple, [28]) to provide a concentration of measure result for the summation of eıθi e−ı2π N :
Lemma 3. (see for example, [28]) For a sequence of i.i.d. random matrix matrices M1 , · · · , MK
PK
with dimension d1 × d2 and their sum M = i=1 Mi , if Mi satisfies
E[Mi ] = 0, kMi k ≤ L, ∀i = 1, · · · , K,

(42)

and M satisfies
(
ν(M ) = max

K
X

E[Mi Mi∗ ]

,

K
X

)
E[Mi∗ Mi ]

,

(43)

i=1

i=1

then

P(kM k ≥ t) ≤ (d1 + d2 ) · exp

−t2 /2
v(M ) + Lt/3


, ∀t ≥ 0.

Applying Lemma 3 to the 1×2 matrix composed of the real and imaginary parts of eıθi e−ı2π
with ν = max(R, R/2) = R, L = 1, d1 + d2 = 3, we have
t2 /2

(44)
si (N −1)
N

t2 /2

P (|Tr(V U ∗ Q)| ≥ |a|t) ≤ 3e− ν+Lt/3 = 3e− R+t/3 , ∀t > 0.

(45)

We further notice that, Ū ’s ( V̄ ’ s) columns are normalized orthogonal frequency atoms (or their
li
complex conjugates) with frequencies N
, with integer li ’s different from the integers sk ’s of those
R complex exponentials. Thus
∗

kU QV k∗ = |a|(N − R).
2

(46)

(N −R) /2
Pick t = N − R, and let R+(N
a positive constant. Solving for
−R)/3 = c log(N ) with c being 

q
R, we obtain R = N − 23 log(N ) + 49 c2 log2 (N ) + 2c log(N )N , which implies (34) holds with

probability approaching 1 if N → ∞. This proves our claims.
12

,

4.2

Tightness of recoverable sparsity guaranteed by Theorem 2

We show that the recoverable sparsity R provided by Theorem 2 is tight for M = {0, 1, 2, ..., 2N −
= N2 .
2} \ {N − 1}. For such a sampling set, wmin = N , and Theorem 2 provides a bound R < wmin
2
In fact, we can show that if R ≥ N2 , we can construct signal examples where the Hankel matrix
recovery approach cannot recover the original signal x. Consider the signal in Theorem 2. We
si (N −1)
choose the coefficients ci ’s such that eıθi e−ı2π N
= 1, then
|Tr(V U ∗ Q)| = |a|

R
X

eıθi e−ı2π

si (N −1)
N

= |a|R,

(47)

i=1

and we also have
∗

kU QV k∗ = |a|(N − R).

(48)

∗

Thus |Tr(V U ∗ Q)| ≥ kU QV k∗ for every Q = H(z) with z in the null space of the sampling
operator. Thus the Hankel matrix recovery cannot recover the ground truth x. This shows that
the prediction by Theorem 2 is tight.

4.3

Average-Case performance analysis with arbitrarily close frequency
atoms

In this section, we further show that the Hankel matrix recovery can successfully recover the superposition of complex exponentials with arbitrarily close frequency atoms. In particular, we give
average performance guarantees on recoverable sparsity R when frequency atoms are arbitrarily
close, and show that the Hankel matrix recovery can deal with much larger recoverable sparsity R
for average-case signals than predicted by Theorem 1.
We consider a signal x composed of R complex exponentials. Among them, R − 1 orthogonal
complex exponentials (without loss of generality, we assume that these R −1 frequencies take values
li
ı2πfcl j
has a frequency arbitrarily
N , where li ’s are integers). The other complex exponential ccl e
close to one of the R − 1 frequencies, i.e.,
xj =

R−1
X

ck eı2πfk j + ccl eı2πfcl j , j ∈ {0, 1, · · · , 2N − 2},

(49)

k=1

where fcl is arbitrarily close to one of the first (R − 1) frequencies. For this setup with arbitrarily
close atoms, we have the following average-case performance guarantee.
Theorem 3. Consider the signal model (49) with R complex exponentials, where the coefficients of
these complex exponentials are iid uniformly distributed random over [0, 2π), and the first (R − 1)
of the complex exponentials are such that the corresponding atom vectors in (10) are mutually
orthogonal, while the R-th exponential has frequency arbitrarily close to one of the first (R − 1)
frequencies (in wrap-around distance). Let cmin = min{|c1 |, |c2 |, ..., |cR−1 |}, and define
drel =

|ccl |
+ 1.
cmin

13

(50)

If we have the observation set M = {0, 1, 2, ..., 2N − 2} \ {N − 1}, and, for any constant c > 0,
if

R=

q
√
√
(2N − 8 N drel + 2c log(N )) + 12cN log(N ) − 48c N drel log(N ) + 4c2 log2 (N )
2

,

(51)

then we can recover the true signal x via Hankel matrix recovery with high probability as N → ∞,
regardless of frequency separations.
Remarks: 1. We can extend this result to cases where neither of the two arbitrarily close
frequencies has on-the-grid frequencies, and the Hankel matrix recovery method can recover a
similar sparsity; 2. Under a similar number of complex exponentials, with high probability, the
Hankel matrix recovery can correctly recover the signal x, uniformly over every possible phases of
the two complex exponentials with arbitrarily close frequencies; 3. We can extend our results to
other sampling sets, but for clarity of presentations, we choose M = {0, 1, 2, ..., 2N − 2} \ {N − 1}
Proof. To prove this theorem, we consider a perturbed signal x̃. The original signal x and the
perturbed x̃ satisfy
xj = x̃j + ccl eı2πfcl j − crm eı2πfrm j , j ∈ {0, 1, · · · , 2N − 2},

(52)

where frm is a frequency such that its corresponding frequency atom is mutually orthogonal with
the atoms corresponding to f1 , ..., and fR−1 . We further define
dmin = min{|c1 |, · · · , |cR−1 |, |crm |}.

(53)

Let us define X̃ = H(x̃), X = H(x), and the error matrix E such that:
X = X̃ + E,

(54)

where


E= 

ccl eı2πfcl ·0 − crm eı2πfrm ·0
..
.
ccl eı2πfcl ·(N −1) − crm eı2πfrm ·(N −1)

···
..
.
···


ccl eı2πfcl ·(N −1) − crm eı2πfrm ·(N −1)

..
 . (55)
.
ccl eı2πfcl ·(2N −2) − crm eı2πfrm ·(2N −2)

Both X and X̃ are rank-R matrices. For the error matrix E, we have
1/2


kEkF = 

X

|ccl eı2πfcl ·(i+k) − crm eı2πfrm ·(i+k) |2 

i,k∈{0,··· ,N −1}

1/2


≤

X

2
(|ccl | + |crm |) 

i,k∈{0,··· ,N −1}



= N 2 (|ccl | + |crm |)

2

1/2

= N (|ccl | + |crm |) .

(56)
14

Following the derivations in Theorem 2, X̃ has the following SVD

Σ̃1
H
N ×N
N ×N
X̃ = Ũ Σ̃Ṽ , Ũ = [Ũ1 Ũ2 ] ∈ C
, Ṽ = [Ṽ1 Ṽ2 ] ∈ C
, Σ̃ =
0

0
0



∈ CN ×N

(57)

where Ũ1 ∈ CN ×R , Σ̃1 ∈ CR×R and Ṽ1 ∈ CN ×R are defined as in (35), (36) and (37). The polar
decomposition of X̃ using its SVD is given by
X̃ = P̃ H̃, P̃ = Ũ1 Ṽ1∗ , H̃ = Ṽ1 Σ̃1 Ṽ1∗ ,
and the matrix P̃ is called the unitary polar factor. Similarly, for X, we have

Σ1
N ×N
N ×N
X = U ΣV , U = [U1 U2 ] ∈ C
, V = [V1 V2 ] ∈ C
,Σ =
0

(58)

0
0


,

(59)

and its polar decomposition for X,
X = P H, P = U1 V1∗ , H = V1 Σ1 V1∗ .

(60)

Suppose that we try to recover x through the following nuclear norm minimization:
min kH(x)k∗
x

s.t. A(x) = b.

(61)

As in the proof of Theorem 2, we analyze the null space condition for successful recovery using
Hankel matrix recovery. Towards this, we first bound the unitary polar factor of X through the
perturbation theory for polar decomposition.
with SVD defined as
and X̃ ∈ Cm×n
Lemma 4. ( [16], Theorem 3.4) For matrices X ∈ Cm×n
r
r
(57) and (59), let σr and σ̃r be the smallest nonzero singular values of X and X̃, respectively, then


2
2
+
|||X − X̃|||,
(62)
|||P − P̃ ||| ≤
σr + σ̃r
max{σr , σ̃r }
where ||| · ||| is any unitary invariant norm.
For our problem, we have m = n = N, r = R. Let σR be the R-th singular value of X. From
(36) and (53), an explicit form for σR is
σR = N dmin .

(63)

Then Lemma 4 implies that
kP − P̃ kF ≤

4
kX − X̃kF .
σR

(64)

From the null space condition for nuclear norm minimization (61), we can correctly recover x if
|Tr(V1 U1∗ Q)| < kŪ1∗ QV̄1 k∗ ,

15

(65)

for every nonzero Q = H(z) with z ∈ N (A), where Ū1 and V̄1 are such that [U1 Ū1 ] and [V1 V̄1 ]
are unitary, i.e., Ū1 = U2 and V̄1 = V2 . Since the observation set M = {0, 1, 2, ..., 2N −2}\{N −1},
Q takes the form in (38) with a ∈ C, and
kŪ1∗ QV̄1 k∗ = |a|(N − R).

(66)

Let us define ∆P = P̃ − P = Ũ1 Ṽ1∗ − U1 V1∗ . Then it follows from Lemma 4 and (56) that
|Tr(V1 U1∗ Q)| = | < Q, U1 V1∗ > |
≤ | < Q, P̃ > | + | < Q, ∆P > |
= |Tr(Ṽ1 Ũ1∗ Q)| + | < Q, ∆P > |
≤ |Tr(Ṽ1 Ũ1∗ Q)| + (kQk2F kk∆P k2F )1/2
√
≤ |Tr(Ṽ1 Ũ1∗ Q)| + |a| N k∆P kF
√
4 N
∗
kEkF
≤ |Tr(Ṽ1 Ũ1 Q)| + |a|
σ̃R
√
4 N
· N (|ccl | + |crm |)
≤ |Tr(Ṽ1 Ũ1∗ Q)| + |a|
N dmin
√
|ccl | + |crm |
≤ |Tr(Ṽ1 Ũ1∗ Q)| + 4|a| N ·
.
dmin

(67)

Thus if
√
|ccl | + |crm |
|Tr(Ṽ1 Ũ1∗ Q)| + 4|a| N ·
< |a|(N − R),
dmin

(68)



√
|Tr(Ṽ1 Ũ1∗ Q)| < |a| N − R − 4 N · drel ,

(69)

namely,

rm |
, then solving (61) will correctly recover x.
where drel is defined as |ccld|+|c
min
The proof of Theorem 2 leads to the concentration inequality (45):


t2 /2
P |Tr(Ṽ Ũ ∗ Q)| ≥ |a|t ≤ 3e− R+t/3 , ∀ t > 0.

√
Taking t = N − R − 4 N drel , we have
√
t2 /2
(N − R − 4 N drel )2 /2
√
=
R + t/3
R + (N − R − 4 N drel )/3

√
√
3 N 2 + R2 + 16N d2rel − 2N R − 8N N drel + 8R N drel
√
= ·
.
2
3R + N − R − 4 N drel

To have successful signal recovery with high probability, we let
√
√
3 N 2 + R2 + 16N d2rel − 2N R − 8N N drel + 8R N drel
√
·
= c log(N ),
2
3R + N − R − 4 N drel
16

(70)

(71)

where c > 0 is a constant. So we have
R2 + sR + r = 0,

(72)

where

√
√
√
s = 8 N drel − 2N − 2c log(N ), r = 16N d2rel − 8 N N drel − cN log(N ) + 4c N drel log(N ). (73)

Solving this leads to
q
√
√
(2N − 8 N drel + 2c log(N )) + 12cN log(N ) − 48c N drel log(N ) + 4c2 log2 (N )
R=
. (74)
2
Since we can freely choose the coefficient crm , we choose crm such that |crm | = cmin =
min{|c1 |, |c2 |, ..., |cR−1 |}. Under such a choice for |crm |, dmin = |crm | = cmin , leading to drel =
|ccl |+|crm |
min
= |cclc|+c
. This concludes the proof of Theorem 3.
dmin
min

5

Separation is always necessary for the success of atomic
norm minimization

In the previous sections, we have shown that the Hankel matrix recovery can recover the superposition of complex exponentials, even though the frequencies of the complex exponentials can be
arbitrarily close. In this section, we show that, broadly, the atomic norm minimization must obey a
non-trivial resolution limit. This is very different from the behavior of Hankel matrix recovery. Our
results in this section also greatly generalize the the necessity of resolution limit results in [26], to
general continuously-parametered dictionary, beyond the dictionary of frequency atoms. Moreover,
our analysis is very different from the derivations in [26], which used the Markov-Bernstein type
inequalities for finite-degree polynomials.
Theorem 4. Let us consider a dictionary with its atoms parameterized by a continuous-valued
parameter τ ∈ C. We also assume that each atom a(τ ) belongs to CN , where N is a positive
integer. We assume that the set of all the atoms span a Q-dimensional subspace in CN .
Suppose the signal is the superposition of several atoms:
x=

R
X

ck a(τk ),

(75)

k=1

where the nonzero ck ∈ C for each k, and R is a positive integer representing the number of active
atoms.
Consider any active atoms a(τk1 ) and a(τk2 ). With the other (R − 2) active atoms and their
coefficients fixed (this includes the case R = 2, namely there are only two active atoms in total), if
the atomic norm minimization can always identify the two active atoms, and correctly recover their
coefficients for a(τk1 ) and a(τk2 ), then the two atoms a(τk1 ) and a(τk2 ) must be well separated such
that
σmin (A)
√
ka(τk1 ) − a(τk2 )k2 ≥ 2 max max
,
(76)
S≥Q A∈M S
S
where S is a positive integer, M S is the set of matrices with S columns and with each of these S
columns corresponding to an atom, and σmin (·) is the smallest singular value of a matrix.
17

Proof. Define the sign of a coefficient ck as
sign(ck ) =

ck
.
|ck |

(77)

Then according to [3] and [26], a necessary condition for the atomic norm to identify the two active
atoms, and correctly recover their coefficients is that, there exists a dual vector q ∈ CN such that
(
a(τk1 )∗ q = sign(ck1 ), a(τk2 )∗ q = sign(ck2 )
(78)
|a(τ )∗ q| ≤ 1, ∀τ ∈
/ {τk1 , τk2 }.
We pick ck1 and ck2 such that |sign(ck ) − sign(cj )| = 2. Then
ksign(ck ) − sign(cj )k = ka(τk1 )∗ q − a(τk2 )∗ qk2 ≤ kqk2 ka(τk1 ) − a(τk2 )k2 ,

(79)

Thus
kqk2 ≥

2
.
ka(τk1 ) − a(τk2 )k2

(80)

Now we take a group of S atoms, denoted by aselect,1 , ... , and aselect,S , and use them to form
the S columns of a matrix A. Then
σmin (A)kqk2 ≤ kA∗ qk2
v
u S
uX
|a∗
=t

select,j q|

≤

2

j=1

√

S,

where the last inequality comes form (78). It follows that
√
S
kqk2 ≤
.
σmin (A)
Define β as the maximal value of

σmin (A)
√
S

(81)

(82)

among all the choices for A and S, namely,
σmin (A)
√
.
S

(83)

ka(τk1 ) − a(τk2 )k2 ≥ 2β,

(84)

β = max max

S≥Q A∈M S

Combining (80) and (82), we have

proving this theorem.

18

6

Orthonormal Atomic Norm Minimization: Hankel matrix
recovery can be immune from atom separation requirements

Our results in the previous sections naturally raise the following question: why can Hankel matrix
recovery work without requiring separations between the underlying atoms while it is necessary
for the atomic norm minimization to require separations between the underlying atoms? In this
section, we introduce the concept of orthonormal atomic norm and its minimization, which explains
the success of Hankel matrix recovery in recovering the superposition of complex exponentials
regardless of the separations between frequency atoms.
Let us consider a vector w ∈ CN , where N is a positive integer. We denote the set of atoms
by AT OMSET , and assume that each atom a(τ ) (parameterized by τ ) belongs to CN . Then the
atomic norm of kwkAT OMIC is given by [3, 27]
( s
)
s
X
X
kwkAT OMIC = inf
|ck | : w =
ck a(τk ) .
(85)
s,τk ,ck

k=1

k=1

We say the atomic norm kxkAT OMIC is an orthonormal atomic norm if, for every x,
kwkAT OMIC =

s
X

|ck |,

(86)

k=1

Ps
where w = k=1 ck a(τk ), ka(τk )k2 = 1 for every k, and a(τk )’s are mutually orthogonal to each
other.
In the Hankel matrix recovery, the atom set AT OMSET is composed of all the rank-1 matrices
in the form uv ∗ , where u and v are unit-norm vectors in CN . Let us assume x ∈ C2N −1 . We can
see the nuclear norm of a Hankel matrix is an orthonormal atomic norm of H(x):
kH(x)k∗ =

R
X

|ck |,

(87)

k=1

Ps
where H(x) = k=1 ck uk vk∗ , H(x) = U ΣV ∗ is the singular value decomposition of H(x), uk is
the k-th column of U , and vk is the k-th column of V . This is because the matrices uk vk∗ ’s are
orthogonal to each other and each of these rank-1 matrices has unit energy.
Let us now further assume that x ∈ C2N −1 is the superposition of R complex exponentials
with R ≤ N , as defined in (3). Then H(x) is a rank-R matrix, and can be written as H(x) =
PR
∗
∗
is the singular value decomposition of H(x), uk is the k-th
k=1 ck uk vk , where H(x) = U ΣV
column of U , and vk is the k-th column of V . Even though the original R frequency atoms a(τk )’s
for x can be arbitrarily close, we can always write H(x) as a superposition of R orthonormal
atoms uk vk∗ ’s from the singular value decomposition of H(x). Because the original R frequency
atoms a(τk )’s for x can be arbitrarily close, they can violate the necessary separation condition
set forth in (76). However, for H(x), its composing atoms can be R orthonormal atoms uk vk∗ ’s
from the singular value decomposition of H(x). These atoms uk vk∗ ’s are of unit energy, and are
orthogonal to each other. Thus these atoms are well separated and have the opportunity of not
violating the necessary separation condition set forth in (76). This explains why the Hankel matrix
recovery approach can break free from the separation condition which is required for traditional
atomic norm minimizations.
19

7

A matrix-theoretic inequality of nuclear norms and its
proof from the theory of compressed sensing

In this section, we present a new matrix-theoretic inequality of nuclear norms, and give a proof
of it from the theory of compressed sensing (using nuclear norm minimization). To the best of
our knowledge, we have not seen the statement of this inequality of nuclear norms, or its proof
elsewhere in the literature.
Theorem 5. Let A ∈ Cm×n , and t = min(m, n). Let σ1 , σ2 , ..., and σt be the singular values of
A arranged in descending order, namely
σ1 ≥ σ2 ≥ · · · ≥ σt .
Let k be any integer such that
σ1 + · · · + σk < σk+1 + · · · + σt .
Then for any orthogonal projector P onto k-dimensional subspaces in Cm , and any orthogonal
projector Q onto k-dimensional subspaces in Cn , we have
kP AQ∗ k∗ ≤ k(I − P )A(I − Q)∗ k∗ .

(88)

kA1:k,1:k k∗ ≤ kA(k+1):m,(k+1):n k∗ ,

(89)

In particular,

where A1:k,1:k is the submatrix of A with row indices between 1 and k and column indices between
1 and k, and A(k+1):m,(k+1):n is the submatrix of A with row indices between k + 1 and m and
column indices between k + 1 and n.
Proof. We first consider the case where all the elements of A are real numbers. Without loss of
generality, we consider


Ik×k
0k×(m−k)
P =
,
(90)
0(m−k)×k 0(m−k)×(m−k)
and

Q=



Ik×k

0k×(n−k)

0(n−k)×k

0(n−k)×(n−k)

.

(91)

Then


A1,1
 ..

P AQ∗ =  .
 Ak,1

···
..
.

A1,k
..
.

0
..
.

···
0

Ak,k

0

20

···
..
.
···
0


0
.. 
. 
 ,
0 

(92)

and

 0

(I − P )A(I − Q)∗ = A − P A − AQ∗ + P AQ∗ =  .
 ..
0

0
···
..
.

0
..
.

···

0



Ak+1,k+1
..
.

0
···
..
.

Ak+1,n
..
.

Am,k+1

···

Am,n



 .

(93)

Thus
kP AQ∗ k∗ = kA1:k,1:k k∗ , k(I − P )A(I − Q)∗ k∗ = kAk+1:m,k+1:n k∗ .

(94)

To prove this theorem, we first show that if σ1 + · · · + σk < σk+1 + · · · + σt , for any matrix
X ∈ Cm×n with rank no more than k, for any positive number l > 0, we have
kX + lAk∗ > kXk∗

(95)

The proof of (95) follows similar arguments as in [21].
kX + lAk∗
≥

t
X

(96)

|σi (X) − σi (lA)|

(97)

i=1

≥

k
X

(σi (X) − σi (lA)) +

i=1

≥

k
X

k
X

|σi (X) − σi (lA)|

(98)

i=k+1

σi (X) + (

i=1

>

t
X

t
X

σi (lA) −

k
X

σi (lA))

(99)

i=1

i=k+1

σi (X) = kXk∗ ,

(100)

i=1

where, for the first inequality, we used the following lemma, which instead follows from Lemma 6.
Pt
Lemma 5. Let G and H be two matrices of the same dimension. Then i=1 |σi (G) − σi (H)| ≤
kG − Hk∗ .
Lemma 6. ( [1, 14]) For arbitrary matrices X, Y , and Z = X − Y ∈ Cm×n . Let Let σ1 , σ2 ,
..., and σt (t = min{m, n}) be the singular values of A arranged in descending order, namely
σ1 ≥ σ2 ≥ · · · ≥ σt . Let si (X, Y ) be the distance between the i-th singular value of X and Y ,
namely,
si (X, Y ) = |σi (X) − σi (Y )|, i = 1, 2, · · · , k.

(101)

Let s[i] (X, Y ) be the i-th largest value of sequence s1 (X, Y ), s2 (X, Y ), · · · , st (X, Y ), then
k
X

s[i] (X, Y ) ≤ kZkk , ∀k = 1, 2, · · · , t,

i=1

where kZkk is defined as

Pk

i=1

σi (Z).
21

(102)

We next show that if kA1:k,1:k k∗ > kA(k+1):m,(k+1):n k∗ , one can construct a matrix X with
rank at most k such that
kX + lAk∗ ≤ kXk∗
for a certain l > 0. We divide this construction into two cases: when A1:k,1:k has rank equal to k,
and when A1:k,1:k has rank smaller than k.
When A1:k,1:k has rank k, we denote its SVD as
A1:k,1:k = U1 ΣV1 ∗ .

Then the SVD of


A1:k,1:k 0
is given by
0
0





∗
A1:k,1:k 0
U1
V1
=
Σ
0
0
0
0

We now construct


X=−

U1
0

Let us denote



U1
0





V1
0



V2 =

∗

V1
0


U2 =

and



(103)

.

,

then the subdifferential of k · k∗ at X is given by
∂kXk∗ = {Z : Z = −U2 V2∗ + M , where kM k2 ≤ 1, M ∗ X = 0, XM ∗ = 0}.

(104)

For any Z ∈ ∂kXk∗ ,
hZ, Ai = −I1 + I2 ,

(105)

I1 = Tr(V2 U2∗ A), I2 = Tr(M ∗ A).

(106)

where

Let us partition the matrix A into four blocks:

A11
A21

A12
A22


,

(107)

where A11 ∈ Rk×k , A12 ∈ Rk×(n−k) , A21 ∈ R(m−k)×(n−k) , and A21 ∈ R(m−k)×(n−k) . Then we
have
∗

 

I1 = Tr(V2 U2 A) = Tr
 

V1 U1∗ 0
= Tr
0
0



V1
0



A11
A21



U1∗

A12
A22

0
 

= Tr(V1 U1∗ A11 ) = Tr(V1 U1∗ U1 ΣV1∗ ) =



k
X
i=1

22



A11
A21

A12
A22

 

σi (A11 ) = kA11 k∗ .

(108)

Since M ∗ X = 0, XM ∗ = 0, kM k2 ≤ 1 and X is a rank-k left top corner matrix, we must have


0
0
M=
,
0 M22
where M22 is of dimension (m − k) × (n − k), and kM22 k2 ≤ 1.
Then
I2 = Tr(M ∗ A)
 

0
0
= Tr
∗
0 M22

(109)


A11
A21

A12
A22

 
(110)

∗
= Tr (M22
A22 ) ≤ kA22 k∗ ,

(111)

where the last inequality is from the fact that the nuclear norm is the dual norm of the spectral
norm, and kM22 k2 ≤ 1.
Thus we have
hZ, Ai = −I1 + I2 ≤ −kA11 k∗ + kA22 k∗ < 0,

(112)

because we assume that kA1:k,1:k k∗ > kA(k+1):m,(k+1):n k∗ . Since hZ, Ai < 0 for every Z ∈ ∂kXk∗ ,
A is in the normal cone of the convex cone generated by ∂k · k∗ at the point X. By Theorem 23.7
in [23], we know that the normal cone of the convex cone generated by ∂k · k∗ at the point X is
the cone of descent directions for k · k∗ at the point of X. Thus A is in the descent cone of k · k∗
at the point X. This means that, when A11 has rank equal to k, there exists a positive number
l > 0, such that
kX + lAk∗ ≤ kXk∗ .
Let us suppose instead that A11 has rank b < k. We can write the SVD of A11 as





∗
Σ 0
U1 U3
A11 =
V1 V3
0 0
Then we construct


X=−

U1
0

U3
0





V1
0

V3
0

(113)

∗
.

By going through similar arguments as above (except for taking care of extra terms involving U3
and V3 ), one can obtain that hZ, Ai < 0 for every Z ∈ ∂kXk∗ .
In summary, no matter whether A11 has rank equal to k or smaller to k, there always exists
a positive number l > 0, such thatkX + lAk∗ ≤ kXk∗ . However, this contradicts (95), and we
conclude kA1:k,1:k k∗ ≤ kA(k+1):m,(k+1):n k∗ , when A has real-numbered elements.
We further consider the case when A is a complex-numbered matrix. We first derive the subdifferential of kXk∗ for any complex-numbered matrix m × n X. For any α ∈ Rm×n and any
β ∈ Rm×n , we define F : R2m×n 7→ R as
 
α
F
= k(α + ıβ)k∗ .
(114)
β


Re(X)
To find the subdifferential of kXk∗ , we need to derive ∂F
, for which we have the
Im(X)
following lemma, the proof of which is given in Appendix 10.3. (Note that in our earlier work [2]
23

and the 
corresponding
 preprint on arxiv.org, we have already shown one direction of 116, namely
Re(X)
H ⊆ ∂F
. Now we show the two sets are indeed equal. )
Im(X)
Lemma 7. Suppose a rank-R matrix X ∈ CM ×N admits a singular value decomposition X =
U ΣV ∗ , where Σ ∈ RR×R is a diagonal matrix, and U ∈ CM ×R and V ∈ CN ×R satisfy U ∗ U =
V ∗ V = I.
Define S ⊆ CM ×N as:

(115)
S = U V ∗ + W | U ∗ W = 0, W V = 0, kW k2 ≤ 1, W ∈ CM ×N ,
and define

F
Then we have
H≡

 
α
β

Re(X)
Im(X)


= kXk∗ .




Re(X)
α + ıβ ∈ S = ∂F
.
Im(X)

(116)

For a complex-numbered matrix A, we will similarly show that, if kA1:k,1:k k∗ > kA(k+1):m,(k+1):n k∗ ,
one can construct a matrix X with rank at most k such that
kX + lAk∗ ≤ kXk∗
for a certain l > 0. We divide this construction into two cases: when A1:k,1:k has rank equal to k,
and when A1:k,1:k has rank smaller than k.
When A1:k,1:k has rank k, we denote its SVD as
A1:k,1:k = U1 ΣV1 ∗ .

Then the SVD of

A1:k,1:k
0


0
0


is given by

A1:k,1:k
0

0
0

We now construct


=


X=−

We denote


U2 =

U1
0



U1
0



U1
0





V1
0



V1
0

Σ



(117)

∗
.


, and V2 =

∗

V1
0


,

then by Lemma 7, the subdifferential of k · k∗ at X is given by
∂kXk∗ = {Z : Z = −U2 V2∗ + M ], where kM k2 ≤ 1, M ∗ X = 0, XM ∗ = 0}.

(118)

For any Z ∈ ∂kXk∗ ,
hZ, Ai = −I1 + I2 ,
24

(119)

where
I1 = Re (Tr(V2 U2∗ A)) , I2 = Re (Tr(M ∗ A)) .
Similar to the real-numbered case, let us partition the matrix A into four blocks:


A11 A12
,
A21 A22
where A11 ∈ Ck×k , A12 ∈ Ck×(n−k) , A21
 

V1
∗
Tr(V2 U2 A) = Tr
0
 
V1 U1∗
= Tr
0

(120)

(121)

∈ C(m−k)×(n−k) , and A21 ∈ C(m−k)×(n−k) . We still have

 
 ∗

A11 A12
U1 0
A21 A22
 
 
0
A11 A12
0
A21 A22

= Tr(V1 U1∗ A11 ) = Tr(V1 U1∗ U1 ΣV1∗ ) =

k
X

σi (A11 ) = kA11 k∗ .

(122)

i=1

So
I1 = Re (Tr(V2 U2 ∗ A)) = kA11 k∗ .
Since M ∗ X = 0, XM ∗ = 0, kM k2 ≤ 1 and X is a rank-k left top corner matrix, we must
have


0
0
M=
,
0 M22
where M22 is of dimension (m − k) × (n − k), and kM22 k2 ≤ 1. Then we have
I2 = Re (Tr(M ∗ A))
  

0
0
= Re Tr
∗
0 M22

(123)


A11
A21

A12
A22

 
(124)

∗
= Re (Tr (M22
A22 )) ≤ kA22 k∗ ,

(125)

where the last inequality is because the nuclear norm is the dual norm of the spectral norm, and
kM22 k2 ≤ 1.
Thus we have
hZ, Ai = −I1 + I2 ≤ −kA11 k∗ + kA22 k∗ < 0,

(126)

because we assume that kA1:k,1:k k∗ > kA(k+1):m,(k+1):n k∗ . Since hZ, Ai < 0 for every Z ∈ ∂kXk∗ ,
A is in the descent cone of k · k∗ at the point X. This means that, when A11 has rank equal to k,
there exists a positive number l > 0, such that
kX + lAk∗ ≤ kXk∗ .
Let us suppose instead that A11 has rank b < k. We can write the SVD of A11 as

A11 =



U1

U3





Σ 0
0 0

25





V1

V3

∗

(127)

Then we construct


X=−

U1
0

U3
0





V1
0

V3
0

∗
.

By going through similar arguments as above (except for taking care of extra terms involving U3
and V3 ), one can obtain that hZ, Ai < 0 for every Z ∈ ∂kXk∗ .
In summary, no matter whether complex-numbered A11 has rank equal to k or smaller to k,
there always exists a positive number l > 0, such thatkX +lAk∗ ≤ kXk∗ . However, this contradicts
(95), and we conclude kA1:k,1:k k∗ ≤ kA(k+1):m,(k+1):n k∗ .

8

Numerical results

In this section, we perform numerical experiments to demonstrate the empirical performance of
Hankel matrix recovery, and show its robustness to the separations between atoms. We use superpositions of complex sinusoids as test signals. But we remark that Hankel matrix recovery can also
work for superpositions of complex exponentials. We consider the non-uniform sampling of entries
studied in [6,27], where we uniformly randomly observe M entries (without replacement) of x from
{0, 1, . . . , 2N − 2}. We also consider two signal (frequency) reconstruction algorithms: the Hankel
nuclear norm minimization and the atomic norm minimization.
We fix N = 64, i.e., the dimension of the ground truth signal x is 127. We conduct experiments
under different M and R for different approaches. For each approach with a fixed M and R,
we test 100 trials, where each trialPis performed as follows. We first generate the true signal
R
x = [x0 , x1 , . . . , x126 ]T with xt = k=1 ck eı2πfk t for t = 0, 1, . . . , 126, where fk are frequencies
drawn from the interval [0, 1] uniformly at random, and ck are complex coefficients satisfying the
model ck = (1 + 100.5mk )ei2πθk with mk and θk uniformly randomly drawn from the interval [0, 1].
2
−3
Let the reconstructed signal be represented by x̂. If kx̂−xk
, then we regard it as a successful
kxk2 ≤ 10
reconstruction. We also provide the simulation results under the Gaussian measurements of x as
in [2].
We plot in Figure 1 the rate of successful reconstruction with respect to different M and R
for different approaches. The black and white region indicate a 0% and 100% of successful reconstruction respectively, and a grey between 0% and 100%. From the figure, we see that the
atomic norm minimization still suffers from non-negligible failure probability even if the number of
measurements approach the full 127 samples. The reason is that, since the underlying frequencies
are randomly chosen, there is a sizable probability that some frequencies are close to each other.
When the frequencies are close to each other violating the atom separation condition, the atomic
norm minimization can still fail even if we observe the full 127 samples. By comparison, the Hankel
matrix recovery approach experiences a sharper phase transition, and is robust to the frequency
separations. We also see that under both the Gaussian projection and the non-uniform sampling
models, both the atomic norm minimization and the Hankel matrix recovery approach have similar
performance.
We further demonstrate the robustness of the Hankel matrix recovery approach to the separations between frequency atoms, as we vary the separations between frequencies. In our first set of
experiments, we take N = 64, |M| = M = 65 (≈ 51% sampling rate) and R = 8, and consider
noiseless measurements. Again we generate the magnitude of the coefficients as 1 + 100.5p where
p is uniformly randomly generated from [0, 1), and the realized magnitudes are 3.1800, 2.5894,

26

40

1

40

1

0.9

35

0.9

35

0.8

R: sparsity (rank of Hankel)

R: sparsity (rank of Hankel)

0.8
30
0.7
25

0.6

20

0.5
0.4

15

0.3
10

30
0.7
25

0.6

20

0.5
0.4

15

0.3
10

0.2
5

0

20

30

40

50

60

70

80

90

100

110

120

0.2

0.1

5

0

0
20

M: number of measurements

0.1

30

40

50

60

70

80

90

100

110

(a) Hankel nuclear norm minimization with random
Gaussian projections

40

(b) Hankel nuclear norm minimization with nonuniform sampling of entries

1

40

0.9

35

1
0.9

35

0.8

0.8

25

20

0.7

30

0.6

25

R: sparsity

R: sparsity

30

0.5
0.4

15

0.7
0.6

20

0.5
0.4

15

0.3
10

5

40

50

60

70

80

90

100

M: number of measurements

110

120

0.2

5

0.1

30

0.3

10

0.2

0
20

0

120

M: number of measurements

0

0
20

0.1
30

40

50

60

70

80

90

100 110 120

0

M: number of measurements

(c) Atomic norm minimization with random Gaussian projections

(d) Atomic norm minimization with non-uniform
sampling of entries

Figure 1: Performance comparisons between atomic norm minimization and Hankel matrix recovery

27

3.5

× 109

3

Imaging function J(f)

2.5

2

1.5

1

0.5

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 2: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.03
2.1941, 2.9080, 3.9831, 4.0175, 4.1259, 3.6182 in this experiment. The corresponding phases of the
coefficients are randomly generated as 2πs, where s is uniformly randomly generated from [0, 1).
In this experiment, the realized phases are 4.1097, 5.4612, 5.4272, 4.7873, 1.0384, 0.4994, 3.1975,
and 0.5846. The first R − 1 = 7 frequencies of exponentials are generated uniformly randomly over
[0, 1), and then the last frequency is added in the proximity of the 3rd frequency. In our 6 experiments, the 8th frequency is chosen such that the frequency separation between the 8th frequency
and the 3rd frequency is respectively 0.03, 0.01, 0.003, 0.001, 0.0003, and 0.0001. Specifically, in our
6 experiments, the locations of the 8 frequencies are respectively {0.3923, 0.9988, 0.3437, 0.9086,
0.6977, 0.0298, 0.4813, 0.3743}, {0.3923, 0.9988, 0.3437, 0.9086, 0.6977, 0.0298, 0.4813, 0.3537},
{0.3923, 0.9988, 0.3437, 0.9086, 0.6977, 0.0298, 0.4813, 0.3467}, {0.3923, 0.9988, 0.3437, 0.9086,
0.6977, 0.0298, 0.4813, 0.3447}, {0.3923, 0.9988, 0.3437, 0.9086, 0.6977, 0.0298, 0.4813, 0.3440}, and
{0.3923, 0.9988, 0.3437, 0.9086, 0.6977, 0.0298, 0.4813, 0.3438}. Hankel matrix recovery approach
2
−9
gives relative error kx̂−xk
, 5.3741 ∗ 10−9 , 3.078 ∗ 10−9 , 2.3399 ∗ 10−9 , 9.8142 ∗ 10−9 ,
kxk2 = 3.899 ∗ 10
−9
and 8.1374 ∗ 10 , respectively. With the recovered data x̂, we use the MUSIC algorithm to identify the frequencies. The recovered frequencies for these 6 cases are respectively: {0.0298, 0.3437,
0.3737, 0.3923, 0.4813, 0.6977, 0.9086, 0.9988}, {0.0298, 0.3437, 0.3537, 0.3923, 0.4813, 0.6977,
0.9086, 0.9988}, {0.0298, 0.3437, 0.3467, 0.3923, 0.4813, 0.6977, 0.9086, 0.9988}, {0.0298, 0.3437,
0.3447, 0.3923, 0.4813, 0.6977, 0.9086, 0.9988}, {0.0298, 0.3437, 0.3440, 0.3923, 0.4813, 0.6977,
0.9086, 0.9988}, and {0.0298, 0.3437, 0.3438, 0.3923, 0.4813, 0.6977, 0.9086, 0.9988}. We illustrate
these 6 cases in Figure 2, 3 , 4 , 5 , 6 , 7, respectively, where the peaks of the imaging function J(f )
are the locations of the recovered frequencies. We can see the Hankel matrix recovery successfully
recovers the missing data and correctly locate the frequencies.
We further demonstrate the performance of Hankel matrix recovery under noisy measurements.
Again, we consider N = 64, |M| = 65 and R = 8. The magnitude of the coefficients is obtained by

28

2.5

× 109

Imaging function J(f)

2

1.5

1

0.5

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 3: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.01

× 109

Imaging function J(f)

3.5

3

Imaging function J(f)

2.5

× 108

6
4
2
0
0.25

0.3

0.35

0.4

Frequency f

2

1.5

1

0.5

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 4: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.003

29

× 109

× 107

Imaging function J(f)

4.5
4

Imaging function J(f)

3.5
3

4

2

0
0.34

2.5

0.345

0.35

Frequency f

2
1.5
1
0.5
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

16

Imaging function J(f)

Figure 5: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.001

× 108

14

Imaging function J(f)

12

8
6
4
2
0

10

× 106

0.343 0.345 0.347

Frequency f

8
6
4
2
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 6: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.0003

30

× 109

Imaging function J(f)

2.5

Imaging function J(f)

2

× 106

2
1
0
0.3436

1.5

0.344

Frequency f

1

0.5

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 7: Noiseless measurements, Hankel matrix recovery: frequency separation distF = 0.0001
1 + 100.5p where p is uniformly randomly generated from [0, 1). The realized magnitudes are 3.9891,
3.6159, 3.7868, 3.9261, 2.1606, 2.4933, 3.2741, and 3.0539 respectively in our experiment. The phase
of the coefficients are obtained by 2πs where s is uniformly randomly generated from [0, 1). In this
example, the realized phases are 5.2378, 1.3855, 2.0064, 1.3784, 0.1762, 4.2739, 1.7979, and 0.1935
respectively. The first R − 1 = 7 frequencies of exponentials are generated uniformly randomly
from [0, 1), and then the last frequency is added with frequency separation 5 ∗ 10−3 from the third
frequency. In this example, the ground truth frequencies are 0.8822, 0.0018, 0.6802, 0.2825, 0.8214,
0.2941, 0.3901, and 0.6852.
We generate the noise vector v ∈ C2N −1 as s1 + ıs2 where each element of s1 ∈ R2N −1 and
s2 ∈ R2N −1 is independently generated from the zero mean standard Gaussian distribution. And
we further normalize v such that kvk2 = 0.1. In this noisy case, we solve the problem
min kH(x)k∗
x

subjectto A(x) = b,

(128)

2
−3
to get the recovered signal x̂, and a relative error kx̂−xk
is achieved, and the location
kxk2 = 1.2 ∗ 10
of recovered frequencies are 0.0018, 0.2825, 0.2941, 0.3901, 0.6802, 0.6852, 0.8214, and 0.8822. We
illustrate the locations of the recovered frequencies in Figure 8. We can see that the Hankel matrix
recovery can also provide robust data and frequency recovery under noisy measurements.

9

Conclusions and future works

In this paper, we have shown, theoretically and numerically, that the Hankel matrix recovery can be
robust to frequency separations in super-resolving the superposition of complex exponentials. By
31

5000
4500

Imaging function J(f)

4000
3500
3000
2500
2000
1500
1000
500
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Frequency f

Figure 8: Noisy measurements, Hankel matrix recovery
comparison, the TV minimization and atomic norm minimization require the underlying frequencies
to be well-separated to super-resolve the superposition of complex exponentials even when the
measurements are noiseless. In particular, we show that Hankel matrix recovery approach can
super-resolve the R frequencies, regardless of how close the frequencies are to each other, from
compressed non-uniform measurements. We presented a new concept of orthonormal atomic norm
minimization (OANM), and showed that this concept helps us understand the success of Hankel
matrix recovery in separation-free super-resolution. We further show that, in traditional atomic
norm minimization, the underlying parameters must be well separated so that the signal can be
successfully recovered if the atoms are changing continuously with respect to the continuouslyvalued parameters; however, for OANM, it is possible the atomic norm minimization are successful
even though the original atoms can be arbitrarily close. As a byproduct of this research, we also
provide one matrix-theoretic inequality of nuclear norm, and give its proof from the theory of
compressed sensing. In future works, it would be interesting to extend the results in this paper
to super-resolving the superposition of complex exponentials with higher dimensional frequency
parameters [6, 7, 31]

10
10.1

Appendix
Proof of Lemma 2

Any solution to the nuclear norm minimization must be X0 + Q, where Q is from the null space
of A. Suppose that the singular value decomposition of X0 is given by
X0 = U ΛV ∗

32

where U ∈ CM ×R , Λ ∈ CR×R , and V ∈ CN ×R .
From Lemma 7, we know the subdifferential of k · k∗ at the point X0 is given by
{Z |Z = U V ∗ + Ū M V̄ ∗ , where kM k2 ≤ 1, U ∗ Ū = 0, Ū ∗ Ū = I, V ∗ V̄ = 0, V̄ ∗ V̄ = I}.
Then from the property of subdifferential of a convex function, for any Z = U V + Ū M V̄ ∗ (with
kM k2 ≤ 1) from the subdifferetial of k · k∗ at the point X0 , we have
kX0 + Qk∗

(129)

≥ kX0 k∗ + hZ, Qi

(130)
∗

∗

∗

= kX0 k∗ + Re (Tr (U QV )) + Re Tr Ū QV̄ M

≥ kX0 k∗ − |Tr (U ∗ QV ) | + Re Tr Ū ∗ QV̄ M ∗ .



(131)
(132)

Because we can take any M with kM k2 ≤ 1, when Q 6= 0, we have
kX0 + Qk∗ ≥ kX0 k∗ − |Tr (U ∗ QV ) | + kŪ ∗ QV̄ k∗
> kX0 k∗ ,

(133)
(134)

where the last step is because the dual norm of the spectral norm is the nuclear norm (which
also holds for complex-numbered matrices). Thus X0 is the unique solution to the nuclear norm
minimization.

10.2

Strict inequality is not always necessary in the null space condition
for successful recovery via nuclear norm minimization

In this subsection, we show that the null space condition for Lemma 2 is not a necessary condition
for the success of nuclear norm minimization, which is in contrast to the null space condition in
Lemma 13 of [21]. Specifically, we show the following claim:
Claim: Let X0 be any M ×N matrix of rank R in CM ×N , and we observe it through a linear mapping
A(X0 ) = b. We also assume that X0 has a singular value decomposition (SVD) X0 = U ΣV ∗ ,
where U ∈ CM ×R , V ∈ CN ×R , and Σ ∈ CR×R is a diagonal matrix. Consider the nuclear norm
minimization (135)
min kXk∗ ,
subject to A(X) = A(X0 ),
(135)
X

Then for the nuclear norm minimization to correctly and uniquely recovers X0 , it is not always
necessary that “for every nonzero element Q ∈ N (A),
−|Tr(U ∗ QV )| + kŪ ∗ QV̄ k∗ > 0,

(136)

where Ū and V̄ are such that [U Ū ] and [V V̄ ] are unitary. ”
For simple presentation, we first use an example in the field of real numbers (where every element
in the null space is a real-numbered matrix ) to illustrate the calculations, and prove this claim.
Building on this real-numbered example, we further give an example in the field of complex numbers
to prove this claim.
Suppose




−1 0
1 1
X0 =
, Q=
.
(137)
0 0
1 1
33

We also assume that the linear mapping A is such that Q is the only nonzero element in the null
space of A. Then the solution to (135) must be of the form A + tQ, where t is any real number.

U=

1
0




,V =

−1
0




, Ū =

0
1




, V̄ =

0
1


.

(138)

One can check that, for this example,
−|Tr(U ∗ QV )| + kŪ ∗ QV̄ k∗ = 0.

(139)

||X0 + tQ||∗ > 1, ∀t 6= 0,

(140)

However, we will show that

implying that X0 is the unique solution to (135).
In fact, we calculate

(−1 + t)2 + t2
T
B = (X0 + tQ)(X0 + tQ) =
(−1 + t)t + t2

(−1 + t)t + t2
2t2


,

(141)

and then the singular values of X0 +tQ are the square roots of the eigenvalues of B. The eigenvalues
of B can be obtained by solving for λ using
det(B − λI) = 0.

(142)

This results in
λ=

a(t) + b(t) ±

p
(a(t) − b(t))2 + 4c(t)
,
2

(143)

where
a(t) = (−1 + t)2 + t2 , b(t) = 2t2 , c(t) = ((−1 + t)t + t2 )2 .

(144)

Thus the two eigenvalues of B are
4t2 − 2t + 1 +

√

16t4 − 16t3 + 8t2 − 4t + 1
,
2
√
4t2 − 2t + 1 − 16t4 − 16t3 + 8t2 − 4t + 1
,
λ2 =
2
λ1 =

and the singular values of X0 + tQ are
s
√
p
4t2 − 2t + 1 + 16t4 − 16t3 + 8t2 − 4t + 1
σ1 = λ 1 =
,
2
s
√
p
4t2 − 2t + 1 − 16t4 − 16t3 + 8t2 − 4t + 1
σ2 = λ 2 =
.
2

34

(145)
(146)

(147)

(148)

After some algebra, we get
(√
kX0 + tQk∗ = σ1 + σ2 =

4t2 + 1, t ≥ 0,
1 − 2t, t < 0.

(149)

This means kX0 + tQk∗ is always greater than 1 for t 6= 0, showing X0 is the unique solution to
the nuclear norm minimization. But −|Tr(U ∗ QV )| + kŪ ∗ QV̄ k∗ ≯ 0.
Now we give an example in the field of complex examples, where the null space of A contains
complex-numbered matrices. Suppose that we have the same matrices X0 and Q. Then the solution
to (135) must be of the form A + tQ, where t is any complex number. Without loss of generality,
let us take t = −ae−ıθ , where a ≥ 0 is a nonnegative real number, and θ is any real number between
0 and 2π. We further denote B = (X0 + tQ)(X0 + tQ)∗ . Then by calculating the eigenvalues of
B, we obtain that
p
(150)
kX0 + tQk∗ = σ1 + σ2 = 4a2 + 2a(1 + cos(θ)) + 1
s 
2
1 + cos(θ)
(1 + cos(θ))2
(151)
+1−
= 4 a+
4
4
where t = −ae−ıθ with a ≥ 0 and θ ∈ [0, 2π). So kX0 + tQk∗ > 1, if a 6= 0 (namely t 6= 0), implying that the nuclear norm minimization can uniquely recovers X0 even though −|Tr(U ∗ QV )| +
kŪ ∗ QV̄ k∗ ≯ 0.

10.3

Proof of Lemma 7

Proof. We write
U = Θ1 + ıΘ2 , V = Ξ1 + ıΞ2 ,
where Θ1 ∈ R

M ×R

M ×R

N ×R

(152)

N ×R

, Θ2 ∈ R
, Ξ1 ∈ R
, and Ξ2 ∈ R
. Then, by direct calculation,




Θ1 −Θ2
Ξ1 −Ξ2
2M ×2R
Θ≡
∈R
,
Ξ≡
∈ R2N ×2R
(153)
Θ2 Θ1
Ξ2 Ξ1


Re(X) −Im(X)
satisfy ΘT Θ = ΞT Ξ = I. Moreover, if we define Ω̂ =
, then
Im(X) Re(X)


Σ
Ω̂ = Θ
ΞT
(154)
Σ
is a singular value decomposition of the real-numbered matrix Ω̂, and the singular values Ω̂ are
those of X, each repeated twice. Therefore,


1
Re(X)
F
= kΣk∗ = kΩ̂k∗ .
(155)
Im(X)
2
Define a linear operator E : R2M ×N 7→ R2M ×2N by
  

α
α −β
E
=
, with α, β ∈ RM ×N .
β
β α
35

By (155) and the definition of Ω̂, we obtain




1
Re(X)
Re(X)
E
F
=
Im(X)
Im(X)
2
∗
.


Re(X)
From convex analysis and Ω̂ = E
, the subdifferential of F is given by
Im(X)


1
Re(X)
∂F
= E ∗ ∂ Ω̂ ,
Im(X)
2
∗

(156)

where E ∗ is the adjoint of the linear operator E.

∆11
On the one hand, the adjoint E is given by, for any ∆ =
∆21
block in RM ×N ,


∆11 + ∆22
∗
E ∆=
.
∆21 − ∆12
∗


∆12
∈ R2M ×2N with each
∆22
(157)

On the other hand, since (154) provides a singular value decomposition of Ω̂,

∂kΩ̂k∗ = ΘΞT + ∆ | ΘT ∆ = 0, ∆Ξ = 0, k∆k2 ≤ 1 .
(158)


Re(X)
Combining (156), (157), (158), and (153) yields the subdifferential of F(·) at
:
Im(X)


Re(X)
∂F
(159)
Im(X)






22
Θ1 ΞT1 + Θ2 ΞT2 + ∆11 +∆
∆11 ∆12
T
2

=
∆=
, Θ ∆ = 0, ∆Ξ = 0, k∆k2 ≤ 1 .
12
∆21 ∆22
Θ2 ΞT1 − Θ1 ΞT2 + ∆21 −∆
2
(160)
We are now ready to show (116).
 



α
Re(X)
α + ıβ ∈ S must also be in ∂F
,
β
Im(X)
∗
namely (159). In fact, for
 any W = ∆1 + ı∆2 satisfying U W = 0, W V = 0 and kW k2 ≤ 1, we
∆1 −∆2
choose ∆ =
. This choice of ∆ satisfies the constraints on ∆ in (159). Furthermore,
∆2 ∆1
U V ∗ + W = (Θ1 ΞT1 + Θ2 ΞT2 + ∆1 ) + ı(Θ2 ΞT1 − Θ1 ΞT2 + ∆2 ). Thus


Re(X)
H ⊆ ∂F
.
(161)
Im(X)
Firstly, we show that any element in H ≡

Secondly, we show that

∂F


Re(X)
⊆ H.
Im(X)

(162)



∆11 ∆12
We let ∆ =
be any matrix satisfying the the constraints on ∆ in (159). We claim
∆21 ∆22
. ∆11 +∆22
12
+ ı ∆21 −∆
satisfies U ∗ W = 0, W V = 0 and kW k2 ≤ 1.
that W =
2
2
36


∆11
In fact, from Θ
∆21
T


∆12
= 0, we have
∆22
+ ΘT1 ∆11 + ΘT2 ∆21 = 0
−

ΘT1 ∆12
ΘT2 ∆11

−

ΘT2 ∆12

+

(163)

=0

(164)

+

ΘT2 ∆22
ΘT1 ∆21

=0

(165)

+

ΘT1 ∆22

=0

(166)

+

Thus we obtain
∆21 − ∆12
∆11 + ∆22
+ı
)
2
2 

T ∆11 + ∆22
T ∆21 − ∆12
T ∆21 − ∆12
T ∆11 + ∆22
= Θ1
+ Θ2
+ ı Θ1
− Θ2
2
2
2
2

U ∗ W = (ΘT1 − ıΘT2 )(

= 0 + ı0 = 0,

(167)
(168)
(169)

where the last two equalities come from adding up (163) and (166), and subtracting (164) from
(165), respectively.

∆11 ∆12
Similarly from
Ξ = 0, we can verify that
∆21 ∆22
W V = 0.
Moreover,
 ∆11 +∆22
kW k2 =

2
∆21 −∆12
2


1 ∆11
=
2 ∆21

1 ∆11
≤
2 ∆21
1 1
≤ +
2 2
= 1,

∆12 −∆21
2
∆11 +∆22
2



 2


1 ∆22 −∆21
∆12
+
∆22
2 −∆12 ∆11
2



1
∆12
∆22 −∆21
+
∆22 2 2 −∆12 ∆11

2



∆22 −∆21
where we used the Jensen’s inequality for the spectral norm, and the fact that 1 ≥
−∆12 ∆11


∆11 ∆12
(which comes from using the variational characterization of spectral norm). This
∆21 ∆22 2
concludes the proof of (162).
Combining (161) and (162), we arrive at (116).

References
[1] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag
New York, 1997.
37

=
2

[2] J. Cai, X. Qu, W. Xu, and G. Ye. Robust recovery of complex exponential signals from random
Gaussian projections via low rank Hankel matrix reconstruction. Applied and Computational
Harmonic Analysis, 41(2):470–490, September 2016.
[3] E. Candès and C. Fernandez-Granda. Towards a mathematical theory of super-resolution.
Comm. Pure Appl. Math, 67(6):906–956, June 2014.
[4] E. J. Candes and B. Recht. Exact matrix completion via convex optimization. Found Comput
Math, 9:717–772, 2009.
[5] E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information
Theory, 52(2):489–509, February 2006.
[6] Y. Chen and Y. Chi. Robust spectral compressed sensing via structured matrix completion.
IEEE Transactions on Information Theory, 60(10):6576–6601, October 2014.
[7] Y. Chi and Y. Chen. Compressive two-dimensional harmonic retrieval via atomic norm minimization. IEEE Transactions on Signal Processing, 63(4):1030–1042, Feb 2015.
[8] Y. Chi, L. L. Scharf, A. Pezeshki, and A. R. Calderbank. Sensitivity to basis mismatch in
compressed sensing. IEEE Transactions on Signal Processing, 59(5):2182–2195, May 2011.
[9] L. Dai and K. Pelckmans. On the nuclear norm heuristic for a Hankel matrix completion
problem. Automatica, 51(Supplement C):268–272, January 2015.
[10] B. G. R. de Prony. Essai experimental et analytique: Sur les lois de la dilatabilite de fluides
elastique et sur celles de la force expansive de la vapeur de l’alkool, a differentes temperatures.
J. de l’Ecole Polytechnique, 1795.
[11] D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–
1306, April 2006.
[12] M. Fazel, H. Hindi, and S. P. Boyd. Log-det heuristic for matrix rank minimization with
applications to Hankel and Euclidean distance matrices. In Proceedings of the 2003 American
Control Conference, 2003., volume 3, pages 2156–2162 vol.3, June 2003.
[13] M. Fazel, T. Pong, D. Sun, and P. Tseng. Hankel matrix rank minimization with applications
to system identification and realization. SIAM. J. Matrix Anal. and Appl., 34(3):946–977,
January 2013.
[14] R. Horn and C. Johnson. Matrix analysis. Cambridge university press, 2012.
[15] Y. Hua and T. K. Sarkar. Matrix pencil method for estimating parameters of exponentially
damped/undamped sinusoids in noise. IEEE Transactions on Acoustics, Speech, and Signal
Processing, 38(5):814–824, May 1990.
[16] W. Li and W. Sun. New perturbation bounds for unitary polar factors. SIAM. J. Matrix Anal.
and Appl., 25(2):362–372, January 2003.
[17] W. Liao and A. Fannjiang. MUSIC for single-snapshot spectral estimation: Stability and
super-resolution. Applied and Computational Harmonic Analysis, 40(1):33–67, January 2016.
38

[18] M. Lustig, D. Donoho, and J. M. Pauly. Sparse MRI: The application of compressed sensing
for rapid MR imaging. Magn. Reson. Med., 58(6):1182–1195, December 2007.
[19] I. Markovsky. Structured low-rank approximation and its applications. Automatica, 44(4):891–
909, April 2008.
[20] K. V. Mishra, M. Cho, A. Kruger, and W. Xu. Spectral super-resolution with prior knowledge.
IEEE Transactions on Signal Processing, 63(20):5342–5357, Oct 2015.
[21] S. Oymak and B. Hassibi. New null space results and recovery thresholds for matrix rank
minimization. November 2010. arXiv: 1011.6326.
[22] B. Recht, W. Xu, and B. Hassibi. Null space conditions and thresholds for rank minimization.
Math. Program., 127(1):175–202, March 2011.
[23] R. Rockafellar. Convex analysis. Princeton university press, 2015.
[24] R. Roy and T. Kailath. ESPRIT-estimation of signal parameters via rotational invariance
techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):984–995,
July 1989.
[25] G. Schiebinger, E. Robeva, and B. Recht. Superresolution without separation. In 2015 IEEE
6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing
(CAMSAP), pages 45–48, December 2015.
[26] G. Tang. Resolution limits for atomic decompositions via markov-bernstein type inequalities.
In 2015 International Conference on Sampling Theory and Applications (SampTA), pages 548–
552, May 2015.
[27] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht. Compressed sensing off the grid. IEEE
Transactions on Information Theory, 59(11):7465–7490, November 2013.
[28] J. Tropp. An Introduction to matrix concentration inequalities. MAL, 8(1-2):1–230, May 2015.
[29] J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G. Baraniuk. Beyond Nyquist:
Efficient sampling of sparse bandlimited signals. IEEE Transactions on Information Theory,
56(1):520–544, January 2010.
[30] K. Usevich and P. Comon. Hankel low-rank matrix completion: Performance of the nuclear
norm relaxation. IEEE Journal of Selected Topics in Signal Processing, 10(4):637–646, June
2016.
[31] W. Xu, J. F. Cai, K. V. Mishra, M. Cho, and A. Kruger. Precise semidefinite programming
formulation of atomic norm minimization for recovering d-dimensional off-the-grid frequencies.
In 2014 Information Theory and Applications Workshop (ITA), pages 1–4, February 2014.

39

