Vincent Duval
email: vincent.duval@inria.fr

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

Sparse Spikes Super-resolution on Thin Grids I: the LASSO

This article analyzes the recovery performance in the presence of noise of sparse 1 regularization, which is often referred to as the Lasso or Basis-Pursuit. We study the behavior of the method for inverse problems regularization when the discretization step size tends to zero. We assume that the sought after sparse sum of Diracs is recovered when there is no noise (a condition which has been thoroughly studied in the literature) and we study what is the support (in particular the number of Dirac masses) estimated by the Lasso when noise is added to the observation. We identify a precise non-degeneracy condition that guarantees that the recovered support is close to the initial one. More precisely, we show that, in the small noise regime, when the non-degeneracy condition holds, this method estimates twice the number of spikes as the number of original spikes. Indeed, we prove that the Lasso detects two neighboring spikes around each location of an original spike. While this paper is focussed on cases where the observations vary smoothly with the spikes locations (e.g. the deconvolution problem with a smooth kernel), an interesting by-product is an abstract analysis of the support stability of discrete 1 regularization, which is of an independent interest. We illustrate the usefulness of this abstract analysis to analyze for the first time the support instability of compressed sensing recovery.

Introduction

We consider the problem of estimating an unknown Radon measure on the torus T = R/Z (i.e. an interval with periodic boundary conditions), m 0 ∈ M(T), from low-resolution noisy observations in a separable Hilbert space H,

y = Φ(m 0 ) + w ∈ H (1)
where w ∈ H is some measurement noise, and Φ : M(T) → H is a bounded linear map such that

∀ m ∈ M(T), Φ(m) = T ϕ(x)dm(x), (2)
where ϕ ∈ C 2 (T, H).

A typical example of such an operation is a convolution, where H = L 2 (T) and ϕ(x) : x → φ(x -x) for some smooth function φ defined on T. Another example is a partial Fourier transform, where H = C P , and ϕ(x) = (e 2iπω k x ) P k=1 ∈ H where ω k ∈ Z are the measured frequencies. For instance, using low frequency -f c ω k = k -f c -1 f c with P = 2f c + 1 is equivalent to using a convolution with the ideal low-pass filter

∀ x ∈ T, φ(x) = fc k=-fc e 2iπkx , (3)
with cutoff frequency f c . To simplify the notation, we shall assume that H is a real Hilbert space, and we leave to the reader the straightforward adaptations to the complex case.

Sparse Regularization

The problem of inverting ( 1) is severely ill-posed. A particular example is when Φ is a low pass filter, which is a typical setting for many problems in imaging. In several applications, it makes sense to impose some sparsity assumption on the data to recover. This idea has been introduced first in the geoseismic literature, to model the layered structure of the underground using sparse sums of Dirac masses [START_REF] Claerbout | Robust modeling with erratic data[END_REF]. Sparse regularization has later been studied by David Donoho and co-workers, see for instance [START_REF] Donoho | Superresolution via sparsity constraints[END_REF].

In order to recover sparse measures (i.e. sums of Diracs), it makes sense to consider the following regularization min m∈M(T)

1 2 ||y -Φ(m)|| 2 + λ|m|(T) (4)
where |m|(T) is the total variation of the measure m, defined as

|m|(T) def. = sup T ψ(x)dm(x) ; ψ ∈ C (T), ||ψ|| ∞ 1 . (5)
This formulation of the recovery of sparse Radon measures has recently received lots of attention in the literature, see for instance the works of [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]. In the case where there is no noise, w = 0, it makes sense to consider λ → 0 and to solve the following limit problem min m∈M(T) {|m|(T) ; Φ(m) = Φ(m 0 )} .

1.2. Lasso

The optimization problem (4) is convex but infinite dimensional, and while there exists solvers when Φ is measuring a finite number of Fourier frequency (see [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF]), they do not scale well with the number of frequencies. Furthermore, the case of an arbitrary linear operator Φ is still difficult to handle, see [START_REF] Bredies | Inverse problems in spaces of measures[END_REF] for an iterative scheme. The vast majority of practitioners thus approximate (4) by a finite dimensional problem computed over a finite grid G def.

= {z i ; i ∈ 0, G -1 } ⊂ T, by restricting their attention to measures of the form

m a,G def. = G-1 i=0 a i δ z i ∈ M(T).
For such a discrete measure, one has |m|(T) = G-1 i=0 |a i | = ||a|| 1 , which can be interpreted as the fact that | • |(T) is the natural extension of the 1 norm from finite dimensional vectors to the infinite dimensional space of measures. Inserting this parametrization in (4) leads to the celebrated Basis-Pursuit problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF], which is also known as the Lasso method in statistics [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF],

min a∈R N 1 2
||y -Φ G a|| 2 + λ||a|| 1 [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] where in the following we make use of the notations

Φ G a def. = Φ(m a,G ) = G-1 i=0 a i ϕ(z i ), (8)
One can understand [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] as performing a nearest neighbor interpolation of the Dirac's locations.

Note that while we focus in this paper on convex recovery method, and in particular 1 -type regularization, there is a vast literature on the subject, which makes use of alternative algorithms, see for instance [START_REF] Odendaal | Two-dimensional superresolution radar imaging using the MUSIC algorithm[END_REF][START_REF] Blu | Sparse Sampling of Signal Innovations[END_REF] and the references therein.

Motivating Example

Figure [START_REF] Amelunxen | Living on the edge: A geometric theory of phase transitions in convex optimization[END_REF] illustrates the typical behavior of the Lasso method [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] to estimate a sparse input measure m 0 (shown in (a)) from observations y = Φm 0 + w, where Φ is the ideal low-pass filter with cutoff frequency f c , i.e. ϕ(x) = φ(x -•) where φ is defined in [START_REF] Bhaskar | Atomic norm denoising with applications to line spectral estimation[END_REF]. In the numerical simulation, we used f c = 12 and an uniform grid of G = 512 points. Here w is a small input noise, and its impact can be visualized in (a) where both y 0 = Φm 0 (plain black curve) and y = y 0 + w (dashed black curve) are displayed. As can be expected, the recovered a λ (solution of [START_REF] Candes | An Introduction to Compressive Sensing[END_REF]) with a small value of λ (here λ = 0.05 is displayed in (c)) is bad because too much noise contaminates the result. A well chosen value of λ (here λ = 4 is displayed in (d)) is able to remove the noise, and to detect spikes located near the input spikes composing m 0 . However, as showed in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], in this small noise setting, one can recover up to twice as many spikes as the input measures, because the spikes of m 0 can get duplicated on immediate nearest neighbors on the grid G. Figure 1, (b), further refines this analysis by displaying the whole path λ → a λ (dashed curves indicate spurious spikes whose locations do not match those of the input measure m 0 ). It is the goal of this paper to precisely analyze and quantify this behavior. In particular, we precisely characterize the "extended support" (those grid locations that are selected when the noise is small and λ well chosen) and show that for deconvolution, it is exactly composed of pairs of nearest neighbors.

Previous Works

Most of the early work to assess the performance of convex sparse regularization has focussed its attention on the finite dimensional case, thus considering only the Lasso problem [START_REF] Candes | An Introduction to Compressive Sensing[END_REF]. While the literature on this subject is enormous, only very few works actually deal with deterministic and highly correlated linear operators such as low-pass convolution kernels. The initial works of Donoho [START_REF] Donoho | Superresolution via sparsity constraints[END_REF] study the Lipschitz behavior of the inverse map y → a , where a is a solution of [START_REF] Candes | An Introduction to Compressive Sensing[END_REF], as a function of the bandwidth of the bandpass filter. The first work to address the question of spikes identification (i.e. recovery of the exact location of the spikes over a discrete grid) is [START_REF] Dossal | Sparse spike deconvolution with minimum scale[END_REF]. This work uses the analysis of 1 regularization introduced by Fuchs in [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. This type of analysis ensures that the support of the input measure is stable under small noise perturbation of the measurements. Our finding is that this is however never the case (the support is always unstable) when the grid is thin enough, and we thus introduce the notion of "extended support", which is in some sense the smallest extension of the support which is stable. The idea of extending the support to study the recovery performance of 1 methods can be found in the work of Dossal [START_REF]A necessary and sufficient condition for exact recovery by 1 minimization[END_REF] who focusses on noiseless recovery and stability in term of 2 error.

Recently, a few works have studied the theoretical properties of the recovery over measures (4). Candès and Fernandez-Granda show in [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF] that this convex program does recover exactly the initial sparse measure when w = 0 and λ → 0 (i.e. program ( 6)) under a minimum-separation condition, i.e. if the spikes are well-separated. The robustness to noisy measurements is analyzed by the same authors in [START_REF] Candès | Super-Resolution from Noisy Data[END_REF] using an Hilbertian norm, and in [START_REF] Fernandez-Granda | Support detection in super-resolution[END_REF][START_REF] Azais | Spike detection from inaccurate samplings[END_REF] in terms of spikes localization. The work of [START_REF] Tang | Near Minimax Line Spectral Estimation[END_REF] analyzes the reconstruction error. Lastly, [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] provides a condition ensuring that (4) recovers the same number of spikes as the input measure and that the error in terms of spikes localization and elevation has the same order as the noise level. It is important to note that in the special case where m 0 is a positive measure, then m 0 is always a solution to [START_REF] Burger | Convergence rates of convex variational regularization[END_REF], as shown in [START_REF] Castro | Exact reconstruction using Beurling minimal extrapolation[END_REF] (see also [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).

Very few works have tried to bridge the gap between these grid-free methods over the space of measures, and finite dimensional discrete approximations that are used by practitioners. These theoretical questions are however relevant from a practitioner's point of view, and we refer [START_REF] Min | FALCON: Fast and Unbiased Reconstruction of High-Density Super-Resolution Microscopy Data[END_REF] for experimental observations of the impact of discretization and the corresponding recovery bias. The convergence (in the sense of measures) of the solutions of the discrete problem toward to ones of the grid-free problem is shown in [START_REF] Tang | Sparse recovery over continuous dictionaries-just discretize[END_REF], where a speed of convergence is shown using tools from semi-infinite programming [START_REF] Still | Discretization in semi-infinite programming: the rate of convergence[END_REF]. The same authors show in [START_REF] Bhaskar | Atomic norm denoising with applications to line spectral estimation[END_REF] that the discretized problem achieves a similar prediction L 2 error as the grid-free method. Γ-convergence results on 1 but also 0 regularization are provided in the PhD work of [25]. In [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], we have shown that solutions of the discrete Lasso problem estimate in general as much as twice the number of spikes as the input measure. We detail in the following section how the present work gives a much more precise and general analysis of this phenomenon.

Contributions

Our paper is composed of two contributions (Theorems 1 and 2) that study the robustness to noise of the support of the solution of Lasso finite dimensional recovery problems. We stress the fact that we always suppose that the sought after sparse measure m 0 is identifiable, i.e. is the solution of the BLASSO program (6) (i.e. in the noiseless case w = 0, λ = 0). This mandatory hypothesis is now well understood, as detailed in Section 1.4, and is always true if the measure m 0 is positive, or under a minimum separation distance between the spikes. Our main contributions study whether the support of the recovered solution is close from the one of m 0 in the presence of a small noise. Such a stability cannot hold in full generality, and requires a strengthening of the optimality condition for m 0 being identifiable, which we refers in the following as a "non-degeneracy" condition.

Section 2 presents our first contribution. This is an improvement over the known analysis of the Lasso in an abstract setting (that is [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] when Φ G is replaced with any finite dimensional linear operator). Whereas Fuchs' result [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF] characterizes the exact support recovery of the Lasso at low noise, our previous work [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] has pointed out that when Fuchs'criterion is not satisfied, the nonzero components of the solutions of the Basis-Pursuit at low noise are contained in the extended support, that is the saturation set of some minimal norm dual certificate. Theorem 1 states that under a sufficient nondegeneracy condition (hypothesis [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], which holds generically), all the components of the extended support are actually nonzero (with a prediction on the signs).

Section 3 applies this result to Problem (7) on thin grids. After recalling the convergence properties of Problem ( 7) towards (4), we show that, if the input measure m 0 = m α 0 ,x 0 = N ν=1 α 0,ν δ x 0,ν has support on the grid (i.e. x 0,ν ∈ G for all ν), and if a non-degeneracy condition holds (the "Non-Degenerate Source Condition", see Definition 2), the methods actually reconstructs at low noise pairs of Dirac masses, i.e. solutions of the form

m λ = N ν=1 α λ,ν δ x 0,ν + β λ,ν δ x 0,ν +εν h , where ε ν ∈ {-1, +1}, (9)
and sign(α λ,ν ) = sign(β λ,ν ) = sign(α 0,ν ). [START_REF] Chandrasekaran | The Convex Geometry of Linear Inverse Problems[END_REF] The precise statement of this result can be found in Theorem 2. Compared to [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] where it is predicted that spikes could appear at most in pairs, this result states that all the pairs do appear, and it provides a closed-form expression for the shift ε. That closed-form expression does not vary as the grid is refined, so that the side on which each neighboring spike appears is in fact intrinsic to the measure, we call it the natural shift. Moreover, we characterize the low noise regime as ||w|| 2 λ = O(1) and λ = O(h). It is worth emphasizing that, in this setting of spikes retrieval on thin grids, our contributions give important information about the structure of the recovered spikes when the noise w is small. This is especially important since, contrary to common belief, the spikes locations for Lasso are not stable: even for an arbitrary small noise w, neither methods retrieve the correct input spikes locations.

Eventually, we illustrate in Section 4 our abstract analysis of the Lasso problem (7) (as provided by Theorem 1) to characterize numerically the behavior of the Lasso for compressed sensing (CS) recovery (i.e. when one replaces the filtering Φ G appearing in [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] with a random matrix). The literature on CS only describes the regime where enough measurements are available so that the support is stable, or does not study support stability but rather 2 stability. Theorem 1 allows us to characterize numerically how much the support becomes unstable (in the sense that the extended support's size increases) as the number of measurements decreases (or equivalently the sparsity increases).

Notations and preliminaries

The set of Radon measures (resp. positive Radon measures) is denoted by M(T) (resp. M + (T)). Endowed with the total variation norm (5), M(T) is a Banach space. Another useful topology on M(T) is the weak* topology: a sequence of measures (m n ) n∈N weak* 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.

Given a separable Hilbert space H, the properties of Φ : M(T) → H and its adjoint are recalled in Proposition 1 in Appendix. The ∞, 2-operator norm of Φ * :

H → C (T) is defined as ||Φ * || ∞,2 def.
= sup {||Φ * w|| ∞ ; w ∈ H, ||w|| 1} (and the ∞, 2 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 (replacing ϕ(x 0,ν ) with

ϕ (x 0,ν ). The concatenation of Φ x 0 and Φ x 0 is denoted by Γ x 0 def. = Φ x 0 Φ x 0 .
We shall 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 (11) lim inf n→+∞ C n = x ∈ T ; lim sup n→+∞ d(x, C n ) = 0 ( 12
)
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. ( 13
) 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

The aim of this section is to study the low noise regime of the Lasso problem in an abstract finite dimensional setting, regardless of the grid stepsize. In this framework, the columns of the (finite dimensional) degradation operator need not be the samples of a continuous (e.g. convolution) operator, and the provided analysis holds for any general Lasso problem. We extend the initial study of Fuchs of the basis pursuit method (see [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]) which gives the analytical expression of the solution when the noise is low and the support is stable. Here, provided we have access to a particular dual vector η 0 , we give an explicit parametrization the solutions of the basis pursuit at low noise even when the support is not stable. This is especially relevant for the deconvolution problem since the support is not stable when the grid is thin enough.

Notations and optimality conditions

We consider in this section observations in an arbitrary separable Hilbert space H, which might be for instance L 2 (T) (e.g. in the case of a convolution) or a finite dimensional vector space. The linear degradation operator is then denoted as A : R G → H. Let us emphasize that in this section, for

a ∈ R G , a ∞ def. = max 0 k G-1 |a k |.
Given an observation y 0 = Aa 0 ∈ H (or y = y 0 + w, where w ∈ H), we aim at reconstructing the vector a 0 ∈ R G by solving the Lasso problem for λ > 0,

min a∈R G 1 2 ||y -Aa|| 2 + λ||a|| 1 (P λ (y))
and for λ = 0 we consider the (Basis-Pursuit) problem = {i ∈ 0, G -1 ; a i = 0}. Also, we let s I def.

min a∈R G ||a|| 1 such that Aa = y 0 . (P 0 (y 0 )) If a ∈ R G ,
= sign(a I ), and supp ± (a)

def. = {(i, s i ) ; i ∈ I} the signed support of a.
The optimality conditions for Problems (P λ (y)) and (P 0 (y 0 )) are quite standard, as detailed in the following proposition.

Proposition 1. Let y ∈ H, and a λ ∈ R G . Then a λ is a solution to (P λ (y)) if and only if there exists p λ ∈ H such that

A * p λ ∞ 1, and (A * p λ ) I = sign(a λ,I ), ( 14
)
λA * p λ + A * (Aa λ -y) = 0. ( 15
)
Similarly, if a 0 ∈ R G , then a 0 is a solution to (P 0 (y 0 )) if and only if Aa 0 = y 0 and there exists p ∈ H such that.

A * p ∞ 1 and (A * p) I = sign(a 0,I ). ( 16
)
Conditions ( 14) and ( 16) merely express the fact that η λ def.

= A * p λ (resp. η def.

= A * p) is in the subdifferential of the 1 -norm at a λ (resp. a 0 ). In that case we say that η λ (resp. η) is a dual certificate for a λ (resp. a 0 ). Condition ( 16) is also called the source condition in the literature [START_REF] Burger | Convergence rates of convex variational regularization[END_REF].

The term dual certificate stems from the fact that p λ (resp. p) is a solution to the dual problem to (P λ (y)) (resp. (P 0 (y 0 ))),

inf p∈C y λ -p 2 2 , (D λ (y)) resp. sup p∈C y 0 , p , (D 0 (y 0 ))
where

C def. = p ∈ H ; max k∈ 0, G-1 |(A * p) k | 1 . ( 17
)
If a is a solution to (P λ (y)) and p λ is a solution to (D λ (y)), then ( 14) and ( 15) hold.

Conversely, for any a ∈ R P and any p λ ∈ H, if ( 14) and ( 15) hold, then a is a solution to (P λ (y)) and p λ is a solution to (D λ (y)). A similar equivalence holds for (P 0 (y 0 )) and (D 0 (y 0 )).

Remark 1. In general, the solutions to (P λ (y)) and (P 0 (y 0 )) need not be unique. However, the dual certificate η λ = A * p λ which appears in ( 14) and ( 15) is unique. On the contrary, the dual certificate η = A * p which appears in ( 16) is not unique in general.

We say that a vector a 0 is identifiable if it is the unique solution to (P 0 (y 0 )) for the input y = Aa 0 . The following classical result gives a sufficient condition for a 0 to be identifiable.

Proposition 2. Let a 0 ∈ R G such that A I is injective and that there exists p ∈ H such that

||(A * p) I c || ∞ < 1 and (A * p) I = sign(a 0,I ), ( 18
)
where

I c = 1, G \ I. Then a 0 is identifiable.
Conversely, if a 0 is identifiable, there exists p ∈ H such that (18) holds and A I is injective (see [START_REF] Grasmair | Necessary and sufficient conditions for linear convergence of 1 -regularization[END_REF]Lemma 4.5]).

Extended support of the Lasso

From now on, we assume that the vector a 0 ∈ R G is identifiable (i.e. a 0 is the unique solution to (P 0 (y 0 )) where y 0 = Aa 0 ). We denote by I = supp(a 0 ) and s I = sign(a 0,I ) the support and the sign of a 0 .

It is well known that (P 0 (y 0 )) is the limit of (P λ (y)) for λ → 0 (see [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] for the noiseless case and [START_REF] Grasmair | Necessary and sufficient conditions for linear convergence of 1 -regularization[END_REF] when the observation is y = y 0 + w and the noise w tends to zero as a multiple of λ) at least in terms of the 2 convergence. In terms of the support of the solutions, the study in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF], which extends the one by Fuchs [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF], emphasizes the role of a specific minimal-norm certificate η 0 which governs the behavior of the model at low noise regimes.

Definition 1 (Minimal-norm certificate and extended support). Let a 0 ∈ R G , and let p 0 be the solution to (D 0 (y 0 )) with minimal norm. The minimal-norm certificate of a 0 is defined as

η 0 def. = A * p 0 . The set of indices ext(a 0 ) def. = {1 j G ; |(η 0 ) j | = 1} is called the extended support of a 0 , and the set ext ± (a 0 ) def. = {(j, (η 0 ) j ) ; j ∈ ext(a 0 )} ⊂ 0, G -1 × {-1, 1} is called the extended signed support of a 0 .
Remark 2. In the case where a 0 is a solution to (P 0 (y 0 )) (which is the case here since we assume that a 0 is an identifiable vector for (P 0 (y 0 ))), we have (I, sign(a 0,I )) ⊂ ext ± (a 0 ). The minimal norm certificate thus turns out to be

η 0 = A * p 0 where p 0 = argmin p∈H {||p|| 2 ; ||A * p|| ∞ 1 and A * I p = s I } . ( 19
)
The minimal norm certificate governs the (signed) support of the solution at low noise regimes insofar as the latter is contained in the extended signed support. The following new theorem, which is proved in Appendix C, shows that, in the generic case, both signed supports are equal.

Theorem 1. Let a 0 ∈ R G \ {0} be an identifiable signal , J def.
= ext(a 0 ) such that A J has full rank, and v J def.

= (A *

J A J ) -1 sign(η 0,J ). Assume that the following non-degeneracy condition holds

∀ j ∈ J \ I, v j = 0. ( 20
)
Then, there exists constants C (1) > 0, C (2) > 0 (which depend only on A, J and sign(a 0,J )) such that for 0 < λ C (1) min i∈I |a 0,I | and all w ∈ H with w C (2) λ the solution ãλ of (P λ (y)) is unique, supp(ã λ ) = J and it reads

ãλ,J = a 0,J + A + J w -λ(A * J A J ) -1 sign(η 0,J ),
where

A + J = (A * J A J ) -1 A * J . Remark 3 (
Comparison with the analysis of Fuchs). When J = I, Theorem 1 recovers exactly the result of Fuchs [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. Note that this result has been extended beyond the 1 setting,see in particular [START_REF] Vaiter | Model Selection with Low Complexity Priors[END_REF][START_REF] Vaiter | Model Consistency of Partly Smooth Regularizers[END_REF] for a unified treatment of arbitrary partly smooth convex regularizers. For this result to hold, i.e. to obtain I = J, one needs to impose that the following pre-certificate

η F def. = A * A +, * I s I (21)
is a valid certificate, i.e. one needs that ||η F,I c || ∞ < 1. This condition is often called the irrepresentability condition in the statistics literature (see for instance [START_REF] Zhao | On Model Selection Consistency of Lasso[END_REF]). It implies that the support I is stable for small noise. Unfortunately, it is easy to verify that for the deconvolution problem, in general, this condition does not hold when the grid stepsize is small enough (see [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]Section 5.3]), so that one cannot use the initial result. This motivates our additional study of the extended support ext(a 0 ) ⊃ I, which is always stable to small noise. While this new result is certainly very intuitive, to the best of our knowledge, it is the first time it is stated and proved, with explicit values of the stability constant involved.

Remark 4. Theorem 1 guarantees that the support of the reconstructed signal ãλ at low noise is equal to the extended support. The required condition v j = 0 in Theorem 1 is tight in the sense that if v j = 0 for some j ∈ J \ I, then the saturation point of η λ may be strictly included in J. Indeed, it is possible, using similar calculations as above, to construct w such that supp ãλ J with λ and w 2 /λ arbitrarily small.

Lasso on Thin Grids

In this section, we focus on inverse problems with smooth kernels, such as for instance the deconvolution problem. Our aim is to recover a measure m 0 ∈ M(T) from the observation y 0 = Φm 0 or y = Φm 0 + w, where ϕ ∈ C k (T; H) (k 2), w ∈ H and

∀x ∈ T, Φm def. = T ϕ(x)dm(x), (22)
so that Φ : M(T) → H is a bounded linear operator. Observe that Φ is in fact weak* to weak continuous and its adjoint is compact (see Lemma 1 in Appendix). Typically, we assume that the unknown measure m 0 is sparse, in the sense that it is of the form m 0 = N ν=1 α 0,ν δ x 0,ν for some N ∈ N * , here α 0,ν ∈ R * and the x 0,ν ∈ T are pairwise distinct.

The approach we study in this paper is the (discrete) Basis Pursuit. We look for measures that have support on a certain discrete grid G ⊂ T, and we want to recover the original signal by solving an instance of (P 0 (y 0 )) or (P λ (y)) on that grid. Specifically, we aim at analyzing the behavior of the solutions at low noise regimes (i.e. when the noise w is small and λ well chosen) as the grid gets thinner and thinner. To this end, we take advantage of the characterizations given in Section 2, regardless of the grid, and we use the Beurling Lasso (4) as a limit of the discrete models.

Notations and Preliminaries

For the sake of simplicity we only study uniform grids, i.e.

G def. = {ih ; i ∈ 0, G -1 } where h def. = 1
G is the stepsize. Moreover, we shall consider sequences of grids (G n ) n∈N such that the stepsize vanishes (h n = 1

Gn → 0 as n → +∞) and to ensure monotonicity, we assume that G n ⊂ G n+1 . For instance, the reader may think of a dyadic grid (i.e. h n = h 0 2 n ). We shall identify in an obvious way measures with support in G n (i.e. of the form Gn-1 k=0 a k δ khn ) and vectors a ∈ R Gn . The problem we consider is a particular instance of (P λ (y)) (or (P 0 (y 0 ))) when choosing A as the restriction of Φ to measures with support in the grid G n ,

A def. = Φ Gn = ϕ(0) . . . ϕ((G -1)h n ) . (23)
On the grid G n , we solve min

a∈R Gn 1 2 ||y -Φ Gn a|| 2 + λ||a|| 1 , (P n λ (y))
and min

a∈R Gn ||a|| 1 such that Φ Gn a = y 0 . (P n 0 (y 0 ))
We say that a measure m 0 = N ν=1 α 0,ν δ x 0,ν (with α 0,ν = 0 and the x 0,ν 's pairwise distinct) is identifiable through (P n 0 (y 0 )) if it can be written as m 0 = Gn-1 k=0 a i δ ihn and that the vector a is identifiable using (P n 0 (y 0 )). As before, given a ∈ R Gn , we shall write I(a) def.

= {i ∈ 0, G n -1 ; a i = 0} or simply I when the context is clear.

The optimality conditions [START_REF] Denoyelle | Support Recovery for Sparse Deconvolution of Positive Measures[END_REF] amount to the existence of some p λ ∈ H such that max

0 k Gn-1 |(Φ * p λ )(kh n )| 1, and (Φ * p λ )(Ih n ) = sign(a λ,I ), ( 24
)
λΦ * p λ + Φ * (Φa λ -y) = 0. ( 25
)
Similarly the optimality condition ( 16) is equivalent to the existence of p ∈ H such that max

0 k Gn-1 |(Φ * p)(kh n )| 1 and (Φ * p)(Ih n ) = sign(a 0,I ). ( 26
)
Notice that the dual certificates are naturally given by the sampling of continuous functions η = Φ * p : T → R, and that the notation η(Ih n ) or (Φ * p)(Ih n ) stands for (η(ih n )) i∈I where I = I(a 0 ) (and similarly for η λ = Φ * p λ and I(a λ )). If m 0 is identifiable through (P n 0 (y 0 )), the minimal norm certificate for the problem (P n 0 (y 0 )) (see Section 2) is denoted by η n 0 , whereas the extended support on G n is defined as

ext n m 0 def. = {t ∈ G n ; η n 0 (t) = ±1} . ( 27
)
From Section 2, we know that the extended support is the support of the solutions at low noise.

The Limit Problem: the Beurling Lasso

Problems (P n λ (y)) and (P n 0 (y 0 )) have natural limits when the grid gets thin. Embedding those problems into the space M(T) of Radon measures, the present authors have studied in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] their convergence towards the Beurling-Lasso used 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] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Tang | Near Minimax Line Spectral Estimation[END_REF].

The idea is to recover the measure m 0 using the following variants of (P λ (y)) and (P 0 (y 0 )): = sup

T ψ(x)dm(x) ; ψ ∈ C(T) and ψ ∞ 1 . (28)
Observe that in this framework, the notation ψ ∞ stands for sup t∈T |ψ(t)|. When m is of the form m = N ν=1 α ν x ν where α ν ∈ R * and x ν ∈ T (with the x ν 's pairwise distinct), |m|(T) = N ν=1 |α ν |, so that those problems are natural extensions of (P λ (y)) and (P 0 (y 0 )). This connection is emphasized in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] by embedding (P n λ (y)) and (P n 0 (y 0 )) in the space of Radon measures M(T), using the fact that sup

T ψ(x)dm(x) ; ψ ∈ C(T), ∀k ∈ 0, G n -1 |ψ|(kh n ) 1 = a 1 if m = Gn-1 k=0 a k δ khn , +∞ otherwise.
We say that m 0 is identifiable through (P ∞ 0 (y 0 )) if it is the unique solution of (P ∞ 0 (y 0 )). A striking result of [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF] is that when Φ is the ideal low-pass filter and that the spikes m 0 = N ν=1 α 0,ν x 0,ν are sufficiently far from one another, the measure m 0 is identifiable through P ∞ 0 (y 0 ). The optimality conditions for (P ∞ λ (y)) and (P ∞ 0 (y 0 )) are similar to those of the abstract Lasso (respectively ( 14), ( 15) and ( 16)). The corresponding dual problems are

inf p∈C ∞ y λ -p 2 2 , (D ∞ λ (y)) resp. sup p∈C ∞ y 0 , p , (D ∞ 0 (y 0 ))
where

C ∞ def. = {p ∈ H ; Φ * p ∞ 1} . (29)
The source condition associated with (P ∞ 0 (y 0 )) amounts to the existence of some p ∈ H such that Φ * p ∞ 1 and (Φ * p)(x 0,ν ) = sign(α 0,ν ) for all ν ∈ {1, . . . , N }.

Here, Φ * p ∞ = sup t∈T |(Φ * p)(t)|. Moreover, if such p exists and satisifies |(Φ * p)(t)| < 1 for all t ∈ T \ {x 0,1 , . . . , x 0,N }, and Φ x 0 has full rank, then m 0 is the unique solution to (P ∞ 0 (y 0 )) (i.e. m 0 is identifiable).

Observe that in this infinite dimensional setting, the source condition (30) implies the optimality of m 0 for (P ∞ 0 (y 0 )) but the converse is not true (see [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]). Remark 5. A simple but crucial remark made in [START_REF] Candès | Towards a Mathematical Theory of Super-Resolution[END_REF] is that if m 0 is identifiable through (P ∞ 0 (y 0 )) and that supp m 0 ⊂ G n , then m 0 is identifiable for (P n 0 (y 0 )). Similarly, the source condition for (P ∞ 0 (y 0 )) implies the source condition for (P n 0 (y 0 )). If we are interested in noise robustness, a stronger assumption is the Non Degenerate Source Condition which relies on the notion of minimal norm certificate for (P ∞ 0 (y 0 )). When there is a solution to (D ∞ 0 (y 0 )), the one with minimal norm, p ∞ 0 , determines the minimal norm certificate η ∞

0 def. = Φ * p ∞ 0 .
When m 0 is a solution to (P ∞ 0 (y 0 )), the minimal norm certificate can be characterized as

η ∞ 0 = Φ * p ∞ 0 where ( 31
)
p ∞ 0 = argmin p∈H {||p|| ; ||Φ * p|| ∞ 1, (Φ * p)(x 0,ν ) = sign(α 0,ν ), 1 ν N } . ( 32
)
As with the discrete Lasso problem, a notion of extended (signed) support ext ± ∞ may be defined and the minimal norm certificate governs the behavior of the solutions at low noise (see [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] for more details). Definition 2. Let m 0 = N ν=1 α 0,ν δ x 0,ν an identifiable measure for (P ∞ 0 (y 0 )), and η ∞ 0 ∈ C (T) its minimal norm certificate. We say that m 0 satisfies the Non-Degenerate Source Condition if

• |η ∞ 0 (t)| < 1 for all t ∈ T \ {x 0,1 , . . . x 0,N }, • η ∞ 0 (x 0,ν ) = 0 for all ν ∈ {1, . . . , N }.
The Non Degenerate Source Condition might seem difficult to check in practice. It turns out that it is easy to check numerically by computing the vanishing derivatives precertificate. Definition 3. Let m 0 = N ν=1 α 0,ν δ x 0,ν an identifiable measure for (P ∞ 0 (y 0 )) such that Γ x 0 def.

= Φ x 0 Φ x 0 has full rank. We define the vanishing derivatives precertificate as

η ∞ V def. = Φ * p ∞ V where p ∞ V def. = argmin p∈H {||p|| ; (Φ * p)(x 0,ν ) = sign(α 0,ν ), (Φ * p) (x 0,ν ) = 0, 1 ν N } . ( 33
)
This precertificate can be easily computed by solving a linear system in the least square sense.

Proposition 3 ([20]

). Let m 0 = N ν=1 α 0,ν δ x 0,ν an identifiable measure for the problem (P ∞ 0 (y 0 )) such that Γ x 0 has full rank. Then, the vanishing derivatives precertificate can be computed by

η ∞ V def. = Φ * p ∞ V where p ∞ V def. = Γ +, * x 0 sign(α 0,• ) 0 , (34)
and Γ +, * x 0 = Γ x 0 (Γ * x 0 Γ x 0 ) -1 . Moreover, the following conditions are equivalent: (i) m 0 satisfies the Non Degenerate Source Condition.

(ii) The vanishing derivatives precertificate satisfies:

• |η ∞ V (t)| < 1 for all t ∈ T \ {x 0,1 , . . . x 0,N }, • η ∞ V (x 0,ν ) = 0 for all ν ∈ {1, . . . , N }.

And in that case, η ∞

V is equal to the minimal norm certificate η ∞ 0 . Remark 6. Using the block inversion formula in [START_REF] Vaiter | Model Selection with Low Complexity Priors[END_REF], it is possible to check that

p ∞ V = Φ +, * x 0 sign(α 0,• ) -ΠΦ x 0 (Φ x 0 * ΠΦ x 0 ) -1 Φ x 0 * Φ +, * x 0 sign(α 0,• ), ( 35
)
where Π is the orthogonal projector onto (Im Φ x 0 ) ⊥ . If we denote by p ∞ F the vector introduced by Fuchs (see [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids II: the Continuous Basis Pursuit[END_REF]), which turns out to be

p ∞ F = argmin p∈H {||p|| ; (Φ * p)(x 0,ν ) = sign(α 0,ν ), 1 ν N } , we observe that p ∞ V = p ∞ F -ΠΦ x 0 (Φ x 0 * ΠΦ x 0 ) -1 Φ x 0 * p ∞ F . Remark 7.
At this stage, we see that two different minimal norm certificates appear: the one for the discrete problem (P n 0 (y 0 )) which should satisfy (26) on a discrete grid G n , and the one for gridless problem (P ∞ 0 (y 0 )) which should satisfy [START_REF] Tang | Near Minimax Line Spectral Estimation[END_REF]. One should not mingle them.

The Lasso on Thin Grids for Fixed λ > 0

As hinted by the notation, Problem (P ∞ λ (y)) is the limit of Problem (P n λ (y)) as the stepsize of the grid vanishes (i.e. n → +∞). Indeed, we may identify each vector a ∈ R Gn with the measure m a = Gn-1 k=0 a k δ khn (so that a 1 = |m a |(T)) and embed (P n λ (y)) into the space of Radon measures. With this identification, the Problem (P n λ (y)) Γ-converges towards Problem (P ∞ λ (y)) (see the definition below), and as a result, any accumulation point of the minimizers of (P n λ (y)) is a minimizer of (P ∞ λ (y)). Remark 8. The space M(T) endowed with the weak* topology is a topological vector space which does not satisfy the first axiom of countability (i.e. the existence of a countable base of neighborhoods at each point). However, each solution m n λ of (P n λ (y)) (resp. m ∞ λ of (P ∞ λ (y))) satisfies

λ|m n λ |(T) λ|m n λ |(T) + 1 2 ||Φm n λ -y|| 2 1 2 ||y|| 2 . ( 36
)
Hence we may restrict those problems to the set

X def. = m ∈ M(T) ; λ|m|(T) 1 2 ||y|| 2
which is a metrizable space for the weak* topology. As a result, we shall work with the definition of Γ-convergence in metric spaces, which is more convenient than working with the general definition [13, Definition 4.1]). For more details about Γ-convergence, we refer the reader to the monograph [START_REF] Maso | An Introduction to Γ-convergence[END_REF].

Definition 4. We say that the Problem (P n λ (y)) Γ-converges towards Problem (P ∞ λ (y)) if, for all m ∈ X, the following conditions hold • (Liminf inequality) for any sequence of measures (m n ) n∈N ∈ X N such that supp(m n ) ⊂ G n and that m n weakly* converges towards m,

lim inf n→+∞ λ|m n |(T) + 1 2 ||Φm n -y|| 2 λ|m|(T) + 1 2 ||Φm -y|| 2 .
• (Limsup inequality) there exists a sequence of measures

(m n ) n∈N ∈ X N such that supp(m n ) ⊂ G n , m n weakly* converges towards m and lim sup n→+∞ λ|m n |(T) + 1 2 ||Φm n -y|| 2 λ|m|(T) + 1 2 ||Φm -y|| 2 .
The following proposition shows the Γ-convergence of the discretized problems toward the Beurling Lasso problem. This ensures in particular the convergence of the minimizers, which was already proved in [START_REF] Tang | Sparse recovery over continuous dictionaries-just discretize[END_REF]. Notice that this Γ-convergence can be seen as a consequence of the study in [25], where discrete vectors a are embedded in M(T) using m a = Gn-1 k=0 a k 1 [khn,(k+1)hn) (as opposed to Gn-1 k=0 a k δ khn ). While that other discretization yields the same convergence of the primal problems, it seems less convenient to interpret the convergence of dual certificates, so that we propose a direct proof (using our discretization) in Appendix D.1.

Proposition 4 ([25]

). The Problem (P n λ (y)) Γ-converges towards (P ∞ λ (y)), and

lim n→+∞ inf (P n λ (y)) = inf (P ∞ λ (y)). ( 37
)
Each sequence (m n λ ) n∈N such that m n λ is a minimizer of (P n λ (y)) has accumulation points (for the weak*) topology, and each of these accumulation point is a minimizer of (P ∞ λ (y)). In particular, if the solution m λ to (P ∞ λ (y)) is unique, the minimizers of (P n λ (y)) converge towards m λ .

Here, we propose to describe the convergence of the minimizers of (P n λ (y)) more accurately than the plain weak-* by studying the dual certificates p λ and looking at the support of the solutions m n λ to (P n λ (y)) (see [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]Section 5.4]). One may prove that m n λ is generally composed of at most one pair of Dirac masses in the neighborhood of each Dirac mass of the solution m ∞ λ = N λ ν=1 α λ,ν δ x λ,ν to (P ∞ λ (y)). More precisely, Proposition 5. Let λ > 0, and assume that there exists a solution to (P ∞ λ (y)) which is a sum of a finite number of Dirac masses:

m ∞ λ = N λ ν=1 α λ,ν δ x λ,ν (where α ν = 0). Assume that the corresponding dual certificate η ∞ λ = Φ * p ∞ λ satisfies |η ∞ λ (t)| < 1 for all t ∈ T \ {x 1 , . . . , x N }.
Then any sequence of solution m n λ = Gn-1 i=0 a n λ,i δ ihn to (P n λ (y)) satisfies

lim sup n→+∞ (supp(m n λ )) ⊂ {x 1 , . . . x N }.
If, moreover, m ∞ λ is the unique solution to (P ∞ λ (y)),

lim n→+∞ (supp(m n λ )) = {x 1 , . . . x N }. ( 38
)
If, additionally, (η ∞ λ ) (x ν ) = 0 for some ν ∈ {1, . . . , N }, then for all n large enough, the restriction of m n λ to (x ν -r, x ν + r) (with

0 < r < 1 2 min ν-ν |x λ,ν -x λ,ν |) is a sum of Dirac masses of the form a λ,i δ ihn + a λ,i+ε i,n δ (i+ε i,n )hn with ε i,n ∈ {-1, 1}, a λ,i = 0 and sign(a λ,i ) = sign(α λ,ν ). Moreover, if a λ,i+ε i,n = 0, sign(a λ,i+ε i,n ) = sign(α λ,ν ).
We skip the proof as it is very close to the arguments of [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF]Section 5.4]. Moreover the proof of Proposition TODO in the companion paper [START_REF] Duval | Sparse Spikes Retrieval on Thin Grids II: the Continuous Basis Pursuit[END_REF] for the C-BP is quite similar.

Convergence of the Extended Support

Now, we focus on the study of low noise regimes. The convergence of the extended support for (P n 0 (y 0 )) towards the extended support of (P ∞ 0 (y 0 )) is analyzed by the following proposition.

From now on, we assume that the source condition for (P ∞ 0 (y 0 )) holds, and that supp m 0 ⊂ G n for n large enough (in other words, y 0 = Φ Gn a 0 for some a 0 ∈ R Gn ), so that m 0 = N ν=1 α 0,i δ x 0,ν is a solution of (P n 0 (y 0 )). Moreover we assume that n is large enough so that |x 0,ν -x 0,ν | > 2h n for ν = ν.

Proposition 6 ([20]

). The following result holds:

lim n→+∞ η n 0 = η ∞ 0 , (39)
in the sense of the uniform convergence (which also holds for the first and second derivatives). Moreover, if m 0 satisfies the Non Degenerate Source Condition, for n large enough, there exists

ε n ∈ {-1, 0, +1} N such that ext ± n (m 0 ) = supp ± (m 0 ) ∪ supp ± (m 0 ) + ε n h n , (40)
where supp

± (m 0 ) + ε n h n def. = {(x 0,ν + ε n ν h n , η ∞ 0 (x 0,ν )) ; 1 ν N }.
That result ensures that on thin grids, there is a low noise regime for which the solutions are made of the same spikes as the original measure, plus possibly one immediate neighbor of each spike with the same sign. However, it does not predict which neighbors may appear and where (is it at the left or at the right of the original spike?).

The following new theorem, whose proof can be found in Appendix D.2, refines that result by giving a sufficient condition for the spikes to appear in pairs (i.e. ε ν = ±1 for 1 ν N ). Moreover, it shows that the value of ε n does not depend on n, and it gives the explicit positions of the added spikes ε ν , for 1 ν N . Theorem 2. Assume that the operator Γ x 0 = Φ x 0 Φ x 0 has full rank, and that m 0 satisfies the Non-Degenerate Source Condition. Moreover, assume that all the components of the natural shift

ρ def. = (Φ * x 0 ΠΦ x 0 ) -1 Φ * x 0 Φ +, * x 0 sign(m 0 (x 0 )) (41)
are nonzero, where Π is the orthogonal projector onto (Im Φ x 0 ) ⊥ . Then, for n large enough, the extended signed support of m 0 on G n has the form

ext ± n (m 0 ) = {(x ν , sign(α 0,ν ))} 1 ν N ∪ {(x ν + ε ν h n , sign(α 0,ν )} 1 ν N (42)
where ε = sign (diag(sign(α 0 ))ρ) .

In the above theorem, observe that Φ * x 0 ΠΦ x 0 is indeed invertible since Γ x 0 has full rank.

Corollary 1. Under the hypotheses of Theorem 2, for n large enough, there exists constants

C (1) n > 0, C (2) n > 0 such that for λ C (1)
n min 1 ν N |α 0,ν |, and for all w ∈ H such that w C

n λ, the solution to (P n λ (y)) is unique, and reads m λ = N ν=1 (α λ,ν δ x 0,ν + β λ,ν δ x 0,ν +εhn ), where

α λ β λ = α 0 0 + Φ + extn w -λ(Φ * extn Φ extn ) -1 sign α 0 α 0 , where ext n (m 0 ) = {x ν } 1 ν N ∪ {x ν + ε ν h n } 1 ν N , ε = sign (diag(sign(α 0 ))ρ) , sign(α λ,ν ) = sign(β λ,ν ) = sign(α 0,ν ).

Asymptotics of the Constants

To conclude this section, we examine the decay of the constants C

n , C

(2) n in Corollary 1 as n → +∞. For this we look at the values of c 1 , . . . , c 5 given in the proof of Theorem 1.

By Lemma 3 applied to Φ extn(m

0 ) = Φ x 0 Φ x 0 + h n (Φ x 0 + O(h n )) , we see that c 1,n def. = ||R I Φ + extn(m 0 ) || ∞,2 ∼ 1 h n ||(Φ * x 0 ΠΦ * x 0 ) -1 Φ * x 0 Π|| ∞,2 , (44) c 2,n def.
= ||v

I || ∞ = R I (Φ * extn(m 0 ) Φ extn(m 0 ) ) -1 s I s I ∞ ∼ 1 h n ||ρ|| ∞ , (45) c 3,n def.

= (||R

K Φ + extn(m 0 ) || ∞,2 ) -1 min k∈K |v k | ∼ min k∈K |ρ k | ||(Φ * x 0 ΠΦ * x 0 ) -1 Φ * x 0 Π|| ∞,2 . (46)
However, the expressions of c 4 and c 5 lead to an overly pessimistic bound on the signalto-noise ratio. Indeed the majorization used in (Appendix C.2) is too rough in this framework: it does not distinguish between neighborhoods of x 0,ν 's, where the certificate is close to 1, and the rest of the domain. The following proposition, whose proof can be found in Appendix D.3, gives a more refined asymptotic.

Proposition 7. The constants C

n in Corollary 1 can be chosen as C

n = O(h n ) and C (2) n = O(1) (1)
, and one has

α λ β λ - α 0 0 ∞ = O w h n , λ h n . (47)

Numerical illustrations on Compressed sensing

In this section, we illustrate the "abstract" support analysis of the Lasso problem provided in Section 2, in the context of 1 recovery for compressed sensing. Let us mention that more experiments, illustrating the doubling of the support for sparse spikes recovery on thin grids are described in the companion paper, in a comparison of the Lasso and the C-BP. Compressed sensing corresponds to the recovery of a high dimensional (but hopefully sparse) vector a 0 ∈ R P from low resolution, possibly noisy, randomized observations y = Ba 0 + w ∈ R Q , see for instance [START_REF] Candes | An Introduction to Compressive Sensing[END_REF] for an overview of the literature on this topic. For simplicity, we assume that there is no noise (w = 0) and we consider here the case where B ∈ R Q×P is a realization from the Gaussian matrix ensemble, where the entries are independent and uniformly distributed according to a Gaussian N (0, 1) distribution. This setting is particularly well documented, and it has been shown, assuming that a 0 is s-sparse (meaning that | supp(a 0 )| = s), that there are roughly three regimes: If s < s 0 def.

= Q 2 log(P ) , then a 0 is with "high probability" the unique solution of (P 0 (y 0 )) (it is identifiable), and the support is stable to small noise, because η F (as defined in ( 21)) is a valid certificate, ||η F || ∞ 1. This is shown for instance in [START_REF] Wainwright | Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using 1 -Constrained Quadratic Programming (Lasso)[END_REF][START_REF]Sharp Support Recovery from Noisy Random Measurements by L1 minimization[END_REF].

If s < s 1 def. = Q 2 log(P/Q) ,
then a 0 is with "high probability" the unique solution of (P 0 (y 0 )), but the support is not stable, meaning that η F is not a valid certificate. This phenomena is precisely analyzed in [START_REF] Chandrasekaran | The Convex Geometry of Linear Inverse Problems[END_REF][START_REF] Amelunxen | Living on the edge: A geometric theory of phase transitions in convex optimization[END_REF] using tools from random matrix theory and so-called Gaussian width computations. If s > s 1 , then a 0 with "high probability" is not the solution of (P 0 (y 0 )). We do not want to give details here on the precise meaning of with "high probability", but this can be precisely quantified in term of probability of success (with respect to the random draw of B) and one can show that a phase transition occurs, meaning that for large (P, Q) the transition between these regimes is sharp.

While the regime s < s 0 is easy to understand, a precise analysis of the intermediate regime s 0 < s < s 1 in term of support stability is still lacking. Figure 2 shows how Theorem 1 allows us to compute numerically the size of the recovered support, hence providing a quantification of the degree of "instability" of the support when a small noise w contaminates the observations. The simulation is done with (P, Q) = (400, 100).

The left part of the figure shows, as a function of s (in abscissa), the probability (with respect to a random draw of Φ and a 0 a s-sparse vector) of the event that a 0 is identifiable (plain curve) and of the event that η F is a valid certificate (dashed curve). This clearly highlights the phase transition phenomena between the three different regimes, and one roughly gets that s 0 ≈ 6 and s 1 ≈ 20, which is consistent with the theoretical asymptotic bounds found in the literature.

The right part of the figure, shows, for three different sparsity levels s ∈ {14, 16, 18}, the histogram of the repartition of |J| where J is the extended support, as defined in Theorem 1. According to Theorem 1, this histogram thus shows the repartition of the sizes of the supports of the solutions to (P λ (y)) when the noise w contaminating the observations y = Ba 0 + w is small and λ is chosen in accordance to the noise level. As one could expect, this histogram is more and more concentrated around the minimum possible value s (since we are in the regime s < s 1 so that the support I of size s is included in the extended support J) as s approaches s 0 (for smaller values, the histogram being only concentrated at s since J = I and the support is stable). Analyzing theoretically this numerical observation is an interesting avenue for future work that would help to better understand the performance of compressed sensing.

Conclusion

In this work, we have provided a precise analysis of the properties of the solution path of 1 regularization in the low-noise regime. A particular attention has been paid to the support set of this path, which in general cannot be expected to match the one of the sought after solution. Two striking examples support the relevance of this approach. For imaging problems (when the observations depend smoothly on the spikes locations), we showed theoretically that in general this support is not stable, and we were able to derive in closed form the solution of the "extended support" that is twice larger, but is stable. In the compressed sensing scenario (i.e. when the operator of the inverse problem Figure 2: Left: probability as a function of s of the event that a 0 is identifiable (plain curve) and of the even that its support is stable (dashed curve). Right: for several value of s, display of histogram of repartition of the sizes |J| of the extended support J.

is random), we showed numerically how to leverage our theoretical findings and analyze the growth of the extended support size as the number of measurements diminishes. This analysis opens the doors for many new developments to better understand this extended support, both for deterministic operators (e.g. Radon transform in medical imaging) and random ones.

Proof. By continuity and bilinearity of the inner product, we see that ∀q ∈ H, q, Φ (k) m = T q, ϕ (k) (t) dm(t).

Since t → q, ϕ (k) (t) is in C (T) we obtain the weak-* to weak continuity and the expression of the adjoint operator. Its compactness, namely that {Φ * p; p ∈ H, ||p|| 1} is relatively compact in C (T), follows from the Ascoli-Arzelà theorem. The last assertion is simply that

d k dt k q, ϕ(t) = q, d k dt k ϕ(t)
The compactness mentioned above yields the following property. Given any bounded sequence {p n } n∈N in H, we may extract a subsequence {p n } n ∈N which converges weakly towards some p ∈ H. Then, the (sub)sequence Φ * p n converges towards Φ * p for the (strong) uniform topology, and its derivatives Φ (k), * p n also converge towards Φ (k), * p for that topology.

Appendix B. 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. Lemma 2. Let A : R N → H, B : R N → R N be linear operators such that A has full rank and B is invertible. Then the Moore-Penrose pseudo-inverse of AB is (AB) + = B -1 A + .

Proof. Since AB has full rank, the classical formula of the pseudo-inverse yields

((AB) * (AB)) -1 (AB) * ) = B -1 (A * A) -1 B -1, * B * A * = B -1 A + .
Lemma 3. Let A, B, B h : R N → H be linear operators such that B h = B + O(h) for h → 0 + , and that A B has full rank. Let Π be the orthogonal projector onto (Im A) ⊥ , and let

G h def. = A * A * + hB * h A A + hB h
and s ∈ R N . Then for h > 0 small enough, G h and B * ΠB are invertible, and

G -1 h s s = 1 h (B * ΠB) -1 B * A +, * s -(B * ΠB) -1 B * A +, * s + O(1), (B.1) A A + hB h + = 1 h (B * ΠB) -1 B * Π -(B * ΠB) -1 B * Π + O(1), (B.2) but A A + hB h +, * s s = A +, * s -ΠB(B * ΠB) -1 B * A +, * s + O(h). (B.3) Proof. Observe that A A + hB h = A B h I N I N 0 hI N so that G h = I N 0 I N hI N A * A A * B h B * h A B * h B h I N I N 0 hI N .
Since A B has full rank, the middle matrix is invertible for h small enough, and

G -1 h = I N -1 h I N 0 1 h I N A * A A * B h B * h A B * h B h -1 I N 0 -1 h I N 1 h I N . Writing a b c d def. = A * A A * B h B * h A B * h B h
, the block inversion formula yields

a b c d -1 = a -1 + a -1 bS -1 ca -1 -a -1 bS -1 -S -1 ca -1 S -1 , where S def. = d -ca -1 b = B * h B h -B * h A(A * A) -1 A * B h = B * h ΠB h is indeed invertible for small h since A B has full rank. Moreover, a -1 bS -1 = A + B h (B * h ΠB h ) -1 , and S -1 ca -1 = (B * h ΠB h ) -1 B * h A +, * . Now, we evaluate G -1 h s s = I N -1 h I N 0 1 h I N a -1 s + a -1 bS -1 ca -1 s -S -1 ca -1 s . We obtain G -1 h s s = 1 h S -1 ca -1 s -S -1 ca -1 s + O(1) = 1 h (B * ΠB) -1 B * A +, * s -(B * ΠB) -1 B * A +, * s + O(1).
Eventually, by Lemma 2, A A + hB h

+ = I N -1 h I N 0 1 h I N A * A A * B h B * h A B * h B h -1 A * B * h .
We obtain

A A + hB h + = I N -1 h I N 0 1 h I N A + -A + B h (B * h ΠB h ) -1 B * h Π -(B * h ΠB h ) -1 B * h Π
and we deduce

A A + hB h + = 1 h (B * ΠB) -1 B * Π -(B * ΠB) -1 B * Π + O(1), and A A + hB h +, * s s = A +, * -ΠB h (B h ΠB h ) -1 B * h A +, * ΠB h (B * h ΠB h ) -1 I N 0 -1 h I N 1 h I N s s = A +, * s -ΠB(B * ΠB) -1 B * A +, * s + O(h).

Appendix C.2. Proof of Theorem 1

We define a candidate solution â by âJ = a 0,J + A + J w -λv J , âJ c = 0 (C.3) and we prove that â is the unique solution to (P λ (y 0 + w)) using the optimality conditions ( 14) and [START_REF] Denoyelle | Support Recovery for Sparse Deconvolution of Positive Measures[END_REF]. We first exhibit a condition for sign(â J ) = sign(η 0,J ). To shorten the notation, we write s J def.

= sign(η 0,J ). Since for i ∈ I, a 0,i = 0, the constraint sign(â I ) = s I is implied by Putting everything together, one sees that â is the unique solution of (P λ (y)) if the following affine inequalities hold simultaneously = {i ∈ 0, G n -1 ; a 0,i = 0}. Moreover, for any choice of sign (ε i ) i∈I ∈ {-1, +1} N , we set J def.

||R I A + J || ∞,
= i∈I {i, i + ε i } and s J = (s j ) j∈J where s i def.

= s i+ε i def.

= sign(a 0,i ) for i ∈ I. Since |x 0,ν -x 0,ν | > 2h n for ν = ν, we have Card J = 2 × Card I = 2N .

Recalling that A = ϕ(0) . . . ϕ((G n -1)h n ) , we consider the submatrices

A I def.
= ϕ(ih n ) i∈I = ϕ(x 0,1 ) . . . ϕ(x 0,N ) and A J\I def.

= ϕ((i + ε i )h n ) i∈I so that up to a reordering of the columns A J = A I A J\I . In order to apply Lemma 4, we shall exhibit a choice of (ε i ) i∈I such that A J has full rank, that v def.

= (A * J A J ) -1 s J satisfies sign(v j ) = -s j for j ∈ J \ I and A * J c A J v ∞ < 1 . The following Taylor expansion holds for A J\I as n → ∞: where ρ is defined in (41), where Π is the orthogonal projector onto (Im Φ x 0 ) ⊥ , and for ν ∈ 1, N , i ν refers to the index i ∈ I such that ih n = x 0,ν . Therefore, v J\I has the sign of -diag(ε i 1 , . . . ε i N )ρ, and it is sufficient to choose ε iν = s iν × sign(ρ ν ) to ensure that sign v J\I = -s J\I for n large enough.

A J\I = A 0 + h n (B 0 + O(h n ))
With that choice of ε, it remains to prove that A * J c A J v ∞ < 1. Let us write pn def.

= A J v = A +, * J s I s I . It is equivalent to prove that for k ∈ J c , |Φ * pn (kh n )| < 1.

Using the above Taylor expansion and Lemma 3 in Appendix, we obtain that lim n→+∞ pn = A +, * 0 s I -ΠB 0 (B * 0 ΠB 0 ) -1 B * 0 A +, * 0 s I = Φ +, * x 0 sign(α 0,• ) -ΠΦ x 0 (Φ x 0 * ΠΦ x 0 ) -1 Φ x 0 * Φ +, * x 0 sign(α 0,• ) = p ∞ V (by [START_REF] Wainwright | Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using 1 -Constrained Quadratic Programming (Lasso)[END_REF]).

Hence, Φ * pn and its derivatives converge to those of η ∞ V = η ∞ 0 , and there exists r > 0 such that for all n large enough, for all 1 ν N , Φ * pn is strictly concave (or stricly convex, depending on the sign of η ∞ 0 (x 0,ν )) in (x 0,ν -r, x 0,ν + r). Hence, for t ∈ (x 0,ν -r, x 0,ν + r) \ [x 0,ν , x 0,ν + ε i(ν) (x 0,ν -r, x 0,ν + r) < 1.

As a consequence, for k ∈ J c , |Φ * pn (kh n )| < 1, and from Lemma 4, we obtain that Φ * pn = η n 0 and N ν=1 {x 0,ν , x 0,ν + ε i(ν) h n } is the extended support on G n .

for t ∈ (x 0,ν -r, x 0,ν ] ∪ [x 0,ν + h n , x 0,ν + r).

On the other hand, the inequality -ω(t) -λ(η n 0 (t) + 1) < 0 holds for ||Φ * || ∞,2 ||w|| 2 < 1.9λ. As a result (D.1) holds for all j such that jh n ∈ (x 0,ν -r, x 0,ν +r), provided that the signal-to-noise ratio satisfies

4 Figure 1 :

 41 Figure 1: Sparse spikes deconvolution results obtained by computing the solution a λ of (7). The color reflects the positions of the spikes on the 1-D grid. (a) shows the input measure m 0 and the observation y = y 0 + w. (b) shows how the solution a λ (vertical axis) evolves with λ (horizontal axis). Each curve shows the evolution of λ → (a λ ) i for indexes i ∈ {1, . . . , G -1}. The color encodes the value of i. Plain curves correspond to correct spikes locations i associated to the input measure m 0 . Dashed curves correspond to incorrect spikes (not present in the input measure m 0 ). (c,d) show the results a λ obtained for two different values of λ.

  we denote by I(a), or I when the context is clear, the support of a, i.e. I(a)def.

  |m|(T) such that Φm = y 0 , (P ∞ 0 (y 0 ))where |m|(T) refers to the total variation of the measure m |m|(T)def.

  2 ||w|| + ||v I || ∞ λ < T, where T = min i∈I |a 0,I | > 0,and R I : u → u I is the restriction operator. As for K = J \ I, for all k ∈ K a 0,k = 0 but we know from Lemma 4 that sign(v k ) = -s k . The constraint sign(â K ) = s K is thus implied by||R K A + J || ∞,2 ||w|| λ min k∈K |v k | >0 .Hence, we have sign âJ = sign η 0,J = s J , and by construction supp(â) = J withA * J (y -Aâ) = λs J . (C.4)To ensure that â is the unique solution to (P λ (y)) with y = y 0 + w, it remains to check that||A * J c (y -Aâ)|| ∞ < λ. (C.5) From (C.3) and (C.2), y -Aâ = y 0 + w -Aa 0 -AA + J w -λAv = I H -A J A + J w -λp 0 = P ker(A * J )w -λp 0 , and we see that (C.5) is implied by||A * J c P ker(A * J ) || 2,∞ ||w|| -λ(1 -||η 0,J c || ∞ )< 0 where by construction ||η 0,J c || ∞ < 1.

c 1

 1 ||w|| + c 2 λ < T where c 1 def.= ||RI A + J || ∞,2 , c 2 def. = ||v I || ∞ , (C.6)||w|| c 3 λ where c 3 def.= (||RK A + J || ∞,2 ) -1 min k∈K |v k | > 0, (C.7) c 4 ||w|| -c 5 λ < 0 where c 4 def. = ||A * J c P ker(A * J ) || 2,∞ , c 5 def. = 1 -||η 0,J c || ∞ > 0. (C.8)Hence, for w < min(c 3 , c 5 c 4 )λ and c 1 c 5 c 4 + c 2 λ < T , the first order optimality conditions hold. and we let I def.

  , with A 0 = A I = Φ x 0 and B 0 = ϕ (x 0,1 ) . . . ϕ (x 0,N ) diag ((ε i 1 ), . . .(ε i N )) = Φ x 0 diag ((ε i 1 ), . . . (ε i N )) .By Lemma 3 in Appendix, the Gram matrix A * J A J is invertible for n large enough, and(A * J A J ) -1 s I s I = 1 h n (diag(ε i 1 , . . . , ε i N )) -1 ρ -(diag(ε i 1 , . . . , ε i N )) -1 ρ + O(1),

  h n ], we have |Φ * pn (t)| < 1. Since by compactness max |η ∞ 0 (t)| ; t ∈ T \ N ν=1 (x 0,ν -r, x 0,ν + r) < 1 we also see that for n large enough max |Φ * pn (t)| ; t ∈ T \ N ν=1

||w|| 2 λ

 2 c, where c > 0 is a constant which only depends onmin ν |(η ∞ 0 ) (x 0,ν )|, ||Φ * || ∞,2 , ||(Φ ) * || ∞,2and sup T\ N ν=1 (x 0,ν -r,x 0,ν +r) |η ∞ 0 |. In other words, including the condition involving c 3,n , we may choose C (2) n = min(c 3,n , c) = O(1).

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. Useful properties of the integral transform Lemma 1. Let k 0 ∈ N * and assume that ϕ ∈ C k 0 (T, H). Then Φ (k) : M(T) → H, m → T ϕ (k) (t)dm(t) is weak-* to weak continuous, and its adjoint operator Φ (k), * : H → C (T) is compact and given by (Φ (k), * q)(t) = q, ϕ (k) (t) for all q ∈ H, t ∈ T.

Eventually, d k dt k (Φ * q)(t) = (Φ (k), * q)(t).

Appendix C. Proofs for Section 2

Appendix C.1. Characterization of η 0

It is shown in [START_REF] Duval | Exact Support Recovery for Sparse Spikes Deconvolution[END_REF] that there exists a low noise regime where the (signed) support of any solution ãλ of P λ (y 0 + w) is included in ext ± (a 0 ), supp ± ãλ ⊂ ext ± (a 0 ). It is therefore crucial to understand precisely the behavior of η 0 and the structure of the extended (signed) support ext ± (a 0 ). Before detailing the proof of Theorem 1, we thus detail in the following lemma a (new) result giving a characterization of η 0 .

Then (J, s J ) is the extended signed support of a 0 , i.e. (J, s J ) = ext ± (a 0 ), if and only if the following two conditions hold:

• for all j ∈ J \ I, v j = 0 or s j = -sign(v j ),

In that case, the minimal norm certificate is given by η 0 = A * A +, * J s J .

Proof. Writing the optimality conditions for [START_REF]Sharp Support Recovery from Noisy Random Measurements by L1 minimization[END_REF], we see that p ∈ H is equal to p 0 if and only if A * p ∞ 1, A * I p = sign(a 0,I ), and there exists u + ∈ (R + ) G and u -∈ (R + ) G such that:

where for i ∈ I c , u +,i (resp. u -,i ) is a Lagrange multiplier for the constraint (A * p) i 1 (resp. (A * p) i -1) which satisfies the complementary slackness condition: u +,i ((A * p) i -1) = 0 (resp u -,i ((A * p) i + 1) = 0), and for i ∈ I, (u +,i -u -,i ) is the Lagrange multiplier for the constraint (A * p) i = sign(a 0 ) i . First, let (J, s J ) = ext ± (a 0 ) (so that J determines the set of active constraints) and p = p 0 . Using the complementary slackness condition we may reformulate (C.1) as

for some v ∈ R G , where v j = 0 or sign v j = -(A * p 0 ) j for j ∈ J \ I, and v j = 0 for j ∈ 0, G-1 \J. Inverting this relation, we obtain v J = (A * J A J ) -1 (η 0 ) J , and the stated conditions hold.

Conversely, let (J, s J ) ⊂ 0, G -1 × {-1, 1} (not necessarily equal to ext ± (a 0 )) such that (I, sign((a 0 ) I )) ⊂ (J, s J ) and that the conditions of the lemma hold, with v J = (A * J A J ) -1 s J . Then, setting p = -A J v J , we see that A * p ∞ 1, A * I p = sign(a 0 ) I , and (C.1) holds with the complementary slackness when setting u +,j = 1 2 max(v j , 0), u -,j = 1 2 max(-v j , 0) for j ∈ J and u ±,j = 0 for j / ∈ J. Then p = p 0 and the equivalence is proved. The liminf inequality of Definition 4 is a consequence of the (weak) lower semicontinuity of the total variation and the norm in H (since Φ is weak* to weak continuous, Φ Gn m n -y weakly converges towards Φm -y):

As for the limsup inequality, we approximate m with the measure

where ω ψ : t → sup |x -x| t |ψ(x) -ψ(x )| is the modulus of continuity of ψ. Therefore, lim n→+∞ m n , ψ = m, ψ , and m n weakly* converges towards m. Incidentally, observe that |m n |(T) |m|(T), so that using the liminf inequality we get lim n→+∞ |m n |(T) = |m|(T). Moreover, by similar majorizations,

so that Φm n converges strongly in L 2 (T) towards Φm. As a result lim n→+∞ ||Φm n -y|| 2 = ||Φm -y|| 2 , and the limsup inequality is proved. Eventually, from [START_REF] Zhao | On Model Selection Consistency of Lasso[END_REF] we deduce the compactness of X, hence the existence of accumulation points, and [START_REF] Maso | An Introduction to Γ-convergence[END_REF]Theorem 7.8] implies that accumulation points of (m n λ ) n∈N are minimizers of (P ∞ λ (y)), as well as (37).

Appendix D.2. Proof of Theorem 2

We define a good candidate for η n 0 and using Lemma 4 we prove that it is indeed equal to η n 0 when the grid is thin enough. To comply with the notations of Section 2, we write

The proof of (47) follows from applying (44) and (45) in the expression for α λ and β λ provided by Corollary 1. Let ω def.

= Φ * Πw, where Π is the orthogonal projector onto (Im Φ x 0 ) ⊥ = ker Φ *

x 0 . In order to ensure (C.5) we may ensure that :

for all j ∈ J c (that is (jh n / ∈ ext n (m 0 )). By the Non-Degenerate Source Condition, there exists r > 0 such that for all ν ∈ {1, . . . , N },

and by compactness sup T\ N ν=1 (x 0,ν -r,x 0,ν +r) |η ∞ 0 | < 1. Since η n 0 → η ∞ 0 (with uniform convergence of all the derivatives), for n large enough, ∀ν ∈ {1, . . . , N }, ∀t ∈ (x 0,ν -r, x 0,ν +r), |η n 0 (t)| > 0.9 and

(with equality of the signs) and sup T\ N ν=1 (x 0,ν -r,x 0,ν +r)

First, for j such that jh n ∈ T \ N ν=1 (x 0,ν -r, x 0,ν + r), we see that it is sufficient to assume ||Φ * || ∞,2 ||w|| 2 < (1 -k)λ to obtain (D.1). Now, let ν ∈ {1, . . . , N } and assume that η ∞ 0 (x 0,ν ) = 1 (so that (η ∞ 0 ) (x 0,ν ) < 0) and that ε ν = 1, the other cases being similar. We make the following observation: if a function f : (-r, +r) → R satisfies f (t) C for some C < 0 and f (0 r). Notice that ω = Φ * Πw is a C 2 function which vanishes on ext n (m 0 ) (hence at x 0,ν and x 0,ν + h n ), and that its second derivative is bounded by ||(Φ ) * || ∞,2 ||w||. Moreover, η n 0 (x 0,ν ) = η n 0 (x 0,ν + h n ) = 1 and sup (x 0,ν -r,x 0,ν +r) (η n 0 )

1 2 (η ∞ 0 ) (x 0,ν ) < 0. Thus, for

, we may apply the observation to ω(• -x 0,ν ) + λ(η n 0 (• -x 0,ν ) -1) so as to get