Exact Support Recovery for Sparse Spikes Deconvolution

Introduction

Super-resolution is a central problem in imaging science, and loosely speaking corresponds to recovering fine scale details from a possibly noisy input signal or image. This thus encompasses the problems of data interpolation (recovering missing sampling values on a regular grid) and deconvolution (removing acquisition blur). We refer to the review articles and the references therein for an overview of these problems.

2 Previous Works

Imposing the exact recovery of the support of the signal to recover might be a too strong assumption. The inverse problem community rather focuses on the $L^{2}$ recovery error, which typically leads to a linear convergence rate with respect to the noise amplitude. The seminal paper of Grasmair et al. gives a necessary and sufficient condition for such a convergence, which corresponds to the existence of a non-saturating dual certificate (see Section 2 for a precise definition of certificates). This can be understood as an abstract condition, which is often difficult to check on practical problems such as deconvolution.

Note that the continuous setting adopted in the present paper might be seen as a limit of such discrete problems, and in Section 5, we relate our results to well-known results on discrete grids.

Inverse problems regularization with measures.

Working over a discrete grid makes the mathematical analysis difficult. Following recent proposals , we consider here this sparse deconvolution over a continuous domain, i.e. in a grid-free setting. This shift from the traditional discrete domain to a continuous one offers considerable advantages in term of mathematical analysis, allowing for the first time the emergence of almost sharp signal-dependent criteria for stable spikes recovery (see references below). Note that while the corresponding continuous recovery problem is infinite dimensional in nature, it is possible to find its solution using either provably convergent algorithms or root finding methods for ideal low pass filters .

Inverse problem regularization over the space of measures is now well understood (see for instance ), and requires to perform variational analysis over a non-reflexive Banach space (as in ), which leads to some mathematical technicalities. We capitalize on these earlier works to build our analysis of the recovery performance.

Theoretical analysis of deconvolution over the space of measures.

For deconvolution from ideal low-pass measurements, the ground-breaking paper shows that it is indeed possible to construct a dual certificate by solving a linear system when the input Diracs are well-separated. This work is further refined in that studies the robustness to noise. In a series of paper the authors study the prediction (i.e. denoising) error using the same dual certificate, but they do not consider the reconstruction error (recovery of the spikes). In our work, we use a different certificate to assess the exact recovery of the spikes when the noise is small enough.

In view of the applications of superresolution, it is crucial to understand the precise location of the recovered Diracs locations when the measurements are noisy. Partial answers to this questions are given in and , where it is shown (under different conditions on the signal-to-noise level) that the recovered spikes are clustered tightly around the initial measure’s Diracs. In this article, we fully answer the question of the position of the recovered Diracs in the setting where the signal-to-noise ratio is large enough.

3 Formulation of the Problem and Contributions.

Following , we hope to recover $m_{0}$ by solving the problem

We may also consider reconstructing $m_{0}$ by solving the following penalized problem for $\lambda>0$, also known as the Beurling LASSO (see for instance ):

This is especially useful if the observation is noisy, in which case $y_{0}$ should be replaced with $y_{0}+w$.

Does the resolution of ($\mathcal{P}_{0}(y_{0})$) for $y_{0}=\Phi m_{0}$ actually recover interesting measures $m_{0}$?

How close is the solution of ($\mathcal{P}_{\lambda}(y_{0})$) to the solution of ($\mathcal{P}_{0}(y_{0})$) when $\lambda$ is small enough?

How close is the solution of $(\mathcal{P}_{\lambda}(y_{0}+w))$ to the solution of ($\mathcal{P}_{\lambda}(y_{0})$) when both $\lambda$ and $w/\lambda$ are small enough?

What can be said about the above questions when solving ($\mathcal{P}_{\lambda}(y_{0})$) with measures supported on a fixed finite grid?

The first question is addressed in the landmark paper in the case of ideal low-pass filtering: measures $m_{0}$ whose spikes are separated enough are the unique solution of ($\mathcal{P}_{0}(y_{0})$) (for data $y_{0}=\Phi m_{0}$). Several other cases (using observations different from convolutions) are also tackled in , particularly in the case of non-negative measures.

The second and third questions receive partial answers in . In it is shown that if the solution of ($\mathcal{P}_{0}(y_{0})$) is unique, the measures recovered by $(\mathcal{P}_{\lambda}(y_{0}+w))$ converge to the solution of ($\mathcal{P}_{0}(y_{0})$) in the sense of the weak-* convergence when $\lambda\to 0$ and $\frac{|\!|w|\!|_{2}^{2}}{\lambda}\to 0$. In , the authors measure the reconstruction error using the $L^{2}$ norm of a low-pass filtered version of recovered measures. In , error bounds are derived from the amplitudes of the reconstructed measure. In , bounds are given in terms of the original measure. However, those works provide little information about the structure of the measures recovered by $(\mathcal{P}_{\lambda}(y_{0}+w))$: are they made of less spikes than $m_{0}$ or, in the contrary, do they present lots of parasitic spikes? What happens if one compels the spikes to belong to a finite grid?

The fourth question is of primary importance since most numerical schemes for sparse regularization solve a finite dimensional optimization problem over a fixed discretization grid. Following , one can remark that in the noiseless setting, if $m_{0}$ is recovered over the continuous domain and if its support is included in the grid, $m_{0}$ is also guaranteed to be recovered by the discretized problem. But this is of little interest in practice because the noise is likely to impact in a different manner the discrete problem and the input measure might fall outside the grid locations. Dossal and Mallat in study the stability of the position of the Diracs on the grid, which leads to overly pessimistic conclusions because noise typically forces the spikes to translate over the domain. Studying the convergence of the discretized problem toward the continuous one is thus important to obtain a precise description of the discretized solution. To the best of our knowledge, the work of is the only one to provide some conclusion about this convergence in term of denoising error. No previous work has studied the capability of the discretized problem to estimate in a precise manner the location of the spikes of the input measure.

The present paper studies in detail the structure of the recovered measure. For this purpose, we define the minimal $L^{2}$-norm certificate. This certificate fully governs the behavior of the regularization when both $\lambda$ and $|\!|w|\!|_{2}/\lambda$ are small.

Our first contribution is a set of results indicating that the regions of saturation of the certificate (when it reaches $+1$ or $-1$) are approximately stable when $\lambda$ and $|\!|w|\!|_{2}/\lambda$ are small enough. This means that the recovered measures are supported closely to the support of the input measure if the latter is identifiable (solution of the noiseless problem ($\mathcal{P}_{0}(y_{0})$)).

Our second contribution introduces the Non Degenerate Source Condition, which imposes that the second derivative of the minimal-norm certificate does not vanish on the saturation points. Under this condition, we show that for $\lambda$ and $|\!|w|\!|_{2}/\lambda$ small enough, the reconstructed measure has exactly the same number of spikes as the original measure and that their locations and amplitudes converge to those of the original one.

Our third contribution shows that under the Non Degenerate Source Condition, the minimal norm certificate can actually be computed in closed form by simply solving a linear system. This in turn also implies that the errors in the amplitudes and locations decay linearly with respect to the noise level.

Our fourth and last contribution focuses on the regularization over a discrete finite grid, which corresponds to the so-called Lasso or Basis Pursuit Denoising problem. We show that when $\lambda$ and $|\!|w|\!|_{2}/\lambda$ are small enough, and provided that the Non Degenerate Source Condition holds, the discretized solution is located on pairs of Diracs adjacent to the input Diracs location. This gives a precise description of how the solution to the discretized problem converges to the one of the continuous problem when the stepsize of the grid vanishes.

Throughout the paper, the proposed definitions and results are illustrated in the case of the ideal low-pass filter, showing that the assumptions are actually relevant. Note that the code to reproduce the figures of this article is available onlinehttps://github.com/gpeyre/2013-FOCM-SparseSpikes/.

Outline of the paper.

Section 2 defines the framework for the recovery of Radon measures using total variation minimization. We also expose basic results that are used throughout the paper. Section 3 is devoted to the main result of the paper: we define the Non Degenerate Source Condition and we show that it implies the robustness of the reconstruction using $(\mathcal{P}_{\lambda}(y_{0}+w))$. In Section 4 we show how the specific dual certificate involved in the Non Degenerate Source Condition can be computed numerically by solving a linear system. Lastly, Section 5 focuses on the recovery of measures on a discrete grid.

4 Notations

where $m_{+}$ (resp. $m_{-}$) denotes the positive (resp. negative) part of $m$. For a discrete measure $m=m_{a,x}$,

Eventually, in order to study small noise regimes, we shall consider domains $D_{\alpha,\lambda_{0}}$, for $\alpha>0$, $\lambda_{0}>0$, where:

Preliminaries

In this section, we precise the framework and we state the basic results needed in the next sections. We refer to for aspects regarding functional analysis and to as far as duality in optimization is concerned.

2 Subdifferential of the Total Variation

It is clear from the definition of the total variation in (7) that it is convex lower semi-continuous with respect to the weak-* topology. Its subdifferential is defined as

Since the total variation is a sublinear function, its subgradient has a special structure. One may show (see Proposition 12 in Appendix A) that

3 Primal and Dual Problems

If $m_{0}$ is the unique solution of ($\mathcal{P}_{0}(y_{0})$), we say that $m_{0}$ is identifiable.

Existence of solutions for ($\mathcal{P}_{\lambda}(y_{0})$) is shown in , and existence of solutions for ($\mathcal{P}_{0}(y_{0})$) can be checked using the direct method of the calculus of variations (recall that for ($\mathcal{P}_{0}(y_{0})$), we assume that the observation is $y_{0}=\Phi m_{0}$).

with $|\!|\eta|\!|_{\infty}\leqslant 1$ and $\eta(x_{i})=\operatorname{sign}(a_{i})$ for $1\leqslant i\leqslant N$.

Another source of information for the study of Problems ($\mathcal{P}_{\lambda}(y_{0})$) and ($\mathcal{P}_{0}(y_{0})$) is given by their associated dual problems. In the case of the ideal low-pass filter, this approach is also the key to the numerical algorithms used in : the dual problem can be recast into a finite-dimensional problem.

The Fenchel dual problem to ($\mathcal{P}_{\lambda}(y_{0})$) is given by

which may be reformulated as a projection on a closed convex set (see )

This formulation immediately yields existence and uniqueness of a solution to ($\mathcal{D}_{\lambda}(y_{0})$).

The dual problem to ($\mathcal{P}_{0}(y_{0})$) is given by

Contrary to ($\mathcal{D}_{\lambda}(y_{0})$), the existence of a solution to ($\mathcal{D}_{0}(y_{0})$) is not always guaranteed, so that in the following (see Definition 5) we make this assumption.

Existence is guaranteed when for instance $\operatorname{Im}\Phi^{*}$ is finite-dimensional (as is the case in the framework of ). If a solution to ($\mathcal{D}_{0}(y_{0})$) exists, the unique solution of ($\mathcal{D}_{\lambda}(y_{0})$) converges to a certain solution of ($\mathcal{D}_{0}(y_{0})$) for $\lambda\to 0^{+}$ as shown in Proposition 1 below.

4 Dual Certificates

The strong duality between $(\mathcal{P}_{\lambda}(y_{0}))$ and ($\mathcal{D}_{\lambda}(y_{0})$) is proved in [4, Prop. 2] by seeing ($\mathcal{D}^{\prime}_{\lambda}(y)$) as a predual problem for ($\mathcal{P}_{\lambda}(y_{0})$). As a consequence, both problems have the same value and any solution $m_{\lambda}$ of ($\mathcal{P}_{\lambda}(y_{0})$) is linked with the unique solution $p_{\lambda}$ of ($\mathcal{D}_{\lambda}(y_{0})$) by the extremality condition

As for ($\mathcal{P}_{0}(y_{0})$), a proof of strong duality is given in Appendix A (see Proposition 13). If a solution $p^{\star}$ to ($\mathcal{D}_{0}(y_{0})$) exists, then it is linked to any solution $m^{\star}$ of ($\mathcal{P}_{0}(y_{0})$) by

Since finding $\eta=\Phi^{*}p^{\star}$ which satisfies (14) gives a quick proof that $m^{\star}$ is a solution of ($\mathcal{P}_{0}(y_{0})$), we call $\eta$ a dual certificate for $m^{\star}$. We may also use a similar terminology for $\eta_{\lambda}=\Phi^{*}p_{\lambda}$ and Problem ($\mathcal{P}_{\lambda}(y_{0})$).

In general, dual certificates for ($\mathcal{P}_{0}(y_{0})$) are not unique, but we consider in the following definition a specific one, which is crucial for our analysis.

Observe that in the above definition, $p_{0}$ is well-defined provided there exists a solution to Problem ($\mathcal{D}_{0}(y_{0})$), since $p_{0}$ is then the projection of onto the non-empty closed convex set of solutions. Moreover, in view of the extremality conditions (14), given any solution $m^{\star}$ to ($\mathcal{P}_{0}(y_{0})$), it may be expressed as

Let $p_{\lambda}$ be the unique solution of Problem ($\mathcal{D}_{\lambda}(y_{0})$), and $p_{0}$ be the solution of Problem ($\mathcal{D}_{0}(y_{0})$) with minimal norm defined in (15). Then

Moreover the dual certificates $\eta_{\lambda}=\Phi^{*}p_{\lambda}$ for Problem ($\mathcal{P}_{\lambda}(y_{0})$) converge to the minimal norm certificate $\eta_{0}=\Phi^{*}p_{0}$. More precisely,

Let $p_{\lambda}$ be the unique solution of ($\mathcal{D}_{\lambda}(y_{0})$). By optimality of $p_{\lambda}$ (resp. $p_{0}$) for ($\mathcal{D}_{\lambda}(y_{0})$) (resp. ($\mathcal{D}_{0}(y_{0})$))

As a consequence $|\!|p_{0}|\!|_{2}^{2}\geqslant|\!|p_{\lambda}|\!|_{2}^{2}$ for all $\lambda>0$.

where $C>0$ does not depend on $t$ nor $k$, hence the uniform convergence. ∎

5 Application to the ideal Low-pass filter

In this paragraph, we apply the above duality results to the particular case of the Dirichlet kernel, defined as

It is well known that in this case the spaces $\operatorname{Im}\Phi$ and $\operatorname{Im}\Phi^{*}$ are finite-dimensional, being the space of real trigonometric polynomials with degree less than or equal to $f_{c}$.

We first check that a solution to ($\mathcal{D}_{0}(y_{0})$) always exists. As a consequence, given any measure $m_{0}$, the minimal norm certificate is well defined.

A striking result of is that discrete measures are identifiable provided that their support is separated enough, i.e. $\Delta(m_{0})\geqslant\frac{C}{f_{c}}$ for some $C>0$, where $\Delta(m_{0})$ is the so-called minimum separation distance.

The minimum separation of the support of a discrete measure $m$ is defined as

We rely on the following theorem, proved by P. Turán .

From this theorem we derive necessary conditions for measures that can be reconstructed by ($\mathcal{P}_{0}(y_{0})$).

There exists a discrete measure $m_{0}$ with $\Delta(m_{0})=\frac{1}{2f_{c}}$ such that $m_{0}$ is not a solution of ($\mathcal{P}_{0}(y_{0})$) for $y_{0}=\Phi m_{0}$.

Writing $\eta(t)=\sum_{k=-f_{c}}^{f_{c}}d_{k}e^{2i\pi kt}$, the polynomial $P(z)=\sum_{k=0}^{2f_{c}}d_{k-f_{c}}z^{k}$ satisfies $P(1)=1=\sup_{|z|=1}|P(z)|=|P(e^{\frac{2i\pi}{2f_{c}}})|$, and $P(e^{2i\pi t_{0}})=0$.

By Theorem 1, we cannot have $|2\pi t_{0}-0|<\frac{\pi}{2f_{c}}$ nor $|2\pi t_{0}-\frac{2\pi}{2f_{c}}|<\frac{\pi}{2f_{c}}$, hence $t_{0}=\frac{1}{4f_{c}}$ and $P(z)=c(1+z^{2f_{c}})$, so that $\eta(t)=\cos(2\pi f_{c}t)$. But this implies $\eta(-\frac{1}{2f_{c}})=-1$, which contradicts the optimality of $\eta$. ∎

In a similar way, we may also deduce the following corollary.

Noise Robustness

This section is devoted to the study of the behavior of solutions to $\mathcal{P}_{\lambda}(y_{0}+w)$ for small values of $\lambda$ and $|\!|w|\!|$. In order to study such regimes, as already defined in (6), we consider sets of the form

First, we introduce the notion of extended support of a measure. Then we show that this concept governs the structure of solutions at small noise regime. After introducing the Non Degenerate Source Condition, we state the main result of the paper, i.e. that under this assumption, the solutions of $\mathcal{P}_{\lambda}(y_{0}+w)$ have the same number of spikes as the original measure, and that these spikes converge smoothly to those of the original measure.

Our first step in understanding the behavior of solutions to $\mathcal{P}_{\lambda}(y_{0}+w)$ at low noise regime is to introduce the notion of extended signed support.

The extended support of $m_{0}$ is defined as:

and the extended signed support of $m_{0}$ as:

$m_{0}$ is a solution to ($\mathcal{P}_{0}(y_{0})$) if and only if $\operatorname{Supp^{\pm}}m_{0}\subset\operatorname{Ext^{\pm}}m_{0}$.

In any case, if $\Phi_{\operatorname{Ext}m_{0}}$ has full rank, the solution to ($\mathcal{P}_{0}(y_{0})$) is unique.

Here, following the notation (1), we have denoted by $\Phi_{\operatorname{Ext}m_{0}}$ the restriction of $\Phi$ to the space of measures with support in $\operatorname{Ext}m_{0}$. The link between Proposition 3 and the source condition is discussed in Section 3.3

2 Local behavior of the support

Assume that there exists a solution to ($\mathcal{D}_{0}(y_{0})$) and let $\varepsilon>0$. Then there exists $\alpha>0$, $\lambda_{0}>0$ such that for all $(\lambda,w)\in D_{\alpha,\lambda_{0}}$,

where given two sets $A$ and $B$, $A\oplus B=\left\{a+b\;;\;~a\in A,b\in B\right\}$ denotes their Minkowski sum.

From the uniform continuity of $\eta_{0}$, for $\varepsilon$ small enough, $\eta_{0}>\frac{1}{2}$ in $\operatorname{Ext}^{+,\varepsilon}$ and $\eta_{0}<-\frac{1}{2}$ in $\operatorname{Ext}^{-,\varepsilon}$, so that $\operatorname{Ext}^{+,\varepsilon}\cap\operatorname{Ext}^{-,\varepsilon}=\emptyset$.

Variations of dual certificates.

From now on, we set $\alpha=\frac{r}{2M}$ and we impose $\frac{|\!|w|\!|_{2}}{\lambda}\leqslant\alpha$. Writing

Structure of the reconstructed measure.

If, in addition, $m_{0}$ is identifiable and $|m_{0}|((x-\varepsilon,x+\varepsilon))\neq 0$, only the second case may happen.

The proof follows the same steps as those of Lemma 1.

Behavior of the minimal norm certificate.

First, observe that if $\eta_{0}^{\prime\prime}(x)\neq 0$ and $\eta_{0}(x)=1$ (resp. $-1$) for $x\in\operatorname{Ext}m_{0}$, then $\eta_{0}^{\prime\prime}(x)<0$ (resp. $>0$). As a consequence, $x$ is an isolated point of $\operatorname{Ext}m_{0}$. For $\varepsilon>0$ small enough, $\operatorname{Ext}m_{0}\cap(x-\varepsilon,x+\varepsilon)=\{x\}$ and $|\eta_{0}^{\prime\prime}(t)|\geqslant\frac{|\eta_{0}^{\prime\prime}(x)|}{2}>0$ for all $t\in(x-\varepsilon,x+\varepsilon)$.

Variations of dual certificates.

We set $\alpha=\frac{r}{2M}$ with $r=\frac{|\eta_{0}^{\prime\prime}(x)|}{2}$ and we impose $\frac{|\!|w|\!|_{2}}{\lambda}\leqslant\alpha$, so that

Structure of the reconstructed measure.

In the proof of Lemma 2 we have relied on the following result.

3 Non Degenerate Source Condition

The notion of extended signed support has strong connections with the source condition introduced in to derive convergence rates for the Bregman distance.

In a finite-dimensional framework, the source condition is simply equivalent to the optimality of $m_{0}$ for ($\mathcal{P}_{0}(y_{0})$) given $y_{0}=\Phi m_{0}$. In the framework of Radon measures, the source condition amounts to assuming that $m_{0}$ is a solution of ($\mathcal{P}_{0}(y_{0})$) and that there exists a solution to ($\mathcal{D}_{0}(y_{0})$). In fact, the source condition simply means that the conditions of Proposition 3 hold.

If one is interested in $m_{0}$ being the unique solution of ($\mathcal{P}_{0}(y_{0})$) for $y_{0}=\Phi m_{0}$ (in which case we say that $m_{0}$ is identifiable), the source condition may be strengthened to give a sufficient condition.

Let $m_{0}=m_{x_{0},a_{0}}$ be a discrete measure. If $\Phi_{x_{0}}$ has full rank, and if

there exists $\eta\in\operatorname{Im}\Phi^{*}$ such that $\eta\in\partial{|\!|m_{0}|\!|_{\text{TV}}}$,

$\forall\,s\notin\operatorname{Supp}(m_{0}),\quad|\eta(s)|<1$,

then $m_{0}$ is the unique solution of ($\mathcal{P}_{0}(y_{0})$).

In this paper, in view of Lemma 2, we strengthen a bit more the Source Condition so as to derive a global stability result concerning the support of the solutions of $\mathcal{P}(y_{0}+w)$ (see Theorem 2).

Let $m_{0}=m_{x_{0},a_{0}}$ be a discrete measure, and $\{x_{0,1},\ldots x_{0,N}\}=\operatorname{Supp}m_{0}$. We say that $m_{0}$ satisfies the Non Degenerate Source Condition (NDSC) if

there exists $\eta\in\operatorname{Im}\Phi^{*}$ such that $\eta\in\partial{|\!|m_{0}|\!|_{\text{TV}}}$.

the minimal norm certificate $\eta_{0}$ satisfies

In that case, we say that $\eta_{0}$ is not degenerate.

The first assumption in the above definition is the standard Source Condition. The last two assumptions impose conditions on the extended signed support, namely that $\operatorname{Supp^{\pm}}m_{0}=\operatorname{Ext^{\pm}}(m_{0})$ and $\eta_{0}^{\prime\prime}(t)\neq 0$ for all $t\in\operatorname{Supp}m_{0}$.

When $\Phi$ is an ideal low-pass filter with cutoff frequency $f_{c}$, there are numerical evidences that measures having a large enough separation distance (proportional to $f_{c}$) satisfy the non degenerate source condition, see Section 4.

4 Main Result

The following theorem, which is the main result of this paper, gives a global result on the precise structure of the solution when the signal-to-noise ratio is large enough and $\lambda$ is small enough.

Let $m_{0}=m_{a_{0},x_{0}}=\sum_{i=1}^{N}a_{0,i}\delta_{x_{0,i}}$ be a discrete measure. Assume that $\Gamma_{x_{0}}$ (defined in (4)) has full rank and that $m_{0}$ satisfies the Non Degenerate Source Condition.

In particular, for $\lambda=\frac{1}{\alpha}|\!|w|\!|_{2}$, we have

In fact, since $\Gamma_{x_{0}}$ has full rank, $\Phi_{\operatorname{Ext}m_{0}}$ has full rank as well and $m_{0}$ is identifiable (by Proposition 3). Therefore, Lemma 2 ensures that there is indeed one spike in each interval, with sign equal to $\eta_{0}(x_{0,i})$.

where $s_{0}=\operatorname{sign}(a_{0})=(\eta_{0}(x_{i,0}))_{1\leqslant i\leqslant N}$, and

The derivative of $E_{s_{0}}$ with respect to $x$ and $a$ reads

so that for $\lambda=0$, $w=0$ and using $y_{0}=\Phi_{x_{0}}a_{0}$, one obtains

$(\hat{a}_{0,0},\hat{x}_{0,0})=(a_{0},x_{0})$,

for any $(\lambda,w)\in W$, $\operatorname{sign}(\hat{a}_{\lambda,w})=s_{0}$,

The constructed amplitudes and locations $(\hat{a}_{\lambda,w},\hat{x}_{\lambda,w})$ coincide with those of the solutions of $\mathcal{P}_{\lambda}(y_{0}+w)$ for all $(\lambda,w)\in W$ such that $|\!|w|\!|_{2}\leqslant\alpha\lambda$. Possibly changing the value of $\lambda_{0}$ so that $D_{\alpha,\lambda_{0}}\subset W$, we obtain the desired result. ∎

Although this paper focuses on identifiable measures, Theorem 2 describes the evolution of the solutions of $\mathcal{P}_{\lambda}(y_{0}+w)$ for any input measure $m_{1}$ such that there exists $m_{0}$ which satisfies the non degenerate source condition and $y_{0}=\Phi m_{1}=\Phi m_{0}$. Instead of converging towards $m_{1}$, the solutions will converge towards $m_{0}$.

5 Extensions

The proof also extends to non-stationary filtering operators, i.e. which can be written as

6 Application to the ideal Low-pass filter

We first observe that the injectivity condition on $\Gamma_{x}$ assumed in Theorem 2 always holds.

As to whether or not the Non Degenerate Source Condition holds for discrete measures, we will discuss this matter in Section 4 more in depth. For now, let us mention that we have observed empirically that this condition holds under the hypotheses of Theorem $1.2$ in , namely that $\Delta(m)>\frac{1.87}{f_{c}}$, but also with measures with far smaller values of $\Delta(m)$.

Vanishing Derivatives Pre-certificate

We show in this section that, if the Non Degenerate Source Condition holds, the minimal norm certificate $\eta_{0}$ is characterized by its values on the support of $m_{0}$ and the fact that its derivative must vanish on the support of $m_{0}$. Thus, one may compute the minimal norm certificate simply by solving a linear system, without handling the cumbersome constraint $|\!|\eta_{0}|\!|_{\infty}\leqslant 1$.

Loosely speaking, we call pre-certificate any “good candidate” for a solution of (14). Typically, a pre-certificate is built by solving a linear system (with possibly a condition on its norm). The following pre-certificate appears naturally in our analysis.

The vanishing derivative pre-certificate associated with a measure $m_{0}=m_{a_{0},x_{0}}$ is $\eta_{\text{\tiny V}}=\Phi^{*}p_{\text{\tiny V}}$ where

It is clear that if the Source Condition (see Definition 4) holds, then $p_{\text{\tiny V}}$ exists (since Problem (31) is feasible). Observe that, in general, $\eta_{\text{\tiny V}}$ is not a certificate for $m_{0}$ since it does not satisfy the constraint $\|\eta_{\text{\tiny V}}\|_{\infty}\leqslant 1$. The following proposition gathers several facts about the vanishing derivative pre-certificate which show that it is indeed a good candidate for the minimal norm certificate.

Let $m_{0}=m_{a_{0},x_{0}}=\sum_{i=1}^{N}a_{0,i}\delta_{x_{0,i}}$ be a discrete measure. The following assertions hold.

Problem (31) is feasible and $\|\eta_{\text{\tiny V}}\|_{\infty}\leqslant 1$ if and only if the Source Condition holds and $\eta_{\text{\tiny V}}=\eta_{0}$.

If $\Gamma_{x_{0}}$ has full rank, then $m_{0}$ satisfies the Non Degenerate Source Condition if and only if Problem (31) is feasible and

The third assertion of Proposition 7 states that it is equivalent to check the Non Degenerate Source Condition on $\eta_{0}$ (Definition 5) or to check the same conditions on $\eta_{\text{\tiny V}}$. In case those conditions hold, one even has $\eta_{\text{\tiny V}}=\eta_{0}$ (first assertion). The main point of this equivalence is that the second assertion yields a practical expression to compute $\eta_{\text{\tiny V}}$ which may be used in numerical experiments (see Section 4.3).

For the first assertion, we observe that if Problem (31) is feasible (and thus $p_{\text{\tiny V}}$ exists) and $\|\eta_{\text{\tiny V}}\|_{\infty}\leqslant 1$, then $\eta_{\text{\tiny V}}\in\partial{|\!|m_{0}|\!|_{\text{TV}}}$ and the Source Condition holds. Hence, $\|p_{\text{\tiny V}}\|_{2}\geqslant\|p_{0}\|_{2}$. On the other hand the minimal norm certificate $\eta_{0}$ must satisfy all the constraints of (31), thus the minimality of the norms of both $\eta_{\text{\tiny V}}$ and $\eta_{0}$ implies that $\eta_{\text{\tiny V}}=\eta_{0}$. The converse implication is obvious.

For the second assertion, Problem (31) can be written as

which is a quadratic optimization problem in a Hilbert space with a finite number of affine equality constraints. Moreover, the assumption that $\Gamma_{x_{0}}$ has full rank implies that the constraints are qualified. Hence it can be solved by introducing Lagrange multipliers $u$ and $v$ for the constraints. One should therefore solve the following linear system to obtain the value of $p=p_{\text{\tiny V}}$

Solving for $(u,v)$ in these equations gives the result.

2 Necessary condition for support recovery

There is a priori no reason for the vanishing derivative pre-certificate $\eta_{\text{\tiny V}}$ to satisfy $|\!|\eta_{\text{\tiny V}}|\!|_{\infty}\leqslant 1$. Here, we prove that that is in fact a necessary condition for (noiseless) exact support recovery to hold on some interval $[0,\lambda_{0})$ with $\lambda_{0}>0$, i.e. the solutions of $\mathcal{P}_{\lambda}(y_{0})$ having exactly $N$ spikes which converge smoothly towards those of the original measure.

Then $\eta_{\text{\tiny V}}$ exists, $\|\eta_{\text{\tiny V}}\|_{\infty}\leqslant 1$ and $\eta_{\text{\tiny V}}=\eta_{0}$.

Let $p_{\lambda}=\frac{1}{\lambda}(y_{0}-\Phi m_{\lambda})=\frac{1}{\lambda}(\Phi_{x_{0}}a_{0}-\Phi_{x_{\lambda}}a_{\lambda})$ be the certificate defined by the optimality conditions (13). We show that $\Phi^{*}p_{\lambda}$ converges towards $\Phi^{*}\Gamma_{x_{0}}^{+,*}\begin{pmatrix}\operatorname{sign}(a_{0})\\ 0\end{pmatrix}=\eta_{\text{\tiny V}}$ (and that the latter exists).

On the other hand, we observe that for $\lambda$ small enough, $\operatorname{sign}(a_{\lambda})=\operatorname{sign}(a_{0})$, and using the notations of the proof of Theorem 2, the implicit equation $E_{s_{0}}(a_{\lambda},x_{\lambda},\lambda,0)=0$ holds. Differentiating that equation at $\lambda=0$ we obtain:

As a consequence, Problem (31) is feasible and we see that $\frac{y_{0}-\Phi_{x_{\lambda}}{a}_{\lambda}}{\lambda}$ converges uniformly (and thus in the $L^{2}$ strong topology) to $\Gamma_{x_{0}}(\Gamma_{x_{0}}^{*}\Gamma_{x_{0}})^{-1}\begin{pmatrix}\operatorname{sign}(a_{0})\\ 0\end{pmatrix}$ and $\Phi^{*}\left(\frac{y_{0}-\Phi_{x_{\lambda}}}{\lambda}\right)$ converges uniformly to $\Phi^{*}\Gamma_{x_{0}}^{+,*}\begin{pmatrix}\operatorname{sign}(a_{0})\\ 0\end{pmatrix}$ (which is precisely $\eta_{\text{\tiny V}}$ from the second assertion of Proposition 7).

Since $\|\Phi^{*}\left(\frac{y_{0}-\Phi_{x_{\lambda}}a_{\lambda}}{\lambda}\right)\|_{\infty}=\|\Phi^{*}p_{\lambda}\|_{\infty}\leqslant 1$ for all $\lambda>0$, we obtain that $\|\eta_{\text{\tiny V}}\|_{\infty}\leqslant 1$, hence the claimed result. ∎

3 Application to the Ideal Low-pass Filter

and compute $(\alpha_{i},\beta_{i})_{i=1}^{N}$ by imposing that $\eta_{\text{\tiny CF}}(x_{i})=\operatorname{sign}(a_{i})$ and $(\eta_{\text{\tiny CF}})^{\prime}(x_{i})=0$.

They show that the constructed pre-certificate is indeed a certificate, i.e. that $|\!|\eta_{\text{\tiny CF}}|\!|_{\infty}\leqslant 1$, provided that the support is separated enough (i.e. when $\Delta(m)\geqslant C/f_{c}$). This result is important since it proves that measures that have sufficiently separated spikes are identifiable. Furthermore, using the fact that $\eta_{\text{\tiny CF}}$ is not degenerate (i.e. $(\eta_{\text{\tiny CF}})^{\prime\prime}(x_{i})\neq 0$ for all $i=1,\ldots,N$), the same authors derive an $L^{2}$ robustness to noise result in , and Fernandez-Granda and Azais et al. use the constructed certificate to analyze finely the local averages of the spikes in .

From a numerical perspective, we have investigated how this pre-certificate compares with the vanishing derivative pre-certificate that appears naturally in our analysis, by generating real-valued measures for different separation distances and observing when each pre-certificate $\eta$ satisfies $|\!|\eta|\!|_{\infty}\leqslant 1$.

As predicted by the result of , we observe numerically that the pre-certificate $\eta_{\text{\tiny CF}}$ is a certificate (i.e. $|\!|\eta_{\text{\tiny CF}}|\!|_{\infty}\leqslant 1$) for any measure with $\Delta(m_{0})\geqslant 1.87/f_{c}$. We also observe that this continues to hold up to $\Delta(m_{0})\geqslant 1/f_{c}$. Yet, below $1/f_{c}$, it may happen that some measures are still identifiable (as asserted using the vanishing derivative pre-certificate $\eta_{\text{\tiny V}}$) but $\eta_{\text{\tiny CF}}$ stops being a certificate, i.e. $|\!|\eta_{\text{\tiny CF}}|\!|_{\infty}>1$. A typical example is shown in Figure 3, where, for $f_{c}=6$ we have used three equally spaced masses as an input, their separation distance being $\Delta(m_{0})\in\{\frac{0.8}{f_{c}},\frac{0.7}{f_{c}},\frac{0.6}{f_{c}},\frac{0.5}{f_{c}}\}$. Here, we have computed an approximation of the minimal norm certificate $\eta_{0}$ by solving ($\mathcal{D}_{\lambda}(y_{0})$) with very small $\lambda$.

For $\Delta(m_{0})=\frac{0.8}{f_{c}}$, both $\eta_{\text{\tiny V}}$ and $\eta_{\text{\tiny CF}}$ are certificates, so that the vanishing derivatives pre-certificate $\eta_{\text{\tiny V}}$ is equal to the minimal norm certificate $\eta_{0}$. For $\Delta(m_{0})=\frac{0.7}{f_{c}}$, $\eta_{\text{\tiny CF}}$ violates the constraint $|\!|\eta_{\text{\tiny CF}}|\!|_{\infty}\leqslant 1$ but the vanishing derivative pre-certificates is still a certificate (even showing that the measure is identifiable). For $\Delta(m_{0})=\frac{0.6}{f_{c}}$ and $\frac{0.5}{f_{c}}$, neither $\eta_{\text{\tiny V}}$ nor $\eta_{\text{\tiny CF}}$ satisfy the constraint, hence $\eta_{\text{\tiny V}}\neq\eta_{0}$. Yet, $\eta_{0}$ ensures that $m_{0}$ is a solution to ($\mathcal{P}_{0}(y_{0})$).

From the experiments we have carried out, we have observed that the vanishing derivative pre-certificate $\eta_{\text{\tiny V}}$ behaves in general at least as well as the square Fejer $\eta_{\text{\tiny CF}}$. The only exceptions we have noticed is for a large number of peaks (when $N$ is close to $f_{c}$), with $\Delta(m_{0})\leqslant\frac{1.5}{f_{c}}$. This is illustrated in Figure 4 which shows a measure $m_{0}$ for which $\eta_{\text{\tiny CF}}$ is a non-degenerate certificate (which shows that it is identifiable), but for which $\eta_{0}\neq\eta_{\text{\tiny V}}$ since $|\!|\eta_{\text{\tiny V}}|\!|_{\infty}>1$ (thus $\eta_{\text{\tiny V}}$ is not a certificate). Typically, we have in this case $\operatorname{Supp^{\pm}}m_{0}\subsetneq\operatorname{Ext^{\pm}}(m_{0})$. Such a measure is identifiable but there is no support recovery for $\lambda>0$ (in the sense of Proposition 8), hence its support is not stable.

Discrete Sparse Spikes Deconvolution

This is nothing but the so-called basis pursuit denoising problem , also known as the Lasso in statistics. Indeed, defining the linear operator $\Psi$ through

so that $|\!|m|\!|_{\text{TV},\mathcal{G}}=+\infty$ when $\operatorname{Supp}(m)\not\subset\mathcal{G}$, and $\sum_{i=1}^{N}|a_{i}|$ otherwise.

2 Certificates over a Discrete Grid

We also introduce the corresponding dual problems:

Let us denote by $G$ the image by $\Phi$ of all measures with support in $\mathcal{G}$. It may happen (for instance if the grid is too rough) that $y_{0}\notin G$, in which case ($\mathcal{P}_{0}^{\mathcal{G}}(y_{0})$) is not feasible and ($\mathcal{D}_{0}^{\mathcal{G}}(y_{0})$) has infinite value. But ($\mathcal{P}_{\lambda}^{\mathcal{G}}(y_{0})$) is then equivalent to $\mathcal{P}_{\lambda}^{\mathcal{G}}(y_{0,G})$ where $y_{0}=y_{0,G}+y_{0,G^{\perp}}$ is an orthogonal decomposition. Problem ($\mathcal{P}_{\lambda}^{\mathcal{G}}(y_{0})$) is thus an approximation of $\mathcal{P}_{0}^{\mathcal{G}}(y_{0,G})$, and the relevant dual problems are $\mathcal{D}_{\lambda}^{\mathcal{G}}(y_{0,G})$ and $\mathcal{D}_{0}^{\mathcal{G}}(y_{0,G})$. For the sake of simplicity, we shall assume from now on that $y_{0}\in G$, but the reader may keep in mind that this hypothesis can be withdrawn by replacing $y$ with $y_{0,G}$.

As a consequence, a solution to ($\mathcal{D}_{0}^{\mathcal{G}}(y_{0})$) always exists, so that we may define the discrete minimal norm certificate:

The solutions of ($\mathcal{P}_{\lambda}^{\mathcal{G}}(y_{0})$) and ($\mathcal{D}_{\lambda}^{\mathcal{G}}(y_{0})$) (resp. ($\mathcal{P}_{0}^{\mathcal{G}}(y_{0})$) and ($\mathcal{D}_{0}^{\mathcal{G}}(y_{0})$)) are related by the extremality conditions (13) (resp. (14)) where the total variation is replaced with its discrete counterpart $|\!|\cdot|\!|_{\text{TV},\mathcal{G}}$.

3 Noise Robustness

As in the continuous case (cf. Section 3), the support of the solutions of $\mathcal{P}_{\lambda}^{\mathcal{G}}(y_{0}+w)$ for $\lambda\to 0^{+}$ and $|\!|w|\!|_{2}=O(\lambda)$ is governed by the minimal norm certificate. We introduce here the discrete counterpart of the extended support of a measure.

and the extended signed support relatively to $\mathcal{G}$ as

It is important to notice that the assumption $y_{0}\in G$ does not mean that the support of $m_{0}$ is included in $\mathcal{G}$, but that there exists a measure with support included in $\mathcal{G}$ which produces the same observation $y_{0}$. Therefore the support of $m_{0}$ and its extended support may even be disjoint.

As in the continuous case, notice that $m_{0}$ is a solution of ($\mathcal{P}_{0}^{\mathcal{G}}(y_{0})$) if and only if $\operatorname{Supp^{\pm}}(m_{0})\subset\operatorname{Ext^{\pm}_{\mathcal{G}}}(m_{0})$.

Now, if $\Phi_{J}$ has full rank, we can invert the extremality condition:

In order to get the exact recovery of the signed support for small noise, we may assume in addition that $\operatorname{Supp^{\pm}}(m_{0})=\operatorname{Ext^{\pm}_{\mathcal{G}}}(m_{0})$ so as to obtain a result analogous to Theorem 2. Precisely, we obtain the following theorem which was initially proved by Fuchs . First, we introduce a pre-certificate.

This pre-certificate, introduced in , is a certificate for $m_{0}$ if and only if $|\!|\eta_{\text{\tiny F}}|\!|_{\infty,\mathcal{G}}\leqslant 1$, in which case it is equal to the discrete minimal norm pre-certificate $\eta_{0}^{\mathcal{G}}$.

If $\Phi_{\operatorname{Supp}m_{0}}$ has full rank, then $\eta_{\text{\tiny F}}$ can be computed by solving a linear system:

For deconvolution problems, an important issue is that Corollary 3 is useless when studying the stability of the original infinite dimensional problem ($\mathcal{P}_{\lambda}(y_{0})$). Indeed, the pre-certificate (38) is not constrained to have vanishing derivatives, so that it generally takes some values strictly greater than $1$ for a generic discrete input measure $m_{0}$. When the stepsize of the grid is small enough, such values are sampled and $|\!|\eta_{\text{\tiny F}}|\!|_{\infty,\mathcal{G}}$ necessarily becomes strictly larger than one. As detailed in Section 4, when shifting from the discrete grid setting to the continuous setting, the natural pre-certificate to consider is the vanishing derivative pre-certificate $\eta_{\text{\tiny V}}$ defined in (31), and not the pre-certificate $\eta_{\text{\tiny F}}$.

4 Structure of the Extended Support for Thin Grids

In the previous section, we have introduced the notion of extended signed support of a measure $m_{0}$ relatively to a grid $\mathcal{G}$, and we have proved that this set, $\operatorname{Ext^{\pm}_{\mathcal{G}}}{m_{0}}$, contains the signed supports of all the reconstructed measures for small noise. In this section, we focus on the structure of the extended support. We show that, if the support of $m_{0}$ belongs to the grid for a sufficiently small stepsize and if the Non Degenerate Source Condition holds, the extended signed support consists in the signed support of $m_{0}$ and possibly one immediate neighbor with the same sign for each spike. Therefore, when the grid stepsize is small enough, the support of the measure is generally not stable for the discrete problem, but the support of the reconstructed measure is a close approximation of the original one.

From now on, for the sake of simplicity, we consider dyadic grids $\mathcal{G}_{n}=\left\{\frac{j}{2^{n}}\;;\;~0\leqslant j\leqslant 2^{n}-1\right\}$. The constraint sets in $\mathcal{D}_{\lambda}^{\mathcal{G}_{n}}(y_{0})$ and ($\mathcal{D}_{\lambda}(y_{0})$) are denoted respectively by

The structure of $\operatorname{Ext^{\pm}_{\mathcal{G}}}(m_{0})$ for large $n$ is intimately related to the convergence of $p^{\mathcal{G}_{n}}_{0}$ to $p_{0}$. First, let us notice the following result, whose proof is given in Appendix C.

Moreover, if there exists a solution to the continuous dual problem ($\mathcal{D}_{0}(y_{0})$),

The proofs given below make use of a remark given in : if a solution of the continuous problem ($\mathcal{P}_{0}(y_{0})$) has support in the grid $\mathcal{G}$, then it is also a solution of the discrete problem ($\mathcal{P}_{0}^{\mathcal{G}}(y_{0})$).

where $\eta_{0}=\Phi^{*}p_{0}$ (resp. $\eta_{0}^{\mathcal{G}_{n}}=\Phi^{*}p_{0}^{\mathcal{G}_{n}}$) denotes the corresponding minimal norm certificate.

First, following , we observe that, since $(\Phi^{*}p_{0})(x_{i})=\operatorname{sign}(a_{i})$ and $|\!|\Phi^{*}p_{0}|\!|_{\infty}\leqslant 1$ (a fortiori $|\Phi^{*}p_{0}\left(\frac{j}{2^{n}}\right)|\leqslant 1$ for $1\leqslant j\leqslant 2^{n}-1$), $\Phi^{*}p_{0}$ is also a dual certificate for $(\mathcal{P}_{0}^{\mathcal{G}_{n}})$ provided $n\geqslant n_{0}$. As a consequence $|\!|p_{0}^{\mathcal{G}_{n}}|\!|_{2}\leqslant|\!|p_{0}|\!|_{2}$.

The consequence regarding $\eta_{0}^{\mathcal{G}_{n}}$ is straightforward. ∎

We may now describe the structure of the extended support for dyadic measures which satisfy the Non Degenerate Source Condition.

Let $m_{0}=\sum_{i=1}^{N}a_{i}\delta_{x_{i}}$ be a discrete dyadic measure which satisfies the Non Degenerate Source Condition. Then, for $n$ large enough, there exists $\varepsilon^{n}\in\{+1,-1\}^{N}$ such that:

where $\operatorname{Supp^{\pm}}(m_{0})+\frac{\varepsilon^{n}}{2^{n}}=\left\{(x_{i}+\frac{\varepsilon^{n}_{i}}{2^{n}},\eta_{0}^{\mathcal{G}_{n}}(x_{i}))\;;\;1\leqslant i\leqslant N\right\}$.

Therefore, by Proposition 10, for $n$ large enough:

$|\eta_{0}^{\mathcal{G}_{n}}(t)|\geqslant\frac{C}{2}>0$ for $t\in(x_{i,0}-\varepsilon,x_{i,0}+\varepsilon)$,

$|(\eta_{0}^{\mathcal{G}_{n}})^{\prime\prime}(t)|\geqslant\frac{C}{2}>0$ for $t\in(x_{i}-\varepsilon,x_{i}+\varepsilon)$,

$\sup_{K_{\varepsilon}}|\eta_{0}^{\mathcal{G}_{n}}|<1$,

and in each interval $(x_{i,0}-\varepsilon,x_{i}+\varepsilon)$, $\eta_{0}^{\mathcal{G}_{n}}$ has the same sign as $\eta_{0}$ and it is strictly concave (resp. strictly convex) if $\eta_{0}(x_{i})=1$ (resp. $-1$).

Assume for instance that $\eta_{0}(x_{i})=1$. The extremality conditions between $p_{0}$ and $m_{0}$ for $(\mathcal{P}_{0}(y))$ also imply that $m_{0}$ is a solution of $(\mathcal{P}_{0}^{\mathcal{G}_{n}}(y_{0}))$. Then, the extremality conditions between $p_{0}^{\mathcal{G}_{n}}$ and $m_{0}$ imply that $\eta_{0}^{\mathcal{G}_{n}}(x_{i})=1$ as well. By the strict concavity of $\eta_{0}^{\mathcal{G}_{n}}$ there is at most one other point $t^{\star}\in(x_{i}-\varepsilon,x_{i}+\varepsilon)$ such that $\eta_{0}^{\mathcal{G}_{n}}(t^{\star})=1$, and since $\eta_{0}^{\mathcal{G}_{n}}(x_{i}\pm\frac{1}{2^{n}})\leqslant 1$, $|t^{\star}-x_{i}|\leqslant\frac{1}{2^{n}}$. Such a point $t^{\star}$ contributes to the extended support of $m$ if and only if it belongs to the grid (i.e. $t^{\star}=x_{i}\pm\frac{1}{2^{n}}$).

The argument for $\eta_{0}(x_{i})=-1$ is similar. This concludes the proof. ∎

Corollary 4 highlights the difference between the continuous and the discretized problems. In the first case, any small noise would induce a slight perturbation of the spikes locations and amplitudes, but their number would stay the same. In the second case, the spikes cannot “move”, so that new spikes may appear, but only at one of the immediate neighbors of the original ones.

For non-dyadic measures, we may show using Proposition 9 that for small, fixed $\lambda>0$, and $n$ large enough, there is at most one pair of spikes (located at consecutive points of the grid) in the neighborhood of each original spike. From our numerical experiments described below (in the case of the ideal low-pass filter), we conjecture that, in the case where there are indeed two spikes, they surround the location of the original spike.

5 Application to the Ideal Low-pass Filter

The Fuchs precertificate $\eta_{\text{\tiny F}}$ is also shown. Some points $t$ of the grid do not satisfy $|\eta_{\text{\tiny F}}(t)|\leqslant 1$, hence the Fuchs pre-certificate is not a certificate and the support is not stable. This was already clear from the fact that $\operatorname{Supp}(m_{0})\subsetneq\operatorname{Ext}_{\mathcal{G}_{n}}(m_{0})$.

Set convergence.

As a consequence $C_{n}$ is the polar set of the convex hull of $\left\{\pm\varphi_{\frac{j}{2^{n}}}\;;\;0\leqslant j\leqslant 2^{n}-1\right\}$.

In the case of the Dirichlet kernel, the vector space $\operatorname{Im}\Phi$ is the space of trigonometric polynomials with degree less than or equal to $f_{c}$. An orthonormal basis of $\operatorname{Im}\Phi$ is given by: $(c_{0},c_{1},\ldots c_{f_{c}},s_{1},\ldots s_{f_{c}})$ where $c_{0}\equiv 1$, $c_{k}:t\mapsto\sqrt{2}\cos(2\pi kt)$ and $s_{k}:t\mapsto\sqrt{2}\sin(2\pi kt)$ for $1\leqslant k\leqslant f_{c}$.

For $f_{c}=1$, we obtain $\varphi_{x}=\frac{1}{3}\left(c_{0}+\sqrt{2}\left(\cos(2\pi x)c_{1}+\sin(2\pi x)s_{1}\right)\right)$, and the vectors $\varphi_{x}$ lie on a circle. The convex hull of $\left\{\pm\varphi_{\frac{j}{2^{n}}}\;;\;0\leqslant j\leqslant 2^{n}-1\right\}$ is thus a cylinder, and its polar set $C_{n}$ is displayed in Figure 7 for $n=3$, $4$, and $7$.

Conclusion

In this paper, we have given a precise statement about the support recovery property of sparse spikes deconvolution with total variation regularization. This support recovery is governed by the non-degeneracy of a minimal norm certificate. This hypothesis can be checked by computing a vanishing derivative pre-certificate, which can be computed in closed form. We have shown that under this non-degeneracy hypothesis, one recovers the same number of spikes and that these spikes converge to the original ones when $\lambda$ and $|\!|w|\!|/\lambda$ are small enough. While previous stability results hold for an arbitrary noise level and make use of any non-degenerate certificate, they are formulated in terms of local averages of the recovered measure and do not describe precisely the support. In contrast, our result which requires a specific certificate to be non-degenerate and a regime where $\lambda$ and $|\!|w|\!|/\lambda$ are small enough provides exact support stability. These settings and results are thus not comparable, and provide complementary informations about the performance of total variation regularization.

Finally, let us note that the proposed method extends to non-stationary filtering operators and to arbitrary dimensions.

Acknowledgements

The authors would like to thank Jalal Fadili, Charles Dossal and Samuel Vaiter for fruitful discussions. This work has been supported by the European Research Council (ERC project SIGMA-Vision).

Appendix A Auxiliary results

For the convenience of the reader, we give here the proofs of several auxiliary results which are needed in the discussion.

There exists a solution to ($\mathcal{P}_{0}(y_{0})$) and the strong duality holds between ($\mathcal{P}_{0}(y_{0})$) and ($\mathcal{D}_{0}(y_{0})$), i.e.

Moreover, if a solution $p^{\star}$ to ($\mathcal{D}_{0}(y_{0})$) exists,

where $m^{\star}$ is any solution to ($\mathcal{P}_{0}(y_{0})$). Conversely, if (53) holds, then $m^{\star}$ and $p^{\star}$ are solutions of respectively ($\mathcal{P}_{0}(y_{0})$) and ($\mathcal{D}_{0}(y_{0})$).

We apply [17, Theorem II.4.1] to ($\mathcal{D}_{0}(y_{0})$) (and not to ($\mathcal{P}_{0}(y_{0})$) as would be natural) rewritten as

Appendix B Proof of Proposition 6

It is therefore sufficient to prove that the columns of the following matrix are linearly independent

If $N<f_{c}$, we complete the family $\{r_{1},\ldots r_{N}\}$ in a family $\{r_{0},r_{1},\ldots r_{f_{c}}\}\subset\SS^{1}$ such that the $r_{i}$’s are pairwise distinct. We obtain a square matrix $M$ by inserting the corresponding columns

Hence, $F$ has at least $2f_{c}+1$ roots in $\SS^{1}$, counting the multiplicities. This imposes that $F=0$, thus $\alpha=0$, and $M$ is invertible. The result is proved.

Appendix C Proof of Proposition 9

Moreover, by the characterization of the projection onto convex sets:

Thus $p_{\lambda}^{\star}$ is the orthogonal projection of $\frac{y_{0}}{\lambda}$ on $C$: $p_{\lambda}^{\star}=P_{C}\left(\frac{y_{0}}{\lambda}\right)=p_{\lambda}$. Since this is true for any subsequence, the whole sequence $p_{\lambda}^{\mathcal{G}_{n}}$ weakly converges to $p_{\lambda}$.

Moreover, by lower semincontinuity and the inclusion $C\subset C_{n}$ we have:

so that $\frac{y_{0}}{\lambda}-p_{\lambda}^{\mathcal{G}_{n}}$ converges strongly to $\frac{y_{0}}{\lambda}-p_{\lambda}$, hence the strong convergence of $p_{\lambda}^{\mathcal{G}_{n}}$ to $p_{\lambda}$.

The rest of the statement follows from Proposition 1.

References