# On the Uniqueness of Solutions for
the Basis Pursuit in the Continuum

Thomas Debarre, Quentin Denoyelle, Julien Fageot

###### Abstract

This paper studies the continuous-domain inverse problem of recovering Radon
measures on the one-dimensional torus from low-frequency Fourier coefficients,
where $K_{c}$ is the cutoff frequency. Our approach consists in minimizing the
total-variation norm among all Radon measures that are consistent with the
observations. We call this problem the basis pursuit in the continuum (BPC).
We characterize the solution set of (BPC) in terms of uniqueness and describe
its sparse solutions which are sums of few signed Dirac masses. The
characterization is determined by the spectrum of a Toeplitz and Hermitian-
symmetric matrix that solely depends on the observations. More precisely, we
prove that (BPC) has a unique solution if and only if this matrix is neither
positive definite nor negative definite. If it has both a positive and
negative eigenvalue, then the unique solution is the sum of at most $2K_{c}$
Dirac masses, with at least one positive and one negative weight. If this
matrix is positive (respectively negative) semi-definite and rank deficient,
then the unique solution is composed of a number of Dirac masses equal to the
rank of the matrix, all of which have nonnegative (respectively nonpositive)
weights. Finally, in cases where (BPC) has multiple solutions, we demonstrate
that there are infinitely many solutions composed of $K_{c}+1$ Dirac masses,
with nonnegative (respectively nonpositive) weights if the matrix is positive
(respectively negative) definite.

##  1 Introduction

In recent years, total-variation (in the sense of measure) regularization
techniques have proved to be very fruitful to solve continuous-domain linear
inverse problems with a sparsity prior. These techniques rely on solid
theoretical foundations [1, 2, 3, 4, 5, 6], but also on many algorithmic
advances [2, 7, 8, 9, 10], and have data-science applications [7, 11, 12, 13].
It is well known that their discrete-domain counterparts (_i.e._ , $\ell^{1}$
regularization methods) lead to variational problems whose solutions are not
necessarily unique [14]. Our goal in this paper is to provide a systematic
study of the uniqueness and of the main properties of the solutions of the
total-variation norm minimization problem when the low-frequency Fourier
coefficients of the signal are prescribed.

###  1.1 Reconstruction via Total-Variation Minimization

Let $\mathbb{T}=\mathbb{R}/2\pi\mathbb{Z}$ be the $1$D torus. We study the
problem recovering _real_ Radon measures $w\in\mathcal{M}(\mathbb{T})$ defined
on the domain $\mathbb{T}$ based on their low-frequency Fourier coefficients

$\displaystyle\forall k\in\mathbb{Z},\ |k|\leq
K_{c},\quad\widehat{w}[k]=y_{k},$ (1)

where $K_{c}\in\mathbb{N}$ denotes the cutoff frequency and
${\bm{y}}=(y_{-K_{c}},\ldots,y_{-1},y_{0},y_{1},\ldots,y_{K_{c}})\in\mathbb{C}^{2K_{c}+1}$
are the observations. As the measures $w\in\mathcal{M}(\mathbb{T})$ are real,
we must have $y_{0}\in\mathbb{R}$ and for all $k\in\\{1,\ldots,K_{c}\\}$,
$y_{k}=\overline{y_{-k}}$. Therefore, the Toeplitz matrix

$\displaystyle\bm{\mathrm{T}}_{\bm{y}}=\begin{pmatrix}y_{0}&y_{1}&\cdots&\cdots&y_{K_{c}}\\\
y_{-1}&y_{0}&y_{1}&\cdots&y_{K_{c}-1}\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
y_{-K_{c}+1}&\cdots&y_{-1}&y_{0}&y_{1}\\\
y_{-K_{c}}&\cdots&\cdots&y_{-1}&y_{0}\\\
\end{pmatrix}\in\mathbb{C}^{(K_{c}+1)\times(K_{c}+1)},$ (2)

which is at the core of our main contribution, is also Hermitian symmetric.
Moreover, the observation vector $\bm{y}\in\mathbb{C}^{2K_{c}+1}$ has only
$2K_{c}+1$ (real) degrees of freedom.

The recovery of a periodic Radon measure from finitely many observations is
clearly an ill-posed problem. Therefore, we choose to formulate the
reconstruction task as a regularized optimization problem using a sparsity
prior. More precisely, in this paper, we consider the problem

$\displaystyle\underset{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)={\bm{y}}}{\inf}\ \left\lVert w\right\rVert_{\mathcal{M}},$ (3)

where $\bm{\nu}:\mathcal{M}(\mathbb{T})\to\mathbb{C}^{2K_{c}+1}$ is the
measurement vector of Fourier coefficients

$\displaystyle\forall
w\in\mathcal{M}(\mathbb{T}),\quad\bm{\nu}(w)=(\widehat{w}[-K_{c}],\ldots,\widehat{w}[0],\ldots,\widehat{w}[K_{c}]),$
(4)

and $\left\lVert\cdot\right\rVert_{\mathcal{M}}$ is the total-variation (TV)
norm on the space of Radon measures $\mathcal{M}(\mathbb{T})$. The TV norm can
be seen as an extension of the $\ell^{1}$ norm to the continuous domain. The
choice of the TV norm promotes sparse continuous-domain reconstruction, and
has recently received a lot of attention (see Section 1.2). In the following,
we name the Problem (3), the _basis pursuit in the continuum_ (BPC), in
reference to its discrete-domain counterpart, the basis pursuit in [15].

###  1.2 Related Works

#### Optimization over Radon measures.

The historical motivation to consider the total-variation as a regularization
norm was to extend discrete $\ell^{1}$ regularization techniques, used in the
theory of compressed sensing to recover sparse vectors [16, 17, 18, 19], for
the recovery of continuous-domain Dirac masses. The goal is to recover point
sources, modelled as a sum of Dirac masses, from finitely many measurements.
This question has received considerable attention in the 21st century,
including methods that are not based on TV regularization, such as finite rate
of innovation (FRI) techniques [20, 21] and Prony’s methods [22, 23, 24].
Several data-science problems can be formulated as a continuous-domain Dirac
recovery problem, including radio-astronomy [25], super-resolution microscopy
[9], or 3D image deconvolution [12]. It is worth noting that other infinite-
dimensional extensions of the compressed sensing framework have been proposed
[26, 27, 19, 28, 29].

The study of optimization problems over the space of Radon measures can be
traced back to the pioneering works of Beurling [30], where Fourier-domain
measurements were also considered. In the early 2010’s, the works of De Castro
and Gamboa [31], Candès and Fernandez-Granda [1, 32], and Bredies and
Pikkarainen [2] considered optimization tasks of the form (3) (or its
penalized version), with both theoretical analyses and novel algorithmic
approaches to recover a sparse-measure solution, in the continuum [33, 7, 34,
35, 36, 37, 38, 12, 39]. The existence of sparse-measure solutions, _i.e._ ,
solutions of the form $\sum_{k=1}^{K}a_{k}\delta_{x_{k}}$, where
$K\in\mathbb{N}^{*}$, $a_{k}\in\mathbb{R}$, and $\delta_{x_{k}}$ is the Dirac
mass at the location $x_{k}$, seems to have been proven for the first time in
[30] and was later improved by Fisher and Jerome in [40]. Since then, a
remarkable revival around TV optimization has occurred recently [41, 42, 43,
10, 44, 45].

#### Uniqueness results for TV optimization.

It is well know that finite-dimensional $\ell^{1}$-regularization, of which
the total-variation norm for Radon measures is the continuous-domain
generalization, can lead to nonunique solutions [14, 46]. This is also the
case for TV regularization. However, under some assumptions uniqueness may
hold. Many uniqueness results for constrained or penalized TV-based
optimization problems have thus been given in the literature, but from
different perspectives than the one studied in this paper.

Usually, the underlying assumption is that the observations ${\bm{y}}$ are
generated via sparse measure $w_{0}$ and the question becomes whether it is
possible to uniquely recover $w_{0}$, either exactly or in a stable way. In
[31], de Castro and Gamboa introduced the concept of _extrema Jordan type
measure_ (see [31, Definition 1]), which gives sufficient conditions on a
given signed (with positive and negative weights) sparse measure to be the
unique solution of a TV-based optimization problem. They also proved that when
the input measure is nonnegative, $k$-sparse and the number of measurements is
greater or equal than $2k+1$, then it is the unique solution of (3) if the
measurement operator is defined from a T-system. Note that it has recently
been proved [47, 48, 49, 50] that in the nonnegativity setting, a $k$-sparse
nonnegative measure can be uniquely recovered from at least $2k+1$
measurements and a nonnegativity constraint without the need for TV
minimization.

Candès and Fernandez-Granda also studied the super-resolution problem of
recovering a ground-truth sparse Radon measure $w_{0}$ from its low-frequency
measurements. They have shown that if the minimal distance between the spikes
of $w_{0}$ is large enough, then (3) has a unique solution, which is $w_{0}$
itself [1, Theorem 1.2]. Duval and Peyré identified the so-called
_nondegenerate source condition_ [3, Definition 5], under which the uniqueness
of the reconstruction together with the recovery of the support of the
underlying ground-truth sparse measure are shown. These results are based on
the key notion of dual certificates, which will also play an important role in
our work. This notion has been introduced for discrete compressed sensing
problems in [51] and connected to TV-based optimization problems in [31].

All these works are clearly related to this paper. However, the approach we
propose here is different: we aim at characterizing the cases of uniqueness
directly over the measurement vector $\bm{y}$, and we are agnostic to the
ground-truth signal that generated it. The closest work in this direction is
our recent publication [52]. We provide a full description of the solution set
of non-periodic TV optimization problems with a regularization operator
$\mathrm{D}^{2}$, where $\mathrm{D}$ is the derivative operator, and spatial
sampling measurements. These problems lead to piecewise-linear
reconstructions. Our work also includes the characterization of the cases of
uniqueness [52, Proposition 6 and Theorem 2].

#### The problem of moments.

This problem, or its extension the _generalized problem of moments_ [53, 54],
is a classical one where one seeks to recover a measure from a sequence of its
(potentially generalized) moments. This problem covers many applications in
various fields, including Fourier-domain measurements, which are simply
moments of trigonometrical polynomials. As a result, the tools developed in
this domain can be harnessed, for example, to solve numerically (3) using
semi-definite programming formulations by generalizing [1] to the multivariate
case [55, 56]. Moreover, there are many existence results for the problem of
moments. In [57, Theorem 6.12], Curto and Fialkow prove the existence of a
sparse nonnegative measure $w_{0}\in\mathcal{M}(\mathbb{T})$ solution of the
truncated trigonometric moment problem (as referred to in [57])

$\displaystyle w\in\mathcal{M}(\mathbb{T}),\quad{\bm{y}}=\bm{\nu}(w),$ (5)

if and only $\bm{\mathrm{T}}_{\bm{y}}$ is positive semi-definite. Furthermore,
solution $w_{0}$ has $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})$ Dirac
masses. Additionally, when $\bm{\mathrm{T}}_{\bm{y}}$ is invertible, there
exist infinitely many such $w_{0}$. When it is not, $w_{0}$ is unique. The
contributions of [57] and their relation to ours will be discussed more
precisely in Remark 5.

###  1.3 Contributions

The existence of a solution to problem (3) is well established and can be
obtained from the direct method in the calculus of variation. Moreover, it is
known that there is always at least one sparse solution composed of at most
$2K_{c}+1$ Dirac masses [40]. However, the solution is in general not unique
(the simplest case of nonuniqueness is with $K_{c}=0$), and previous works
studying this question often start by assuming that the measurements come from
a particular input signal. In this paper, we focus on

  1. 1.

characterizing all the cases of uniqueness for (3);

  2. 2.

describing the sparse solutions, _e.g._ the bounds on the number of Dirac
masses and the signs of the weights;

from simple conditions depending _only_ on the measurement vector ${\bm{y}}$,
involving in particular the matrix $\bm{\mathrm{T}}_{\bm{y}}$. The novelty of
our approach thus lies in the fact that we are able to provide relatively deep
information on the form of the sparse solutions of (3) and answer in all cases
the question of uniqueness agnostically to the input signal that generated
${\bm{y}}$.

Our first contribution, Theorem 1 in Section 3.1, provides several equivalent
conditions for the solution set of (3) to be composed of only nonnegative
measures. We prove that if one of these conditions is not satisfied _and_
$y_{0}\geq 0$, then there is a unique solution composed of at most $2K_{c}$
Dirac masses, with at least one positive and one negative weight. One of these
equivalent conditions is used, in Corollary 1, to formulate a simple criterion
on the magnitudes of the entries of ${\bm{y}}$ which is a sufficient condition
for uniqueness. Theorem 1 can of course be readily adapted to the nonpositive
case.

Theorem 1 does not cover all the situations that may arise since it does not
adjudicate the uniqueness of a solution to (3) when the solution set is
composed of only nonnegative (or nonpositive) measures. This limitation is
tackled in our main contribution, Theorem 2, in Section 3.2, which we state
below. We recall that the Toeplitz matrix $\bm{\mathrm{T}}_{\bm{y}}$ is given
in (2).

######  Theorem.

The solution set of problem (3) can be characterized as follows:

  1. a)

If $\bm{\mathrm{T}}_{\bm{y}}$ has at least one negative and one positive
eigenvalue, then (3) has a unique solution composed of at most $2K_{c}$ Dirac
masses, with at least one positive and one negative weight;

  2. b)

If $\bm{\mathrm{T}}_{\bm{y}}$ is positive, respectively negative, semi-
definite and $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})<K_{c}+1$, then
(3) has a unique solution composed of exactly
$\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})$ positive, respectively
negative, Dirac masses;

  3. c)

If $\bm{\mathrm{T}}_{\bm{y}}$ is positive, respectively negative, definite
(which implies that $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})=K_{c}+1$),
then (3) has infinitely many solutions, and among sparse solutions none with
less than $K_{c}+1$ Dirac masses and uncountably many of them composed of
$K_{c}+1$ positive, respectively negative, Dirac masses.

This theorem provides information on the form of the sparse solutions, from
conditions on the spectrum of the Hermitian Toeplitz matrix
$\bm{\mathrm{T}}_{\bm{y}}$. Moreover, all possible scenarios are covered since
all vectors ${\bm{y}}\in\mathbb{R}\times\mathbb{C}^{K_{c}}$ fall in one single
case of the theorem. Therefore, it also yields a final answer to the question
of uniqueness.

In the case when $\bm{\mathrm{T}}_{\bm{y}}$ is positive (or negative) semi-
definite and rank deficient, our result can be derived from [57, Theorem
6.12], once we admit that any nonnegative (or nonpositive) measures that match
the observations is a solution of (3)111For a more detailed discussion on this
matter, see Remark 5.. Our contributions are therefore closely related to this
literature. However our framework is also different, and one of the novelty of
our work lies in the bridges made between these related results in order to
answer the question of uniqueness for (BPC). Consequently, we also choose to
present, as much as possible, our contributions in a self-contained fashion.
The proofs are based upon known tools from the field of point-source recovery:

  * •

dual certificates (see Proposition 1);

  * •

the Herglotz theorem (see Proposition 4), which characterizes positive sparse
measures in terms of their Fourier coefficients;

  * •

the Caratheodory-Pisarenko-Fejer decomposition [58, 59, 60] (see Proposition
7), which leads to algorithms such as MUSIC [22].

##  2 Mathematical Preliminaries

In Section 2.1, we introduce the mathematical background of this paper. We
also present the optimization problem of interest. In Section 2.2, we then
remind the main tools from duality theory that we use for studying the total-
variation minimization problem.

###  2.1 Periodic Radon Measures and basis pursuit in the continuum

#### Radon measures.

Let $\mathcal{M}(\mathbb{T})$ be the space of periodic _real_ Radon measures.
By the Riesz-Markov theorem [61], $\mathcal{M}(\mathbb{T})$ is the continuous
dual of the space $\mathcal{C}(\mathbb{T})$ of continuous periodic real
functions endowed with the supremum norm
$\left\lVert\cdot\right\rVert_{\infty}$. The total-variation norm on
$\mathcal{M}(\mathbb{T})$ is the dual norm associated to
$(\mathcal{C}(\mathbb{T}),\left\lVert\cdot\right\rVert_{\infty})$ and is thus
given by

$\displaystyle\left\lVert
w\right\rVert_{\mathcal{M}}=\sup_{\varphi\in\mathcal{C}(\mathbb{T}),\
\left\lVert\varphi\right\rVert_{\infty}\leq 1}\left\langle
w,\,\varphi\right\rangle.$ (6)

The normed space
$(\mathcal{M}(\mathbb{T}),\left\lVert\cdot\right\rVert_{\mathcal{M}})$ is then
a Banach space. The total-variation norm can be seen as the extension to the
continuum of the $\ell^{1}$ norm for vectors, as for any sparse measure

$\displaystyle
w_{{\bm{a}},{\bm{x}}}=\sum_{k=1}^{K}a_{k}\delta_{x_{k}},\quad\text{with}\quad
K\in\mathbb{N}^{*},\forall k\in\\{1,\ldots,K\\},\ a_{k}\in\mathbb{R},\
x_{k}\in\mathbb{T},$ (7)

where the locations of the Dirac masses $x_{k}$ are pairwise distinct, we have

$\displaystyle\left\lVert
w_{{\bm{a}},{\bm{x}}}\right\rVert_{\mathcal{M}}=\left\lVert{\bm{a}}\right\rVert_{1}.$
(8)

We also consider the set of positive Radon measures
$\mathcal{M}_{+}(\mathbb{T})$, which are Radon measures $w$ such that
$\left\langle w,\,\varphi\right\rangle\geq 0$ for any positive continuous
function $\varphi$ on $\mathbb{T}$. The set of probability measures, _i.e._
nonnegative measures $w$ with total-variation norm $\left\lVert
w\right\rVert_{\mathcal{M}}=1$, is denoted by $\mathcal{P}(\mathbb{T})$.

#### Forward operator.

We consider the measurement operator given by

$\displaystyle\bm{\nu}:w\in\mathcal{M}(\mathbb{T})\mapsto(\widehat{w}[-K_{c}],\ldots,\widehat{w}[0],\ldots\widehat{w}[K_{c}])\in\mathbb{C}^{K_{c}}\times\mathbb{R}\times\mathbb{C}^{K_{c}},$
(9)

where $K_{c}\in\mathbb{N}$ is the cutoff frequency and for all $|k|\leq
K_{c}$,
$\widehat{w}[k]=\int_{0}^{2\pi}\mathrm{e}^{-\mathrm{i}kt}\mathrm{d}w(t)$ is
the $k$-th Fourier coefficient of $w$. The operator $\bm{\nu}$ is a low-pass
operator that only keeps the low-frequency Fourier coefficients.

#### Optimization problem.

Let
${\bm{y}}=(y_{-K_{c}},\ldots,y_{0},\ldots,y_{K_{c}})\in\mathbb{C}^{2K_{c}+1}$
such that222These requirements on the observations vector ${\bm{y}}$ come from
the fact that otherwise, the equation $\bm{\nu}(w)={\bm{y}}$ has no solution
in $\mathcal{M}(\mathbb{T})$, since $w$ is a real Radon measure.

$\displaystyle y_{0}\in\mathbb{R}\quad\text{and}\quad\forall
k\in\\{1,\ldots,K_{c}\\},\ y_{k}=\overline{y_{-k}},$ (10)

be a given observations vector. We aim to solve the linear inverse problem
$\bm{\nu}(w)={\bm{y}}$. We introduce our terminology for solutions of this
problem in the following definition.

######  Definition 1.

Let ${\bm{y}}\in\mathbb{C}^{2K_{c}+1}$ given as in Equation (10). We say that
$w\in\mathcal{M}(\mathbb{T})$ is a _representing measure for ${\bm{y}}$_, if
$w$ satisfies $\bm{\nu}(w)={\bm{y}}$.

This linear inverse problem is ill-posed, as it has infinitely many
representing measures. To tackle this issue, we choose to favor sparse
solutions. Our approach consists in solving the following optimization problem

$\displaystyle\underset{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)={\bm{y}}}{\min}\ \left\lVert w\right\rVert_{\mathcal{M}}.$ (BPC)

A solution of (BPC) (which is known to exist) therefore has the minimal total-
variation norm among all representing measures for ${\bm{y}}$. As the total-
variation norm is an extension of the $\ell^{1}$ norm, it is known to promote
sparse solutions (composed of a sum of Dirac masses). We denote this problem
the basis pursuit in the continuum (BPC) as a tribute to its finite-
dimensional counterpart, the Basis Pursuit [15].

###  2.2 Dual Certificates for the basis pursuit in the continuum

The analysis of (BPC) benefits from the theory of duality for infinite-
dimensional convex optimization, as exposed for instance by Ekeland and Temam
in [62]. This line of research has proven to be fruitful to study optimization
on measure spaces [31, 32, 3, 63, 42, 52]. We mostly rely on the concepts and
results exposed in [3, 52], but very similar tools can be found elsewhere [31,
32]. Considering the dual problem to (BPC) and writing the optimality
conditions that link the solutions of both problems333Note that dual
certificates always exist for the (BPC) with Fourier measurements [1]. leads
to the notion of _dual certificates_ , which are continuous functions on
$\mathbb{T}$ satisfying some conditions (see Proposition 1 below). In
particular, dual certificates enable to _certify_ that some
$w\in\mathcal{M}(\mathbb{T})$ is a solution of (BPC) and to localize its
support. In the next definition, we introduce some notations that ease the
related statements. We recall that a Radon measure
$w\in\mathcal{M}(\mathbb{T})$ can be uniquely decomposed as $w=w_{+}-w_{-}$,
where $w_{+}$ and $w_{-}$ are nonnegative measures (Jordan decomposition).

######  Definition 2.

Let $w\in\mathcal{M}(\mathbb{T})$. We define the _signed support_ of $w$ as

$\displaystyle\operatorname{supp}_{\pm}(w)=\operatorname{supp}(w_{+})\times\\{1\\}\cup\operatorname{supp}(w_{-})\times\\{-1\\},$
(11)

where $\operatorname{supp}(\tilde{w})$ is the support of
$\tilde{w}\in\mathcal{M}(\mathbb{T})$.

Let $\eta\in\mathcal{C}(\mathbb{T})$. The positive and negative saturation
sets of $\eta$ are given by

$\displaystyle\operatorname{sat}_{+}(\eta)=\eta^{-1}(\\{1\\})\quad\text{and}\quad\operatorname{sat}_{-}(\eta)=\eta^{-1}(\\{-1\\}),$
(12)

respectively. Finally, we define the _signed saturation set_ of $\eta$ as

$\displaystyle\operatorname{sat}_{\pm}(\eta)=\operatorname{sat}_{+}(\eta)\times\\{1\\}\cup\operatorname{sat}_{-}(\eta)\times\\{-1\\}.$
(13)

Now, we give two results which help us to characterize the cases of uniqueness
for (BPC), in our main contribution Theorem 2. The next proposition introduces
formally the notion of dual certificates for the (BPC) problem.

######  Proposition 1.

There exists a function $\eta\in\mathcal{C}(\mathbb{T})$, which is a real
trigonometrical polynomial of degree at most $K_{c}$, satisfying
$\left\lVert\eta\right\rVert_{\infty}\leq 1$ and such that for any solution
$w_{0}\in\mathcal{M}(\mathbb{T})$ of (BPC), we have one of the following
equivalent conditions:

  * •

$\left\langle w_{0},\,\eta\right\rangle=\left\lVert
w_{0}\right\rVert_{\mathcal{M}}$;

  * •

$\operatorname{supp}_{\pm}(w_{0})\subset\operatorname{sat}_{\pm}(\eta)$.

Such a function $\eta$ is denoted as a _dual certificate_.

Proposition 1 is stated in some other, nonetheless equivalent, form in [3,
Proposition 3], where dual certificates of the optimization problem (BPC) are
studied444Duval and Peyré consider more general measurement operators whose
image can lie in a Hilbert space and exemplify their results for low-frequency
measurements.. A key role is played by the adjoint operator
$\bm{\nu}^{*}:\mathbb{C}^{K_{c}}\times\mathbb{R}\times\mathbb{C}^{K_{c}}\rightarrow\mathcal{C}(\mathbb{T})$
(denoted by $\Phi^{*}$ in [3]), due to the fact that dual certificates must be
in $\mbox{Im}(\bm{\nu}^{*})$. In our setup, we have that

$\bm{\nu}^{*}(c_{-K_{c}},\ldots,c_{-1},c_{0},c_{1},\ldots,c_{K_{c}})=\sum_{|k|\leq
K_{c}}c_{k}e_{k},$ (14)

where $e_{k}:t\in\mathbb{T}\mapsto\mathrm{e}^{-\mathrm{i}kt}$. The role of
real trigonometric polynomials in Proposition 1 is explained by the fact that
the vectors
${\bm{c}}\in\mathbb{C}^{K_{c}}\times\mathbb{R}\times\mathbb{C}^{K_{c}}$ are
Hermitian symmetric. We do not provide a detailed proof of Proposition 1,
since it has already been exposed elsewhere. It is for instance done in [52,
Propositions 1 & 2] in a different setting, but the arguments can be readily
adapted.

An important consequence of Proposition 1 for the study of uniqueness of
(BPC), is the following proposition that can also be deduced from [3] (see
also [31]).

######  Proposition 2.

If there exists a nonconstant555In the more general case studied in [3], this
corresponds to the nondegeneracy condition of the dual certificate. dual
certificate for the problem (BPC), then it has a unique solution of the form
$w=\sum_{k=1}^{K}a_{k}\delta_{x_{k}}$ with $K\leq 2K_{c}$ and
$a_{k}\in\mathbb{R}$, $x_{k}\in\mathbb{T}$.

For the sake of completeness, a proof of Proposition 2 can be found in
Appendix A.

##  3 Toeplitz Characterization of (BPC)

In this section, we present our contributions. Theorem 1 in Section 3.1 first
provides several equivalent conditions which ensure that the solution set of
(BPC) is solely composed of nonnegative (or nonpositive) measures. This can be
proved not to hold when a simple criterion on the coefficient values of
${\bm{y}}$ is satisfied, see Corollary 1. By the second part of Theorem 1,
this leads to the existence of a unique sparse solution composed of at most
$2K_{c}$ Dirac masses, with at least one positive and one negative weight.
Theorem 1 paves the way towards our main contribution, Theorem 2 in Section
3.2, which characterizes the solution set of (BPC) from simple condition on
the spectrum of the Toeplitz and Hermitian symmetric matrix
$\bm{\mathrm{T}}_{\bm{y}}$ introduced in (2). In particular, it gives all the
cases where uniqueness holds, see Corollary 2.

###  3.1 A New Criterion of Uniqueness for (BPC)

Before stating the main results of this section, let us first prove, in the
next lemma, that the total-variation norm of a Radon measure upper-bounds its
Fourier coefficients. Lemma 1 also provides elementary characterizations for
nonnegative Radon measures that we use in Theorem 1.

######  Lemma 1.

Let $w\in\mathcal{M}(\mathbb{T})$. Then,

  1. 1.

For any $k\in\mathbb{Z}$, we have $|\widehat{w}[k]|\leq\left\lVert
w\right\rVert_{\mathcal{M}}$;

  2. 2.

$w\in\mathcal{M}_{+}(\mathbb{T})$ if and only if $\left\lVert
w\right\rVert_{\mathcal{M}}=\widehat{w}[0]$;

  3. 3.

$w\in\mathcal{P}(\mathbb{T})$ if and only if $\left\lVert
w\right\rVert_{\mathcal{M}}=\widehat{w}[0]=1$.

###### Proof.

We distinguish the three cases of the lemma.

  1. 1.

The result is obvious for $k=0$ since

$|\widehat{w}[0]|=|\langle
w,1\rangle|\leq\sup_{\varphi\in\mathcal{C}(\mathbb{T}),\
\left\lVert\varphi\right\rVert_{\infty}\leq 1}\langle w,\varphi\rangle=\lVert
w\rVert_{\mathcal{M}},$ (15)

by picking both $\varphi\equiv 1$ and $\varphi\equiv-1$. It is worth noting
that this argument does not work for $k\neq 0$ since
$\widehat{w}[k]=\int_{0}^{2\pi}\mathrm{e}^{-\mathrm{i}kt}\mathrm{d}w(t)$ where
$t\mapsto\mathrm{e}^{-\mathrm{i}kt}$ is a _complex_ continuous function. Hence
$\widehat{w}[k]$ cannot be bounded by $\left\lVert
w\right\rVert_{\mathcal{M}}$ since
$\left\lVert\cdot\right\rVert_{\mathcal{M}}$ is the dual norm to the space of
_real_ continuous functions (endowed with the uniform norm). Let us fix $k\neq
0$ and assume that $\widehat{w}[k]=r\mathrm{e}^{\mathrm{i}\alpha}\neq 0$ with
$r>0$ and $\alpha\in[0,2\pi)$ (the case $\widehat{w}[k]=0$ is obvious). Let
$\psi:t\in\mathbb{T}\mapsto\mathrm{e}^{-\mathrm{i}\alpha}\mathrm{e}^{-\mathrm{i}kt}$.
Then, we have

$\int_{0}^{2\pi}\psi(t)\mathrm{d}w(t)=\mathrm{e}^{-\mathrm{i}\alpha}\widehat{w}[k]=r$
(16)

and

$\int_{0}^{2\pi}\overline{\psi(t)}\mathrm{d}w(t)=\overline{\int_{0}^{2\pi}\psi(t)\mathrm{d}\bar{w}(t)}=\overline{\int_{0}^{2\pi}\psi(t)\mathrm{d}w(t)}=r=\int_{0}^{2\pi}\psi(t)\mathrm{d}w(t).$
(17)

Hence, setting $\kappa=\Re(\psi)$, we have that
$\kappa\in\mathcal{C}(\mathbb{T})$ with
$\left\lVert\kappa\right\rVert_{\infty}\leq\sup_{x\in\mathbb{T}}|\psi(x)|=1$
and

$|\widehat{w}[k]|=r=\left\langle
w,\,\kappa\right\rangle\leq\sup_{\varphi\in\mathcal{C}(\mathbb{T}),\
\left\lVert\varphi\right\rVert_{\infty}\leq 1}\left\langle
w,\,\varphi\right\rangle=\left\lVert w\right\rVert_{\mathcal{M}},$ (18)

which concludes the proof.

  2. 2.

Any $w\in\mathcal{M}(\mathbb{T})$ can be uniquely decomposed as
$w=w_{+}-w_{-}$ where $w_{+}$, $w_{-}\in\mathcal{M}_{+}(\mathbb{T})$ (Jordan
decomposition). Moreover, $\lVert w\rVert_{\mathcal{M}}=\lVert
w_{+}\rVert_{\mathcal{M}}+\lVert w_{-}\rVert_{\mathcal{M}}=\langle
w_{+},1\rangle+\langle w_{-},1\rangle=\widehat{w}_{+}[0]+\widehat{w}_{-}[0]$.
Then,

$w\in\mathcal{M}_{+}(\mathbb{T})\ \Leftrightarrow\ w_{-}=0\ \Leftrightarrow\
\widehat{w}_{-}[0]=0\ \Leftrightarrow\ \lVert
w\rVert_{\mathcal{M}}=\widehat{w}_{+}[0]=\widehat{w}[0],$ (19)

which concludes the proof.

  3. 3.

Finally, $w\in\mathcal{M}_{+}(\mathbb{T})$ is a probability measure if and
only if $\lVert w\rVert_{\mathcal{M}}=1$, which concludes the proof.

∎

Next, we provide a lower bound on the minimal value of (BPC).

######  Lemma 2.

We have that

$\underset{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)=\bm{y}}{\min}\quad\left\lVert
w\right\rVert_{\mathcal{M}}\geq\max_{0\leq k\leq K_{c}}|y_{k}|.$ (20)

###### Proof.

We know that (BPC) has at least one solution $w_{0}\in\mathcal{M}(\mathbb{T})$
that reaches its minimum value. Then, according to Lemma 1, we have
$\left\lVert w_{0}\right\rVert_{\mathcal{M}}\geq|\widehat{w_{0}}[k]|=|y_{k}|$
for all $-K_{c}\leq k\leq K_{c}$, which yields (20). ∎

We can now state the main result of this section.

######  Theorem 1.

The following conditions are equivalent:

  1. 1.

there exists $w_{0}\in\mathcal{M}_{+}(\mathbb{T})$ such that
$\bm{\nu}(w_{0})=\bm{y}$;

  2. 2.

the solution set of (BPC) is $\\{w\in\mathcal{M}_{+}(\mathbb{T}):\
\bm{\nu}(w)=\bm{y}\\}$;

  3. 3.

we have

$y_{0}=\underset{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)=\bm{y}}{\min}\quad\left\lVert w\right\rVert_{\mathcal{M}}.$ (21)

Assume that $y_{0}\geq 0$. Additionally, if the above equivalence is not
satisfied, then (BPC) has a unique solution, composed of at most $2K_{c}$
Dirac masses, with at least one positive and one negative weight.

###### Proof.

Let us first prove that the items 1, 2, 3 are equivalent.

#####  1$\Rightarrow$3.

Set $m=\underset{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)=\bm{y}}{\min}\left\lVert w\right\rVert_{\mathcal{M}}$. By Lemma 1,
we have, for any $w\in\mathcal{M}(\mathbb{T})$, the equivalence

$\displaystyle w\in\mathcal{M}_{+}(\mathbb{T})\Longleftrightarrow\left\lVert
w\right\rVert_{\mathcal{M}}=\widehat{w}[0].$ (22)

As a result, we get that $m\leq\left\lVert
w_{0}\right\rVert_{\mathcal{M}}=\widehat{w_{0}}[0]=y_{0}$. Finally, from Lemma
2, we have that $m\geq y_{0}$, which yields $m=y_{0}$666Note that we also
proved that $w_{0}$ is solution of (BPC)..

#####  3$\Rightarrow$2.

Let $w_{0}\in\mathcal{M}(\mathbb{T})$ be a solution of (BPC). Therefore,
$\widehat{w_{0}}[0]=y_{0}=\left\lVert w_{0}\right\rVert_{\mathcal{M}}$, and by
Lemma 1, we deduce that $w_{0}$ is a nonnegative measure that satisfies the
constraints $\bm{\nu}(w_{0})=\bm{y}$.

#####  2$\Rightarrow$1.

This is a direct consequence of the fact that the solution set of (BPC) is
non-empty.

Next, if the equivalence is not satisfied, it implies that there is no
nonnegative measure solution. Let $\eta$ be a dual certificate for problem
(BPC), as given by Proposition 1. We have $\left\lVert
w_{0}\right\rVert_{\mathcal{M}}=\left\langle w_{0},\,\eta\right\rangle$ for
any solution $w_{0}\in\mathcal{M}(\mathbb{T})$ of (BPC). Using Proposition 2,
we know that if the dual certificate is nonconstant, then the solution of
(BPC) is unique and composed of at most $2K_{c}$ Dirac masses, with at least
one negative and one positive weight. Let us assume by contradiction that
$\eta$ is constant _i.e._ , $\eta=t\mapsto\varepsilon$ with
$\varepsilon\in\\{\pm 1\\}$. We thus have

$\left\lVert w_{0}\right\rVert_{\mathcal{M}}=\left\langle
w_{0},\,\eta\right\rangle=\varepsilon\widehat{w_{0}}[0]=\varepsilon y_{0}.$
(23)

This implies in particular that $\varepsilon y_{0}>0$, since $w_{0}\neq 0$ due
to the nonnegativity of $w_{0}$. Yet we have $y_{0}\geq 0$, which, in turn,
implies that $\varepsilon=1$. This shows that $\left\lVert
w_{0}\right\rVert_{\mathcal{M}}=\widehat{w_{0}}[0]$, which, together with
Lemma 2, yields $w_{0}\in\mathcal{M}_{+}(\mathbb{T})$. This contradicts our
initial assumption, which concludes the proof. ∎

######  Remark 1.

The equivalent conditions of Theorem 1 can be easily adapted to the
nonnegative case by changing the signs accordingly. Moreover, Theorem 1
implies that if there is no nonnegative and no nonpositive representing
measure for ${\bm{y}}$, then (BPC) has a unique solution.

######  Remark 2.

In Theorem 1, the equivalent conditions show that there is a nonnegative
representing measure for ${\bm{y}}$ if and only if the solution set of (BPC)
is composed of all the nonnegative representing measures for ${\bm{y}}$. This
suggests that minimizing the TV norm plays no role in the context of non-
negative measures and can be replaced by a simple nonnegativity constraint.
This is consistent with recent results [47, 48, 49, 50] which proved, in
different setups, that when the observations ${\bm{y}}$ are generated by a
nonnegative measure, then replacing the TV norm with a nonnegativity
constraint is enough to uniquely recover the input measure, provided that the
number of measurements is sufficient. From those contributions, we see that
the equivalence between Items 1 and 2 is not new. However, the difference with
these works lies in the fact that we do not assume that ${\bm{y}}$ is
generated by a nonnegative sparse measure. Moreover, our main goal with
Theorem 1 is elsewhere. We prove that when the equivalence is not satisfied,
then we must be in a case of uniqueness, which is, to the best of our
knowledge, a new result.

From Theorem 1 and Lemma 2, we can deduce a simple criterion on the magnitude
of the coefficients of ${\bm{y}}$ which ensures that the solution of (BPC) is
unique. This criterion appears to be practically fruitful since uniqueness
follows trivially for a large class of observation vectors $\bm{y}$.

######  Corollary 1.

If $|y_{0}|<|y_{k_{0}}|$, for some $k_{0}\neq 0$, then (BPC) has a unique
solution, composed of at most $2K_{c}$ Dirac masses, with at least one
positive and one negative weight.

###### Proof.

By Lemma 2, we have $\min_{w\in\mathcal{M}(\mathbb{T}),\
\bm{\nu}(w)=\bm{y}}\left\lVert
w\right\rVert_{\mathcal{M}}\geq|y_{k_{0}}|>|y_{0}|$. This implies that the
equivalent conditions of Theorem 1 do not hold, as Item 3 is not valid. We are
thus in the uniqueness scenario of Theorem 1. ∎

###  3.2 Characterization of Solutions of (BPC) Using
$\bm{\mathrm{T}}_{\bm{y}}$

In this section, we prove, in Theorem 2, that the sign of the solutions of
(BPC) is directly related to spectral properties of the matrix
$\bm{\mathrm{T}}_{\bm{y}}$ formed from the observation vector ${\bm{y}}$
defined as

$\displaystyle\bm{\mathrm{T}}_{\bm{y}}=\begin{pmatrix}y_{0}&y_{1}&y_{2}&\ldots&y_{K_{c}}\\\
y_{-1}&y_{0}&y_{1}&\ldots&y_{K_{c}-1}\\\
y_{-2}&y_{-1}&y_{0}&\ldots&y_{K_{c}-2}\\\ \vdots&&&\ddots&\\\
y_{-{K_{c}}}&y_{-K_{c}+1}&y_{-K_{c}+2}&\ldots&y_{0}\\\ \end{pmatrix}.$ (24)

More precisely, as $\bm{\mathrm{T}}_{\bm{y}}$ is Hermitian symmetric, one of
the following three statements must hold:

  * •

$\bm{\mathrm{T}}_{\bm{y}}$ has at least one negative and one positive
eigenvalue;

  * •

$\bm{\mathrm{T}}_{\bm{y}}$ is positive or negative semi-definite and rank
deficient;

  * •

$\bm{\mathrm{T}}_{\bm{y}}$ is positive or negative-definite.

In Theorem 2, we prove that each of these scenarios leads to different
properties of the solution set of (BPC), all expressed in terms of the nature
of the sign of the solutions and of uniqueness.To this end, we first
characterize the existence of a nonnegative representing measure for
${\bm{y}}$ in terms of positive semi-definiteness of the matrix
$\bm{\mathrm{T}}_{\bm{y}}$ in Proposition 3. It can be obtained from [57,
Theorem 6.12], but we include for the sake of completeness.

######  Proposition 3.

The two following conditions are equivalent:

  1. 1.

there exists $w_{0}\in\mathcal{M}_{+}(\mathbb{T})$ such that
$\bm{\nu}(w_{0})=\bm{y}$;

  2. 2.

the Hermitian matrix
$\bm{\mathrm{T}}_{\bm{y}}\in\mathbb{C}^{(K_{c}+1)\times(K_{c}+1)}$, defined in
(24), is positive semi-definite.

###### Proof.

#####  1$\Rightarrow$2.

Let $w_{0}$ be a nonnegative representing measure for ${\bm{y}}$.
Consequently, by Proposition 4 in Appendix B, we have that
$\sum_{k,\ell\in\mathbb{Z}}\widehat{w_{0}}[k-\ell]z_{k}\overline{z}_{\ell}\geq
0$, for any complex sequence $(z_{k})_{k\in\mathbb{Z}}$ with finitely many
nonzero terms. In particular, restricting to sequences such that $z_{k}=0$ for
$k<0$ and $k>K_{c}$, we have that

$\sum_{k,\ell=0}^{K_{c}}\widehat{w_{0}}[k-\ell]z_{k}\overline{z}_{\ell}\geq
0.$ (25)

Since $\widehat{w_{0}}[k-\ell]=y_{k-\ell}$ for all
$k,\ell\in\\{0,\ldots,K_{c}\\}$, we deduce that $\bm{\mathrm{T}}_{\bm{y}}$ is
positive semi-definite.

#####  2$\Rightarrow$1.

We denote $\mathcal{P}_{K_{c}}(\mathbb{T})$ the space of real trigonometric
polynomials of degree at most $K_{c}$. Let us consider the linear mapping
$\Phi:\mathcal{P}_{K_{c}}(\mathbb{T})\rightarrow\mathbb{R}$ such that for all
$|k|\leq K_{c}$, $\Phi(e_{k})=y_{k}$. Then, $\Phi$ must be positive. Indeed,
let $p\in\mathcal{P}_{K_{c}}(\mathbb{T})$ such that $p\geq 0$. According to
Proposition 5 in Appendix B, $p$ can be written as $p=|q|^{2}$ for some
complex trigonometric polynomial $q=\sum_{k=0}^{K_{c}}z_{k}e_{k}$ with
$z_{k}\in\mathbb{C}$. This implies that
$p=\sum_{k,\ell=0}^{K_{c}}z_{k}\overline{z}_{\ell}e_{k-\ell}$ and therefore
that

$\Phi(p)=\sum_{k,\ell=0}^{K_{c}}y_{k-\ell}z_{k}\overline{z}_{\ell}=\left\langle\bm{\mathrm{T}}_{\bm{y}}{\bm{z}},\,{\bm{z}}\right\rangle\geq
0\quad\text{where}\quad{\bm{z}}=(z_{0},\ldots,z_{K_{c}})\in\mathbb{C}^{K_{c}+1}.$
(26)

Then, according to Proposition 6 in Appendix B, $\Phi$ can be extended to a
positive, linear, and continuous functional from $\mathcal{C}(\mathbb{T})$ to
$\mathbb{R}$. This implies by the Riesz-Markov theorem [61] that there exists
$w_{0}\in\mathcal{M}_{+}(\mathbb{T})$ such that $\Phi=w_{0}$. Moreover, by
construction of $\Phi$, $w_{0}$ satisfies $\bm{\nu}(w_{0})=\bm{y}$.
Consequently, Item 1 is proved.

∎

######  Remark 3.

Proposition 3 can readily be adapted to the nonpositive case, since there
exists a nonpositive representing measure for ${\bm{y}}$ if and only if
$\bm{\mathrm{T}}_{\bm{y}}$ is negative semi-definite.

Proposition 3 gives another equivalent condition to Item 1 of Theorem 1 which
involves the matrix $\bm{\mathrm{T}}_{\bm{y}}$. Building on this result, the
statement on the nature of the solutions of (BPC) can be refined by leveraging
the fact that $\bm{\mathrm{T}}_{\bm{y}}$ is a Toeplitz matrix. Indeed, it is
well known that a positive semi-definite and rank deficient Toeplitz matrix
can be uniquely decomposed as the product
$\bm{\mathrm{V}}\bm{\mathrm{D}}\bm{\mathrm{V}}^{*}$, where $\bm{\mathrm{V}}$
is a Vandermonde matrix whose columns are given by complex exponentials,
$\bm{\mathrm{D}}$ is a positive-definite diagonal matrix whose size is the
rank of the starting Toeplitz matrix and $V^{*}$ is the conjugate transpose of
$V$. This is the Pisarenko decomposition [58, 59, 60], also known as the
Carathéodory-Fejér-Pisarenko (CFP) decomposition. This result is recalled in
Appendix C, for the sake of completeness. The next lemma is then the last
missing piece towards Theorem 2; it relates this decomposition of the Toeplitz
matrix $\bm{\mathrm{T}}_{\bm{y}}$ to the existence of a sparse representing
measure for ${\bm{y}}$.

######  Lemma 3.

For all $0\leq K\leq K_{c}+1$,
$\bm{a}=(a_{1},\ldots,a_{K})\in(\mathbb{R}_{>0})^{K}$ and
$\bm{x}=(x_{1},\ldots,x_{K})\in\mathbb{T}^{K}$ with pairwise distinct entries,
the following statements are equivalent:

  1. a)

$\bm{y}=\bm{\nu}(w_{\bm{a},\bm{x}})$ with
$w_{\bm{a},\bm{x}}=\sum_{k=1}^{K}a_{k}\delta_{x_{k}}$;

  2. b)

$\bm{\mathrm{T}}_{\bm{y}}=\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$
where $\bm{\mathrm{V}}_{\bm{x}}\in\mathbb{C}^{(K_{c}+1)\times K}$ is the
Vandermonde matrix whose $k$-th column is given by $\bm{e_{K_{c}}}(x_{k})=(1\
\mathrm{e}^{\mathrm{i}x_{k}}\ \cdots\
\mathrm{e}^{\mathrm{i}K_{c}x_{k}})^{T}\in\mathbb{R}\times\mathbb{C}^{K_{c}}$
and $\bm{\mathrm{D}}_{\bm{a}}\in\mathbb{R}^{K\times K}$ the diagonal matrix
with the entries of $\bm{a}$ on the diagonal.

###### Proof.

Let $K\leq K_{c}+1$, $\bm{a}\in(\mathbb{R}_{>0})^{K}$, and
$\bm{x}\in\mathbb{T}^{K}$ be as in the statement of the lemma.

First, suppose that a) holds. Then, for any $0\leq m\leq K_{c}$ and $0\leq
n\leq K_{c}-m$, we have

$\displaystyle y_{m}$
$\displaystyle=\sum_{k=1}^{K}a_{k}\mathrm{e}^{-\mathrm{i}mx_{k}}=\sum_{k=1}^{K}a_{k}\mathrm{e}^{\mathrm{i}nx_{k}}\mathrm{e}^{-\mathrm{i}(m+n)x_{k}}=\left\langle(\mathrm{e}^{\mathrm{i}nx_{k}})_{1\leq
k\leq K},\,(a_{k}\mathrm{e}^{\mathrm{i}(m+n)x_{k}})_{1\leq k\leq
K}\right\rangle.$ (27)

We notice that $(\mathrm{e}^{\mathrm{i}nx_{k}})_{1\leq k\leq K}$ is the
$(n+1)$-th row of the matrix $\bm{\mathrm{V}}_{\bm{x}}$ and
$(a_{k}\mathrm{e}^{-\mathrm{i}(m+n)x_{k}})_{1\leq k\leq K}$ the $(m+n+1)$-th
column of $\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$. Therefore,
$y_{m}$ is the $(n+1,m+n+1)$ entry of the matrix
$\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$.
Hence, the elements of the $m$-th upper diagonal of
$\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$
are $y_{m}$, and since
$\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$
is Hermitian symmetric, we get that
$\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}=\bm{\mathrm{T}}_{\bm{y}}$.

Conversely suppose that b) holds. Then, the first line of
$\bm{\mathrm{T}}_{\bm{y}}$ gives the vector $\bm{y}$ and as demonstrated in
(27) the first line of
$\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$
gives $\bm{\nu}(w_{\bm{a},\bm{x}})$, which implies that
${\bm{y}}=\bm{\nu}(w_{{\bm{a}},{\bm{x}}})$. ∎

######  Remark 4.

The statements of Lemma 3 can once again readily be adapted to the case where
the weights $\bm{a}$ are negative. In this case, the Toeplitz matrix
$\bm{\mathrm{T}}_{\bm{y}}$ is negative semi-definite.

We can now state our main result, which relies on Theorem 1, Proposition 3,
Proposition 7, and Lemma 3.

######  Theorem 2.

The solution set of (BPC) can be characterized as follows:

  1. a)

If $\bm{\mathrm{T}}_{\bm{y}}$ has at least one negative and one positive
eigenvalue, then (BPC) has a unique solution composed of at most $2K_{c}$
Dirac masses, with at least one positive and one negative weight;

  2. b)

If $\bm{\mathrm{T}}_{\bm{y}}$ is positive, respectively negative, semi-
definite and $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})<K_{c}+1$, then
(BPC) has a unique solution composed of exactly
$\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})$ positive, respectively
negative, Dirac masses;

  3. c)

If $\bm{\mathrm{T}}_{\bm{y}}$ is positive, respectively negative, definite
(which implies $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})=K_{c}+1$), then
(BPC) has infinitely many solutions, none of which are sums of less than
$K_{c}+1$ Dirac masses and uncountably many of them composed of $K_{c}+1$
Dirac masses with positive, respectively negative, weights.

###### Proof.

If a) holds, then by Proposition 3 there is no nonnegative or nonpositive
representing measure for ${\bm{y}}$. Hence, by Theorem 1, (BPC) has a unique
solution composed of at most $2K_{c}$ Dirac masses, with at least one positive
and one negative weight.

Suppose that the assumptions of b) are satisfied. Without loss of generality,
we can assume that $\bm{\mathrm{T}}_{\bm{y}}$ is positive semi-definite. Then
by the CFP decomposition, which is recalled in Proposition 7 in Appendix C,
there exist unique sets $\\{x_{1},\ldots,x_{K}\\}\subset\mathbb{T}$ (the
$x_{k}$ are pairwise distinct) and
$\\{a_{1},\ldots,a_{K}\\}\subset\mathbb{R}_{>0}$ with
$K=\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})<K_{c}+1$ such that

$\displaystyle\bm{\mathrm{T}}_{\bm{y}}=\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*},$
(28)

with $\bm{x}=(x_{1},\ldots,x_{K})$, $\bm{a}=(a_{1},\ldots,a_{K})$,
$\bm{\mathrm{V}}_{\bm{x}}\in\mathbb{C}^{(K_{c}+1)\times K}$ the Vandermonde
matrix whose $k$-th column is given by $\bm{e_{K_{c}}}(x_{k})=(1\
\mathrm{e}^{\mathrm{i}x_{k}}\ \cdots\
\mathrm{e}^{\mathrm{i}K_{c}x_{k}})^{T}\in\mathbb{C}^{K_{c}+1}$ and
$\bm{\mathrm{D}}_{\bm{a}}\in\mathbb{R}^{K\times K}$ is a diagonal matrix with
$\bm{a}$ on the diagonal. By Lemma 3, Equation (28) is equivalent to

$\displaystyle\bm{y}=\bm{\nu}(w_{\bm{a},\bm{x}})\quad\text{with}\quad
w_{\bm{a},\bm{x}}=\sum_{k=1}^{K}a_{k}\delta_{x_{k}}.$ (29)

Then, according to Theorem 1 (equivalence between Items 1 and 2), the solution
set of (BPC) is $\\{w\in\mathcal{M}_{+}(\mathbb{T}):\bm{\nu}(w)=\bm{y}\\}$.
Therefore, $w_{\bm{a},\bm{x}}$ is a solution of (BPC), which is composed of
$K<K_{c}+1$ positive Dirac masses. By Lemma 3, the uniqueness of the CFP
decomposition, and Item 2 of Theorem 1, it is the unique solution of (BPC)
with less than $K_{c}+1$ Dirac masses. By [31, Theorem 2.1], it is the unique
solution altogether, since it is possible to build a nonconstant dual
certificate such that its signed saturation set is exactly
$\operatorname{supp}_{\pm}(w_{\bm{a},\bm{x}})$, which is a sufficient
condition of uniqueness by Proposition 2.

Finally, suppose that the assumption of c) is satisfied. Without loss of
generality, we can assume that $\bm{\mathrm{T}}_{\bm{y}}$ is positive-
definite. Once again by Proposition 7, there are uncountably many
decompositions
$\bm{\mathrm{T}}_{\bm{y}}=\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$
with $\bm{x}=(x_{1},\ldots,x_{K_{c}+1})\in\mathbb{T}^{K_{c}+1}$ whose elements
are pairwise distinct and
$\bm{a}=(a_{1},\ldots,a_{K_{c}+1})\in(\mathbb{R}_{>0})^{K_{c}+1}$. By Lemma 3
and Theorem 1 (equivalence between Items 1 and 2), this implies that for all
these $(\bm{a},\bm{x})$ pairs, $w_{\bm{a},\bm{x}}$ is a solution of (BPC)777As
stated in Proposition 7, one can arbitrarily choose one of the $x_{k}$ in
$\mathbb{T}$ in the decomposition
$\bm{\mathrm{T}}_{\bm{y}}=\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$,
which proves that $t\in\mathbb{T}\mapsto 1$ is the unique dual certificate in
this setup. Indeed any $(x_{k},1)\in\mathbb{T}\times\\{\pm 1\\}$ must be in
the signed saturation set of any dual certificate.. As a result, there are
uncountably many solutions consisting of $K_{c}+1$ Dirac masses with positive
weights. There can be no solution consisting of less than $K_{c}+1$ Dirac
masses, since they would necessarily have positive weights and once again, by
[31, Theorem 2.1], that solution would be the unique one, which we have proved
to be false. ∎

######  Remark 5.

Item b) of Theorem 2 can be deduced from well-grounded results in the
literature. Indeed, it is known from a classical result [57, Theorem 6.12] in
the field of moment problems, that ${\bm{y}}$ has a unique nonnegative
representing measure consisting of
$\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})$ Dirac masses if and only if
$\bm{\mathrm{T}}_{\bm{y}}$ is positive semi-definite and rank deficient
(_i.e._ , $\operatorname*{rank}(\bm{\mathrm{T}}_{\bm{y}})\leq K_{c}$). Next,
this measure is the unique solution of (BPC), since by [31, Theorem 2.1],
${\bm{y}}$ is generated from a nonnegative measure composed of less than
$K_{c}+1$ Dirac masses. This can also be proved by the equivalence between
Items 1 and 2 of Theorem 1. We also again recover the fact, mentioned in
Remark 2, that the TV norm plays no role in this context of nonnegativity.
Concerning Item c) when $\bm{\mathrm{T}}_{\bm{y}}$ is full rank, [57, Theorem
6.12] states that there are infinitely many nonnegative representing measures
composed of $K_{c}+1$ Dirac masses. However, Theorem 1 is, to the best of our
knowledge, the first known result which proves that they are all solutions of
(BPC).

######  Remark 6.

Theorem 2 provides a sharper (and tight888Consider the measure
$w_{0}=\sum_{k=0}^{2K_{c}-1}(-1)^{k}\delta_{\frac{2\pi k}{2K_{c}}}$, the
measurements ${\bm{y}}=\bm{\nu}(w_{0})$, and the function
$\eta\in\mathcal{C}(\mathbb{T})$ defined as $\eta=t\mapsto\cos(K_{c}t)$. Then,
$\eta$ is a real trigonometric polynomial of degree $K_{c}$ and
$\operatorname{supp}_{\pm}(w_{0})\subset\operatorname{sat}_{\pm}(\eta)$, which
implies by Proposition 1 that $w_{0}$ is a solution of (BPC).) upperbound,
$2K_{c}$, on the number of Dirac masses of a sparse solution for (BPC) than
Representer Theorems [64] which give the upperbound $2K_{c}+1$. This improved
bound arises when the assumptions of a) hold. Note that in this context, the
sparsity of the unique solution is no longer equal to the rank of
$\bm{\mathrm{T}}_{\bm{y}}$ since the CFP decomposition is valid only when
$\bm{\mathrm{T}}_{\bm{y}}$ is positive (or negative) semi-definite. This is
confirmed by the fact that one can construct examples of a solution of (BPC)
consisting of more than $K_{c}+1$ Dirac masses88footnotemark: 8, while the
rank of $\bm{\mathrm{T}}_{\bm{y}}$ is bounded by $K_{c}+1$.

From Theorem 2, we readily deduce all the situations of uniqueness for (BPC).
They are summarized in the next corollary.

######  Corollary 2.

The problem (BPC) has a unique solution if and only if
$\bm{\mathrm{T}}_{\bm{y}}$ is neither positive nor negative definite.

##  4 Conclusion

This paper deals with the linear continuous-domain inverse problem (BPC),
where the goal is to recover a periodic Radon measure from its low-frequency
Fourier coefficients ${\bm{y}}$ using a sparsity prior. We studied the
question of uniqueness without making any assumptions of the ground-truth
signal that generated ${\bm{y}}$. In this context, we proved that it can be
characterized from simple conditions on the spectrum of the Toeplitz matrix
$\bm{\mathrm{T}}_{\bm{y}}$. We also demonstrated that this matrix contains
information on the form of the sparse solutions of (BPC), namely their number
of Dirac masses, or a bound thereon, and the signs of their weights.

## Acknowledgments

The authors are grateful to Christian Remling for his help regarding the
extension of positive linear functionals in Proposition 6. They also thank
Shayan Aziznejad, Adrian Jarret, Matthieu Simeoni, and Michael Unser for
interesting discussions. Julien Fageot is supported by the Swiss National
Science Foundation (SNSF) under Grants P2ELP2_181759 and P400P2_194364. The
work of Thomas Debarre is supported by the SNSF under Grant 200020_184646 / 1.

##  Appendix A Proof of Proposition 2

###### Proof.

Let $\eta$ be a nonconstant dual certificate for (BPC) and
$w_{0}\in\mathcal{M}(\mathbb{T})$ a solution. Firstly, $\eta$ is a
trigonometric polynomial of degree at most $K_{c}$ and so is its derivative
$\eta^{\prime}$. Since $\eta$ is nonconstant, $\eta^{\prime}$ has at most
$2K_{c}$ roots [65, p. 150]. By Proposition 1, we have
$\operatorname{supp}_{\pm}(w_{0})\subset\operatorname{sat}_{\pm}(\eta)$, hence
any point in the support of $w_{0}$ is a root of $\eta^{\prime}$.
Consequently, $w_{0}$ is composed of at most $2K_{c}$ Dirac masses. Let
$\bm{\tau}=(\tau_{1},\ldots,\tau_{P})\in\mathbb{T}^{P}$ be the pairwise
distinct roots of $\eta^{\prime}$, with $P\leq 2K_{c}$. Then, we have
$w_{0}=\sum_{p=1}^{P}a_{p}\delta_{\tau_{p}}$, with
$\bm{a}=(a_{1},\ldots,a_{P})\in\mathbb{R}^{P}$ (note that some weights may be
equal to $0$). Moreover, any other solution of (BPC) must be of the form
$w_{\bm{\tilde{a}},\bm{\tau}}=\sum_{p=1}^{P}\tilde{a}_{p}\delta_{\tau_{p}}$,
with $\bm{\tilde{a}}=(\tilde{a}_{1},\ldots,\tilde{a}_{P})\in\mathbb{R}^{P}$
(once again some weights may be equal to $0$), where

$\displaystyle\bm{\nu}(w_{0})={\bm{y}}=\bm{\nu}(w_{\bm{\tilde{a}},\bm{\tau}}).$
(30)

Consider the matrix

$\bm{\mathrm{M}_{\bm{\tau}}}=\begin{bmatrix}\mathrm{e}^{\mathrm{i}K_{c}\tau_{1}}&\ldots&\mathrm{e}^{\mathrm{i}K_{c}\tau_{P}}\\\
\vdots&\ddots&\\\
\mathrm{e}^{\mathrm{i}\tau_{1}}&\ldots&\mathrm{e}^{\mathrm{i}\tau_{P}}\\\
1&\ldots&1\\\
\mathrm{e}^{-\mathrm{i}\tau_{1}}&\ldots&\mathrm{e}^{-\mathrm{i}\tau_{P}}\\\
\vdots&\ddots&\\\
\mathrm{e}^{-\mathrm{i}K_{c}\tau_{1}}&\ldots&\mathrm{e}^{-\mathrm{i}K_{c}\tau_{P}}\\\
\end{bmatrix}=\left[\mathrm{e}^{\mathrm{i}k\tau_{p}}\right]^{1\leq p\leq
P}_{-K_{c}\leq k\leq K_{c}}\in\mathbb{C}^{(2K_{c}+1)\times P}.$ (31)

By definition of $\bm{\nu}$ and by Equation (30), we get that
$\bm{\nu}(\bm{a}-\bm{\tilde{a}})=\bm{\mathrm{M}_{\bm{\tau}}}(\bm{a}-\bm{\tilde{a}})=\bm{0}$.
The matrix $\bm{\mathrm{M}_{\bm{\tau}}}$ is a Vandermonde-type matrix, which
is therefore of full rank $P$, since $P\leq 2K_{c}$ and
$\tau_{1},\ldots,\tau_{P}$ are pairwise distinct. Hence the nullspace of
$\bm{\mathrm{M}_{\bm{\tau}}}$ is trivial and $\bm{a}=\bm{\tilde{a}}$, which
prove the uniqueness of the solution $w_{0}$. ∎

##  Appendix B Trigonometric Toolbox

This section is dedicated to known theoretical results (or easily deducible
therefrom) that play a crucial role in our contributions in this paper.

A sequence $(a_{k})_{k\in\mathbb{Z}}$ of complex numbers is _positive
definite_ if $a_{0}\in\mathbb{R}_{+}$, $a_{-k}=\overline{a_{k}}$ for any
$k\geq 0$, and for any sequence $(z_{k})_{k\in\mathbb{Z}}$ of complex numbers
with finitely many nonzero terms, we have

$\sum_{k,\ell\in\mathbb{Z}}a_{k-\ell}z_{k}\overline{z_{\ell}}\geq 0.$ (32)

######  Proposition 4 (Herglotz Theorem).

A sequence $(a_{k})_{k\in\mathbb{Z}}$ is positive-definite if and only if
there exists a nonnegative measure $w\in\mathcal{M}_{+}(\mathbb{T})$ such that
$\widehat{w}[k]=a_{k}$ for all $k\in\mathbb{Z}$.

This theorem was obtained by Herglotz in [66]. For a modern exposition, we
refer to [67, Theorem 7.6]. The Herglotz theorem is an application of the
Bochner theorem, which characterizes the Fourier transform of probability
measures on locally Abelian groups $G$ [68], here with $G=\mathbb{T}$.

For $K\geq 0$, we denote by $\mathcal{P}_{K}(\mathbb{T})$ the set of real
trigonometric polynomial of degree at most $K$; _i.e._ , functions of the form
$p=\sum_{|k|\leq K}c_{k}e_{k}$ such that $c_{0}\in\mathbb{R}$ and
$c_{-k}=\overline{c_{k}}\in\mathbb{C}$ for any $1\leq k\leq K$.

######  Proposition 5 (Fejér–Riesz Theorem).

Let $p=\sum_{|k|\leq K}c_{k}e_{k}\in\mathcal{P}_{K}(\mathbb{T})$ be a positive
trigonometric polynomial of degree $K\geq 0$. Then, there exists a complex
trigonometric polynomial $q=\sum_{k=0}^{K_{c}}z_{k}e_{k}$ such that
$p=|q|^{2}$.

The Fejér–Riesz theorem was conjectured by Fejér [69] and shown by Riesz [70].
See [71, p. 26] for a recent exposition of this classical result. The next
proposition deals with the extension of positive linear functionals from
trigonometric polynomials to the space of continuous functions.

######  Proposition 6.

Let $K\geq 0$. Let $\Phi:\mathcal{P}_{K}(\mathbb{T})\rightarrow\mathbb{R}$ be
a linear and positive functional (_i.e._ , $\Phi(p)\geq 0$ for any $p\geq 0$).
Then, there exists an extension
$\Phi:\mathcal{C}(\mathbb{T})\rightarrow\mathbb{R}$ which is still linear and
positive. Moreover, any such extension is continuous on
$(\mathcal{C}(\mathbb{T}),\lVert\cdot\rVert_{\infty})$.

###### Proof.

Let $E$ be an ordered topological vector space, $C$ its positive cone, and
$M\subset E$. By [72, Corollary 2 p. 227], if $C\cap M$ contains an interior
point of $C$, then any continuous, positive, and linear form over $M$ can be
extended as a continuous, positive, and linear form over $E$.

We apply this result to $E=\mathcal{C}(\mathbb{T})$, whose positive cone is
the space of positive continuous functions $\mathcal{C}_{+}(\mathbb{T})$, and
to $M=\mathcal{P}_{K}(\mathbb{T})$. Then, $C\cap
M=\mathcal{C}_{+}(\mathbb{T})\cap\mathcal{P}_{K}(\mathbb{T})$ contains the
constant function $p=1$, which is an interior point of
$\mathcal{C}_{+}(\mathbb{T})$ since $\\{f\in\mathcal{C}(\mathbb{T}),\ \lVert
f-1\rVert_{\infty}<\frac{1}{2}\\}\subset\mathcal{C}_{+}(\mathbb{T})$.

In our case, $\Phi$ is continuous over
$(\mathcal{P}_{K}(\mathbb{T}),\lVert\cdot\rVert_{\infty})$, since it is a
linear functional over a finite-dimensional space. Hence, $\Phi$ is
continuous, positive, and linear, and admits the desired extension. ∎

##  Appendix C The Carathéodory-Fejér-Pisarenko Decomposition

In this appendix, we give, for the sake of completeness, the Carathéodory-
Fejér-Pisarenko decomposition which plays a major role in our main
contribution Theorem 2. Proposition 7, is a transcription from [60, Theorem
1], up to slight adaptations of notations and reformulations. Before stating
the result, let us define the column matrix $\bm{e}_{K}(x)=(1\
\mathrm{e}^{\mathrm{i}x}\ \cdots\ \mathrm{e}^{\mathrm{i}Kx})^{T}$, for all
$x\in\mathbb{T}$ and $K\in\mathbb{N}$.

######  Proposition 7.

Let $K\in\mathbb{N}$, $\bm{\mathrm{T}}\in\mathbb{C}^{(K+1)\times(K+1)}$ be a
Hermitian Toeplitz matrix, and $r=\operatorname*{rank}(\bm{\mathrm{T}})$.
Then, the two following conditions are equivalent:

  1. 1.

$\bm{\mathrm{T}}$ is positive semi-definite;

  2. 2.

$\bm{\mathrm{T}}=\bm{\mathrm{V}}_{\bm{x}}\bm{\mathrm{D}}_{\bm{a}}\bm{\mathrm{V}}_{\bm{x}}^{*}$,
where $\bm{x}=(x_{1},\ldots,x_{r})\in\mathbb{T}^{r}$ has pairwise distinct
elements, $\bm{\mathrm{V}}_{\bm{x}}\in\mathbb{C}^{(K+1)\times r}$ is the
Vandermonde matrix whose columns are $\bm{e}_{K}(x_{k})$ for
$k\in\\{1,\ldots,r\\}$, and $\bm{\mathrm{D}}_{\bm{a}}\in\mathbb{R}^{r\times
r}$ is a diagonal matrix with
$\bm{a}=(a_{1},\ldots,a_{r})\in(\mathbb{R}_{>0})^{r}$ on the diagonal.

Moreover, when $\bm{\mathrm{T}}$ is rank-deficient (i.e. $r<K+1$), then the
decomposition in Item 2 is unique up to any permutation applied to the
coefficients of $\bm{x}$ and $\bm{a}$. When $\bm{\mathrm{T}}$ has full rank,
then there are uncountably many $\\{x_{1},\ldots,x_{K+1}\\}\subset\mathbb{T}$
such that the decomposition holds. Note that $x_{K+1}$ can be arbitrarily
chosen in $\mathbb{T}$.

We remark that the decomposition given in [60, Theorem 1] is as a sum of
$r$-rank one matrices $a_{k}\bm{e}_{K}(x_{k})\bm{e}_{K}(x_{k})^{*}$. This can
readily be shown to be equivalent to the decomposition in Proposition 7.

Secondly, the result of [60], does not adjudicate on the uniqueness of the
decomposition when the Toeplitz matrix $\bm{\mathrm{T}}$ is of full rank.
However, by carefully studying the proof of [60, Theorem 1], one can see that
the full-rank case is studied in detail (see in particular Equations (10) to
(12)). We summarized the conclusion at the end of Proposition 7.

## References

  * [1] E. Candès and C. Fernandez-Granda, “Super-resolution from noisy data,” _Journal of Fourier Analysis and Applications_ , 2013.
  * [2] K. Bredies and H. Pikkarainen, “Inverse problems in spaces of measures,” _ESAIM: Control, Optimisation and Calculus of Variations_ , vol. 19, no. 01, pp. 190–218, 2013.
  * [3] V. Duval and G. Peyré, “Exact support recovery for sparse spikes deconvolution,” _Foundations of Computational Mathematics_ , vol. 15, no. 5, pp. 1315–1355, 2015.
  * [4] M. Unser, J. Fageot, and J. P. Ward, “Splines are universal solutions of linear inverse problems with generalized TV regularization,” _SIAM Review_ , vol. 59, no. 4, pp. 769–793, 2017.
  * [5] C. Boyer, A. Chambolle, Y. de Castro, V. Duval, F. D. Gournay, and P. Weiss, “On representer theorems and convex regularization,” _SIAM Journal on Optimization_ , vol. 29, no. 2, pp. 1260–1281, 2019.
  * [6] M. Unser and J. Fageot, “Native Banach spaces for splines and variational inverse problems,” _arXiv preprint arXiv:1904.10818_ , 2019.
  * [7] N. Boyd, G. Schiebinger, and B. Recht, “The alternating descent conditional gradient method for sparse inverse problems,” _SIAM Journal on Optimization_ , vol. 27, no. 2, pp. 616–639, 2017.
  * [8] H. Gupta, J. Fageot, and M. Unser, “Continuous-domain solutions of linear inverse problems with Tikhonov vs. generalized TV regularization,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 17, pp. 4670–4684, 2018.
  * [9] Q. Denoyelle, V. Duval, G. Peyré, and E. Soubies, “The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy,” _Inverse Problems_ , 2019.
  * [10] A. Flinth, F. de Gournay, and P. Weiss, “On the linear convergence rates of exchange and continuous methods for total variation minimization,” _Mathematical Programming_ , pp. 1–37, 2020.
  * [11] J.-B. Courbot, V. Duval, and B. Legras, “Sparse analysis for mesoscale convective systems tracking,” _Signal Processing: Image Communication_ , vol. 85, p. 115854, 2020.
  * [12] J.-B. Courbot and B. Colicchio, “A fast homotopy algorithm for gridless sparse recovery,” _Inverse Problems_ , vol. 37, no. 2, p. 025002, 2021.
  * [13] M. Simeoni, “Functional penalised basis pursuit on spheres,” _Applied and Computational Harmonic Analysis_ , vol. 53, pp. 1–53, 2021.
  * [14] R. Tibshirani, “The lasso problem and uniqueness,” _Electronic Journal of Statistics_ , vol. 7, pp. 1456–1490, 2013.
  * [15] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” _SIAM review_ , vol. 43, no. 1, pp. 129–159, 2001.
  * [16] D. Donoho, “Compressed sensing,” _IEEE Transactions on Information Theory_ , vol. 52, no. 4, pp. 1289–1306, 2006.
  * [17] M. Elad, _Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing_. Springer, 2010.
  * [18] S. Foucart and H. Rauhut, _A mathematical introduction to compressive sensing_. Birkhäuser Basel, 2013, vol. 1.
  * [19] M. Unser, J. Fageot, and H. Gupta, “Representer theorems for sparsity-promoting $\ell_{1}$ regularization,” _IEEE Transactions on Information Theory_ , vol. 62, no. 9, pp. 5167–5180, 2016.
  * [20] M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation,” _IEEE Transactions on Signal Processing_ , vol. 50, no. 6, pp. 1417–1428, 2002.
  * [21] M. Simeoni, A. Besson, P. Hurley, and M. Vetterli, “CPGD: Cadzow plug-and-play gradient descent for generalised FRI,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 42–57, 2020.
  * [22] R. Schmidt, “Multiple emitter location and signal parameter estimation,” _IEEE transactions on antennas and propagation_ , vol. 34, no. 3, pp. 276–280, 1986.
  * [23] G. Plonka and M. Tasche, “Prony methods for recovery of structured functions,” _GAMM-Mitteilungen_ , vol. 37, no. 2, pp. 239–258, 2014.
  * [24] W. Liao and A. Fannjiang, “Music for single-snapshot spectral estimation: stability and super-resolution,” _Applied and Computational Harmonic Analysis_ , vol. 40, no. 1, pp. 33–67, 2016.
  * [25] H. Pan, T. Blu, and M. Vetterli, “Towards generalized FRI sampling with an application to source resolution in radioastronomy,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 4, pp. 821–835, 2016.
  * [26] 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.
  * [27] B. Adcock and A. Hansen, “Generalized sampling and infinite-dimensional compressed sensing,” _Foundations of Computational Mathematics_ , vol. 16, no. 5, pp. 1263–1323, 2016.
  * [28] Y. Traonmilin, G. Puy, R. Gribonval, and M. Davies, “Compressed sensing in Hilbert spaces,” in _Compressed Sensing and its Applications_. Springer, 2017, pp. 359–384.
  * [29] A. Bhandari and Y. Eldar, “Sampling and super resolution of sparse signals beyond the Fourier domain,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 6, pp. 1508–1521, 2018.
  * [30] A. Beurling, “Sur les intégrales de Fourier absolument convergentes et leur applicationa une transformation fonctionnelle,” in _Ninth Scandinavian Mathematical Congress_ , 1938, pp. 345–366.
  * [31] Y. de Castro and F. Gamboa, “Exact reconstruction using Beurling minimal extrapolation,” _Journal of Mathematical Analysis and applications_ , vol. 395, no. 1, pp. 336–354, 2012.
  * [32] E. Candè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.
  * [33] A. Eftekhari and M. B. Wakin, “Greed is super: a new iterative method for super-resolution,” in _2013 IEEE Global Conference on Signal and Information Processing_. IEEE, 2013, pp. 631–631.
  * [34] C. Elvira, R. Gribonval, C. Soussen, and C. Herzet, “OMP and continuous dictionaries: is k-step recovery possible?” in _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 5546–5550.
  * [35] ——, “When does OMP achieve exact recovery with continuous dictionaries?” _Applied and Computational Harmonic Analysis_ , vol. 51, pp. 374 – 413, 2021. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1063520320300841
  * [36] A. Flinth, F. de Gournay, and P. Weiss, “On the linear convergence rates of exchange and continuous methods for total variation minimization,” _Mathematical Programming_ , pp. 1–37, 2020.
  * [37] T. Debarre, J. Fageot, H. Gupta, and M. Unser, “B-spline-based exact discretization of continuous-domain inverse problems with generalized TV regularization,” _IEEE Transactions on Information Theory_ , 2019.
  * [38] Y. Traonmilin, J.-F. Aujol, and A. Leclaire, “Projected gradient descent for non-convex sparse spike estimation,” _IEEE Signal Processing Letters_ , vol. 27, pp. 1110–1114, 2020.
  * [39] L. Chizat, “Sparse optimization on measures with over-parameterized gradient descent,” _Mathematical Programming_ , pp. 1–46, 2021.
  * [40] S. Fisher and J. Jerome, “Spline solutions to ${L}^{1}$ extremal problems in one and several variables,” _Journal of Approximation Theory_ , vol. 13, no. 1, pp. 73–83, 1975.
  * [41] J. Azais, Y. de Castro, and F. Gamboa, “Spike detection from inaccurate samplings,” _Applied and Computational Harmonic Analysis_ , 2015.
  * [42] V. Duval and G. Peyré, “Sparse regularization on thin grids I: the LASSO,” _Inverse Problems_ , vol. 33, no. 5, p. 055008, 2017.
  * [43] ——, “Sparse spikes super-resolution on thin grids II: the continuous basis pursuit,” _Inverse Problems_ , vol. 33, no. 9, p. 095008, 2017.
  * [44] C. Poon and G. Peyré, “Multidimensional sparse super-resolution,” _SIAM Journal on Mathematical Analysis_ , vol. 51, no. 1, pp. 1–44, 2019\.
  * [45] C. Poon, N. Keriven, and G. Peyré, “Support localization and the Fisher metric for off-the-grid sparse regularization,” in _The 22nd International Conference on Artificial Intelligence and Statistics_ , 2019.
  * [46] A. Ali and R. Tibshirani, “The generalized lasso problem and uniqueness,” _Electronic Journal of Statistics_ , vol. 13, no. 2, pp. 2307–2347, 2019\.
  * [47] C. Pouchol and O. Verdier, “The ML–EM algorithm in continuum: sparse measure solutions,” _Inverse Problems_ , vol. 36, no. 3, p. 035013, 2020\.
  * [48] ——, “Linear inverse problems with nonnegativity constraints through the beta-divergences: sparsity of optimisers,” _arXiv preprint arXiv:2006.15845_ , 2020.
  * [49] A. Eftekhari, J. Tanner, A. Thompson, B. Toader, and H. Tyagi, “Sparse non-negative super-resolution—simplified and stabilised,” _Applied and Computational Harmonic Analysis_ , vol. 50, pp. 216–280, 2021.
  * [50] A. Eftekhari, T. Bendory, and G. Tang, “Stable super-resolution of images: theoretical study,” _Information and Inference: A Journal of the IMA_ , vol. 10, no. 1, pp. 161–193, 2021.
  * [51] E. Candès and Y. Plan, “A probabilistic and RIPless theory of compressed sensing,” _arXiv preprint arXiv:1011.3854_ , 2010.
  * [52] T. Debarre, Q. Denoyelle, M. Unser, and J. Fageot, “Sparsest piecewise-linear regression of one-dimensional data,” _Journal of Computational and Applied Mathematics_ , p. 114044, 2021.
  * [53] J. B. Lasserre, “A semidefinite programming approach to the generalized problem of moments,” _Mathematical Programming_ , vol. 112, no. 1, pp. 65–92, 2008.
  * [54] ——, _Moments, positive polynomials and their applications_. World Scientific, 2009, vol. 1.
  * [55] Y. de Castro, F. Gamboa, D. Henrion, and J.-B. Lasserre, “Exact solutions to super resolution on semi-algebraic domains in higher dimensions,” _IEEE Transactions on Information Theory_ , vol. 63, no. 1, pp. 621–630, 2016.
  * [56] P. Catala, V. Duval, and G. Peyré, “A low-rank approach to off-the-grid sparse superresolution,” _SIAM Journal on Imaging Sciences_ , vol. 12, no. 3, pp. 1464–1500, 2019.
  * [57] R. E. Curto and L. Fialkow, “Recursiveness, positivity and truncated moment problems,” _Houston Journal of Mathematics_ , vol. 17, pp. 603–635, 1991\.
  * [58] C. Carathéodory and L. Fejér, “Über den zusammenhang der extremen von harmonischen funktionen mit ihren koeffizienten und über den picard-landau’schen satz,” _Rendiconti del Circolo Matematico di Palermo (1884-1940)_ , vol. 32, no. 1, pp. 218–239, 1911.
  * [59] V. F. Pisarenko, “The retrieval of harmonics from a covariance function,” _Geophysical Journal International_ , vol. 33, no. 3, pp. 347–366, 1973.
  * [60] Z. Yang and L. Xie, “Frequency-selective Vandermonde decomposition of Toeplitz matrices with applications,” _Signal Processing_ , vol. 142, pp. 157–167, 2018.
  * [61] J. Gray, “The shaping of the Riesz representation theorem: A chapter in the history of analysis,” _Archive for History of Exact Sciences_ , vol. 31, no. 2, pp. 127–187, 1984.
  * [62] I. Ekeland and R. Temam, _Convex Analysis and Variational Problems_. SIAM, 1976.
  * [63] C. Fernandez-Granda, “Super-resolution of point sources via convex programming,” _Information and Inference: A Journal of the IMA_ , 2016.
  * [64] J. Fageot and M. Simeoni, “TV-based reconstruction of periodic functions,” _Inverse Problems_ , vol. 36, no. 11, p. 115015, 2020.
  * [65] M. Powell, _Approximation theory and methods_. Cambridge university press, 1981.
  * [66] G. Herglotz, “Uber potenzreihen mit positivem, reelen teil im einheitskreis,” _Ber. Verhandl. Sachs Akad. Wiss. Leipzig, Math.-Phys. Kl._ , vol. 63, pp. 501–511, 1911.
  * [67] Y. Katznelson, _An introduction to harmonic analysis_. Cambridge University Press, 2004.
  * [68] W. Rudin, _Fourier analysis on groups_. Wiley Online Library, 1962, vol. 121967.
  * [69] L. Fejér, “Über trigonometrische Polynome.” _Journal für die reine und angewandte Mathematik_ , vol. 1916, no. 146, pp. 53–82, 1916.
  * [70] F. Riesz, “Über ein Problem des Herrn Carathéodory.” _Journal für die reine und angewandte Mathematik_ , vol. 1916, no. 146, pp. 83–87, 1916.
  * [71] S. Barry, _Orthogonal polynomials on the unit circle_. American Mathematical Soc., 2005.
  * [72] H. Schaefer, “Locally convex topological vector spaces,” in _Topological Vector Spaces_. Springer, 1971, pp. 36–72.