1

Two-Dimensional Super-Resolution via Convex
Relaxation

arXiv:1711.08239v1 [] 22 Nov 2017

Iman Valiulahi, Sajad Daei, Farzan Haddadi and Farzad Parvaresh

Abstract—In this paper, we address the problem of recovering
point sources from two dimensional low-pass measurements,
which is known as super-resolution problem. This is the fundamental concern of many applications such as electronic imaging,
optics, microscopy, and line spectral estimation. We assume that
the point sources are located in the square [0, 1]2 with unknown
locations and complex amplitudes. The only available information
is low-pass Fourier measurements band-limited to integer square
[−fc , fc ]2 . The signal is estimated by minimizing Total Variation
(TV) norm, which leads to a convex optimization problem. It is
shown that if the sources are separated by at least 1.68/fc , there
exist a dual certificate that is sufficient for exact recovery.
Index Terms—Super-Resolution, continuous dictionary, convex
optimization, Dirichlet kernel, dual certificate.

I. I NTRODUCTION
Two dimensional (2-D) super resolution refers to recovering
2-D point sources from their low-resolution measurements.
One may think of this problem as recovering a high resolution
image of stars in a photo captured by a low-resolution telescope. Various other fields are also involved in this problem.
In the direction of arrival (DOA) estimation, far field point
sources are to be located in terms of their 2-D directions
using measurements by a two-dimensionally dispersed array
of sensors. Applications are vast from Radar, sonar to cellular communication systems. The main performance measure
for any DOA estimation algorithm is its ability to resolve
two closely-spaced sources which leads to the term superresolution methods [1]. High-dimensional super-resolution
has also important applications in off-the-grid Multiple-input
multiple-output (MIMO) radar where the aim is to estimate the
angle-delay-Doppler continuous triplets from the reflections
recorded at receiver antennas [2]. Another example is high
dimensional medical imaging, a diagnosis method to determine
the presence of some certain diseases [3].
Consider r high-frequency 2-D signals in the form of Dirac
delta functions. The signal is observed after convolution with
a low-pass kernel. In some applications, there is no exact
information about the kernel. In this case, joint estimation of
the signal and the kernel is required which is blind superresolution [4], [5]. In many scenarios, the low-pass kernel is
known before-hand. In this paper, we assume that the signal
is observed through convolution with a 2-D sinc kernel bandlimited to the integer square [−fc , fc ]2 . With this assumption,
the measurements are in the form of superposition of r
sinusoids with arbitrary complex amplitudes. This model has
a closed relation with 2-D line spectral estimation.
Conventional parametric approaches to super-resolve sparse
2-D point sources are based on decomposition of measurement

space into orthogonal signal and noise subspaces such as 2-D
MUSIC [6], 2-D unitary ESPRIT [7] and Matrix Enhancement
Matrix Pencil (MEMP) method [8]. However, these techniques
are sensitive to noise and outliers. They are also dependent on
model order. Discrete 2-D super-resolution suggests that one
can recover the sparse signal by solving an `1 minimization
problem [9]–[12]. This method assumes all the point sources
to lie on the grid. However, this assumption is not realistic in
practice. When the true point sources do not lie on the grid, basis mismatch occurs which leads to reduced performance. One
is able to achieve better reconstruction using finer grids, but
this imposes higher computational complexity [13], [14]. To
overcome grid mismatch, [15] presented a new method based
on convex optimization that recovers the infinite-dimensional
signal from low-resolution measurements by minimizing a
continuous version of `1 norm known as Total Variation (TV)
norm. Similar to compressed sensing, a sufficient condition for
exact recovery is the existence of a dual certificate orthogonal
to the null-space of the measurements with sign pattern of
the signal in the support and magnitude less than one in offsupport locations. [15] constructed this dual certificate as a
linear combination of r shift copies of forth power of Dirichlet
kernel (and its derivatives). They prove that existence of such a
linear combination imposes 2/fc minimum separation between
the point sources for 1-D situation where fc is the cut-off
frequency. In 2-D case, the sources must be separated at
least by 2.38/fc to construct dual polynomial band-limited
to integer square [−fc , fc ]2 .
Implementation of TV norm minimization problem may
seem tough because of infinite dimensionality of the primal
variable. To handle this situation, one can convert the dual
problem to a tractable semidefinite program (SDP) using
Positive Trigonometric Polynomial (PTP) theory. In fact,
PTP theory provides conditions to control the magnitude of
trigonometric polynomials in signal domain by some linear
matrix inequalities (LMI) [16]–[18]. Moreover, it is possible
to control the magnitude of trigonometric polynomial in any
partition of signal domain which can be translated to prior
information [19], [20].
The approach of [15] was extended to off-the-gird spectral
estimation in compressed sensing (CS) regime [21]. It shows
that atomic norm minimization can recover a 1-D continuous
spectrally sparse signal from partial time domain samples as
long as the frequency sources are separated by 4/n where n is
number of Nyquist samples. Proof is based on constructing a
random dual certificate that guarantee exact recovery with high
probability. Similar to this work, [18] presented 2-D random
dual polynomial time-limited to integer square [−2M, 2M ]2

2

for estimating the true off-the-grid 2-D frequencies under the
condition that they satisfy a minimum separation 1.19/M .
[22] investigated multi-dimension frequency reconstruction
by minimizing nuclear norm of a Hankel matrix subject to
some time domain constraints known as Enhanced Matrix
Completion (EMaC). Recently, Fernandez in [23], has shown
that the guaranty for exact recovery of 1-D point sources
using TV norm minimization can be improved up until the
minimum separation 1.26/fc by constructing a dual certificate
that interpolates the sign pattern of closer point sources. The
main idea of his work is to use the product of p Dirichlet
kernels with different bandwidths instead of its forth power
that was used in [15] for 1-D case. This leads to a better
trade-off between the spikiness of the dual polynomial in the
support locations and decay of its tail.
The main result of this paper is to guarantee that TV
norm minimization achieves exact solution as long as the
2-D sources are separated by at least 1.68/fc . Specifically,
we extend the approach of Fernandez to the recovery of 2-D
point sources which lie in [0, 1]2 with arbitrary locations and
complex amplitudes. For this purpose, we first propose a 2-D
low-pass kernel caped by the integer square [−fc , fc ]2 which is
obtained by tensorizing the 1-D kernel used by Fernandez [23].
In comparison with the 2-D kernel used by [15], our kernel
better balances between spikiness at the origin and decay of
its tail. Then we construct 2-D low-pass dual polynomial by
linearly combining r shifted copies of the kernel and its partial
derivatives. Our theoretical guaranty requires bounds on the 1D and 2-D kernels which are verified by numerical simulations
given in Section V.
The rest of the paper is organized as follows. The problem
is formulated in Section II. Section III presents TV norm
minimization and the proposed uniqueness guaranty. Implementation of the dual problem is given in Section IV. In
Section V results are validated via numerical experiments.
Finally, we conclude the paper and introduce future directions
in Section VI.
Notation. Throughout the paper, scalars are denoted by
lowercase letters, vectors by lowercase boldface letters, and
matrices by uppercase boldface letters. The ith element of the
vector x and the k = (k1, k2) element of the matrix X are
given by xi and xk , respectively. |·| denotes cardinality for sets
and absolute value for scalars. For a function f and a matrix
A, kf k∞ and kAk∞ are defined as kf k∞ = sup|f (t)| and
t
P
kAk∞ = sup kAxk∞ = maxi j |Ai,j |, respectively.
kxk∞ ≤1

Null space of linear operators are denoted by null(·). relint(C)
denotes relative interior of a set C. f (i (t) and f i1 ,i2 (t) denote
ith derivate and i1 , i2 partial derivatives of 1-D function f (t)
and 2-D function f (t := (t1 , t2 )), respectively. (·)T and (·)H
shows transpose and hermitian of a vector, respectively. sgn(x)
denotes the element-wise sign of the vector x. Also, vec(X)
denotes the columns of X being stacked on top of each other.
The inner
R product between two functions f and g is defined as
hf, gi : f (t)g(t)dt. ⊗ and ⊗ denotes tensor and Kronecker
C

D

product, respectively. The adjoint of a linear operator F is
denoted by F ∗ .

II. P ROBLEM F ORMULATION
We consider a mixture of r 2-D Dirac function on a
continuous support T :
x2D (t) =

r
X

di δ(t − ti ),

(1)

i=1

where di = |di |ejφi is an arbitrary complex amplitude of
each point source with φi ∈ [0, 2π), ti := [t1i , t2i ]T in the
continuous square [0, 1]2 , and δ(·) denotes Dirac function.
Assume that the only available information about x2D is its 2D Fourier transform band-limited to integer square [−fc , fc ]2
as:
Z
r
X
yk =
e−j2πhk,ti x2D (t)(dt) =
di e−j2πhk,tj i , (2)
[0,1]2

i=1

where k = (k1 , k2 ) ∈ J, J = {−fc , ..., fc } × {−fc , ..., fc }
denotes all of indices of the signal (fc is an integer). It is
beneficial to consider each observation an element of a matrix
Y ∈ Cn×n as below:
Y := F2D x2D ,

(3)

which n := 2fc + 1 and F2D is the 2-D linear operator
that maps a continuous function to its lowest 2-D Fourier
coefficients up until the integer square [−fc , fc ]2 . The problem
is then to estimate x2D from the observation matrix Y .
III. T OTAL VARIATION M INIMIZATION FOR 2-D S OURCES
To super-resolve the point sources from Fourier measurements, one can use the following optimization problem:
min kz2D kTV subject to Y = F2D z2D ,

PTV :

z2D

(4)

where TV norm promotes sparse atomic measures which
define as:
X
kz2D kTV := sup
|z2D (E)|,
(5)
ρ

E∈ρ

in which ρ is any partition of [0, 1]2 into finite number of
disjoint measurable 2-D subsets and |z2DP
(E)| is a positive
r
measure on E. In particular, kx2D kTV = i=1 |di |.
The main goal of this paper is to show that, PTV exactly
recovers x2D if the sources satisfy some mild separation. In
the following, we define the minimum distance of a point from
a 2-D set.
Definition 3.1: Let T2 be the product space of two circles
obtained by identifying the endpoints on [0, 1]2 . For each set
of points T ⊂ T2 , the minimum separation is defined as:
∆(T ) :=
=

inf

ti ,tj ∈T, ti 6=tj

inf

ti ,tj ∈T, ti 6=tj

kti − tj k∞

max{|t1i − t1j |, |t2i − t2j |},

(6)

where |t1i − t1j | and |t2i − t2j | denote warp-around distances
on the unit circle.
It has been shown that PTV can achieve exact recovery for
fc ≥ 512 as long as the components of the support are separated by at least 2.38/fc [15]. The following theorem which
is the main result of this paper states that for fc ≥ 2 × 103

3

under some milder separation condition on the support, PTV
can reach the exact solution.
Theorem 3.1: Let T = {tj }rj=1 be the support of x2D . If
fc ≥ 2 × 103 and the minimum septation obeys
∆(T ) ≥ 1.68λc ,

(7)

where λc := 1/fc , then the solution of PTV is unique.
A. Uniqueness Guaranty
To prove uniqueness of PTV , it is sufficient to find a
function Q(t) known as dual certificate which is orthogonal
to the null space of F2D and belongs to relative interior of
sub-differential of TV norm at the original point x2D [15].
Proposition 3.2: If the conditions of Theorem 3.1 hold, then
for any sign pattern v ∈ C|T | with |vj | = 1 ∀j there exist a
low-pass function
X
Q(t) =
qk ej2πht,ki ,
(8)

Fernandez in [23] proposed Kγ (t) for 1-D situation instead
of forth power of Dirichlet kernel that was previously used in
[15]. This kernel provides a better trade-off between spikiness
in the origin and the order of tail decay. This motivates
proposition of 2-D kernel in the form of (11).
If Q(t) was constructed such that only (9) is satisfied, the
magnitude of the resulting polynomial may exceed one near
the elements of the support T . To handle this situation, we
force the derivative of the polynomial to be zero at the support
of x2D . We construct Q(t) as
X
10
Q(t) =
αi K2D (t − ti ) + β1i K2D
(t − ti )
ti ∈T
01
+β2i K2D
(t − ti ),

(15)

10
to better control K2D (t) and its derivatives. K2D
(t) and
01
K2D (t) denote the partial derivatives of K2D (t) with respect
to t1 , t2 , respectively. Therefore, instead of (9) and (10), the
following conditions are considered.

k∈J

such that
Q(ti ) = vi ,

ti ∈ T,

(9)

|Q(t)| < 1,

t∈
/ T.

(10)

The conditions (8), (9) and (10) refer to the fact that Q(t) ∈
null⊥ (F2D ) ∩ relint(∂k·kTV (x2D )). The proof of Proposition
is given in Appendix B.
It is beneficial to emphasize that if the sign of closelyspaced sources differ from each others, then it is ill-posed to
interpolate sign pattern of x2D a the low-pass trigonometric
polynomial. That’s why the minimum separation condition is
required. This can be rebated if the sign of sources be the
same as in [24], [25].

K2D = Kγ ⊗ Kγ ,

(11)

C

where Kγ (t), ∀t ∈ [0, 1] is multiplication of three Dirichlet
kernel K(f, t) with different cut-off frequencies defined as
below:
Kγ (t) =

3
Y

K(γi fc , t) =

i=1

fc
X

ck ej2πkt ,

(12)

k=−fc

(16)

ti ∈ T.

(17)

IV. I MPLEMENTATION
It may seem challenging to find an exact solution of PTV
since the variable lies in a continuous domain. Due to the
establishment of Slater’s condition and convexity of PTV
strong duality holds. Therefore, one can consider the following
dual problem
max

To construct the dual certificate Q(t) in Proposition 3.2
under the conditions of Theorem 3.1, we first propose the
following 2-D low-pass kernel:

ti ∈ T,

∇Q(ti ) = 0,

In Appendix B, it is shown that one can always find interpolation coefficients α, β1 , β2 ∈ C|T | under the conditions of
Theorem 3.1.

C∈Cn×n

B. Construction of the dual certificate

Q(ti ) = vi ,

∗
RehC, Y iF subject to kF2D
Ck∞ ≤ 1,

where Reh· , ·iF denotes the real part of Frobenius inner
product, C is the dual variable, and the inequality constraint
implies that the modulus of the following trigonometric polynomial is uniformly bounded by 1:
X
∗
(F2D
C)(t) :=
ck ej2πht,ki .
(19)
k∈J

Also this inequality can be converted to some linear matrix
inequalities using PTP theory. Then the problem can be
considered as a SDP which can be solved in polynomial time
[17]. Hence, (18) is equivalent to
max RehY , CiF

where

C,Q0
f
X
1
ej2πkt ,
K(f, t) =
2f + 1

(13)

k=−f

in which f is the cut-off frequency, γ1 = 0.247, γ2 = 0.339,
γ3 = 0.414, and c ∈ Cn is the convolution of the Fourier
coefficient of K(γ1 fc , t), K(γ2 fc , t), and K(γ3 fc , t). Consequently,
X
K2D (t) =
ck1 ck2 ej2πht,ki .
(14)
k∈J

(18)

(20)

subject to δk = tr[Θk Q0 ], k ∈ J,


Q0
vec(C)

  0,
(vec(C))H
1
2

2

where Q0 ∈ Cn ×n is a positive semidefinite Hermitian
matrix, Θk = Θk2 ⊗ Θk1 , Θk ∈ Cn×n is an elementary
D

Toeplitz matrix with ones on it’s k-th diagonal and zeros else
where. δk = 1 if k = (0, 0), and zero otherwise.

4

15
Upper bound on K
Upper bound on K2
Upper bound on |K1|

10

Upper bound on |K3|

5

0

-5
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

(a)
14
12

2
Upper bound on |K 21
|
2D
Upper bound

10

Upper bound

1

on |K 10
|
2D
on |K 30
|
2D

0

8

-1

6

-2

4

-3

2

-4

0
0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

Lower bound on K00
2D
Upper bound on |K11
|
2D
Upper bound on K20
2D

-5
0

0.05

0.1

0.15

0.2

(b)

0.25

0.3

0.35

0.4

(c)

Fig. 1: (a)Bounds on 1-D kernel Kγ` (t)/fc` . The bounds are calculated on the grid size  = 10−6 covering the interval
i1 i2
0 ≤ t/λc ≤ 1.68/2. All bounds are monotone in [0, 0.212568]. (b) and (c) Bounds on K2D
(t)/fci1 +i2 and its partial
derivatives. The bounds are calculated on the grid size  = 10−6 covering the interval 0 ≤ t1 /λc ≤ 0.4.

5

14

Bound on Z01
4

Bound on Z11
12

Bound on Z00
Bound on Z02

10

3

Bound on Z03
Bound on Z12

8
6

2

4

1
2

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0
0

0.9

0.1

0.2

0.3

(a)

0.4

0.5

0.6

0.7

0.8

0.9

(b)

Fig. 2: Bounds on Z i1 i2 (ktk2 )/fci1 +i2 in (58). The bounds are calculated on the grid size  = 10−6 covering the interval
0 ≤ ktk2 /λc ≤ 1.68/2.

Dual Polynomial
True Sources
Estimated Soureces

1

0.5

0
1

0.8

0.6

0.4
t2

0.2

0

0

0.2

0.4

0.6

0.8

1

t1

Fig. 3: 2-D Point sources recovery using the dual polynomial (22). The true sources are estimated by localizing the modulus
of the dual polynomial is one.

5

(a)

(b)

Fig. 4: Graphs showing phase transition of successful recovery of PTV over 10 trials. In (a) and (b), the number of samples
is 64 and 100, respectively.

By strong duality, for any solution x̂2D and Ĉ of PTV and
(20), respectively, we have:
∗
hF2D x2D , ĈiF = hx2D , F2D
Ĉi = kx̂2D kTV =

hx̂2D , sgn(x̂2D )i.

(21)

∗
Therefore, (F2D
Ĉ)(t) = sgn(x̂2D (t)) ∀t ∈ T . This suggests
that one can find the support by looking for t ∈ [0, 1]2 such
∗
Ĉ)(t)| = 1 (see Fig. 3).
that |(F2D

V. E XPERIMENT
In this section, we numerically provide some bounds on
Kγ (t) and its derivatives to show their monotonicity in the
interval |t| ≤ 0.212568λc which is necessary in Lemma B.2.
These bounds are shown in Fig.1(b)and 1(c)1 . The proof of
Theorem 3.1 makes essentially use of the bounds on K2D (t),
its partial derivatives and Z which is defined in (58). These
bounds are numerically shown in Figs. 1(b), 1(c) and Fig.
2, respectively. It may seem surprising at the first sight how
the 2-D kernels are drawn versus one variable. Precisely, the
proof of Lemma B.2 requires some bounds on 2-D kernels in
t : ktk2 ≤ 0.212568λc . Remark that the positive definiteness
of the Hessian matrix H in (52) is why the radius 0.212568λc
is chosen. Since the bounds are monotonic both on t1 and
t2 in the interval 0 ≤ t ≤ 0.212568λc (See Appendix D
and Fig. 1(a)), it is sufficient to evaluate them on the line
t1 = t2 ≤ 0.212568λc . Moreover, the small grid size  = 10−6
that is used in the simulations imposes much computational
complexity in the 2-D case. This idea that was first used
by [15] leads to simple computations. Fig. 1(b) and 1(c)
demonstrate bounds on K2D (t) and its partial derivatives with
the condition that t1 = t2 .
We further uniformly generate r = 25 2-D points in [0, 1]2
with coefficients di ∼ (0.5 + χ2 (1)) exp (j2π U[0, 1]) : i =
1, ..., r and build 2-D Fourier measurements in the form of (2)
up until the square [−fc , fc ]2 in which fc = 15. To reconstruct
the location of point sources from the measurements, we first
implement the SDP problem (20) using CVX [26]. Then, the
following dual polynomial is obtained by the solution Ĉ.
X
T
∗
(F2D
Ĉ)(t) :=
ĉk ej2πt k .
(22)
k∈J
1 These

bounds are evaluated using [23] and the MATLAB code therein.

∗
Based on (21) one can localize |(F2D
Ĉ)(t)| = 1 to find the
signal support as shown in Fig. 3.
In the last experiment, we evaluate how the success rate
scales with changing number of spikes and minimum separation in different number of samples. Fig. 4 shows that the
phase transition occurs near about 1.4/λc .

VI. C ONCLUSION A ND F UTURE D IRECTIONS
This paper is concerned with the recovery of 2-D point
sources where we are given low-resolution measurements
caped to integer square [−fc , fc ]2 . We show that TV norm
minimization achieves exact recovery when the sources are
separated by at least 1.68/fc . The proof is based on construction of a 2-D low-pass dual polynomials that can interpolate
any sign patterns of the support signal.
There are several interesting future directions to be explored.
[18] has shown that off-the-grid 2-D point sources can be
recovered from partially observed Fourier coefficients as long
as the separation is 2.38/fc . This bound can be improved to
1.68/fc using the proposed 2-D dual polynomial in Proposition 3.2. It is beneficial to consider our 2-D problem in line
spectral estimation when the measurements are corrupted with
sparse noise using the approach of [27].
A PPENDIX A
U SEFUL L EMMAS
The proof sketch of our 2-D low-pass polynomial construction is based on the bounds on the 1-D kernel Kγ (t) in (12)
and its derivatives. These bounds are derived in [23, Section
4.1] based on Taylor series expansion of Dirichlet kernel and
its derivatives around origin.
Lemma A.1: [23, Lemma 4.4] For any ` ∈ {0, 1, 2, 3}, if τ
is such that |fc t − τ | ≤ , ∀fc ≥ 103 and ∀t ∈ [0, 1], then
we have the following non-asymptotic bounds on Kγ` (t)
L
U
Bγ,`
(τ ) − (2π)`+1 fc`  ≤ Kγ` (t) ≤ Bγ,`
(τ ) + (2π)`+1 fc` ,
(23)
L
U
where Bγ,`
and Bγ,`
are defined in [23, Section B.1].
Consequently, one has upper bounds on the magnitude of
Kγ (t) and its derivatives as:
∞
L
U
|Kγ` (t)| ≤ Bγ,`
(τ, ) = max{|Bγ,`
(τ )|, |Bγ,`
(τ )|}

+(2π)`+1 fc` .

(24)

6

Lemma A.2: [23, Lemma 4.6] For fc ≥ 103 , ` ∈ {0, 1, 2, 3}
and |t| ≤ 450
fc the following decreasing bound is established:
|Kγ` (t)| ≤ bγ,` (fc t),

(25)

where bγ,` (fc t) is defined in [23, Section B.2]. Also, there is
a global upper bound as:
|Kγ` (t)| ≤ (2πfc )` .

(26)

Since the upper bound on sum of |Kγ` (t)| and its shift copies
are required for 2-D situation, the result of [23, Lemma 4.7]
with minor changes is given below.
Lemma A.3: Following [23, Lemma 4.7], suppose 0 ∈ T and
∆(T ) ≥ τmin /fc where τmin := ∆min /λc = 1.68. If fc ≥ 103
and γ = [0.247, 0.339, 0.414]T , then for all t ∈ [0, ∆min /2]
and τ such that τ −  ≤ fc t ≤ τ ,  ≥ 0,
X
|Kγ` (t − ti )| ≤ H` (τ ) + H` (−τ ),
(27)
ti ∈T \{0}

where
H` (τ ) :=

20
X

max



∞
(u, ), bγ,` ((i + 4)τmin ) + C̃` ,
max (Bγ,`

u∈Gi,τ

i=1

(28)
where Gi,τ covers the interval [iτmin − τ, (i + 4)τmin ] with 
equispaced steps and
C̃` =

267
X

bγ,` ((i − 1/2)τmin ) + C` ,

(29)

i=21

where C0 = 7.89 × 10−7 , C1 = 4.96 × 10−6 , C2 = 3.12 ×
10−5 , and C3 = 1.96 × 10−4 .
The following bounds are beneficial in the proof of Lemmas
B.2 and B.3,
X
|Kγ` (t − ti )| ≤ H` (0),
ti ∈T ∩(− 21 ,0)

X

|Kγ` (t − ti )| ≤ H` (τmin /2).

(30)

ti ∈T ∩(0, 21 )

A PPENDIX B
P ROOF OF P ROPOSITION 3.2
To meet (16) and (17) and obtain upper bounds on interpolation coefficients, we present the following Lemma.
Lemma B.1: If the condition of Theorem 3.1 hold, in (15),
there exist coefficient vectors α, β1 and β2 satisfying
kαk∞ ≤ 1 + 3.7 × 10−2 ,
(31)

To prove this lemma, the approach of [15] is followed.
Without loss of generality, we assume the unit square [0, 1]2
be mapped to [−1/2, 1/2]2 . First, (16) and (17) are written in
matrix form as:

   
E00 E10 E01
α
v
E10 E20 E11  β1  = 0 ,
(33)
E01 E11 E02
β2
0
where
(i i )

(Ei1 i2 )`,j = K2D1 2 (t` − tj ).

To bound the infinity norm of the sub-matrices in (33), 1-D
results can be used as below:
X
kI − E00 k∞ = max
|K2D (ti − t0 )|
≤ max
t0

X

To control the magnitude of Q(t) near the elements of the
support T , we present the following lemmas. Without loss of

ti ∈T \t0

|Kγ (t1i − t10 )||Kγ (t2i − t20 )|,

(36)

ti ∈T \t0

where ti = (t1i , t2i ), t0 = (t10 , t20 ) and the inequality follows
form (11). To apply the 1-D result as discussed in AppendixA
to 2-D case, we divide the set T \{t0 } into regions |t1i −t01 | ≤
∆min /2 or |t2i − t20 | ≤ ∆min /2 and min(|t1j − t10 |, |t2j −
t20 |) ≥ ∆min /2. With this assumption, we reach:
X
max
|Kγ (t1i − t10 )||Kγ (t2i − t20 )|
t0
|t1i −t10 |≤∆min /2 or |t2i −t20 |≤∆min /2,
ti 6=t0
t20

(32)

(34)

The interpolation coefficients are calculated from the above
equations. Since Kγ and Kγ2 are even and Kγ1 is odd, E00 ,
E20 , E11 and E02 are symmetric, while E01 and E10 are
T
T T
antisymmetric.
Let β = [β1T , β2T ]T , Ẽ = [E10
, E01
] and

E20 , E11
Ẽ2 =
. Therefore, the above matrix system is
E11 , E02
converted to:

   
E00 −Ẽ1T α
v
=
.
(35)
β
0
Ẽ1
Ẽ2

≤ max kKγ k∞

where β = [β1T , β2T ]T . Also, if v1 = 1, then
α1 ≥ 1 − 3.7 × 10−2 .

A PPENDIX C
P ROOF OF L EMMA B.1

t0

Also, H` (τ ) and H` (−τ ) are strictly increasing and decreasing
functions, respectively.

kβk∞ ≤ 2.4 × 10−2 λc ,

generality, we can assume that the first element of the support
T is located in 0.
Lemma B.2: Assume, without loss of generality, 0 ∈ T .
Then if the conditions of Theorem 3.1 hold, for any t : 0 <
ktk2 ≤ 0.212568λc , |Q(t)| < 1.
Lemma B.3: Assume, without loss of generality, 0 ∈ T .
Then if the conditions of Theorem 3.1 hold, |Q(t)| < 1 for
any t : 0.212568λc ≤ ktk2 < ∆min .
The proof of our main result requires a numerical upper bound
on (23) and (14) which are shown in Fig. 1.

|Kγ (t2i − t20 )|

t2j 6=t20

+ max kKγ k∞
t10

X
X

|Kγ (t1i − t10 )|

t1j 6=t10

≤ 2H0 (0) + 2H0 (0),

(37)

7

where the last inequality stems from (27) when τ = 0 and
the fact that |Kγ (t)| ≤ 1. Also the first one is the result of
minimum separation ∆min between the sources and the union
bound.
For the last region, we have:
X
|Kγ (t1i − t10 )||Kγ (t2i − t20 )|
max
t0
min(|t1i −t10 |,|t2i −t20 |)≥∆min /2,
ti 6=t0


≤
≤

X

max

t10
|t1i −t10 |≥∆min /2,
t1i 6=t10
(2H0 (0))2 ,

|Kγ2 (0)|

and value of |Kγ2 (0)|

1
0.251
.
≤
2
− k|Kγ (0)|I − E02 k∞
fc2
(45)

By using (42) and (43),
−1
+ kE11 k2∞ kE02
k∞ ≤ 0.591 fc2 .
(46)


X
max
|Kγ (t2i − t20 )|

t20
|t2i −t20 |≥∆min /2
t2i 6=t20 ,

Similarity (45) reads
(38)

where the last inequality stems from the minimum separation
condition and (27). Consequently,
X
kI − E00 k∞ = max
|Kγ (ti − t0 )|
(39)
t0

−1
kE02
k∞ ≤

1
1−kI−M k∞

k|Kγ2 (0)|I − S1 k∞ ≤k|Kγ2 (0)|I − E02 k∞


|Kγ (t1i − t10 )|

Respected to kM −1 k∞ ≤
Fig. 1(a), we reach:

ti ∈T \t0

kS1−1 k∞ ≤

0.251
1
. (47)
≤
|Kγ2 (0)| − k|Kγ2 (0)|I − S1 k∞
fc2

Next, (41), (42) and (45) allow to bound S2
−1
kS2 k∞ ≤ kE10 k∞ + kE11 k∞ kE02
k∞ kE01 k∞

≤ 9.1 × 10−2 fc ,

(48)

using (39), (48), (47), (41), and (45) we achieve
≤ 4H0 (0) + 4H02 (0) ≤ 3.17 × 10−2 .

(40)

kI − S3 k∞ ≤ kI − E00 k∞ + kS2 k2∞ kS1−1 k∞
−1
+ kE01 k2∞ kE02
k∞ ≤ 3.6 × 10−2 ,
(49)

By applying the same approach, we reach:
kE10 k∞ ≤ 2H1 (0) + 2kKγ1 k∞ H0 (0) + 4H1 (0)H0 (0)
≤ 8.7 × 10−2 fc ,

(41)

where the bound follows from Fig. 1(a) and (27). Same bound
holds for E01 . Similarly,
kE11 k∞ ≤ 4kKγ1 k∞ H1 (0) + 4H12 (0) ≤ 0.181 fc2 .

(42)

1
≤ 1.037.
(50)
1 − kI − S3 k∞
One can bound the interpolation vector with the above results
as below:
kS3−1 k∞ ≤

kαk∞ ≤ kS3−1 k∞ ≤ 1 + 3.7 × 10−2 ,
kβ1 k∞ ≤ kS1−1 S2 S3−1 k ≤ kS1−1 kkS2 kkS3−1 k ≤ 2.4 × 10−2 ,

Eventually,

α1 = v1 − ((I − S3−1 )v)1

k|Kγ2 (0)|I − E20 k∞ ≤ 2H2 (0) + 2kKγ2 k∞ H0 (0)
+4H2 (0)H0 (0) ≤ 0.583 fc2 ,

(43)

where the above inequities come is obtained by (27) and fact
that kKγ2 k∞ occur at origin (see Fig. 1(a)).
To ease notation, consider,
−1
S1 = E20 − E11 E02
E11 ,
−1
S2 = E10 − E11 E02
E01 ,
−1
S3 = E00 + S2T S1−1 S2 − E01 E02
E01 ,

(44)

where S1 is the Schur’s complement of E02 . Also by the
definition of inverse of Schur’s complement, we have


−1
S1−1
−S1−1 E11 E02
Ẽ2−1 =
−1
−1
−1
−1 .
−E02
E11 S1−1 E02
+ E02
E11 S1−1 E11 E02
Regarding the fact that S3 is the Schur’s complement of Ẽ2 ,
the solution of linear system can be written as
  

I
α
=
(E00 + Ẽ1T Ẽ2−1 Ẽ1 )−1 v
β
−Ẽ2−1 Ẽ1


with this bound we have

 

I
α
−1
 S3−1 v.
−S1 S2
⇔ β1  = 
−1
β2
E02
(E11 S1−1 S2 − E01 )

≥ 1 − kS3−1 k∞ kI − S3 k∞ ≥ 1 − 3.7 × 10−2 ,

(51)

where the last inequality holds when v1 = 1. The upper bound
computations for kβ2 k∞ follows from the same strategy.
A PPENDIX D
P ROOF OF L EMMA B.2
In the previous section we showed that Q(t) satisfies (16)
and (17). In this section by showing that the Hessian matrix
 20

Q (t) Q11 (t)
H=
(52)
Q11 (t) Q02 (t)
is negative definite in the domain ktk2 ≤ 0.212568λc , we
prove that the magnitude of Q(t) can not exceed one in
this domain. For this purpose, first using (23) and (24),
we establish non-asymptotic bounds on (11) and its partial
derivative as follows:
 L
 L

K2D (t) ≥ Bγ,0
(τ1 ) − (2π) Bγ,0
(τ2 ) − (2π) ,
 U
 U

20
K2D
(t) ≤ Bγ,2
(τ1 ) + (2π)3 fc2  Bγ,0
(τ2 ) + (2π) ,
10
∞
|K2D
(t)| ≤ [Bγ,1
(τ1 , )],

 ∞

11
∞
|K2D (t)| ≤ Bγ,1 (τ1 , ) Bγ,1
(τ2 , ) ,
21
∞
|K2D
(t)| ≤ |Kγ2 (0)|[Bγ,1
(τ2 , )],
30
∞
|K2D
(t)| ≤ [Bγ,3
(τ1 , )],

(53)

8

where the functions within the brackets are all monotone in the
interval 0 ≤ t ≤ 0.212568λc as shown in Fig. 1(a). Regarding
this and the fact that ktk∞ ≤ ktk2 , we can evaluate the nonasymptotic bounds at t1 = t2 = 0.212568λc to show that for
any t : ktk2 ≤ 0.212568λc ,

This leads to
X

|K2D (t − ti )|

ti ∈{|t1 |≤∆min /2 or |t2 |≤∆min /2},
(ktk2 ≤∆min /2)∩R2+

≤ kKγ (t)k∞

X

|Kγ (t2 − t2i )|

0≤t2 ≤∆min /2,
t2i ∈[− 21 , 21 ]\{0}

K2D (t) ≥ 0.8,

20
K2D
(t) ≤ −3.1 fc2 ,

10
|K2D
(t)| ≤ 0.9fc ,

11
|K2D
(t)| ≤ 0.8 fc2 ,

21
|K2D
(t)| ≤ 4.09 fc2 ,

30
|K2D
(t)| ≤ 10.04 fc3 .

+ kKγ (t)k∞

X

X

≤

X

X

+

X

0≤t1 ≤∆min /2,
t1i ∈(0, 21 ]

|Kγ (t2 − t2i )|

0≤t2 ≤∆min /2,
t2i ∈(0, 21 ]

≤ 2H0 (0) + 2H0 (ktk2 fc + ),

(56)

where the first inequality follows from the union bound,
minimum separation between point sources and (11). The
second inequality is obtained by splitting [− 21 , 12 ]\0 to positive
and negative intervals and |Kγ | ≤ 1. The last one is obtained
by the same approach as in the last inequality in the (55).
The only work that remains is to bound the summation when
ti ∈ {min{|t1 |, |t2 |} ≥ ∆min /2} ∩ R2+ . For this purpose,
we divide this quadrant to two regions |t1 − t1i | ≤ ∆min
or |t2 − t2i | ≤ ∆min and min(|t1 − t1i |, |t2 − t2i |) ≥ ∆min as
below:

|Kγ (t2 − t2i )|

|Kγ (t1 − t1i )|

|Kγ (t2 − t2i )|

|Kγ (t1 − t1i )|

0≤t1 ≤∆min /2
t1i ∈[− 12 ,−∆min /2]

+ kKγ (t)k∞

!
X

|Kγ (t2 − t2i )|

0≤t2 ≤∆min /2
t2i ∈[−∆min /2, 12 ]

X

|Kγ (t1 − t1i )|

+



X


|K(t1 − t1i )|

0≤t1 ≤∆min /2,
|t1 −t1i |≥∆min ,
t1i ∈[∆min /2, 12 ]

X


|K(t2 − t2i )|

0≤t2 ≤∆min /2,
|t2 −t2i |≥∆min ,
t2i ∈[∆min /2, 12 ]

≤ 2H0 (ktk2 fc + ) + H02 (ktk2 fc + ),

≤ H0 (0)H0 (τ1 ) + H0 (0)H0 (τ2 ) + H0 (0)H0 (0)
≤ 2H0 (0)H0 (ktk2 fc + ) + H0 (0)H0 (0),

|Kγ (t2 − t2i )|

0≤t1 ≤∆min/2,
t1i ∈[∆min /2, 21 ]

0≤t2 ≤∆min /2
t2i ∈[− 12 ,−∆min /2]

!

X

0≤t2 ≤∆min/2,
t2i ∈[∆min /2, 12 ]

!
X

|K2D (t − ti )|

≤ kKγ (t)k∞

0≤t2 ≤∆min /2
t2i ∈[− 12 ,−∆min /2]

0≤t1 ≤∆min /2
t1i ∈[− 12 ,−∆min /2]

+

|Kγ (t1 − t1i )| +

(ktk2 ≤∆min /2)∩R2+

!

!

X

|Kγ (t2 − t2i )|

0≤t2 ≤∆min /2,
t2i ∈[− 21 ,0)

X

|Kγ (t1 − t1i )|

0≤t1 ≤∆min /2
t1i ∈[∆min /2, 12 ]

+

X

|K2D (t − ti )| ≤

!

X

|Kγ (t1 − t1i )| +

0≤t1 ≤∆min /2,
t1i ∈[− 12 ,0)

ti ∈{min(|t1 |,|t2 |)≥∆min /2}\R2+ ,
(ktk2 ≤∆min /2)∩R2+

X

|Kγ (t1 − t1i )|

0≤t1 ≤∆min /2,
t1i ∈[− 21 , 12 ]\{0}

(54)

01
02
12
03
The same bounds hold for K2D
, K2D
, K2D
and K2D
.
Remark that the right-hand side of the second bound in (53)
is multiplication of the negative increasing and the positive
decreasing functions Kγ2 and Kγ , respectively, (See Fig. 1(a)).
Later,
we leverage the same technique as in [15] to bound
P
i1 i2
∀ktk2 ≤ ∆min /2. Consider a
ti ∈T \0 |K2D (t − ti )|,
special case i1 = i2 = 0. Without loss of generality,
we assume t ∈ R2+ and 0 ∈ T . Also, we consider that
ti ∈ {min(|t1 |, |t2 |) ≥ ∆min /2}. To bound the sum, we split
the domain {min(|t1 |, |t2 |) ≥ ∆min /2} to different regions.
First, assume that ti ∈ {min(|t1 |, |t2 |) ≥ ∆min /2} \ R2+ ,

X

(57)

(55)
where the first inequality is obtained using the union bound
and minimum separation between the sources. The second one
is similar to the last inequality in (55.

where the first inequality follows from the union bound and
splitting the region into three quadrants. The second inequality
is a result of the first line of (30) and Lemma A.3. The last
one is obtained using the facts |fc ti − τi | ≤  : ∀i = 1, 2,
ktk∞ ≤ ktk2 and that H0 (τ ) is strictly increasing.
Next, assume that ti ∈ {|t1 | ≤ ∆min /2 or |t2 | ≤ ∆min /2}.

i1 i2
The above approach is applied to K2D
(t) for ktk2 ≤
∆min /2 as follows:

X
ti ∈T \0

i1 i2
|K2D
(t − ti )| ≤ Z i1 i2 (ktk2 ),

(58)

9

where for u > 0,
Z

i1 i2

1.4

(u) ≤

1.2

Hi1 (ufc + )Hi2 (0) + Hi1 (0)Hi2 (0) + Hi1 (0)Hi2 (ufc + )
+ kK i2 k∞ Hi1 (0) + kK i1 k∞ Hi2 (0)

1

0.8

+ kK i2 k∞ Hi1 (ufc + ) + kK i1 k∞ Hi2 (ufc + )

0.6

+ kK i2 k∞ Hi1 (ufc + ) + kK i1 k∞ Hi2 (ufc + )
+ Hi1 (ufc + )Hi2 (ufc + ), ∀i1 , i2 ∈ {0, 1, 2, 3}, (59)

0.4

0.2

where we used the first line of (30) and the fact that H` (τ )
is strictly increasing. Also, kKk∞ and its derivatives can be
obtained using (24) and (26) (See Fig. 1(a)).
To show that H is negative definite in ktk2 ≤ 0.212568λc , it
is sufficient to have Tr(H) < 0 and det(H) > 0,

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Fig. 5: The bound in (65) versus ktk2 /λc . The bound is strictly
less than one in the region 0.212568λc ≤ ktk2 ≤ ∆min /2.

Tr(H) = Q20 (t) + Q02 (t),
det(H) = |Q20 (t)||Q02 (t)| − |Q11 (t)|2 .

(60)

A PPENDIX E
P ROOF OF LEMMA B.3

We can easily write Q20 (t) form (15) as follows:
X
20
30
Q20 (t) =
αi K2D
(t − ti ) + β1i K2D
(t − ti )
ti ∈T
21
+β2i K2D
(t − ti ).

(61)

Regarding (53) and (59) we obtain
X
20
20
Q20 (t) ≤ α1 K2D
(t) + kαk∞
|K2D
(t − ti )|

In the previous section using the assumption that 0 ∈ T ,
we showed that |Q(t)| < 1 when ktk2 ≤ 0.212568λc . In this
section, we show that |Q(t)| < 1 in 0.212568λc ≤ ktk2 ≤
∆min . We first bound |Q(t)| in 0.212568λc ≤ ktk2 ≤ ∆min /2
as:

ti ∈T \0


X
30
30
21
+ kβk∞ |K2D
(t)| +
|K2D
(t − ti )| + |K2D
(t)|

|Q(t)| =

+

21
|K2D
(t


− ti )| ≤

20
α1 K2D
(t)

+ Z (ktk2 )



30
30
21
21
+ kβk∞ |K2D (t)| + Z (ktk2 ) + |K2D (t)| + Z (ktk2 )
fc2 ,

(62)

where the last inequality is obtained by Z 30 (u), Z 21 (u) at
u = 0.212568λc , (54) which is reported in Figs. 1(b) and
1(c) evaluated with  = 10−6 and the result of Lemma B.1.
Further, using (54) and (58), we obtain a bound on |Q11 (t)|
at ktk2 = 0.212568λc as follows:


11
11
00
|Q (t)| ≤ kαk∞ |K2D (t)| + Z (ktk2 )


21
12
+ kβk∞ |K2D
(t)| + Z 21 (ktk2 ) + |K2D
(t)| + Z 12 (ktk2 )
≤ 1.4743 fc2 .

(63)

Using (60), (62), and (63), it is clear that Tr(H) < 0 and
det(H) > 0 at for any t : ktk2 ≤ 0.212568λc .
In the above, we demonstrated that Q(t) is concave in any
small ball around 0. It remains to show that Q(t) ≤ −1 does
not occur in the ball ktk2 ≤ 0.212568λc as follow:
Q(t) ≥ α1 K2D (t) − kαk∞ Z 00 (ktk2 )


01
10
− kβk∞ |K2D
(t)| + |K2D
(t)| + 2Z 01 (ktk2 )
≥ 0.393.
This concludes the proof.


+
− ti ) ≤ kαk∞ |K2D (t)|


X
10
01
+ |K2D (t − ti )| +kβk∞ |K2D
(t)|+|K2D
(t)|
01
β2i K2D
(t

20

ti ∈T \0

≤ −1.4809

10
αi K2D (t − ti ) + β1i K2D
(t − ti )

ti ∈T

ti ∈T \0

X

X

ti ∈T \0


X
X
10
01
+ |K2D (t − ti )| + |K2D (t − ti )|
ti ∈T \0

ti ∈T \0




00
≤ kαk∞ |Kγ (ktk2 )| + Z (ktk2 ) + kβk∞ |Kγ1 (ktk2 )|

1
10
+ |Kγ (ktk2 )| + 2Z (ktk2 ) ,
(65)
where in the last inequity the property |K2D (t)| ≤
|Kγ (t1 )||Kγ (t2 )| ≤ |Kγ (ktk2 )| is used, since Kγ (t1 ) and
Kγ (t2 ) are both decreasing in the aforementioned region 2 and
the maximum is achieved at t1 = 0, t2 = ktk2 , or vice versa.
01
10
|K2D
(t)| and |K2D
(t)| can be bounded with similar approach.
We numerically show that the upper bound on |Q(t)| is less
than one in the region 0.212568λc ≤ ktk2 ≤ ∆min /2 as in
Fig. 5.
Assume that tc is the closest point in the support to 0. It might
be possible that ∆min ≤ ktc k2 < 2∆min . Therefore, |Q(t)|
must be bounded in the region ∆min /2 ≤ ktk2 < ∆min . For
this purpose, we extend the approach in [23, Lemma 4.3] to

(64)
2 See

Fig. 1(a).

10

two-dimensional situation as below:


00
|Q(t)| ≤kαk∞ |K2D (t)| + Z∞


01
10
10
+ kβk∞ |K2D
(t)| + |K2D
(t)| + 2Z∞
.

(66)

01
10
where the upper bounds on |K2D (t)|, |K2D
(t)| and |K2D
(t)|
in ∆min /2 ≤ ktk2 < ∆min can be obtained by (24) and (25)
as:

|K2D (t)| ≤ |Kγ (t1 )||Kγ (t2 )|
≤

max |Kγ (t1 )|



∞
≤ max max Bγ,0 (u, ), bγ,0 (τmin )
= 0.152,
∆min /2≤t1 <∆min



u∈G

01
|K2D
(t)| ≤ |Kγ (t1 )||Kγ1 (t2 )|

max |Kγ1 (t2 )|




∞
≤ max max Bγ,1 (u, ), bγ,1 (τmin )
= 0.825, (67)

≤

∆min /2≤t2 <∆min

u∈G

where |Kγ | ≤ 1 is used and the upper bounds are obtained by
searching for maximum value of the kernel in the interval
[∆min /2, ∆min ] with a grid step size  = 10−6 . Similar
10
01
| as well. Also,
| the same bound holds for |K2D
to |K2D
∞
∞
Z00 = 0.66 and Z10 = 2.2919 are obtained using (59)
and the second line of (30). To complete the proof, we
have numerically shown |Q(t)| ≤ 0.9866 in the domain
∆min /2 ≤ ktk2 < ∆min with step-size  = 10−6 . This
concludes the proof.
R EFERENCES
[1] H. Krim and M. Viberg, “Two decades of array signal processing
research: the parametric approach,” IEEE signal processing magazine,
vol. 13, no. 4, pp. 67–94, 1996.
[2] R. Hecket and M. Soltanolkotabi, “Generalized line spectral estimation
for radar and localization,” in Compressed Sensing Theory and its
Applications to Radar, Sonar and Remote Sensing (CoSeRa), 2016 4th
International Workshop on, pp. 21–23, IEEE, 2016.
[3] H. Greenspan, “Super-resolution in medical imaging,” The Computer
Journal, vol. 52, no. 1, pp. 43–63, 2008.
[4] P. Campisi and K. Egiazarian, Blind image deconvolution: theory and
applications. CRC press, 2016.
[5] Y. Chi, “Guaranteed blind sparse spikes deconvolution via lifting and
convex optimization,” IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 4, pp. 782–794, 2016.
[6] Y. Hua, “A pencil-music algorithm for finding two-dimensional angles
and polarizations using crossed dipoles,” IEEE Transactions on Antennas
and Propagation, vol. 41, no. 3, pp. 370–376, 1993.
[7] M. Haardt, M. D. Zoltowski, C. P. Mathews, and J. Nossek, “2d unitary
esprit for efficient 2d parameter estimation,” in Acoustics, Speech, and
Signal Processing, 1995. ICASSP-95., 1995 International Conference
on, vol. 3, pp. 2096–2099, IEEE, 1995.
[8] Y. Hua, “Estimating two-dimensional frequencies by matrix enhancement and matrix pencil,” IEEE Transactions on Signal Processing,
vol. 40, no. 9, pp. 2267–2280, 1992.
[9] F. Santosa and W. W. Symes, “Linear inversion of band-limited reflection
seismograms,” SIAM Journal on Scientific and Statistical Computing,
vol. 7, no. 4, pp. 1307–1330, 1986.
[10] S. Levy and P. K. Fullagar, “Reconstruction of a sparse spike train
from a portion of its spectrum and application to high-resolution
deconvolution,” Geophysics, vol. 46, no. 9, pp. 1235–1243, 1981.
[11] R. G. Baraniuk, “Compressive sensing [lecture notes],” IEEE signal
processing magazine, vol. 24, no. 4, pp. 118–121, 2007.

[12] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles:
Exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on information theory, vol. 52, no. 2, pp. 489–
509, 2006.
[13] M. F. Duarte and R. G. Baraniuk, “Spectral compressive sensing,”
Applied and Computational Harmonic Analysis, vol. 35, no. 1, pp. 111–
129, 2013.
[14] Y. Chi, L. L. Scharf, A. Pezeshki, and A. R. Calderbank, “Sensitivity to
basis mismatch in compressed sensing,” IEEE Transactions on Signal
Processing, vol. 59, no. 5, pp. 2182–2195, 2011.
[15] E. J. Candès and C. Fernandez-Granda, “Towards a mathematical theory
of super-resolution,” Communications on Pure and Applied Mathematics, vol. 67, no. 6, pp. 906–956, 2014.
[16] B. Dumitrescu, Positive trigonometric polynomials and signal processing
applications, vol. 103. Springer, 2007.
[17] 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 (d 2) off-the-grid frequencies,” in Information
Theory and Applications Workshop (ITA), 2014, pp. 1–4, IEEE, 2014.
[18] Y. Chi and Y. Chen, “Compressive two-dimensional harmonic retrieval
via atomic norm minimization,” IEEE Transactions on Signal Processing, vol. 63, no. 4, pp. 1030–1042, 2015.
[19] K. V. Mishra, M. Cho, A. Kruger, and W. Xu, “Spectral super-resolution
with prior knowledge,” IEEE transactions on signal processing, vol. 63,
no. 20, pp. 5342–5357, 2015.
[20] I. Valiulahi, H. Fathi, S. Daei, and F. Haddadi, “Off-the-grid twodimensional line spectral estimation with prior information,” arXiv
preprint arXiv:1704.06922, 2017.
[21] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht, “Compressed sensing
off the grid,” IEEE transactions on information theory, vol. 59, no. 11,
pp. 7465–7490, 2013.
[22] Y. Chen and Y. Chi, “Spectral compressed sensing via structured
matrix completion,” in International Conference on Machine Learning,
pp. 414–422, 2013.
[23] C. Fernandez-Granda, “Super-resolution of point sources via convex
programming,” Information and Inference: A Journal of the IMA, vol. 5,
no. 3, pp. 251–303, 2016.
[24] V. I. Morgenshtern and E. J. Candes, “Stable super-resolution of positive
sources: the discrete setup,” preprint, 2014.
[25] G. Schiebinger, E. Robeva, and B. Recht, “Superresolution without separation,” in Computational Advances in Multi-Sensor Adaptive Processing
(CAMSAP), 2015 IEEE 6th International Workshop on, pp. 45–48, IEEE,
2015.
[26] M. Grant, S. Boyd, and Y. Ye, “Cvx: Matlab software for disciplined
convex programming,” 2008.
[27] C. Fernandez-Granda, G. Tang, X. Wang, and L. Zheng, “Demixing
sines and spikes: Robust spectral super-resolution in the presence of
outliers,” Information and Inference: A Journal of the IMA, 2016.

