Vincent Duval
email: vincent.duval@inria.fr

Gabriel Peyré
email: gabriel.peyre@ens.fr

Sparse Spikes Super-resolution on Thin Grids II: the Continuous Basis Pursuit

This article analyzes the performance of the Continuous Basis Pursuit (C-BP) method for sparse super-resolution. The C-BP has been recently proposed by Ekanadham, Tranchina and Simoncelli as a refined discretization scheme for the recovery of spikes in inverse problems regularization. One of the most well known discretization scheme, the Basis Pursuit (BP, also known as Lasso) makes use of a finite dimensional 1 norm on a grid. In contrast, the C-BP uses a linear interpolation of the spikes positions to enable the recovery of spikes between grid points. When the sought-after solution is constrained to be positive, a remarkable feature of this approach is that it retains the convexity of the initial 1 problem. The present paper shows how the C-BP is able to recover the spikes locations with sub-grid accuracy in the favorable case. We also prove that this regime generally breaks when the grid is too thin, and we describe precisely the artifacts that appear: each spike is approximated by a pair of Dirac masses. We show numerical illustrations of these phenomena, and evaluate numerically the validity of the technical assumptions of our analysis.

Introduction

This article studies a specific convex optimization approach, the Continuous Basis-Pursuit (C-BP) for sparse super-resolution. A detailed review of the literature on superresolution, and in particular variational regularization technics, can be found in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF], which is dedicated to the Basis Pursuit (BP, or Lasso) method.

In the following, we focus for simplicity on the compact 1-D domain T = R/Z (i.e. an interval with periodic boundary conditions), but the algorithms considered (Lasso and C-BP) can be extended to higher dimensional settings (see Section 1.6).

Super-resolution

We formalize the sparse super-resolution problem mathematically as the question of recovering an unknown Radon measure m 0 ∈ M(T) defined on the torus T = R/Z from noisy linear observations in a separable Hilbert space H, which we write as

y = Φ(m 0 ) + w ∈ H (1)
where w ∈ H is some measurement noise. The terminology "super-resolution" refers here to the fact that Φ : M(T) → H is a bounded linear map defined through the integration against a continuous kernel function ϕ :

T → H ∀ x ∈ T, Φ(m) = T ϕ(x)dm(x). (2)
The continuity of ϕ is crucial, since it allows one to pose the problem over the space of measures, and thus enables the possible recovery of highly localized solutions (e.g. sums of Dirac masses). In order to avoid unnecessary technicalities, we only consider smooth impulse responses (typically ϕ ∈ C 5 (T, H)).

A typical class of such problems are the so-called deconvolution problems, when the operator Φ is translation invariant. This corresponds to using H = L 2 (T), ϕ(x) : x → φ(x -x) for some smooth kernel φ defined on T. This deconvolution setup is equivalent to computing the measurements over the Fourier domain. When the highest measured frequency f c is finite, this corresponds to using H = C 2fc+1 and ϕ(x) = ( φk e 2ikxπ ) fc k=-fc for some weights φk ∈ C which are the Fourier coefficients of φ.

Sparse Regularization

Since Φ is usually ill-posed, a regularization scheme is needed to perform its inversion. Following several recent works (see for instance [START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF]), we study here sparse regularizations induced by the total variation of the measure (i.e. the total absolute mass)

|m|(T) def. = sup T ψ(x)dm(x) ; ψ ∈ C (T), ψ ∞ 1 . (3)
For discrete measures defined on a finite grid

G def. = {z i ; i ∈ 0, G -1 } ⊂ T (4)
of points, which take the form

m a,G def. = G-1 i=0 a i δ z i ∈ M(T),
the total variation is equal to the usual discrete 1 norm

|m a,G |(T) = a 1 = i |a i |,
which is at the heart of the celebrated Basis Pursuit [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] method (also known as the Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]). The total variation is thus the natural way to extend these intrinsically discrete and finite-dimensional methods to the infinite-dimensional class of Radon measures, to enable a grid-free regularization.

This total variation is used as a regularizer to define the Beurling LASSO (BLasso) [START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF] min m∈M(T)

1 2 y -Φ(m) 2 H + λ|m|(T). (5)
which is an infinite dimensional convex optimization problem. In the noiseless setting, w = 0, taking the limit λ → 0 leads to the following constrained problem min m∈M(T) {|m|(T) ; Φ(m) = Φ(m 0 )} .

From BP to C-BP

The simplest way to compute approximate solutions to [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] is to restrict the solution to live in the finite dimensional sub-space of measures supported on the grid G defined in [START_REF] Bredies | Inverse problems in spaces of measures[END_REF]. This is exactly equivalent to computing the weights a of the measure by solving the BP problem

min a∈R G 1 2 y -Φ G a 2 H + λ a 1 (7)
where we defined the restriction of Φ to the discretization grid as

Φ G a def. = Φ(m a,G ) = G-1 i=0 a i ϕ(z i ) (8)
To obtain a better approximation of the infinite dimensional problem, [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] proposes to perform a first order approximation of the kernel,

G-1 i=0 a i ϕ(z i + s i ) ≈ G-1 i=0 a i ϕ(z i ) + G-1 i=0 a i s i ϕ (z i ). (9)
We introduce the derivative operator restricted to the sampling grid

Φ G b def. = Φ (m b,G ) = G-1 i=0 b i ϕ (z i ), (10)
and to ease the exposition, we consider a uniform grid G def.

= {i/G ; i ∈ 0, G -1 } of G points, so that the grid size is h def.

= 1/G. The C-BP method of [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] assumes that the unknown measure is nonnegative, and, after a change of variables, solves min

(a,b)∈R G ×R G 1 2 y -Φ G a -Φ G b 2 H + λ a 1 subject to |b| h 2 a, (11)
where the inequality should be understood component-wise. Note also that the obtained a is always nonnegative, hence the C-BP method is tailored for the recovery of nonnegative measures. This is a convex optimization problem, which can be solved using traditional conic optimization methods. As detailed in Section 2.2, this problem can also be re-cast as a Lasso in dimension 2G with positivity constraints (see Section 2.2).

Hence it can be solved using a large variety of first order proximal method, the most simple one being the Forward-Backward, see [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] and the references therein. If (a , b ) are solutions of [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], one recovers an output discrete measure defined by

m = a i =0 a i δ x i where x i def. = ih + b i a i , (12)
where we set b i a i = 0 whenever a i = 0. The rationale behind [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] is to perform a first order Taylor approximation of the operator Φ, where the variable τ i def.

= b i /a i ∈ [-h/2, h/2] encodes the horizontal shift of the Dirac location with respect to the grid sample ih. The landmark idea introduced in [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] is that, while the optimization is non-convex with respect to the pair (a, τ ), it is convex with respect to the pair (a, b).

Previous Works

There is a large body of literature on the study of the recovery performance of the Lasso problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. We refer to the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF] for a detailed overview. Let us however insist on the fact that only a small part of these previous works tackles the super-resolution case where the operator Φ is highly "correlated", which can be informally understood as cases associated to a continuous underlying kernel ϕ. As highlighted above, these cases are naturally paired with a continuous infinite dimensional problem [START_REF] Candès | Super-Resolution from Noisy Data[END_REF]. The theoretical analysis of this setting is recent, and we refer in particular to the works [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF] which showed that some minimal separation between the spikes (the so-called "Rayleigh limit") is necessary and sufficient to achieve exact recovery in the absence of noise, for deconvolution problems. Several related works have studied the impact of noise on this recovery, see for instance [START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Candès | Super-Resolution from Noisy Data[END_REF][START_REF] Fernandez-Granda | Support detection in super-resolution[END_REF][START_REF] Azais | Spike detection from inaccurate samplings[END_REF]. In two recent papers, including the initial work [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] and the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF], we have shown how to transfer support stability properties of the infinite dimensional BLasso (5) to the discretized Lasso problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. Most notably, these results show that solutions of the discrete Lasso problem estimate in general twice the number of spikes of the input measure. It is important to note that in the special case where m 0 is a nonnegative measure (which is the setup considered by the C-BP method) and Φ is a convolution with a typical kernel such as Dirichlet or Gauss, m 0 is always a solution to [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF] (see for instance [START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Schiebinger | Superresolution without Separation[END_REF] and [START_REF] Denoyelle | Support Recovery for Sparse Deconvolution of Positive Measures[END_REF] for a refined analysis of the stability to noise in this special case).

Contributions and organization of the paper

The main purpose of this paper is to evaluate the behavior of the C-BP and its reconstruction artifacts, in the same spirit as the results in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF] for the basic Lasso.

First of all, Section 2 shows that the C-BP problem [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] can be recast as a Lasso under positivity constraints. It proposes an abstract analysis of support stability properties of such a class of problems, under a non-degeneracy condition (hypothesis (34)), see Theorem 1. The framework is general, and the results hold when Φ G , Φ G are replaced with any linear operator A and B.

In Section 3, we turn to the C-BP problem as a method for solving continuous inverse problems (e.g. deconvolution) with the help of a grid. First, we highlight a regime in which the C-BP recovers the spikes locations with sub-grid accuracy. This is the ideal situation. But we notice that this regime generally breaks if the grid is too thin. The rest of the paper is devoted to describe the situation in that less favorable setting. We show the Γ-convergence of Problem [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], as the grid gets thinner and thinner, towards the BLasso (5) with positivity constraints: the solutions of [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] converge in the weak* topology towards solutions of [START_REF] Candès | Super-Resolution from Noisy Data[END_REF].

Section 4 is devoted to a fine analysis of the support of the solutions using thin grids. First, for fixed λ > 0 and under a mild assumption, we prove that each spike of the solution to ( 5) is approximated with one or two consecutive spikes, and those spikes are "blocked" at half-grid points. It is remarkable that, although the situation is a priori considerably richer than with the Lasso (see Table 1), the C-BP yields a similar behavior in practice.

One may object that those artifacts are due to too large values of λ or the noise level. We study the low noise regime (λ and w H small, i.e. of order O(h 3 )) associated with those thin grids, and we show that, under some non-degeneracy condition (the "Twice Non-Degenerate Source Condition", see Definition 5), the recovered spikes still appear in pairs (see Theorem 3), one of them being "free"

m λ = N ν=1 α (1) λ,ν δ xν +tν + α (2) λ,ν δ xν +εν h/2
where

ε ν ∈ {-1, +1}, -h/2 < t ν < h/2,
and we provide a closed form expression for ε, which depends on some corresponding natural shift intrinsic to the measure. The corresponding low noise regime is characterized by

w H λ = O(1) and λ = O(h 3
), which should be compared with the one for the Lasso:

w H λ = O(1) and λ = O(h).
Let us mention that this result holds for unknown spikes that are not necessarily on the grid, but in its neighborhood (i.e. at distance at most O(h 3/2 ) from some point of the grid), that is a situation which is a priori favorable to C-BP (as the Taylor expansion ( 9) is a good approximation).

Let us also stress the fact that the results of Section 4 do not follow from the study in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF], as they crucially depend on the structure of the operator (Φ G Φ G ) and the cone constraint. As a result, the conditions for the low noise regime and the quantities involved in the natural shift are different from the Lasso. Moreover, those results crucially depend on the structure of the C-BP (two operators, the latter being the derivative of the former).

Eventually, we illustrate in Section 5 these theoretical results with numerical experiments comparing Lasso and C-BP. We first highlight in Section 5.1 the improvements brought by C-BP over Lasso for spikes that are isolated and that fall offthe-grid. Then, we explore the validity of the Twice Non-Degenerate Source Condition, and we highlight the doubling phenomenon. We display the evolution of the solution path λ → a λ (a solution of ( 7)) and λ → (a λ , b λ ) (a solution of [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]). These paths are piecewise-affine, and our contributions (Theorem 3) precisely characterize the first affine segment of these paths, which perfectly matches the numerical observations.

To summarize, this paper shows how the C-BP is able to reach sub-grid accuracy in favorable situation, outperforming the Lasso. It also proves, however, that there is a regime where artifacts appear. A natural question is whether those artifacts appear on the typical grids used by practitioners. Our numerical experiments suggest that their appearance depends not only on the grid size, but also on the complexity of the measure to recover (are the spikes well separated or densely clustered?). For simple input measures (i.e. not densely clustered), the phenomenon only appears on very thin grids, so that the practitioner usually obtains the correct number of spikes, with a fairly precise estimation of the locations. However, if the measure has dense clusters, the phenomenon is likely to appear even on grids that are not so thin, preventing a faithful estimation of the support.

The limitation of the Lasso and C-BP are due to the polyhedral nature of the finite-dimensional approximation functional (related to the 1 norm). Improving support recovery requires to use more advanced approximation, for instance SDP relaxation as introduced in [START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF][START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]. These methods are truly off-the-grid, and thus do not perform a polyhedral approximation of the continuous problem. They suffer however from other difficulties (large computational cost, difficult analysis of support recovery in more than 1 dimension, . . . ).

Extensions

While we restrict here the exposition to 1-D problems, the C-BP formulation [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] can be extended to cope with measures in arbitrary dimension d 1, i.e. to consider m 0 ∈ M(T d ). This requires to define at each sampling grid point indexed by i a vector

b i = (b i,k ) d k=1 ∈ R d together with the constraint b i ∞ h 2 a i , and also to use a matrix Φ G defined as Φ G b def. = i∈G d k=1 b i,k ∂ k ϕ(x i ) ∈ H
where ∂ k denote the differential operator with respect to the k th direction in R d . The optimality conditions stated in this paper should readily extend to this setting, but the fine analysis of the support seems nontrivial to adapt.

The paper [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] also proposes other interpolation schemes than a first order Taylor expansion at the grid points. In particular, they develop a "polar" interpolation which makes use of two adjacent grid points. This method seems to outperform the linear interpolation in practice, and has been employed to perform spikes sorting in neuronal recordings [START_REF] Ekanadham | A unified framework and method for automatic neural spike identification[END_REF].

Extending the results we propose in the present paper to these higher dimensional settings and alternative interpolation schemes is an interesting avenue for future work.

Let us also mention that an important problem is to extend the C-BP method [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF] to measures with arbitrary signs and that can even be complex-valued. Unfortunately, the corresponding constraint |b| |a| is then non-convex, which makes the mathematical analysis apparently much more involved. A non-convex and non-smooth optimization solver is proposed for this problem in [START_REF] Florescu | A Constrained Optimization Approach For Complex Sparse Perturbed Models[END_REF], and shows promising practical performance for spectrum estimation.

Notations and preliminaries

The set of Radon measures (resp. nonnegative Radon measures) is denoted by M(T) (resp. M + (T)). Endowed with the total variation norm (3), M(T) is a Banach space. Another useful topology on M(T) is the weak* topology: a sequence of measures (m n ) n∈N weakly* converges towards m ∈ M(T) if and only if for all ψ ∈ C (T), lim n→+∞ T ψdm n = T ψdm. Any bounded subset of M(T) (for the total variation) is relatively sequentially compact for the weak* topology. Moreover the topology induced by the total variation is stronger than the weak* topology, and the total variation is sequentially lower semi-continuous for the weak* topology. Throughout the paper, given α ∈ R N and x 0 ∈ T N , the notation m α,x 0 def. = N ν=1 α ν δ x 0,ν hints that α ν = 0 for all ν (contrary to the notation m a,G ), and that the x 0,ν 's are pairwise distinct.

The space H denotes a separable Hilbert space. As explained in the companion paper [12, Lemma 1], the operator Φ : M(T) → H defined in (2) is weak-* to weak continuous, and so are the operators involving the derivatives, for k ∈ N,

∀ m ∈ M(T), Φ (k) (m) = T ϕ (k) (x)dm(x).
Their respective adjoint operators, Φ (k), * : H → C (T), are given by (Φ (k), * q)(t) = q, ϕ (k) (t) for all q ∈ H, t ∈ T. Moreover, Φ (k), * q has the regularity of ϕ and

d k dt k (Φ * q)(t) = (Φ (k), * q)(t). The ∞, H-operator norm of Φ * : H → C (T) is defined as Φ * ∞,H def.
= sup { Φ * w ∞ ; w ∈ H, w H 1} (and the ∞, H operator norm of a matrix is defined similarly). Given a vector x 0 ∈ T N , Φ x 0 refers to the linear operator

R N → H, with ∀α ∈ R N , Φ x 0 α def. = Φ(m α,x 0 ) = N ν=1 α ν ϕ(x 0,ν ).
It may also be seen as the restriction of Φ to measures supported on the set {x 0,ν ; ν ∈ 1, N }. A similar notation is adopted for Φ x 0 , resp. Φ (k)

x 0 (replacing ϕ(x 0,ν ) with ϕ (x 0,ν ), resp. ϕ (k) (x 0,ν )). The concatenation of Φ x 0 and Φ x 0 is denoted by

Γ x 0 def. = Φ x 0 Φ x 0 .
We rely on the notion of set convergence. Given a sequence (C n ) n∈N of subsets of T, we define lim sup

n→+∞ C n = x ∈ T ; lim inf n→+∞ d(x, C n ) = 0 (13) lim inf n→+∞ C n = x ∈ T ; lim sup n→+∞ d(x, C n ) = 0 ( 14
)
where d is defined by d(x, C) = inf x ∈C |x -x| and |x -x | refers to the distance between x and x on the torus. If both sets are equal, let C be the corresponding set (then C is necessarily closed), we write

lim n→+∞ C n = C. ( 15
)
If the sequence (C n ) n∈N is nondecreasing (C n ⊂ C n+1 ), then lim n→∞ C n = n∈N C n , and if it is nonincreasing (C n ⊃ C n+1 ) then lim n→∞ C n = n∈N C n (
where C denotes the closure of C). We refer the reader to [START_REF] Rockafellar | Variational analysis. Grundlehren der mathematischen Wissenschaften[END_REF] for more detail about set convergence. We shall also use this notion in Hilbert spaces, with obvious adaptations.

Abstract analysis of the Lasso with cone constraint

This section studies a simple variant of the Lasso with cone constraint in an abstract setting. The results stated here shall be useful in Section 3, since this variant turns out to be the Continuous Basis-Pursuit when the degradation operator is the integration of an impulse response and its derivative.

Notations

Given a parameter h > 0, we consider the convex cone generated by the vectors (1, h

2 ) and (1, -h 2 ),

C h def. = (c, d) ∈ R × R ; c 0 and -c h 2 + |d| 0 . ( 16
)
We also define the cone

C G h as the set of vectors (a, b) ∈ R G × R G such that for all k ∈ 0, G -1 (a k , b k ) ∈ C h . Now, given a vector (a 0 , b 0 ) ∈ C G h (i.e. ∀k ∈ 0, G -1 , a 0,k 2 h |b 0,k |), we observe y 0 def.
= Aa 0 + Bb 0 , where A : R G → H and B : R G → H are linear operators, or its noisy version y = y 0 + w where w ∈ H. To recover (a 0 , b 0 ) from y or y 0 , we consider the following reconstruction problems:

min (a,b)∈C G h 1 2 y -Aa -Bb 2 H + λ a 1 , (Q λ (y))
and for λ = 0, min

(a,b)∈C G h a 1 such that Aa + Bb = y 0 . (Q 0 (y 0 ))
Our main focus is on the support recovery properties of (Q λ (y)). Precisely, we split the "support" of (a, b) ∈ C G h into several parts:

I def.
= supp(a)

def.

= {i ∈ 0, G -1 ; a i > 0} (17) = I (r) ∪ I (l) (18)
where

I (r) def. = i ∈ I ; a i + 2 h b i > 0 , I (l) def. = i ∈ I ; a i - 2 h b i > 0 . (19)
In general

I (r) ∩ I (l) = ∅. If (a λ , b λ ) is a solution of (Q λ (y))
, we say that we have exact support recovery provided that

I (r) (a λ , b λ ) = I (r) (a 0 , b 0 ) and I (l) (a λ , b λ ) = I (l) (a 0 , b 0 ).
Remark 1. The notation I (r) , I (l) shall become clearer in the next section. When considering the Continuous Basis-Pursuit on a grid with stepsize h > 0, points i in I (r) correspond to Dirac masses which "tend to be on the right", that is they do not coincide with the left half-grid point ih -h 2 . Similarly, points in I (l) correspond to Dirac masses which "tend to be on the left", as they do not coincide with the right half-grid point ih + h 2 . In fact, if i ∈ I (r) \ I (l) , it corresponds to a Dirac mass at the right half-grid point: δ ih+ h 2 , and if i ∈ I (l) \ I (r) , it corresponds to a Dirac mass at the left half-grid point: l) , it corresponds to a Dirac mass which may belong "freely" to the interval (ih -h 2 , ih + h 2 ) (see Figure 1).

δ ih-h 2 . If i ∈ I (r) ∩ I (

Parametrization as a positive Lasso

To characterize the solutions of (Q λ (y)) and (Q 0 (y 0 )), it is convenient to reparametrize the problem as a Lasso with positivity constraint, writing for all i ∈ 0, G -1 ,

a i b i def. = 1 1 h 2 -h 2 r i l i or r i l i = 1 2 1 h 1 2 -1 h a i b i (20)
In the following, we define the linear map

H h : r l -→ a b (21)
Observe that (a i , b i ) ∈ C h if and only if r i 0 and l i 0. Moreover, given (a, b) ∈ C G h ,

I c = {i ∈ 0, G -1 ; (r i , l i ) = (0, 0)} , I (r) = {i ∈ 0, G -1 ; r i > 0} , and
I (l) = {i ∈ 0, G -1 ; l i > 0} .
Therefore, Problems (Q λ (y)) and (Q 0 (y 0 )) are respectively equivalent to the Lasso and Basis Pursuit with positivity constraint: r) or I (l) , the spikes of the solutions to [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] are supported on half-grid points or in the interval ((i -1/2)h, (i + 1/2)h).

min (r,l)∈(R + ) G ×(R + ) G λ r l 1 + 1 2 y -A h r l 2 H ( Qλ (y)) (i -1)h ih (i + 1)h i ∈ I (l) \ I (r) (i -1)h ih (i + 1)h i ∈ I (r) \ I (l) (i -1)h ih (i + 1)h i ∈ I (r) ∩ I (l)
and min

(r,l)∈(R + ) G ×(R + ) G r l 1 such that A h r l = y 0 , ( Q0 (y 0 ))
where

A h def. = A + h 2 B A -h 2 B : R 2G → H.
The "support recovery" of (a 0 , b 0 ) through (Q λ (y)) is equivalent to the support recovery of (r 0 , l 0 ) through ( Qλ (y)).

As described below, the characterization of minimizers and the support recovery properties of the Lasso with positivity constraint ( Qλ (y)) are quite similar to those of the classical Lasso described in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Section 2].

Since the regularization term is of the form

F (r, l) def. = G-1 i=0 f (r i ) + G-1 i=0 f (l i ), with f (x) def.
= sup {qx ; q 1} = x if x 0, +∞ otherwise, its subdifferential is the product of the subdifferentials ∂f (r i ) and ∂f (l i ) for 1 i G -1, where

∂f (x) = {1} if x > 0, (-∞, 1] if x = 0.
That is similar to the subdifferential of | • | at x ∈ R which is -1, [-1, 1] or 1 if x < 0, x = 0 or x > 0 respectively. Hence, one may adapt the standard results for the Lasso to the Lasso with positivity constraint, simply by replacing the conditions η ∞ 1 with max η 1 (and similarly for strict inequalities) wherever they appear. We leave the detail to the reader, and in the following, we use those results freely to derive the properties of the Lasso with cone constraint (Q λ (y)).

Optimality conditions

The optimality conditions for ( Qλ (y)) and ( Q0 (y 0 )), written in terms of (a λ , b λ ), yield the following results.

Proposition 1. Let y ∈ H, (a λ , b λ ) ∈ C G h , and I = I(a λ , b λ ). Then (a λ , b λ ) is a solution to (Q λ (y)) if and only if there exists p λ ∈ H such that max (A * + h 2 B * )p λ 1, and max (A * - h 2 B * )p λ 1, (22)
(A * I (r) + h 2 B * I (r) )p λ = 1 I (r) , and
(A * I (l) - h 2 B * I (l) )p λ = 1 I (l) , (23)
λ A * B * p λ + A * B * (Aa λ + Bb λ -y) = 0. ( 24
)
Similarly, (a 0 , b 0 ) ∈ C G h is a solution to (Q 0 (y 0 )) if and only if Aa 0 + Bb 0 = y 0 and there exists p ∈ H such that

max (A * + h 2 B * )p 1, and max (A * - h 2 B * )p 1, (25)
(A * I (r) + h 2 B * I (r) )p = 1 I (r) , and
(A * I (l) - h 2 B * I (l) )p = 1 I (l) , (26)
where I = I(a 0 , b 0 ).

If the inequalities outside the support are strict, it is possible to ensure the uniqueness of the solution.

Proposition 2. Under the hypotheses of Proposition 1, if (

A + h 2 B) I (r) (A -h 2 B) I (l) has full rank and if p λ (resp. p) satisfies ∀k ∈ I c , (A * p λ ) k + h 2 |(B * p λ ) k | < 1, ( 27
) ∀i ∈ I (l) \ I (r) , ((A * + h 2 B * )p λ ) i < 1, ( 28
) ∀i ∈ I (r) \ I (l) , ((A * - h 2 B * )p λ ) i < 1, (29)
then (a λ , b λ ) (resp. (a 0 , b 0 )) is the unique solution to (Q λ (y)) (resp. (Q 0 (y 0 ))).
One may interpret the optimality conditions of Proposition 1 as the primal-dual relations between the solutions of (Q λ (y)) and (Q 0 (y 0 )) with the solutions of their respective dual problems

inf p∈D y λ -p 2 H (E λ (y)) sup p∈D y, p (E 0 (y))
where

D def. = p ∈ H ; max k∈ 0, G-1 (A * p) k + h 2 |(B * p) k | 1 . (30)
Conversely, p ∈ H is a solution to (E λ (y)) (resp. (E 0 (y))) if and only if p ∈ D and p satisfies the conditions of Proposition 1.

Low noise behavior of C-BP

The theorem of Fuchs [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF] for the Lasso describes an almost necessary and sufficient condition for the support stability of the problem at low noise. Its adaptation to the positive Lasso is straightforward. However, the criterion that it provides is not satisfied in general, and the support at low noise is strictly larger than (I (r) (a 0 , b 0 ), I (l) (a 0 , b 0 )). We provide below a finer description of that support by studying the minimal norm certificate.

Definition 1 (Minimal norm certificate). Let (a 0 , b 0 ) ∈ C G h . Its minimal norm certificate is η0 def. = A * + h 2 B * A * -h 2 B * p 0 where p 0 ∈ H is the solution to (E 0 (y)) with minimal norm. The extended support is ext (rl) (a 0 , b 0 ) = ext (r) (a 0 , b 0 ), ext (l) (a 0 , b 0 ) , where ext (r) (a 0 , b 0 ) = j ∈ 0, G -1 ; ((A * + h 2 B * )p 0 ) j = 1 , (31)
ext (l) (a 0 , b 0 ) = j ∈ 0, G -1 ; ((A * - h 2 B * )p 0 ) j = 1 . (32)
From the optimality conditions, if (a 0 , b 0 ) is a solution of (Q 0 (y 0 )) then I (r) ⊂ ext (r) (a 0 , b 0 ) and I (l) ⊂ ext (l) (a 0 , b 0 ) (where I = I(a 0 , b 0 )), and p 0 can be characterized as

p 0 = argmin p∈H p H ; A * + h 2 B * A * -h 2 B * p ∈ ∂F (r 0 , l 0 ) . (33)
It is now possible to describe the behavior of (Q λ (y)) at low noise in the generic case. We state the following theorem for problems of the form (Q λ (y)) and (Q 0 (y 0 )) as it is of independent interest. But in Section 4.2 below (see Theorem 3 and Corollary 1), we establish a more precise version of this result, which describes the constants and the extended support, in the special case of the C-BP for a continuous inverse problem.

Theorem 1. Let (a 0 , b 0 ) ∈ C G h \ {0} be an identifiable signal, (J (r) , J (l) ) def. = ext (rl) (a 0 , b 0 ) such that Âh def. = (A + h 2 B) J (r) (A -h 2 B) J (l) has full rank. Let u J (r) v J (l) def. = -( Â * h Âh ) -1 s where s def. = (1, . . . , 1) * ∈ R |J (r) |+|J (l) | ,
and assume that the following non-degeneracy condition holds

∀ j ∈ J (r) \ I (r) , u j > 0, and ∀ j ∈ J (l) \ I (l) , v j > 0. ( 34
)
Then, there exists constants

C (1) > 0, C (2) > 0, C (3)
> 0 such that for

C (1) w H + C (2) λ min 1 2 a 0,i + 1 h b 0,i ; i ∈ I (r) (a 0 , b 0 ) (35) ∪ 1 2 a 0,i - 1 h b 0,i ; i ∈ I (l) (a 0 , b 0 ) (36)
and l) , and it reads

w H C (3) λ, the solution (a λ , b λ ) to (Q λ (y)) is unique, I (r) (a λ , b λ ) = J (r) , I (l) (a λ , b λ ) = J (
a λ b λ = a 0 b 0 + H h Â+ h w -λH h ( Â * h Âh ) -1 s,
where H h is defined in [START_REF] Tang | Atomic decomposition of mixtures of translation-invariant signals[END_REF].

Some comments about the proofs of Theorem1 can be found in Appendix B.

Continuous-Basis Pursuit on (thin) grids

Now, we turn to the "continuous" inverse problem described in the introduction, and we assume that each α ν (1 ν N ) is positive. We aim at recovering m 0 using the Continuous Basis-Pursuit (C-BP) proposed in [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF]. Given a grid G with stepsize h > 0, the goal is to reconstruct a measure m =

Gn-1 i=0 a i δ ihn+t i where t i ∈ [-h 2 , h 2
] which estimates m 0 . Applying a Taylor expansion to ϕ and setting b i = t i a i , the authors of [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] are led to solve min

(a,b)∈C G h 1 2 y -Φ G a -Φ G b 2 H + λ a 1 (Q λ (y)) min (a,b)∈C G h a 1 such that Φ G a + Φ G b = y 0 . (Q 0 (y 0 ))
which are particular instances of (Q λ (y)) and (Q 0 (y 0 )), with the choice (A, B) = (Φ G , Φ G ). To study the behavior of the solutions to these problems, we shall apply the results of the previous section, and in particular Lemma 3.

Motivating example: the ideal regime

Let us first examine a regime in which the C-BP introduced in [START_REF] Ekanadham | Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit[END_REF] identifies the spikes locations with sub-grid accuracy, motivating its use for inverse problems instead of the Lasso.

Let h > 0 be fixed, let x 1 , . . . , x N ∈ G be fixed points and

I ∈ 0, G -1 N such that x = (x 1 , . . . , x N ) = Ih. Assuming that a solution a b to (Q λ (y)) has support (I, I),
we deduce by restricting (24) to (I, I) that

λ 1 N 0 + Φ * x Φ x * Φ x Φ x a I b I -y = 0. ( 37
)
Writing Γ x def.

= Φ x Φ x , and assuming that Γ x has full rank, we get

a I b I = (Γ * x Γ x ) -1 Γ * x y -λ(Γ * x Γ x ) -1 1 N 0 . ( 38
)
If the input is y = Φm 0 + w with m 0 def.

= N ν=1 α ν δ x 0,ν and x 0,ν = x ν + s ν , then

a I b I = α β + Γ + x (R α (s) + w) -λ(Γ * x Γ x ) -1 1 N 0 , (39)
where

β ν = α ν s ν , Γ + x = (Γ * x Γ x ) -1 Γ * x and R α (s) = Φm 0 -Γ x α β = O( α ∞ s 2 ∞ )
is the remainder of the Taylor expansion of Φm 0 around x. In other words, provided this regime holds, the C-BP is able to retrieve the positions

x ν + s ν up to an error O( α ∞ s 2 ∞ + Γ * x w ∞ + λ)
, yielding a better precision than the Lasso (which yields a O(h) error) provided w and λ are small enough. We call that regime the ideal regime.

The existence of such a regime, i.e. when the solutions to

(Q λ (y)) have support (I, I) is discussed in the next theorem (which is proved in Appendix C.1). Before stating it, we define η V def. = Φ * Γ +, * x 1 N 0 provided Γ x has full rank.
Theorem 2. Let x ∈ G N , such that Γ x has full rank, and assume that

max t∈G\{x 1 ,...,x N } η V ± h 2 η V (t) < 1. (IC h )
Then there exists constants C 1 > 0 (which only depends on x and ϕ), C 2 > 0 (which depends on x,ϕ and h), such that for all input measure m 0 def.

= N ν=1 α ν δ x 0,ν with α ν > 0 and x 0,ν = x ν + s ν , all λ > 0, w ∈ L 2 (T) with s ∞ < h 2 1 -C 1 α ∞ s 2 ∞ + Γ * x w ∞ + λ min α , ( 40
)
and α ∞ s 2 ∞ + w H λ < C 2 , ( 41
)
the solution to (Q λ (y)) is unique, has support (I, I), and is given by (39).

Remark 2. Condition (IC h ) ensures that for all measures which have support in a small neighborhood of x 1 , . . . , x N , the C-BP is able to identify the support up to a small error. It is similar to the Non-Degenerate Source Condition (NDSC) introduced in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] to study the noise stability of the Beurling Lasso and which involves the vanishing derivatives precertificate (see below). Whereas some theoretical results ensure the NDSC for sufficiently separated measures (see [START_REF] Tang | Atomic decomposition of mixtures of translation-invariant signals[END_REF]), it seems more challenging to ensure a priori the validity of (IC h ).

In the particular case of a single spike and a convolution operator (that is H = L 2 (T), ϕ(x) : x → φ(x -x)), the following result ensures the existence of the ideal regime (see Appendix C.2 for the proof). Proposition 3. If Φ is a convolution operator with φ ∈ C 4 (T) \ {0} such that φ is not T -periodic for T < 1, there exists h 1 > 0 such that for all h ∈ (0, h 1 ], any x ∈ G satisfies the hypotheses of Theorem 2. In particular, for any input m 0 = α 1 δ x 1 +s 1 , the solution is

a i 1 b i 1 = α 1 α 1 s 1 + O(α 1 s 2 1 + + Γ * x w ∞ + λ)).
For measures with more Dirac masses, it seems difficult to state any general result. Numerical experiments reported in Section 5.1 suggest that the ideal regime exists for reasonable filters and measures with sufficiently separated spikes. But this regime crucially depends on the stepsize h. Indeed, as a consequence of Lemma 5, assuming (IC h ) for all h small enough yields strong consequences such as η V

(3) (x ν ) = 0, which is not true in general. Therefore we conjecture that for typical signals and filters, Condition (IC h ) is only valid in some interval h 0 < h < h 1 , where h 0 > 0. As the numerical experiments suggest, h 0 and h 1 depend on the repartition of x 1 , . . . x N : the interval (h 0 , h 1 ) is large for well separated spikes, and small for densely clustered spikes.

The Positive Beurling Lasso

As the C-BP motivation stems from a Taylor expansion (see [START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF]) which is only valid for small shifts s, it is natural to expect that the performance of C-BP improves when using medium or small stepsizes, as opposed to larger ones. The situation is in fact more subtle. Now and for the next section, we are interested in the behavior of the model on a thin grid G n , n ∈ N, with stepsize h n 0 + as n → +∞. The problems we consider are min

(a,b)∈C Gn hn 1 2 y -Φ Gn a -Φ Gn b 2 H + λ a 1 (Q n λ (y)) min (a,b)∈C Gn hn a 1 such that Φ Gn a + Φ Gn b = y 0 . (Q n 0 (y 0 ))
and their dual problems are respectively equivalent to:

inf q∈D n y λ -q 2 H (E n λ (y)) sup q∈D n y 0 , q (E n 0 (y 0 ))
where D n def. = q ∈ H ; max k∈ 0, Gn-1

(Φ * q)(kh n ) + h n 2 |(Φ * q) (kh n )| 1 , (42)
As we explain below, a natural limit model of C-BP as n → +∞ is the positive Beurling Lasso,

min m∈M + (T) 1 2 y -Φm 2 H + λm(T), (Q ∞ λ (y))
and min

m∈M + (T) m(T) such that Φm = y 0 , (Q ∞ 0 (y 0 ))
where M + (T) refers to the space of positive Radon measures. The indicator function of positive measures plus the total mass may be encoded in the quantity:

m(T) + ι M + (T) (m) = sup T ψ(t)dm(t) ; ψ ∈ C (T) and sup t∈T ψ(t) 1 . (43)
The characterization of optimality, the notions of minimal norm certificates and extended support are straightfoward adaptations of those of the Beurling Lasso exposed in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Section 3]. Again, it essentially amounts to replacing condition η ∞ 1 with sup t∈T η(t) 1 where η = Φ * p for p ∈ H. For instance, up to the addition of a constant, the dual problems to (Q ∞ λ (y)) and (Q ∞ 0 (y 0 )) are respectively:

inf p∈D ∞ y λ -p 2 H (E ∞ λ (y)) sup p∈D ∞ y 0 , p (E ∞ 0 (y 0 ))
where

D ∞ def. = p ∈ H ; sup t∈T (Φ * p)(t) 1 . (44)
As for the Beurling Lasso, the low noise behavior of (Q ∞ λ (y)) is governed by the minimal norm solution of (E ∞ 0 (y 0 )) (see [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Section 3]). That solution being difficult to compute in general, one is led to study a "good candidate" for it, the vanishing derivatives precertificate, which can easily be computed by solving a linear system in the least square sense. In this paper, we are not directly interested in the low noise behavior of (Q ∞ λ (y)) but we shall use this precertificate as an auxiliary quantity, hence we may adopt the following definition.

Definition 2. Let m 0 = N ν=1 α 0,ν δ x 0,ν an identifiable measure for the problem (Q ∞ 0 (y 0 )) such that Γ x 0 def. = Φ x 0 Φ x 0 has full rank.
The vanishing derivatives precertificate is defined as

η V,∞ def. = Φ * p V,∞ where p V,∞ def. = Γ +, * x 0 s 0 , ( 45
)
where s = (1, . . . , 1) T ∈ R N and Γ +, * x 0 = Γ x 0 (Γ * x 0 Γ x 0 ) -1 .

The Limit Problem for Thin Grids

Let us recall that we obtain a measure from the vector (a, b) ∈ C Gn hn by setting

m = Gn-1 i=0 a i δ ihn+b i /a i (46) with the convention that b i /a i = 0 if a i = 0. It should be noticed that b i /a i ∈ [-hn 2 , hn 2
]. In this section we prove the Γ-convergence of (Q n λ (y)) towards (Q ∞ λ (y)). Since all the solutions to (Q n λ (y)) belong to X + def.

= m ∈ M + (T) ; λ|m|(T) 1 2 y 2 H , we may restrict the problems to X + , which is metrizable for the weak* topology. Hence, we may use the following formulation of Γ-convergence valid in metric spaces (see [START_REF] Maso | An Introduction to Γ-convergence[END_REF]). Definition 3. We say that the Problem (Q n λ (y)) Γ-converges towards Problem (Q ∞ λ (y)) if, for all m ∈ X + , the following conditions hold

• (Liminf inequality) for any sequence of measures (m n ) n∈N ∈ X N + of the form (46) with (a (n) , b (n) ) ∈ C Gn hn such that m n weakly* converges towards m, lim inf n→+∞ λ a (n) 1 + 1 2 Φ Gn a (n) + Φ Gn b (n) -y 2 H λm(T) + 1 2 Φm -y 2 H .
• (Limsup inequality) there exists a sequence of measures

(m n ) n∈N ∈ X N + of the form (46) with (a (n) , b (n) ) ∈ C Gn
hn such that m n weakly* converges towards m and

lim sup n→+∞ λ a (n) 1 + 1 2 Φ Gn a (n) + Φ Gn b (n) -y 2 H λm(T) + 1 2 Φm -y 2 H .
The following proposition, which is proved in Appendix C.3, states the Γconvergence of the model and its consequences.

Proposition 4. The Problem (Q n λ (y)) Γ-converges towards (Q ∞ λ (y)), and
lim n→+∞ (inf (Q n λ (y))) = inf (Q ∞ λ (y)). ( 47
)
Each sequence (m λ,n ) n∈N such that m λ,n is a minimizer of (Q n λ (y)) has accumulation points (for the weak*) topology, and each of these accumulation points is a minimizer of (Q ∞ λ (y)). In particular, if the solution m λ,∞ to (Q ∞ λ (y)) is unique, the whole sequence (m λ,n ) n∈N converges towards m λ,∞ .

Convergence of the support

Though Proposition 4 states the convergence of the solutions of (Q n λ (y)) towards those of (Q ∞ λ (y)), it does not describe the supports of the solutions. We now study the convergence of those supports using dual certificates and the optimality conditions (Proposition 1). In this continuous context, a dual certificate is determined by a function η = Φ * p ∈ C (T) where p ∈ H, and if (a, b) is a solution to (Q n λ (y)),

I (r) = i ∈ 0, G n -1 ; b i > - h n 2 a i ⊂ i ∈ 0, G n -1 ; η + h n 2 η (ih n ) = 1 , I (l) = i ∈ 0, G n -1 ; b i < h n 2 a i ⊂ i ∈ 0, G n -1 ; η - h n 2 η (ih n ) = 1 .
To sum up, we shall exploit the following observations

• if η + hn 2 η (ih n ) = 1 but η -hn 2 η (ih n ) < 1, a spike may appear at ih n + hn 2 , • if η -hn 2 η (ih n ) = 1 but η + hn 2 η (ih n ) < 1, a spike may appear at ih n -hn 2 , • if η + hn 2 η (ih n ) = 1 and η -hn 2 η (ih n ) = 1
, a spike may appear anywhere in the interval [ih n -hn 2 , ih n + hn 2 ]. In the next two paragraphs, we describe the behavior of the support. Those results rely on auxiliary Lemmas in Appendix D.

Asymptotics of the Support for fixed λ > 0

The following proposition relies on the convergence of the dual certificates (see Lemma 7 in Appendix). It states that in the generic case, one may observe up to two pairs of spikes for each spike of the solution of the positive Beurling-lasso. In the statement below, r is chosen such that 0 < r < 1 2 min ν =ν |x ν -x ν |. Proposition 5. Let λ > 0, and assume that there exists a solution m λ,∞ to (Q ∞ λ (y)) which is a sum of a finite number of Dirac masses, m λ,∞ = N ν=1 α ν δ xν where α ν > 0.

Assume that η λ,∞ satisfies |η λ,∞ (t)| < 1 for all t ∈ T \ {x 1 , . . . , x N }.
Then any sequence of solution

m λ,n = Gn-1 i=0 a λ,i δ ihn+b λ,i /a λ,i to (Q n λ (y)) satisfies lim sup n→+∞ (supp m λ,n ) ⊂ {x 1 , . . . x N }. If, moreover, m λ,∞ is the unique solution to (Q ∞ λ (y)), lim n→+∞ (supp(m λ,n )) = {x 1 , . . . x N }. ( 48
)
If, additionally, (η λ,∞ ) (x ν ) = 0 for some ν ∈ {1, . . . , N }, then for all n large enough, the restriction of m λ,n to (x ν -r, x ν + r) is a sum of Dirac masses whose configuration is given in Table 1, and if (η λ,∞ ) (3) (x ν ) = 0, then only the cases indicated with ( * ) may appear. Remark 3. Proposition 5 states that the support of the C-BP on thin grids actually depends on the properties of the dual certificate η λ,∞ of the (positive) Beurling Lasso. The condition η λ,∞ (x ν ) = 0 seems to be overwhelming, or generic, and it is ensured for instance if λ is small and the Non-Degenerate Source Condition holds (see [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]). As for the condition η

(3)
λ,∞ (x ν ) = 0, it also seems to be generic (with the notable exception of single spike input measures), as there is nothing to impose η

λ,∞ (x ν ) = 0 in the positive Beurling Lasso. As a result, in practice, one does not observe all the configurations given in Table 1, and only the cases indicated with ( * ) appear, the case of two spikes being again overwhelming.

This means that when approximating the positive Beurling Lasso with the Continuous Basis-Pursuit, if the grid is too thin, one generally sees two spikes instead of one, and those spikes are at successive half-grid points:

(ih + h 2 , (i + 1)h + h 2 ) or (ih -h 2 , (i + 1)h -h 2 ).

Asymptotic of the Low Noise Support

Now, we pursue the discussion of Section 3.1, trying to describe the solutions when h is too small for (IC h ) to hold. Again, we consider measure m 0 def.

= N ν=1 α ν δ x 0,ν where x 0,ν = x ν + s ν , and we assume that x ∈ (G n ) N for n large enough (for the sake of simplicity, we consider increasing grids (G n ⊂ G n+1 and we assume that x ∈ G 0 ). As the computations in Section 3.1 suggest, we may split the observation as y = y +(R α (s)+w) where y def.

= Γ x α β and β ν = α ν s ν for all 1 ν N . In other words, we regard the remainder R α (s) of the Taylor expansion as an additional noise term induced by the shift s.

Whereas the previous subsection considered a fixed value of λ and w, here, to be able to describe precisely the support based upon intrinsic properties of x, we focus our attention on the simpler situation of a low noise regime, that is:

• the parameter λ > 0 is small, • the noise w ∈ H is small, • the shift s ∈ R N is small.
The bounds on λ, w and s depend on n (i.e. on h n ), they will be made precise below. In that regime, the problem (Q n λ (y)) approximates min

(a,b)∈C Gn hn a 1 such that Φ Gn a + Φ Gn b = y, (Q n 0 (y))
and the support of the solutions to (Q n λ (y)) is governed by the saturations of the minimal norm solutions of the dual problem (E n 0 (y)). The difficult point here is that the minimal norm solutions of (E n 0 (y)) do not converge towards the minimal norm solution of (E ∞ 0 (y)), and we need introduce a new variational problem to carry the study further.

= argmin

p∈H p H ; ∀ν ∈ {1, . . . , N }, (Φ * p)(x ν ) = 1, (Φ * p) (x ν ) = 0 and (Φ * p) (3)

(x ν ) = 0 , (49)
whenever the above set is not empty.

Note that p T is the solution to a quadratic minimization under linear constraint, and can hence be computed by solving a linear system, provided Φ

x Φ x Φ (3) x has full rank, p T = Γ * x Φ (3) x * +    1 N 0 N 0 N    = (Π (Im Φ (3) x ) ⊥ Γ x ) + (Π (Im Γ x ) ⊥ Φ (3) x ) +    1 N 0 N 0 N    = (Π (Im Φ (3) x ) ⊥ Γ x ) + 1 N 0 N , (50)
where

Π (Im Γ x ) ⊥ (resp. Π (Im Φ (3) x ) ⊥ ) is the orthogonal projector onto (Im Γ x ) ⊥ (resp. (Im Φ (3)
x ) ⊥ ), and Γ x = Φ x Φ x . The third derivative precertificate is involved in the following technical assumption.

Definition 5 (Twice Non-Degenerate Source Condition). Given x ∈ (G 0 ) N , we say that the Twice Non-Degenerate Source Condition (TNDSC) holds if p T in (49) is well defined and if it satisfies, for η T = Φ * p T ,

∀t ∈ T \ {x 1 , . . . , x N }, η T (t) < 1, ∀ν ∈ {1, . . . , N }, η T (x ν ) < 0 and η (4) T (x ν ) > 0.
Remark 4. In view of Lemma 4 in Appendix C.2, the Twice Non-Degenerate Source Condition ensures that there exists n 1 ∈ N such that for all n n 1 , p T ∈ D n . From the optimality conditions (Proposition 1), we deduce that for any (α, s)

∈ (R * + ) N × R N , the corresponding vector (a, b) ∈ R Gn × R Gn defined by (a i , b i ) = (α ν , β ν ) if ih n = x ν 0 otherwise, (51)
is a solution to (Q n 0 (y)), where y = Φ Gn a + Φ Gn b, provided s ∞ hn 2 (i.e. (a, b) ∈ C hn ). We are now in position to describe precisely the corresponding extended support, with a prediction on the location of the neighbor. The proof of this Theorem can be found in Appendix D.2.

Theorem 3. Let x ∈ (G 0 ) N such that the operator Φ x Φ x Φ (3) x
has full rank and that the Twice Non Degenerate Source condition (Definition 5) holds. Moreover, assume that all the components of the natural shift = Φ Gn a + Φ Gn b, is a solution to (Q n 0 (y)) and its extended support has the form

ρ def. = (Φ (3) * x Π (Im Γ x ) ⊥ Φ (3) x ) -1 Φ (3) * x Γ +, *
ext (r) n (a, b) = {i 1 , . . . , i N } ∪ {i ν -1 ; ν ∈ 1, N and ρ ν > 0} ext (l) n (a, b) = {i 1 , . . . , i N } ∪ {i ν + 1 ; ν ∈ 1, N and ρ ν < 0} .
where

i ν ∈ 0, G n -1 is defined by i ν h n = x ν .
Remark 5. The extended support is locally constant: ext

(r) n (a, b) = ext (r)
n (a, 0) and ext

(l) n (a, b) = ext (l) n (a, 0) for all s such that s ∞ hn 2 .
The next result is a specific variant of Theorem 1 which precisely describes the low noise solutions on thin grids. It states that, at low noise, the C-BP reconstructs a measure of the form

m λ = N ν=1 α (1) λ,ν δ xν +tν + α (2) λ,ν δ xν +εν h/2
where

ε ν ∈ {-1, +1}, -h/2 < t ν < h/2.
As in the ideal regime, the model is able to recover the locations of the original spikes (using β ν = s ν α ν ) up to a small error, but two parasitic spikes appear at neighboring half-grid points.

Corollary 1. Under the hypotheses of Theorem 3, there exists constants C (1) > 0, C (2) > 0 and C (3) > 0 such that for any input y = Φm 0 + w, with m 0 = N ν=1 α ν δ x 0,ν and x 0,ν = x ν + s ν , the conditions

• C (1) α ∞ s 2 ∞ + w H + C (2) λ (h n ) 3 min α, • α ∞ s 2 ∞ + w H C (3) λ,
imply that the solution to (Q n λ (y)) is unique. Defining the vector I by Ih def.

= x, the nonzero components of the solution are

(a λ ) I (b λ ) I = α β + (Π (Im Φ (3) x ) ⊥ Γ x ) + w -λ(Γ * x Π (Im Φ (3) x ) ⊥ Γ x ) -1 1 N 0 N + O ∆ h 3 O ∆ h 2 , ( 53
)
where we denoted ∆ def.

= w H + α ∞ s 2 ∞ + λ, and, letting ε def.

= -sign (ρ) (see (52)),

(a λ ) I+ε (b λ ) I+ε = O ∆ h 3 O ∆ h 2 with (a λ ) I+ε + 2 h diag(ε)(b λ ) I+ε = 0. ( 54
)
The proof is given in Appendix D.3.

Numerical illustrations

In this section, we illustrate the relevance of our analysis to gain a precise understanding of the recovery performance of 1 -type methods (Lasso and C-BP) for deconvolution. The code to reproduce these numerical experiments is available online ‡.

Ideal regime for the deconvolution problem

We begin by illustrating the ideal regime highlighted in Section 3.1: C-BP can give a better result than Lasso, and locate spikes with sub-grid accuracy, provided the grid size is not too small.

For this purpose, we consider the deconvolution problem, that is ϕ(x) = φ(• -x), and we assume that the input measure has the form m 0 def.

= N ν=1 α ν δ iν h+sν where α ν > 0 are positive amplitudes, i ν ∈ {0, . . . , G -1} are grid indices, and s ν ∈ [0, h] indicates a shift of the positions outside the grid. We do not specifically add noise, considering observations y = Φm, but let us note that if the spikes do not lie on the grid, this is somehow equivalent to adding a "structured" interpolation noise in the observation. In the following experiments, Φ is a Gaussian filter of standard deviation 0.06, with observations Φm ∈ R P sampled on a uniform grid of P = 1024 points.

Figure 2, compares the solution path (evolution of the solution as a function of λ) of the Lasso (with positivity constraints) and C-BP in the case of a single input spike N = 1. It is obtained for a grid size G = 32, but quite remarkably, for this single spike case (and as opposed to the case N > 1 considered below), the same conclusion holds for any grid size G. This result shows that, while the Lasso always recovers a pair of spikes at quantized indices {i 1 , i 1 + 1}, in sharp contrast, C-BP correctly recovers a ‡ https://github.com/gpeyre/2015-IP-lasso-cbp/ single Dirac, which approximates the input position i 0 + s 0 for small λ. Note however that if λ is chosen too small, then the "structured" interpolation noise starts having an effect, and the recovered measure becomes degenerate (blue spurious spikes). Figure 3 shows that the situation is more intricate in the case of N = 3 input spikes (a similar conclusion holds for larger N ). This illustrates the conclusion of Section 3.1. The behaviour of the Lasso solution is simple to understand, and is always composed (even for very small λ) of pairs of spikes located at {i ν , i ν + 1} around each input spike location i ν h + s ν . In contrast, for the C-BP, two situations emerge when the grid size h = 1/G is not too small (G = 32 on the left) If a spike location i ν h + s ν is sufficiently far away from the other locations (here the leftmost spike), then C-BP performs well, and recovers a single spike, with a location approximating very precisely the input one. For small λ however, the solution degenerates and produces spurious spikes. If a spike location i ν + s ν h is located too close from another one (the cluster of two spikes on the right part of the domain illustrates this), then C-BP operates very similarly to Lasso, and quantizes the positions, as already seen in Section 5.3 when the spikes are on-the-grid. If the grid size h = 1/G is too small (G = 64 on the right of Figure 2), the quantization effects impacts both Lasso and C-BP, which both fails to locate spikes between grid points, as studied in Section 4.1.

Convergence of pre-certificates

In this section and in Section 5.3, we consider the deconvolution problem again, but φ is an ideal filter, i.e. whose Fourier coefficients

∀ k ∈ Z, φ(k) def. = T φ(t)e -2iπkt dt satisfy φ(k) = 1 if k ∈ {-f c , .
. . , f c } and φ(k) = 0 otherwise. This allows us to implement exactly the Φ operator appearing in the Lasso and C-BP problem since Im(Φ) is a finite dimensional space of dimension Q = 2f c + 1, i.e. it can be represented using a matrix of size (Q, P ) when evaluated on a grid of P points. In Figures 4 and5 we used f c = 10. We first notice that for all the (positive) input measures (i.e. whatever the spacing between the Diracs), η V,∞ is always a non-degenerate certificate (in the sense of Proposition 2), meaning that one actually has η V,∞ = η 0,∞ (where the minimal norm certificate η 0,∞ is the minimal norm solution of (D ∞ 0 (y 0 )) in [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]). This empirical finding is the subject of another recent work on the asymptotic of sparse recovery of positive measures when the spacing between the Diracs tends to zero [START_REF] Denoyelle | Support Recovery for Sparse Deconvolution of Positive Measures[END_REF]. Since η 0,∞ is nondegenerate, one can thus apply [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Theorem 2] to analyze the extended support of the Lasso on a thin grid (see Section 5.3 below for a numerical illustration).

1 1 1 1 1 1 N = 2 N = 3
For the C-BP problem, the situation is however more contrasted. We observe that when the Dirac masses are separated enough (first row) then the pre-certificate µ T is a valid certificate, meaning the the Twice Non-Degenerate Source Condition (see Definition 5) holds. This means that Theorem 3 can be applied to analyze the extended support of C-BP on a thin grid (see Section 5.3 below for a numerical illustration). But when the Dirac masses are too close (second and third rows), one has η T ∞ > 1, so that one cannot ensure the support stability of the C-BP solution with our result.

Extended support for deconvolution on a thin grid

We still consider the case of an ideal low pass filter. Figure 5 displays the evolution, as a function of λ (in abscissa) of the solution a λ of the Lasso (Eq. ( 7)) and of the solution (a λ , b λ ) of the C-BP (Q n λ (y)), on a thin grid. We consider here the case of an input measure with two nearby Diracs (displayed as red/blue dots in the upper-left part of the Figure). To simplify the interpretation, we set the Dirac masses on the grid (x 0,ν = x ν ) and we do not add noise (w = 0). Each 1-D curve (either plain or dashed) represents the evolution of a single coefficient, e.g. (a λ ) i , for some index i (only non-zero coefficients are displayed).

The solutions path λ → a λ (for Lasso) and λ → (a λ , b λ ) (for C-BP) are continuous and piecewise affine, which is to be expected since the regularizations ( 1 and 1 under conic constraints) are polyhedral. The upper-left plot in the figure displays the precertificate η V,∞ (in magenta, see Definition 2) and η T (in green, see Definition 4). This shows graphically that these two precertificates are non-degenerate (in the sense of [12, Proposition 3] and Definition 5) so that the conclusions of [12, Theorem 2] and Theorem 3 hold, hence precisely describing the evolution of the solution on the extended support when λ is small. On these graphs, this corresponds to the first segment of the corresponding piecewise affine paths.

The behavior for BP agrees with our analysis. As predicted by [12, Corollary 1], there exists a range of values 0 < λ < λ 0 on which the solution is exactly supported on the extended support J, which is composed of four spikes (the plain curve corresponds to the support I and the dashed curve corresponds to J\I). Also, as predicted by [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Proposition 7] in the case w = 0, we verify that λ 0 = O(h n ) and that the Lipschitz constant of λ → a λ is of order O(1/h n ).

In sharp contrast, the behavior for C-BP is less regular, since the range 0 < λ < λ 0 on which the solution is supported on the extended support is shorter, as it can be clearly seen on the zoom for very small values of λ. This is in agreement with Corollary 1 which shows that λ 0 is of the order of O(h n 3 ) and that the Lipschitz constant of λ → (a λ , b λ ) is of order O(1/h n 3 ). On this range of small λ, as predicted by Theorem 3, the support of the solutions (which correspond to the extended support J described in Theorem 3) is composed of one pair of neighboring spikes for each original spike. For indices on the support i ∈ I, one has |(b λ ) i |/(a λ ) i < h/2 (the constraint is non-saturating, and the spike moves "freely" inside (ih -h 2 , ih + h 2 )) while for indices on the extended part i ∈ J\I, one has |(b λ ) i |/(a λ ) i = h/2 (the constraint is saturating, the spikes are fixed at half-grid points). Another part of the path is interesting, for λ not so small (say λ > λ 1 ), which is in fact the prominent regime in the non-zoomed figure. For this range of λ, there is still a pair of spikes for each original spike, but this time both spikes saturate, on same side. This observation should be related to Proposition 5 and Remark 3 which predict that, in the case where η

(3) λ,∞ (x λ,ν ) = 0, the C-BP yields either one spike or a pair of spikes with the same shift (the latter case is in fact overwhelming).

Conclusion

In this paper, we have provided a detailed analysis of the support recovery properties of the C-BP method. We have highlighted the existence of three different regimes. In the first one, the model identifies the spikes locations up to a very small error. This is the ideal situation. Unfortunately, for typical unknown signals, this regime breaks down as the grid size becomes small, and all the sooner as the measure has dense clusters. In the second one, for each unknown spike, the model yields two spikes saturating at consecutive half-grid points: it holds when λ > 0 is fixed and the grid is small. In the last one, the model identifies one free spike and an additional one which saturates a half grid neighbor: it holds when the grid size and λ > 0 are small, and the unknown spikes are in a neighborhood of the grid points.

These results explain how the C-BP yields better recovery performance than the Lasso for isolated spikes falling off-the-grid. They also explain that a necessary condition for this gain is the use of grids that are not so small. Finding precise conditions ensuring the existence of the ideal regime is an interesting avenue for future works.

Then for h > 0 small enough, M h has full rank and

(M * h M h ) -1    1 N 1 N 1 N    = - 1 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (C * Π (Im Γ) ⊥ C) -1 C * Γ +, * 1 N 0 + o 1 h 3 , (A.2) M + h = 1 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (Π (Im Γ) ⊥ C h ) + + o 1 h 3 , (A.3) but M +, * h    1 N 1 N 1 N    = Γ +, * 1 N 0 N -Π (Im Γ) ⊥ C h +, * C * h Γ +, * 1 N 0 N . (A.4)
Proof. Observe that

M h = Γ C h Z, where Z def. =    I N I N I N h 2 I N -h 2 I N h 2 diag(ε) 0 0 h 3 diag(ε)    .
We note that

Z -1 =    1 2 I N 1 h I N 1 h 3 diag -1+ε 2 1 2 I N -1 h I N 1 h 3 diag 1-ε 2 0 0 1 h 3 diag(ε)    .
Moreover, writing a b c d

def. = Γ * Γ Γ * C h C * h Γ C * h C h
, we see from the full rank assumption that a, T def.

= a -bd -1 c and S def.

= d -ca -1 b are invertible, at least for h > 0 small enough. The block inversion formula yields (see [START_REF] Horn | Matrix Analysis. 2nd[END_REF]Section 0.7.3])

Γ * Γ Γ * C h C * h Γ C * h C h -1 = T -1 -a -1 bS -1 -S -1 ca -1 S -1 = T -1 -T -1 bd -1 -d -1 cT -1 S -1
with, from straightforward formulations,

T = Γ * Π (Im C h ) ⊥ Γ S = C * h Π (Im Γ) ⊥ C h a -1 bS -1 = T -1 bd -1 = Γ + C h (C * h Π (Im Γ) ⊥ C h ) -1 = (Γ * Π (Im C h ) ⊥ Γ) -1 ΓC + h S -1 ca -1 = d -1 cT -1 = (C * h Π (Im Γ) ⊥ C h ) -1 C h Γ + = C + h Γ(Γ * Π (Im C h ) ⊥ Γ) -1
where Γ + = (Γ * Γ) -1 Γ is the pseudo-inverse of Γ and Π (Im Γ) ⊥ = Id H -Γ(Γ * Γ) -1 Γ * is the orthogonal projector onto (Im Γ) ⊥ , and similarly for C h . As a result,

(M * h M h ) -1 = Z -1 Γ * Γ Γ * C h C * h Γ C * h C h -1 Z * ,-1 , Since Z * ,-1    1 N 1 N 1 N    =    1 N 0 N 0 N    , we see that (M * h M h ) -1    1 N 1 N 1 N    = Z -1 T -1 -a -1 bS -1 -S -1 ca -1 S -1    1 N 0 N 0 N    (A.5) = 1 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (-S -1 ca -1 ) 1 N 0 +    1 2 Id N 1 h Id N 1 2 Id N -1 h Id N 0 0    T -1 1 N 0 (A.6)
which yields (A.2). Moreover, the formula for the Moore-Penrose pseudo-inverse [2, Theorem 1] yields

Γ C h + = (Π (Im C h ) ⊥ Γ) + (Π (Im Γ) ⊥ C h ) + .
From Lemma 1, we deduce that

M + h = Z -1 (Π (Im C h ) ⊥ Γ) + (Π (Im Γ) ⊥ C h ) + (A.7) = 1 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (Π (Im Γ) ⊥ C h ) + +    1 2 Id N 1 h Id N 1 2 Id N -1 h Id N 0 0    (Π (Im C h ) ⊥ Γ) + (A.8)
Considering its adjoint, we obtain

M +, * h    1 N 1 N 1 N    = 0 + (Π (Im C h ) ⊥ Γ) + 1 N 0 N .

Appendix B. Proofs for Section 2

The proof of Theorem 1 is similar to the proofs of Theorem 3 and Corollary 1 which are detailed below, therefore we omit it. Let us mention however that it relies on the following fundamental Lemma (which is a simplified version of [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]Lemma 4]), which characterizes η0 . Lemma 3. Let J (r) , J (l) ⊂ 0, G -1 , and (a 0 , b 0 ) ∈ C G h . Assume that (I (r) , I (l) )

def.

= (I

(r) (a 0 , b 0 ), I (l) (a 0 , b 0 )) is such that I (r) ⊂ J (r) , I (l) ⊂ J (l) and Âh def. = (A + h 2 B) J (r) (A -h 2 B) J (l) has full rank. Define u J (r) v J (l) def. = -( Â * h Âh ) -1 s where s def. =    1 . . . 1    ∈ R |J (r) |+|J (l) | . Then (J (r) , J (l)
) is the extended support of (a 0 , b 0 ) if and only if the following two conditions hold:

• for all j ∈ J (r) \ I (r) , u j 0, and for all j ∈ J (l) \ I (l) , v j 0.

• max

(A + h 2 B) * J (r) c (A -h 2 B) * J (l) c Âh u J (r) v J (l) < 1.
Moreover, in that case, the minimal norm certificate is given by

η0 = -A h * Âh ( Â * h Âh ) -1 s. Appendix C. Proofs for Section 3 Appendix C.1. Proof of Theorem 2
We study when the solutions to (Q λ (y)) have support (I, I). In view of Proposition 1, and assuming that Γ x has full rank, the vector (a, b) defined by ( 38) is a solution iff • r i > 0 and l i > 0 for all i ∈ I (where (r, l) is defined from (a, b) in ( 20)),

• The vector

p λ def. = 1 λ y -Γ x a I b I = 1 λ Π (Im Γ x ) ⊥ y + Γ +, * x 1 N 0 , (C.1)
where Π (Im Γ x ) ⊥ is the orthogonal projector onto (Im Γ x ) ⊥ , satisfies

∀ν ∈ {1, . . . , N }, (Φ * p λ )(x ν ) = 1, (Φ * p λ )(x ν ) = 0, (C.2) ∀t ∈ G \ {x 1 , . . . , x N }, (Φ * p λ )(t) ± h 2 (Φ * p λ )(t) 1. (C.3)
Let us deal with the first item. Let ν ∈ 1, N and i ν ∈ 0, G -1 such that i ν h = x ν . From (39) we deduce that

a iν ± 2 h b iν α ν ± 2 h β ν -C 1 α ∞ s 2 ∞ + Γ * x w ∞ + λ
where C 1 depends on the norms of Φ * x ,Φ x * , (Γ * x Γ x ) -1 1 N 0 and ϕ , but can be chosen independent from 0 < h 1. Since β ν = α ν s ν , we see that a iν ± 2 h b iν > 0 provided (40) holds.

As for the second item, we notice that (C.2) is satisfied by construction of p λ .

Moreover, setting η

V def. = Φ * Γ +, * x 1 N 0 , ξ s,w def. = Φ * Π (Im Γ x ) ⊥ y, we rewrite (C.3) as η V ± h 2 η V (t) + 1 λ ξ s,w ± h 2 ξ s,w (t) 1. Since ξ s,w = Φ * Π (Im Γ x ) ⊥ (R α (s) + w), there exists some constant C2 > 0 such that max t∈G\{x 1 ,...,x N } ξ s,w (t) C2 α ∞ s 2 ∞ + w H . As a result, defining C 2 def. = 1 C2 1 - max t∈G\{x 1 ,...,x N } η V ± h 2 η V (t) > 0, (C.4)
we see that (C.3) provided (41). The conclusion follows from Propositions 1 and 2.

Appendix C.2. Proof of Proposition 3

By the translation invariance of the problem, it is sufficient to prove the result for x = (0), I = (0).

By integration by parts, we observe that for a convolution filter,

∀z ∈ T, ϕ (k) (z), ϕ (j) (z) = ϕ (k) (0), ϕ (j) (0) (C.5) =    (-1) j-k 2 ϕ ( j+k 2 ) (0) 2 H if j + k is even, 0 otherwise. (C.6)
Incidentally, Γ x has full rank, and η V (t)

def. = Φ * Γ +, * x 1 0 (t) = 1 ϕ(0) 2 H ϕ(t), ϕ(0) . From
the Cauchy-Schwarz inequality and the fact that φ has no period smaller than 1, η V (t) < 1 for all t ∈ T \ 0. Moreover, from (C.6) we deduce that

η V (0) = η V (3) (0) = 0, η V (2) (0) < 0 and η V (4) (0) > 0.
From Lemma 4 below, we deduce that there exists h 1 > 0 such that for all h ∈ (0,

h 1 ], max t∈G\{0} η V ± h 2 η V (t) < 1. (C.7)
hence, condition (IC h ) holds. The claimed result follows.

The proof of Proposition 3 relies on the following Lemma which will also be helpful for the study of the low noise support in Section 4.2.

Lemma 4. Let {x 1 , . . . , x N } ⊂ G, η ∈ C 4 (T) such that for all t ∈ T \ {x 1 , . . . , x N }, η(t) < 1 and ∀ν ∈ {1, . . . , N }, η(x ν ) = 1, η (x ν ) = 0, η (3) (x ν ) = 0, η (4) (x ν ) > 0. t η (4) η (3) η η η -r 0 r + 0 0 η (-r) < 0 η (-r) < 0 η (0) η (0) η (r) < 0 η (r) < 0 0 0 1 1
Table C1: Variations of η and its derivatives.

Then, there exists h 1 > 0 such for all stepsize h ∈ (0,

h 1 ], max t∈G\{x 1 ,...x N } η ± h 2 η (t) < 1.
Remark 6. The condition η (3) (x ν ) = 0 might seem surprising, but it is in fact necessary: if it does not hold, by Lemma 5, for all h small enough there exists t ∈ G \ {x 1 , . . . x N } such that η ± h 2 η (t) 1. Proof. Let r > 0 small enough so that the intervals (x ν -r, x ν + r) for ν ∈ {1, . . . , N } are pairwise disjoint, and such that η (t) < 0, and η (4) (t) > 0 for all t ∈ (x ν -r, x ν + r).

We first prove that η(kh)+ h 2 |η (kh)| < 1 for all k such that kh ∈ (x ν -r, x ν +r)\{x ν }. To simplify the notation, we assume without loss of generality that x ν = 0. The variations of η and its derivatives are given in Table C1.

Let us observe that the function

θ : t → η(t) -t 2 η (t) is (strictly) decreasing in [0, r), since ∀t ∈ (0, r), θ (t) = 1 2 (η (t) -tη (t)) = 1 2 t 0 (η (u) -η (t)) <0 du < 0. (C.8)
Hence, for all k such that kh ∈ (0, r),

η(kh) - h 2 η (kh) = η(kh) - kh 2 η (kh) =θ(kh)<θ(0)=1 + (k -1)h 2 η (kh) <0 < 1. (C.9)
On the other hand, θ is (strictly) increasing on (-r, 0] since

∀t ∈ (-r, 0), θ (t) = 1 2 (η (t) -tη (t)) = 1 2 t 0 (η (u) -η (t)) <0 du > 0. (C.10)
As a consequence, for all k such that kh ∈ (-r, 0),

η(kh) + h 2 η (kh) = η(kh) - kh 2 η (kh) =θ(kh)<θ(0)=1 + (k + 1)h 2 η (kh) 0 < 1. (C.11)
Thus we see that η(kh) + h 2 |η (kh)| < 1 for all kh ∈ (-r, r) \ {0}, and we proceed similarly on all the intervals of the form (x ν -r, x ν + r). Now, by a compactness argument, there exists a constant β < 1 such that η(t) β for all t ∈ T \ N ν=1 (x ν -r, x ν + r). For h > 0 small enough, the inequality h 2 (sup t∈T |η (t)|) < 1 -β holds, and we conclude that η(kh)

+ h 2 |η (kh)| < 1 for all t ∈ T \ N ν=1 (x ν -r ν , x ν + r ν ). Appendix C.3. Proof of Proposition 4
We observe that our embedding of the discrete problem into the continuous one, that is

m n = Gn-1 i=0 a (n) i δ ihn+b i /a i , yields a (n) 1 = |m n |(T) = m n (T).
For the liminf inequality, let (m n ) n∈N be of the form (46) which weakly* converges towards m. We notice that Φ Gn b

(n) = Φ ( Gn-1 i=0 b (n) i δ ihn ), where Φ : m → T ϕ (x)dm(x) is continuous from M(T) to H (in the strong topologies). Moreover, Gn-1 i=0 b (n) i δ ihn (T) h n 2 Gn-1 i=0 a (n) i h n 2λ 1 2 y 2 H + 1 → 0, so that Φ Gn b (n) converges strongly towards 0 in H. Additionally, Φ Gn a (n) = Φ( Gn-1 i=0 a (n)
i δ ihn ) and for all ψ ∈ C (T),

Gn-1 i=0 a (n) i δ ihn+b i /a i - Gn-1 i=0 a (n) i δ ihn , ψ = Gn-1 i=0 a (n) i (ψ(ih n + b i /a i ) -ψ(ih n )) Gn-1 i=0 a (n) i ω ψ h n 2 → 0
where

ω ψ : t → sup |x -x| t |ψ(x) -ψ(x )| is the modulus of continuity of ψ. As a result, Gn-1 i=0 a (n) i δ ihn -m n * 0 so that Gn-1 i=0 a (n)
i δ ihn weakly* converges to m. Hence, Φ Gn a (n) weakly converges towards Φm in H. To sum up, Φ Gn a (n) + Φ Gn b (n) -y weakly converges towards Φm -y and we conclude by invoking the lower semi-continuity of both terms:

lim inf n→+∞ λ a (n) 1 + 1 2 Φ Gn a (n) + Φ Gn b (n) -y 2 H = lim inf n→+∞ λ|m n |(T) + 1 2 Φ Gn a (n) + Φ Gn b (n) -y 2 H λm(T) + 1 2 Φm -y 2 H .
For the limsup inequality, we build a recovery sequence m n by choosing a

(n) k = m([kh n , (k + 1)h n )) and b (n) k = 0 for all k ∈ 0, G n -1 . Then, for all n, a (n) 1 = m(T) and Φ Gn-1 i=0 a (n) i δ ihn -Φm H Gn-1 i=0 [ihn,(i+1)hn) (ϕ(t) -ϕ(ih n ))dm(t) H m(T)ω ϕ (h n ) → 0
since ϕ is uniformly continuous on T. As a result, Φm n -y strongly converges towards Φm -y and the limsup inequality is proved.

Appendix D. Proofs of Section 4

The following lemma is central in our analysis. It studies sequences of dual certificates (η n ) n∈N . For 0 < r < 1 2 min ν =ν |x ν -x ν |, ν ∈ {1, . . . , N }, it will be useful to consider the sets:

S (r) n,ν (r) def. = t ∈ G n ∩ (x ν -r, x ν + r) ; η n + h n 2 η n (t) = 1 , S (l) n,ν (r) def.
=

t ∈ G n ∩ (x ν -r, x ν + r) ; η n - h n 2 η n (t) = 1 .
Lemma 5. Let (x 1 , . . . , x N ) ∈ T N pairwise distinct, and let {η n } n∈N ∈ (C 3 (T)) N be a sequence of functions which converges uniformly towards some η ∞ (and similarly for the derivatives) such that for all ν ∈ {1, . . . , N }, η ∞ (x ν ) = 1 and for all t ∈ T\{x 1 , . . . , x N }, η ∞ (t) < 1.

(i) Then

lim sup n→+∞ t ∈ G n ; η n (t) + h n 2 |η n (t)| = 1 ⊂ {x 1 , . . . , x N }. (D.1)
In particular for r > 0 small enough, there exists n 0 ∈ N such that for n n 0

t ∈ G n ; η n (t) + h n 2 |η n (t)| = 1 = N ν=1 S (r) n,ν (r) ∪ S (l) n,ν (r) ⊂ N ν=1 (x ν -r, x ν + r).
Assume moreover that for all n ∈ N and all t ∈ G n , η n (t) + hn 2 |η n (t)| 1. For each ν ∈ {1, . . . , N }:

(ii) If η ∞ (x ν ) = 0, then there exists n 0 ∈ N such that for n n 0 , each set S (r) n,ν (r) and S (l) n,ν (r) is of the form ∅, {ih n }, or {ih n , (i + 1)h n }, and if both sets are nonempty: max S (r) n,ν (r) min S (l) n,ν (r).

(iii) If η (3)
∞ (x ν ) = 0, then there exists n 0 ∈ N such that for each n n 0 , S

n,ν (r) = ∅ or S (l) n,ν (r) = ∅. (iv) If η (4) ∞ (x ν ) = 0, the set of n ∈ N such that S (r) n,ν (r) = {(i n -1)h n , i n h n } and S (l) n,ν (r) = {i n h n , (i n + 1)h n } (with the same i n ∈ 0, G n -1 ) is finite. (r)
Proof. (i) For all r ∈ (0, r), by compactness, sup {η ∞ (t) ; t ∈ T \ (x ν -r, x ν + r)} < 1. Thus by uniform convergence there exists n 0 ∈ N such that for all n n 0 , (η n ± hn 2 η n ) < 1 on T \ N ν=1 (x ν -r, x ν + r), and the first claim is proved. (ii) If moreover η ∞ (x ν ) = 0, it is in fact negative. Choosing r ∈ (0, r) small enough and then n large enough, we may assume that η n < -k 0 in (x ν -r, x ν + r), for some k 0 > 0, and by (D.1) that S

n | < -k 0 2 for n large enough, so that both functions η n + hn 2 η n and η n -hn 2 η n are strictly concave in (x ν -r, x ν + r). This implies that S n,ν (r) = ∅, it must change sign in (x ν -r, x ν + r) and thus it vanishes exactly once, at some ξ ∈ (x ν -r, x ν + r). Then for t ∈ (x ν -r, ξ),

(η n - h n 2 η n )(t) = (η n + h n 2 η n )(t) -h n η n (t) 1 -h n η n (t) < 1 so that min S (l) n,ν (r) ξ. Similarly max S (r)
n,ν (r) ξ. (iii) By contradiction, assume that the set of n ∈ N such that S (r) n ,ν (r) = ∅ and S (l) n ,ν (r) = ∅ is infinite. We may extract a subsequence n = n (m) such that there exists i n , j n ∈ 0, G n -1 (denoted hereafter i, j) with ih n ∈ S

1 η n ((i + 1)h n ) - h n 2 η n ((i + 1)h n ) = η n (ih n ) + h n η n (ih n )(1 - 1 2 ) =1 +h n 2 η n (ih n ) 1 2! - 1 2 =0 +h n 3 η n (3) (ih n )α 3 + h n 4 1 0 η n (4) (ih n + th n ) (1 -t) 3 3! - (1 -t) 2 2! × 2 dt, and
1 η n ((j -1)h n ) + h n 2 η n ((j -1)h n ) = η n (jh n ) -h n η n (jh n )(1 - 1 2 ) =1 +h n 2 η n (jh n ) 1 2! - 1 2 =0 -h n 3 η n (3) (jh n )α 3 + h n 4 1 0 η n (4) (jh n -th n ) (1 -t) 3 3! - (1 -t) 2 2! × 2 dt
where α k is defined in (D.6). Now, let n → +∞. By (D.1), ih n → x ν and jh n → x ν , and using the uniform convergence of η

(k) n towards η (k)
∞ , dividing by h n 3 , we obtain respectively 0 -η

∞ (x ν ) × 1 12 and 0 η

(3)

∞ (x ν ) × 1 12 , thus η (3)
∞ (x ν ) = 0. (iv) Assume, by contradiction, that the mentioned set is infinite. For such n, a Taylor expansion at ih n yields (we write i for i n ): 3 3! × 2 dt, and

1 = η n ((i + 1)h n ) - h n 2 η n ((i + 1)h n ) = η n (ih n ) + h n 2 η n (ih n ) =1 +γ 3 h n 3 η n (3) (ih n ) + γ 4 h n 4 η n (4) (ih n ) + h n 5 1 0 η n (5) (ih n + th n ) (1 -t) 4 4! - (1 -t)
1 = η n ((i -1)h n ) + h n 2 η n ((i -1)h n ) = η n (ih n ) - h n 2 η n (ih n ) =1 -γ 3 h n 3 η n (3) (ih n ) + γ 4 h n 4 η n (4) (ih n ) + h n 5 1 0 η n (5) (ih n + th n ) (1 -t) 4 4! - (1 -t) 3 3! × 2 dt, with γ k = 1 k! - 1 (k-1)!×2
. Summing both equalities, dividing by h n 4 and taking the

limit n → +∞ yields (η ∞ ) (4) (x ν ) = 0, a contradiction.
This other lemma focusses on the limit of the sets D n defined in (42).

Lemma 6. As n → +∞, the sets D n converge towards D ∞ defined in (44) (in the sense of set convergence).

Proof. We observe that E n ⊂ D n ⊂ F n , where

E n def. = p ∈ H ; max t∈T (Φ * p)(t) + h n 2 |(Φ * p) (t)| 1 , F n def. = p ∈ H ; max k∈ 0, Gn-1 Φ * p(kh n ) 1
so that it suffices to prove that E n and F n converge towards D ∞ . On the one hand, it is clear that D ∞ = n∈N F n , and the sequence F n is non-increasing. On the other hand, it is possible to check that D ∞ = n∈N E n , and the sequence E n is non-decreasing. As a consequence, the claimed set convergences hold (see [START_REF] Rockafellar | Variational analysis. Grundlehren der mathematischen Wissenschaften[END_REF]Ex. 4.3]).

Let us recall that the dual problem to (Q n λ (y)) is the projection onto the closed convex set

D n def. = p ∈ H ; (Φ * p)(ih n ) + h n 2 |(Φ * p) (ih n )| 1 .
Since the set convergence of D n (see Lemma 6 above) implies the convergence of the projections onto D n (see [START_REF] Rockafellar | Variational analysis. Grundlehren der mathematischen Wissenschaften[END_REF], or [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] for a direct proof in a similar context), we obtain: Lemma 7. Let p λ,n (resp. p λ,∞ ) be a solution of (E n λ (y)) (resp. (E ∞ λ (y))), and η λ,n = Φ * p λ,n (resp. η λ,∞ = Φ * p λ,∞ ). Then

lim n→+∞ p λ,n = p λ,∞ strongly in H, lim n→+∞ η (k) λ,n = η (k)
λ,∞ in the sense of the uniform convergence, for all k ∈ N up to the regularity of ϕ.

We are now in position to prove Proposition 5.

Proof of Proposition 5. By Lemma 7, we know that the dual certificates η λ,n converge towards η λ,∞ . By Lemma 5 (i) and the optimality conditions, we have thus lim sup n→+∞ (supp(m λ,n )) ⊂ {x 1 , . . . , x N }.

If m λ,∞ is the unique solution, assume by contradiction that lim inf(supp(m λ,n )) {x 1 , . . . , x N }. Then there is some ν, some ε > 0 such that (up to a subsequence) (supp(m λ,n )) ∩ (x ν -ε, x ν + ε) = ∅. This contradicts the Γ-convergence result (Prop. 4) which ensures that m λ,n converges towards m λ,∞ in the weak* topology. As a result lim n→+∞ (supp(m λ,n )) = {x 1 , . . . , x N }.

If µ λ,∞ (x ν ) = 0, Lemma 5 ensures that the sets S n,ν (r), one may check that the only possible saturation points of η λ,n + hn 2 η λ,n and η λ,n -hn 2 η λ,n are given in Table 1. The optimality conditions of Proposition 1 imply that m λ,n is at most a sum of Dirac masses at those locations.

If η

λ,∞ (x ν ) = 0, Lemma 5 (iii) implies that for n large enough, S

n,ν (r) = ∅ or S (r) n,ν (r) = ∅ (but not both). Hence there are at most two (successive) saturations, produced either by η λ,n + hn 2 η λ,n or by η λ,n -hn 2 η λ,n .

Proof. As mentioned above, the Twice Non-Degenerate Source Condition and Lemma 4 imply η T is a certificate for (Q n 0 (y)). As a result, p 0,n p T and the sequence (p 0,n ) n∈N is bounded in H. We may extract a subsequence p 0,n which weakly converges towards some p ∈ H, and then p lim inf n →+∞ p 0,n p T . Since Φ * and Φ (k), * are compact (see [12, Lemma 1]), we obtain that η

(k) 0,n = (Φ * p 0,n ) (k) converges toward η(k) def.
= (Φ * p) (k) in the (strong) topology of uniform convergence. We immediately obtain that η(t) 1 for all t ∈ T, and η(x ν ) = 1, η(x ν ) = 0 for all ν ∈ {1, . . . , N }.

Moreover, applying Lemma 5 to Φ * p 0,n (observing that

x ν ∈ S (r) n,ν (r) ∩ S (l)
n,ν (r)), we get η(3) (x ν ) = 0. As a result, p is admissible for (49), hence p T p . Thus in fact p T = p and p T = p. Since the limit of the extracted subsequence does not depend on the choice of the subsequence, in fact the whole sequence converges. Moreover, the convergence is strong in H since lim n→+∞ p 0,n = p T .

As a consequence of the above convergence result, the third derivative precertificate controls the extended support on thin grids. = Φ Gn a + Φ Gn b, is a solution to (Q n 0 (y)) and its extended support is given by: where

ext (r) n (a, b) = N ν=1 S (r) n,ν (
• S (r) n,ν (r) is equal to {x ν } or {x ν -h n , x ν }, • S (l) n,ν (r) is equal to {x ν } or {x ν , x ν + h n }. Moreover, one cannot have simultaneously S (r) n,ν (r) = {x ν -h n , x ν } and S (l) n,ν (r) = {x ν , x ν + h n }.
Proof. By Remark 4 η T is a solution to (E n 0 (y)) and (a, b) is a solution to (Q n 0 (y)). Applying Lemma 5 to η 0,n , η T , we see that S (r) n,ν (r) is of the form ∅, {ih n } or {(i -1)h n , ih n }, and that S (l) n,ν (r) is of the form ∅, {jh n } or {jh n , (j + 1)h n }, with i j. On the other hand, by the extremality relations between η 0,n (solution of (E n 0 (y))) and (a, b) (solution of (Q n 0 (y))),

x ν ∈ S (r) n,ν (r) and x ν ∈ S (l) n,ν (r). As a consequence S (r) n,ν (r) is equal to {x ν } or {x ν -h n , x ν }, and S (l) n,ν (r) is equal to {x ν } or {x ν , x ν + h n }. Now, since η 4
T (0) = 0, the fourth point of Lemma 5 ensures that for n large enough, one cannot have simultaneously S

(r) n,ν (r) = {x ν -h n , x ν } and S (l) n,ν (r) = {x ν , x ν + h n }.
Remark 7. As Proposition 7 shows, for each original spike, at most one pair of spikes appears at low noise: the original spike slightly shifted and either the immediate left neighbor shifted by +h n /2 or the immediate right neighbor shifted by -h n /2.

Appendix D.2. Proof of Theorem 3

We proceed by building a good candidate for η 0,n , making the ansatz that for all ν ∈ {1, . . . , N }, its saturation points satisfy if ρ ν > 0, then S (r) n,ν (r) = {x ν -h n , x ν }, and S (l) n,ν (r) = {x ν }, (D.3) if ρ ν < 0, then S (r) n,ν (r) = {x ν }, and S (l) n,ν (r) = {x ν , x ν + h n }, (D.4) and then, using Lemma 3, we prove that this candidate is indeed the minimal norm certificate.

To comply with the notations of Lemma 3, let us write

I (r) def. = I (l) def. = I def. = {i ∈ 0, G n -1 ; a i = 0}.
For any choice of shift (ε i ) i∈I ∈ {-1, +1} N , we set J (r) def. = I (r) ∪ {i + ε i ; i ∈ I and ε i = -1} and J (l) def.

= I (l) ∪ {i + ε i ; i ∈ I and ε i = +1}. Since |x ν -x ν | > 2h n for ν = ν and n large enough, we have Card J (r) + Card J (l) = 3 × Card I = 3N . The idea is to find a choice of ε such that u j > 0 for all j ∈ J (r) \ I, and v j > 0 for all j ∈ J (l) \ I, where

u J (r) v J (l) def. = -( Â * h Âh ) -1 1 J (r) 1 J (l) , Âh def. = (A + h 2 B) J (r) (A -h 2 B) J (l) A def.
= Φ Gn and B def.

= Φ Gn .

In this particular case where I (r) = I (l) = I, all j in (J (r) \ I) ∪ (J (l) \ I) may be uniquely written as j = i + ε i for some i ∈ I, where ε i ∈ {-1, +1}. We may swap the columns of Âh so as to reformulate the condition u J

(r) v J (l) = -( Â * h Âh ) -1 1 3N into    u I v I tI    = -( Ā * h Āh ) -1    1 N 1 N 1 N    , (D.5)
where Āh def.

= A I + hn 2 B I A I -hn 2 B I A I+ε -hn 2 B I+ε diag(ε) and ti > 0 for all i ∈ I (more precisely ti = u i-1 for ε i = -1, ti = v i+1 for ε i = 1). But a Taylor expansion yields A I+ε - h n 2 B I+ε diag(ε) = Φ x =A I + h n 2 Φ x =B I diag(ε) + (h n ) 3 (γ 3 Φ (3)
x diag(ε) + o(1)),

where we defined

γ k def. = 1 k! - 1 (k -1)! × 2 . (D.6)
Hence, we may apply Lemma 2 to Φ x , Φ x and (γ 3 Φ

x + o(1)) so as to obtain tI = -

1 γ 3 h n 3 diag(ε)ρ + o 1 h n 3 .
Therefore it is sufficient to choose ε = -sign(ρ) to make all the components of tI nonnegative (recall that γ 3 < 0). With that choice of ε, it remains to prove that max

(A + h 2 B) * J (r) c (A -h 2 B) * J (l) c Âh u J (r) v J (l) < 1.
Let us write pn def.

= Âh

u J (r) v J (l) . Since u J (r) v J (l) = -( Â * h Âh ) -1 1 3N , we get pn = Â+, * h 1 3N = Ā+, * h 1 3N
, and applying Lemma 2 again, we see that pn converges towards p T (using (50)).

By construction of pn ,

∀j ∈ J (r) \ I, (Φ * pn + h n 2 (Φ * pn ) )(jh n ) = 1,
and ∀j ∈ J (l) \ I, (Φ * pn -

h n 2 (Φ * pn ) )(jh n ) = 1, (D.7)
which may be summarized as

∀i ∈ I, (Φ * pn -ε i h n 2 (Φ * pn ) )((i + ε i )h n ) = 1.
Arguing as in the proof of point (iv) in Lemma 5 (replacing "1 = . . ." with "1 . . ." and using that η

T (x ν ) > 0), we may prove that for n large enough, (Φ * pn + ε i hn

2 (Φ * pn ) )((i -ε i )h n ) < 1.
Then, by the same argument of compactness and local concavity as in point (ii) of Lemma 5, we observe that

k ∈ 0, G n -1 ; (Φ * pn + h n 2 (Φ * pn ) )(kh n ) 1 ⊂ J (r) , k ∈ 0, G n -1 ; (Φ * pn - h n 2 (Φ * pn ) )(kh n ) 1 ⊂ J (l) ,
and those inclusions are in fact equalities. That precisely means that max

(A + h 2 B) * J (r) c (A -h 2 B) * J (l) c pn < 1.
Hence, by Lemma 3, Φ * pn is the minimal norm certificate η 0,n and (J (r) h n , J (l) h n ) is the extended support. This concludes the proof.

Appendix D.3. Proof of Corollary 1

We build a pair of candidate solutions for the primal and dual problems, and we prove that they satisfy the optimality conditions. Again, we change variables so as to deal with the positive Lasso, working with (r λ , l λ ) rather than (a λ , b λ ) (see [START_REF] Schiebinger | Superresolution without Separation[END_REF]). In particular, we define (r, l) from (a, b) using [START_REF] Schiebinger | Superresolution without Separation[END_REF].

Moreover, as the noise w and the remainder of the Taylor expansion R α (s) play the same role, we set w def. = R α (s) + w, to simplify the notation. In the rest of the proof, we assume that there exists κ ∈ (0, 1) such that s ∞ κ hn 2 : as we shall see, it is not restrictive since the constraints on the "noise" w impose s h n . Recall the notation A def.

= Φ Gn , B def.

= Φ Gn and A

h def. = A + h 2 B A -h 2 B
. Defining (J (r) , J (l) ) as in the proof of Theorem 3, we let Âh def.

= (

A + h 2 B) J (r) (A -h 2 B) J (l) (again, Âh has full rank for h small enough since Φ x Φ x Φ (3) x has full rank). Now, we let            (r λ ) J (r) (l λ ) J (l) def. = Â+ h y -λ( Â * h Âh ) -1 1 3N = r J (r) l J (l) + Â+ h w + λ u J (r) v J (l) , p λ def. = 1 λ y -Âh (r λ ) J (r) (l λ ) J (l) = 1 λ Π (Im Âh ) ⊥ y + Â+, * h 1 3N , (D.8)
where u, v are defined as in the proof of Theorem 3 by

u J (r) v J (l) def. = -( Â * h Âh ) -1 1 J (r) 1 J (l) = -( Â * h Âh ) -1 1 3N . Observe that by construction of p λ , A + h 2 B A -h 2 B * p λ = Â * h p λ = 1 3N
. It remains to prove that (i) For all i ∈ I, r λ,i 0 and l λ,i 0.

(ii) For all j ∈ J (r) \ I (resp. j ∈ J (l) \ I) , r λ,j 0 (resp. l λ,j 0).

(iii) For k / ∈ J (r) (resp. k / ∈ J (l) ) ((A * + hn 2 B * )p λ ) k < 1 (resp. ((A * -hn 2 B * )p λ ) k < 1)
Regarding the first two points, we apply the same reordering of the columns as in the proof of Theorem 3,

   (r λ ) I (l λ ) I (z λ ) I    =    r I l I 0 N    + Ā+ h w -λ( Ā * h Āh ) -1 1 3N , (D.9)
where (z λ ) i = (r λ ) i-1 if i ∈ J (r) \ I, and (l λ ) i+1 otherwise (i.e. i ∈ J (l) \ I). Using the same Taylor expansion (denoting Φ

(3)

x,h def.

= Φ

(3)

x + o(1)), combined with (A.8) and (A.6), we get

Ā+ h = 1 γ 3 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (Π (Im Γ x ) ⊥ Φ (3) x,h ) + +    1 2 Id N 1 h Id N 1 2 Id N -1 h Id N 0 0    (Π (Im Φ (3) x,h ) ⊥ Γ x ) +
and ( Ā * h Āh ) -1 1 3N = -

1 γ 3 h 3    diag -1+ε 2 diag 1-ε 2 diag(ε)    (Φ (3), * x,h Π (Im Γ x ) ⊥ Φ (3) x,h ) -1 Φ (3) x,h Γ + x 1 N 0 +    1 2 Id N 1 h Id N 1 2 Id N -1 h Id N 0 0    (Γ * x Π (Im Φ (3) x,h ) ⊥ Γ x ) -1 1 N 0 .
As a result, the following componentwise inequality holds,

   (r λ ) I (l λ ) I (z λ ) I+ε       r I l I 0 N    -Â+ h ∞,H w H -λ ( Ā * h Āh ) -1 1 3N ∞
From the above expressions, and using the fact that (Φ

(3), *

x,h Π (Im Γ x ) ⊥ Φ

x,h ) -1 Φ

(3)

x,h Γ + As for (z λ ) I , i.e. the components of (r λ ) J (r) \I and (l λ ) J (l) \I , we note that in fact,

(z λ ) I -Â+ h ∞,H w H + λ 1 γ 3 h 3 diag(ε)(Φ (3), * x,h Π (Im Γ x ) ⊥ Φ (3) x,h ) -1 Φ (3)
x,h Γ + .

Hence, they are positive provided Â+ = Φ * Π (Im Âh ) ⊥ w and η 0,n def.

= Φ * ( Â * h Âh ) -1 1 3N = Φ * p 0,n yields the minimal norm certificate η0,n = (η 0,n

+ h 2 η 0,n )(G n ) (η 0,n -h 2 η 0,n )(G n ) = (A + h 2 B) * (A -h 2 B) * ( Â * h Âh ) -1 1 3N .
Given 0 < r < 1 2 min ν =ν |x ν -x ν |, let N (r)

def.

= ν (x ν -r, x ν +r) be a neighborhood of the x ν 's. By the Twice Non-Degenerate Source condition, we may choose r > 0, such that = µ We first deal with the case S To summarize, we have proved the global inequalities (D.13) and (D.14). The (strict) extremality relations hold for (r λ , l λ ) and p λ and they are unique solutions of the primal and dual problems respectively. The conditions on w H λ stemming from (D.12), and (D.17)-(D. [START_REF] Rockafellar | Variational analysis. Grundlehren der mathematischen Wissenschaften[END_REF]) define the bound C (3) . The condition on the signal to noise ratio w / min α and λ/ min α given in (D.10) define the bounds C (1) and C (2) .

To finish, using the mapping H h , we recover (a λ , b λ ) from (D.9) so as to derive (53). We obtain Proof. We let g -(t)

(a λ ) I (b λ ) I = a I b I + (Π (Im Φ (3) x,h ) ⊥ Γ x ) + w + 1 |γ 3 | 1 h 3 diag(ε) 1 2h 2 diag(ε) (Π (Im Γ x ) ⊥ Φ (3) x,h ) + w -λ(Γ * x Π (Im Φ (3) x,h ) ⊥ Γ x ) -1 1 N 0 N + λ |γ 3 |
def.

= f (t) -h 2 f (t) and g + (t)

def.

= f (t) + h 2 f (t). It suffices to show that g -(t) < 1 and g + (t) < 1 in the corresponding intervals.

Observe that ∀t ∈ (-r, r), g

-(t) = f (t) - h 2 f (3) (t) - k 2 2
< 0 so that g -is strictly concave. Since g -(0) = g -(h) = 1, we deduce that g -(t) < 1 for all t ∈ [-r, 0) ∪ (h, r].

As for g + , we observe similarly that g + is strictly concave. Since g + (0) = h 2 f (0) < 0 and g + is decreasing, we deduce that g + (t) < g + (0) = 1 for all t ∈ (0, r].

We obtain the desired result if we can prove that g + (-h) < 1. Now,

f (h) + f (-h) = 2 f (0) + h 2 f (0) 2 + h 4 f (4) (0) 4! + h 5 1 0
(f (5) (sh) -f (5) (-sh)) (1 -s) 4 4! ds and h 2 (-f (h) + f (-h)) = h -f (0)h -h 3 f (4) (0) 3! -h 5 1 0 (f (5) (sh) -f (5) (-sh)) (1 -s) 3 2 × 3! ds.

Hence, g -(h) + g + (-h) = 2f (0) + 2h 4 f (4) (0) 1 4! -1 2 × 3! + h 5 1 0 (f (5) (sh) -f (5) (-sh))

(1 -s) for h small enough. We conclude that the claimed inequality holds.

Figure 1 :

 1 Figure 1: Depending on i being in I (r) or I (l) , the spikes of the solutions to[START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] are supported on half-grid points or in the interval ((i -1/2)h, (i + 1/2)h).

Definition 4 (

 4 Third derivative precertificate). Given x ∈ (G 0 ) N , we define the third derivative precertificate as η T def. = Φ * p T where p T def.

  are nonzero. Then, for n large enough, any vector (a, b) ∈ C hn defined by (51), with y def.

Figure 2 :

 2 Figure 2: Lasso and C-BP paths are functions of λ (from blue to red) for a single Dirac input measure (N = 1).

Figure 3 :

 3 Figure 3: Lasso and C-BP paths are functions of λ (from blue to red) for N = 3 input Diracs.

Figure 4 :

 4 Figure 4: Display of η V,∞ (red) and η T (blue) pre-certificate for different input positive measures m 0 (showed as black dots to symbolize the position of the Diracs).

Figure 4

 4 Figure 4 illustrates for the case of two (N = 2) and three (N = 3) spikes the behavior of the vanishing pre-certificate η V,∞ (see Definition 2) useful to analyze Lasso/BLasso problems and of the pre-certificate η T (see Definition 4) useful to analyze C-BP problems.We first notice that for all the (positive) input measures (i.e. whatever the spacing between the Diracs), η V,∞ is always a non-degenerate certificate (in the sense of Proposition 2), meaning that one actually has η V,∞ = η 0,∞ (where the minimal norm certificate η 0,∞ is the minimal norm solution of (D ∞ 0 (y 0 )) in[START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]). This empirical finding is the subject of another recent work on the asymptotic of sparse recovery of positive measures when the spacing between the Diracs tends to zero[START_REF] Denoyelle | Support Recovery for Sparse Deconvolution of Positive Measures[END_REF]. Since η 0,∞ is nondegenerate, one can thus apply[START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF] Theorem 2] to analyze the extended support of the

5 CFigure 5 :

 55 Figure5: Display of the evolution as a function of λ of the solutions of the Lasso and C-BP problems. Note that dashed curved have been (artificially) slightly shifted to avoid that they overlap with the plain curve.

  (r) ⊂ (x ν -r, x ν + r). By uniform convergence, η n + hn 2 |η

  (r) (resp. S (l) n,ν (r)) is of the form ∅, {ih n }, or {ih n , (i + 1)h n }. Observe also that η n + hn 2 η n -(η n -hn 2 η n ) = h n η n .Since the function η n is strictly decreasing in (x ν -r, x ν + r), it vanishes at most once. If S (r) n,ν (r) = ∅ and S (l)

  (r m ), jh n ∈ S (l) n,ν . Combining the Taylor expansions of η n and (η n ) around ih n (resp. jh n ), we get

  (r) are of the form ∅, {ih n }, or {ih n , (i + 1)h n }. Moreover, since lim n→+∞ (supp m λ,n ) = {x 1 , . . . , x N } we must have S (r) n,ν (r) = ∅ or S (l)n,ν (r) = ∅. Using the fact that max S

Proposition 7 .

 7 Let x ∈ G 0 , such that the Twice Non Degenerate Source Condition holds. Then, for n large enough, any vector (a, b) ∈ C hn defined by (51), with y def.

  r), and ext (l) n (

3 |

 3 (h) 3 (Π (Im Γ x ) ⊥ Φ h Āh ) -1 1 3N ∞ ∼ 1 |γ 3 |(h) 3 ρ ∞ . Since min i∈I r i = min ν∈{1,...,N } 1 2 α ν + 1 hn α ν s ν (1-κ) 2min α, and similarly min i∈I l i(1-κ) 2min α, we deduce that (r λ ) I and (l λ ) I have positive components provided(h n ) 3 min α c 1 w H + c 2 λ,

|γ 3

 3 |h 3 (|ρ|+o(1))

  η

  t∈T\N (r) η T (t) < 1.Let us recall that η 0,n → η T in the sense of the uniform convergence (and similarly for the derivatives). As a result, for n ∈ N large enough,

  (r) = {x ν }, S (l) n,ν (r) = {x ν , x ν + h}. Let f def. = 1 λ ω(• -x ν ) + η 0,n (• -x ν ). By definition of Π (Im Âh ) ⊥ , ω(x ν ) = ω (x ν ) = ω(x ν + h) -h 2 ω (x ν + h) = 0, so that f (0) = 1, f (0) = 0, and f (h) -h 2 f (h) = 1. (D.22)Moreover, letting k 2 = 3 8 k2 , k 4 = 1 2 k4 , k 5 = k5 , we see from Eq. (D.15) to (D.[START_REF] Rockafellar | Variational analysis. Grundlehren der mathematischen Wissenschaften[END_REF]) that f satisfies the hypotheses of Lemma 8 below. We deduce that the local inequalities (D.20) and (D.21) hold. The symmetric case, S (r)n,ν (r) = {x ν -h, x ν }, S(l)n,ν (r) = {x ν }, is handled similarly, replacing f with f (-•).

1 h 3 1 2h 2 - 1 |γ 3 | 1 h 3 1 2h 2 λ |γ 3 | 1 h 3 1 2h 2 Lemma 8 .f ( 4 )∞ k 5 ,

 131213121312845 (|ρ| + o(1)) (|ρ| + o(1)). and using that r i = 0 (resp.l i = 0) if z i = l i (resp. r i ), we get (a λ ) I+ε (b λ ) I+ε = diag(ε)(Π (Im Φ (3) x,h ) ⊥ Γ x ) + w (Π (Im Φ (3) x,h ) ⊥ Γ x ) + w + (|ρ| + o(1)) diag(ε)(|ρ| + o(1)) . Let r > 0, f ∈ C 5 ([-r, r]), k 2 > 0, k 4 >0, and k 5 > 0. Then, for all h > 0 small enough, the conditionsf (0) = 1, f (0) = 1, and f (h) -h 2 f (h) = 1, (D.23) sup t∈(-r,r)f (t) -k 2 , (t) k 4 and f(5) (D.24)imply ∀t ∈ [-r, 0) ∪ (h, r], f (t) -h 2 f (t) < 1, (D.25)and ∀t ∈ [-r, -h] ∪ (0, r], f (t) + h 2 f (t) < 1. (D.26)

  g -(h) = f (0) = 1 and f (4) (0) k 4 > 0, we obtain g + (-h) 1 -

  H < λ |γ 3 |h 3 min {|ρ i | + o(1) ; i ∈ I}.This condition holds for large n provided w H /λ c 3 , wherec 3 = min i∈I |ρ i | 2 (Π (Im Γ x ) ⊥ Φ

	(3) x ) + To summarize, we have proved the first two points. For the last point, we have to ensure that max η 0,n + ω λ (jh) + h 2 η 0,n + ω λ (jh) < 1 for all j ∈ (J (r) ) C , ∞,H . η 0,n + ω λ (jh) -h 2 η 0,n + ω λ (jh) < 1 for all j ∈ (J (l) ) C , (A we are led to check that where ω def.	(D.12) (D.13) (D.14)

h ∞,H w * + h 2 B * ) (J (r) ) c (A * -h 2 B * ) (J (l) ) c p λ < 1

Since by construction

p λ = 1 λ Π (Im Âh ) ⊥ y + Â+, * h 1 3N = 1 λ Π (Im Âh ) ⊥ w + Â+, * h 1 3N = 1 λ Π (Im Âh ) ⊥ w + p 0,n ,

  Thus it remains to prove that for each ν ∈ {1, . . . , N }, < 1 for t∈ (x ν -r, x ν + r) ∩ G n \ S (r) < 1 for t ∈ (x ν -r, x ν + r) ∩ G n \ S (l)n,ν (r). (D.21)

		η 0,n +	ω λ	+	h 2	(η 0,n +	ω λ	) (t) n,ν (r),
																	(D.20)
	and	η 0,n +	ω λ	-	h 2	(η 0,n +	ω λ	) (t)
															5) T	∞	+ 1,	(D.16)
				h 2	(η 0,n ) ∞			1 -k0 6	and	h 2	(η 0,n ) (3)	∞	k2 8	.
	Now, we assume that	w H λ	is small enough, so that
								(Φ (j) ) *	∞,H	w H λ	1 -k0 6	, for j ∈ {0, 1},	(D.17)
								(Φ (j) ) *	∞,H	w H λ	k2 8	, for j ∈ {2, 3},	(D.18)
			and		(Φ (4) ) *	∞,H		w H λ	k4 4	.		(D.19)
		η 0,n +	ω λ	+	h 2	(η 0,n +	ω λ	) (t)	1 + k0 2	+	1 -k0 6	+	1 -k0 6	+	1 2	1 -k0 6	< 1.

Then, using the fact that and |ω (j) |(t) (Φ (j) ) * ∞,H w H and h 1, we obtain sup t∈T\N (r)

Acknowledgements

We would like to thank Charles Dossal, Jalal Fadili and Samuel Vaiter for stimulating discussions on the notion of extended support. This work has been supported by the European Research Council (ERC project SIGMA-Vision).

Appendix A. Asymptotic expansion of the inverse of a Gram matrix

In this Appendix, we gather some useful lemmas on the asymptotic behavior of inverse Gram matrices. The proof of the following lemma can be found in [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids I: the LASSO[END_REF]. Lemma 1. Let A : R N → H, B : R N → R N be linear operators such that A has full rank and B is invertible. Then (AB)

and let

Asymptotics of the Minimal Norm Certificates

We begin with two propositions concerning minimal norm certificates. From Remark 4, given x ∈ G 0 , if the Twice Non-Degenerate Source Condition (Definition 5) holds, then the vector (a, b) defined by (51), with y def.

= Φ Gn a + Φ Gn b, is a solution to (Q n 0 (y)) for all n large enough, and η T is a valid dual certificate, i.e. a solution to (E n 0 (y)). In fact the associated minimal norm certificates (which thus exist) converge towards η T . Proposition 6. Let x ∈ G 0 satisfy the Twice Non-Degenerate Source Condition (and η T the corresponding Third derivative (pre)certificate). Let p 0,n be the minimal norm solution of (E n 0 (y)), and η 0,n = Φ * p 0,n . Then, • lim n→+∞ p 0,n = p T for the H strong topology,

in the sense of the uniform convergence, for all k ∈ N up to the regularity of ϕ.