Yann Traonmilin

Jean-François Aujol

The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem

The sparse spike estimation problem consists in estimating a number of off-thegrid impulsive sources from under-determined linear measurements. Information theoretic results ensure that the minimization of a non-convex functional is able to recover the spikes for adequately chosen measurements (deterministic or random). To solve this problem, methods inspired from the case of finite dimensional sparse estimation where a convex program is used have been proposed. Also greedy heuristics have shown nice practical results. However, little is known on the ideal non-convex minimization method. In this article, we study the shape of the global minimum of this non-convex functional: we give an explicit basin of attraction of the global minimum that shows that the non-convex problem becomes easier as the number of measurements grows. This has important consequences for methods involving descent algorithms (such as the greedy heuristic) and it gives insights for potential improvements of such descent methods.

Introduction 1.Context

Sums of sparse off-the-grid spikes can be used to model impulsive sources in signal processing (e.g. in astronomy, microscopy,...). Estimating such signals from a finite number of Fourier measurements is known as the super-resolution problem [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF]. Also, the estimation of spikes from random Fourier measurements is at the core of the compressive K-means algorithm were k-means cluster centers are estimated from a compressed database [START_REF] Keriven | Compressive k-means[END_REF]. In the space M of finite signed measure over R d , we aim at recovering x 0 = i=1,k a i δ t i from the measurements y = Ax 0 + e,

(1) * Contact author : yann.traonmilin@math.u-bordeaux.fr 1 where δ t i is the Dirac measure at position t i , the operator A is a linear observation operator, y ∈ C m are the m noisy measurements and e is a finite energy observation noise. Recent works have shown that it is possible to estimate spikes from a finite number of adequately chosen Fourier measurements as long as their locations are sufficiently separated, using convex minimization based variational methods in the space of measures [START_REF] Candès | Super-resolution from noisy data[END_REF][START_REF] Bhaskar | Atomic norm denoising with applications to line spectral estimation[END_REF][START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Castro | Exact solutions to super resolution on semi-algebraic domains in higher dimensions[END_REF][START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF]. Other general studies on inverse problems have shown that an ideal non-convex method (unfortunately computationally inefficient) can be used to recover these signals as long as the linear measurement operator has a restricted isometry property (RIP) [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. Information Theory[END_REF]. In the case of super-resolution, adequately chosen random compressive measurements have been shown to meet the sufficient RIP conditions for separated spikes, thus guaranteeing the success of the ideal non-convex decoder [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF]. These RIP results are based on an adequate kernel metric on M. It must be noted that, according to the work of [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. Information Theory[END_REF], the success of the convex decoders as described in [START_REF] Candès | Super-resolution from noisy data[END_REF] for regular Fourier sampling implies a (lower) restricted isometry property of A with respect to such a kernel metric (and not with the natural total variation metric: in this case no RIP is possible with finite regular Fourier measurements, see e.g. [START_REF] Boyer | Adapting to unknown noise level in sparse deconvolution[END_REF]). Greedy heuristics have also been proposed to approach the non-convex minimization problem and they have shown good practical utility [START_REF] Keriven | Sketching for Large-Scale Learning of Mixture Models[END_REF][START_REF] Keriven | Compressive k-means[END_REF][START_REF] Traonmilin | Spikes superresolution with random fourier sampling[END_REF].

While giving theoretical recovery guarantees, the convex-based method is nonconvex in the space of parameters (amplitudes and locations) due to a polynomial root finding step. Also, it is difficult to implement in dimensions larger than one in practice [START_REF] Duval | A low-rank approach to off-the-grid sparse deconvolution[END_REF]. Greedy heuristics based on orthogonal matching pursuit are implemented in higher dimension (they can practically be used up to d = 50), but they still miss theoretical recovery guarantees [START_REF] Keriven | Sketching for Large-Scale Learning of Mixture Models[END_REF]. It would be possible to overcome the limitations of such methods if it were possible to perform the ideal non-convex minimization:

x * ∈ argmin x∈Σ Ax -y 2 ( 2
)
where Σ is a low-dimensional set modeling the separation constraints on the k Diracs. Theoretical recovery guarantees for this minimization have been given in [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF]. While simple in its formulation, properties of this minimization procedure have not yet been thoroughly studied.

In this article, as a first important step towards the understanding of the non-convex sparse spike estimation problem (2), we study its formulation in the parameter space (the space of amplitudes and locations of the Diracs). We observe that a smooth nonconvex optimization can be performed.

We place ourselves in a context where the number of measurements, either deterministic or random, guarantees the success of the ideal non-convex decoder with respect to a kernel metric • h , i.e. when we can ensure that:

x * -x 0 h ≤ C e 2 , ( 3
)
where C is an absolute constant with respect to e and x 0 ∈ Σ k,ǫ , the set Σ k,ǫ is the set of sums of k spikes separated by ǫ on a given bounded domain. Qualitatively, the kernel metric can be viewed as a measure of the energy at a given resolution set by a kernel h (see Section 2.3). The bound (3) is guaranteed by a restricted isometry property of A defined using such kernel metric [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF]. This RIP setting is verified in the deterministic (see Section 2.3) and random weighted Fourier measurement contexts [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF]. We link this RIP of measurement operators with the conditioning of the Hessian of the global minimum, and we give an explicit basin of attraction of the global minimum in the parameter space. This study has direct consequences for the theoretical study of greedy approaches. Indeed a basin of attraction permits to give recovery guarantees for the gradient descent (the initialization must fall within the basin), which is a step in the iterations of the greedy approach.

Parametrization of the model set Σ

Let Σ ⊂ M be a model set (union of subspaces) and

x 0 ∈ Σ. Let f (x) = Ax -y 2 . Definition 1.1 (Parametrization of Σ). A parametrization of Σ is a function φ such that Σ ⊂ φ(R d ) = {φ(θ) : θ ∈ R d }. Definition 1.2 (Local minimum). The point θ ∈ R d is a local minimum of g : R d → R if there is ǫ > 0 such that for any θ ′ ∈ R d such that θ -θ ′ 2 ≤ ǫ, we have g(θ) ≤ g(θ ′ ).
In the following, we consider the model of ǫ-separated Diracs with ǫ > 0:

Σ = Σ k,ǫ := {φ(θ) = r=1,k a r δ tr : θ = (a, t 1 , .., t k ) ∈ R k(d+1) , a ∈ R k , t r ∈ R d , ∀r = l, t r -t l 2 > ǫ, t r ∈ B 2 (R)}, (4)
where

B 2 (R) = {t ∈ R d : t 2 ≤ R}. (5)
Note that, in this paper, the Dirac distributions could be supported on any compact set. We use B 2 (R) for the sake of simplicity. For t r ∈ R d , we write t r = (t r,j ) j=1,d .

We consider the following parametrization of Σ k,ǫ :

i=1,k a i δ t i = φ(θ) with θ = (a 1 , .., a k , t 1 , .., t k ). We define Θ k,ǫ := φ -1 (Σ k,ǫ ). (6)
We consider the problem

θ * ∈ arg min θ∈E g(θ) = arg min θ∈E Aφ(θ) -y 2 . ( 7
)
where

E = R k(d+1) or E = Θ k,ǫ and g(θ) = f (φ(θ)).
Note that when E = Θ k,ǫ , performing minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF] allows to recover the minima of the ideal minimization (2), yielding stable recovery guarantees under a RIP assumption. Hence we are particularly interested in this case. When E = R k(d+1) , we speak about unconstrained minimization for minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF].

The objective of this paper is to study the shape of the basin of attraction of the global minimum of ( 7) when E = Θ k,ǫ .

Basin of attraction and descent algorithms

In this work, we are interested in minimizing g defined in [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]. Since g is a smooth function, a classical method to minimize g is to consider a fixed step gradient descent. The algorithm is the following. Consider an initial point θ 0 ∈ R d and a step size τ > 0. We define by recursion the sequence θ n by

θ n+1 = θ n -τ ∇g(θ n ) ( 8
)
Such algorithm is used as a refinement step in the greedy heuristic based on orthogonal matching pursuit [21, Algorithm 1, Step 5] in the practical setting of compressive statistical learning.

We now give the definition of basin of attraction that we will use in this paper.

Definition 1.3 (Basin of attraction). We say that a set Λ ⊂ R d is a basin of attraction of g if there exists θ * ∈ Λ and τ > 0, such that if θ 0 ∈ Λ then the sequence θ n defined by [START_REF] Candès | Super-resolution from noisy data[END_REF] converges to θ * .

This definition of basin of attraction is related to the following classical optimization result (see e.g. [START_REF] Ciarlet | Introduction to numerical linear algebra and optimisation[END_REF]):

Proposition 1.1. Assume g to be a smooth coercive convex function, whose gradient is L Lipschitz. Let θ 0 ∈ R d . Then, if τ < 1
L , there exists θ * ∈ R d such that the sequence θ n defined by [START_REF] Candès | Super-resolution from noisy data[END_REF] converges to θ * .

An immediate consequence of the previous proposition is the following corollary.

Corollary 1.1. Assume g to be a smooth function. Assume that g has a minimizer θ * ∈ R d . Assume that there exists an open set Λ ⊂ R d such that θ * ∈ Λ , g is convex on Λ with L Lipschitz gradient. Assume also that the sequence θ n generated by the descent algorithm remains in Λ. Then, if θ 0 ∈ Λ and τ < 1 L , the sequence θ n defined by (8) converges to θ * . Remark 1.1. Assume that g is in C 2 . Let λ max (t) the largest eigenvalue of the Hessian matrix of g(t). Let Θ ⊂ R d an open set. If there exists L > 0 such that for all t in Θ, λ max (t) ≤ L, then g has a L Lipschitz gradient in Θ.

It is not obvious that the unconstrained gradient descent defined in iterations [START_REF] Candès | Super-resolution from noisy data[END_REF] and the corresponding notion of basin of attraction is suitable to perform constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]. In fact, we show in this paper (essentially through Lemma 3.1) that the global minimum of constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF] has a basin of attraction.

Related work

While original for the sparse spike estimation problem, it must be noted that the study of non-convex optimization schemes for linear inverse problems has gained attraction recently for different kinds of low-dimensional models. For low-rank matrix estimation, a smooth parametrization of the problem is possible and it has been shown that a RIP guarantees the absence of spurious minima [START_REF] Zhao | A nonconvex optimization framework for low rank matrix estimation[END_REF][START_REF] Bhojanapalli | Global optimality of local search for low rank matrix recovery[END_REF]. In [START_REF] Waldspurger | Phase retrieval with random gaussian sensing vectors by alternating projections[END_REF], a model for phase recovery with alternated projections and smart initialization is considered. Conditions on the number of measurements guarantee the success of the technique. In the area of blind deconvolution and bi-convex programming, recent works have exploited similar ideas [START_REF] Ling | Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing[END_REF][START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF].

In the case of super-resolution, the idea of gradient descent has been studied in an asymptotic regime (k → ∞) in [START_REF] Chizat | On the global convergence of gradient descent for overparameterized models using optimal transport[END_REF] with theoretical conditions based on Wasserstein gradient flow for the initialization. In our case, we study the particular super-resolution problem with a fixed number of impulsions and we place ourselves in conditions where stable recovery is guaranteed, leading to explicit conditions on the initialization.

The objective of this article is to investigate to what extent these ideas can be applied to the theoretical study of the case of spike super-resolution estimation.

The question of projected gradient descent raised in the last Section has been explored for general low-dimensional models [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF]. It has been shown that the RIP guarantees the convergence of such algorithms with an ideal (often non practical) projection. Approached projected gradient descents have also been studied and shown to be successful for some particular applications [START_REF] Golbabaee | Inexact gradient projection and fast data driven compressed sensing[END_REF]. The spikes super-resolution problem adds the parametrization step to these problems.

Contributions and organization of the paper

After a precise description of the setting, the definition of the kernel metric of interest and the associated restricted isometry for the spike estimation problem at the beginning of Section 2, this article gives the following original results:

1. A bound on the conditioning of the Hessian at a global minimum of the minimization in the parameter space is given in Section 2. This bound shows that the better RIP constants are (RIP constants improve with respect to the number of measurements), the better the non-convex minimization problem behaves. It also shows that there is a basin of attraction of the global optimum where no separation constraints are needed (for descent algorithms with an initialization close to the minimum, separation constraints can be discarded).

2. An explicit shape of the basin of attraction of global minima is given in Section 3.

The size of the basin of attraction increases when the RIP constant gets better.

To conclude, we discuss the role of the separation constraint in descent algorithms in Section 4, and we explain why enforcing a separation might improve them.

Conditioning of the Hessian

This section is devoted to the study of the Hessian matrix of g. In particular, we provide a bound on the conditioning of the Hessian at a global minimum of the minimization in the parameter space.

Notations

The operator A is a linear operator modeling m measurements in C m ( ImA ⊂ C m ) on the space of measures on R d defined by: for l = 1, m,

(Au) l = R d α l (t) du(t) (9)
where (α l ) l is a collection of functions in C 2 (B 2 (R)) (twice continuously differentiable functions on B 2 (R) defined in ( 5)).

Notice that the integral used in ( 9) is in fact a duality product u, α l between a function in C 2 (B 2 (R)) and a finite signed measure over R d . As the α l are in C 2 (B 2 (R)), we can similarly apply A to distributions of order 1 and 2 with support included in the relative interior of B 2 (R) which we note rintB 2 (R).

While a lot of results for spike super-resolution are expressed on the d-dimensional Torus T d , we prefer the setting of Diracs with bounded support on R d which is often closer to the physics of the considered phenomenom. However, our work is directly extended to the Torus setting by replacing R d by T d and B 2 (R) by T d .

In C m , we consider the Hermitian product x, y = x i ȳi . An example of such measurement operator is the (weighted) Fourier sampling: (Au) l = 1 √ m R d c l e -j ω l ,t du(t) for some chosen frequencies ω l ∈ R d and frequency dependent weights c l ∈ R.

Let x = i=1,k a i δ t i . By linearity of A, we have

(Ax) l = k i=1 (Aδ t i ) l = k i=1 a i α l (t i ). ( 10
)
With g(θ) = f (φ(θ)) = Aφ(θ) -y 2 2 , we get:

g(θ) = m l=1 k i=1 a i α l (t i ) -y l 2 . (11)
In the following, the notion of directional derivative will be important.

Definition 2.1 (Directional derivatives). Let f be a C 1 function, and v ∈ R d such that v 2 = 1.
Then we can define the directional derivative of f in direction v by:

f ′ v (t) := v, ∇f (t) = lim h→0 + f (t + hv) -f (t) h ( 12
)
Let f be a C 2 function, and

(v 1 , v 2 ) ∈ R 2d such that v 1 2 = v 2 2 = 1.
Then we can define the second order directional derivative of f in directions v 1 and v 2 by:

f ′′ v 1 ,v 2 (t) := v 1 , ∇ 2 f (t)v 2 (13) Notice that of course f ′′ v 1 ,v 2 (t) = f ′′ v 2 ,v 1 (t). If v 1 = v 2 , we write f ′′ v 1 (t) := f ′′ v 1 ,v 1 (t)
In particular, they permit to introduce derivatives of Dirac measures supported on R d .

Definition 2.2 (Directional derivatives of Dirac

). Let v ∈ R d such that v 2 = 1. The distribution δ ′ t 0 ,v is defined by δ ′ t 0 ,v , f = -f ′ v (t 0 ). It is the limit of ν η = - δ t 0 +ηv -δt 0 η for η → 0 + in the distributional sense : for all h ∈ C 1 (R d ), R h(t) dν η (t) → η→0 + δ ′ t 0 ,v , h . Similarly, the distribution δ ′′ t 0 ,v is defined by δ ′′ t 0 ,v , f = f ′′ v (t 0 ) for f ∈ C 2 (R d ) and the distribution δ ′′ t 0 ,v 1 ,v 2 is defined by δ ′′ t 0 ,v 1 ,v 2 , f = f ′′ v 1 ,v 2 (t 0 ) for f ∈ C 2 (R d ) where f ′′ v 1 ,v 2 is the derivative of f in direction v 1 chained with the derivative of f in direction v 2 . When v = e i is a vector of the canonical basis of R d , we write δ ′ t 0 ,i = δ ′ t 0 ,e i and δ ′′ t 0 ,i = δ ′′ t 0 ,e i ,e i .
We now have the necessary tools to start the study of the Hessian of g.

Gradient and Hessian of the objective function g

We calculate the gradient and Hessian of g in the two following propositions. We start with the gradient of g.

Proposition 2.1. For any θ ∈ R 2k , we have:

∂g(θ) ∂a r = 2Re Aδ tr , Aφ(θ) -y , (14)
∂g(θ) ∂t r,j = -2a r Re Aδ ′ tr ,j , Aφ(θ) -y . ( 15
)
Proof. See Appendix A.1.

The next proposition gives the values of the Hessian matrix of g which has a simple expression with the use of derivatives of Diracs.

Proposition 2.2. For any θ ∈ R k(d+1) H 1,r,s = ∂ 2 g(θ) ∂a r ∂a s = 2Re Aδ tr , Aδ ts . ( 16
)
H 2,r,j 1 ,s,j 2 = ∂ 2 g(θ) ∂t r,j 1 ∂t s,j 2 = 2a r a s Re Aδ ′ tr ,j 1 , Aδ ′ ts,j 2 + 1(r = s)2a r Re Aδ ′′ tr ,j 1 ,j 2 , Aφ(θ) -y . ( 17
)
H 12,r,s,j = ∂ 2 g(θ) ∂a r ∂t s,j = -2a s Re Aδ tr , Aδ ′ ts,j -1(r = s)2Re Aδ ′ ts ,j , Aφ(θ) -y . ( 18
)
Hence the Hessian can be decomposed as the sum of two matrices

H = G + F with G 1,r,s = 2Re Aδ tr , Aδ ts , G 2,r,j 1 ,s,j 2 = 2a r a s Re Aδ ′ tr ,j 1 , Aδ ′ ts,j 2 , G 12,r,s,j = -2a s Re Aδ tr , Aδ ′ ts,j . (19)
and

F 1,r,s = 0, F 2,r,j 1 ,s,j 2 = 1(r = s)2a r Re Aδ ′′ tr ,j 1 ,j 2 , Aφ(θ) -y , F 12,r,s,j = -1(r = s)2Re Aδ ′ ts,j , Aφ(θ) -y . ( 20
)
Proof. See Appendix A.1.

Kernel, dipoles and the RIP

In order to be able to build an operator A with a RIP, we define a reproducible kernel Hilbert space (RKHS) structure on the space of measures as in [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF], see also [START_REF] Sriperumbudur | Hilbert space embeddings and metrics on probability measures[END_REF]. The natural metric on the space of finite signed measures, the total variation of measures, is not well suited for a RIP analysis of the spikes super-resolution problems, as it does not measure the spacing between Diracs. When using the RIP, fundamental objects appear in the calculations: dipoles of Diracs. In this section we show that the typical RIP implies a RIP on dipoles and their generalization.

Definition 2.3 (Kernel, scalar product and norm). For finite signed measures over R d , the Hilbert structure induced by a kernel h (a smooth function from

R d × R d → R
) is defined by the following scalar product between 2 measures π 1 , π 2

π 1 , π 2 h = R d R d h(t 1 , t 2 ) dπ 1 (t 1 ) dπ 2 (t 2 ). ( 21
)
We can consequently define

π 1 2 h = π 1 , π 1 h . ( 22
)
We have the relation

π 1 + π 2 2 h = π 1 2 h + 2 π 1 , π 2 h + π 2 2 h . ( 23
)
Measuring distances with the help of • h can be viewed as measuring distances at a given resolution set by h. Typically we use Gaussian kernels where the sharper the kernel is, the more accurate it is.

The next definition is taken from [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF]. Compared to [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF], we need to introduce a new definition.

Definition 2.4 ((ǫ-)Dipole, separation). An ǫ-dipole (noted dipole for simplicity) is a measure π = a 1 δ t 1 -a 2 δ t 2 where t 1 -t 2 2 ≤ ǫ. Two dipoles π 1 = a 1 δ t 1 -a 2 δ

Definition 2.5 (Generalized dipole).

A generalized dipole ν is either a dipole or a distribution of order 1 of the form a 1 δ t + a 2 δ ′ t,v . Two generalized dipoles are ǫ-separated if their support are strictly ǫ-separated (with respect to the ℓ 2 -norm on R d ).

In this article we use regular, symmetrical, translation invariant kernels. Most recent developments to non translation invariant kernels [START_REF] Poon | Support localization and the fisher metric for off-the-grid sparse regularization[END_REF] could be considered to generalize this work, but they are out of the scope of this article for the sake of simplicity.

Assumption 2.1. A kernel h follows this assumption if

• h ∈ C 2 (R d , R d ).
• h is symmetrical with respect to 0, translation invariant, i.e. we can write h(t

1 , t 2 ) = ρ( t 1 -t 2 2 ) where ρ ∈ C 2 (R). • h(t, t) = ρ(0) = 1 = max t∈R d ,s∈R d |h(t, s)|, ρ ′ (0) = 0, and ρ ′′ (0) < 0.
• there is a constant

c h such that 0 < c h ≤ ǫ 2 and ρ(t) ≤ 1 -|ρ ′′ (0)| 2 t 2 for t ∈ [0, c h ] (the existence of c h is a consequence of previous assumptions).
• there is a constant µ h such that, for all two ǫ-separated dipoles,

ν 1 , ν 2 h ≤ µ h ν 1 h ν 2 h (mutual coherence).
Note that the assumption that h ∈ C 2 guarantees the existence of integrals with respect to finite signed measures and duality product with distribution of order 1 with bounded supports.

Example The now almost canonical well behaved kernel is the Gaussian kernel. From [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF], for ǫ = 1, using h 0 (t, s) = e -(t-s) 2 /(2σ 2 k ) with σ 2 k = 1 2.4log(2k-1)+24 , we have that h 0 follows Assumption 2.1 with µ h 0 = 3 4(k-1) . The following Lemma and definition extend the scalar product induced by h to generalized dipoles.

Lemma 2.1. Let ν 1 = a 1 δ t 1 + b 1 δ ′ v 1 ,t 1 , ν 2 = a 2 δ t 2 + b 2 δ ′ v 2 ,
t 2 be two generalized dipoles. Then ν 1 and ν 2 are limits (in the distributional sense) of two sequences of dipoles ν η 1 1 and ν η 2 2 for η 1 , η 2 → 0, the quantity ν η 1 1 , ν η 2 2 h converges, the limit is unique (does not depend on the choice of ν η 1 1 and ν η 2 2 ) and

lim η 1 ,η 2 →0 ν η 1 1 , ν η2 2 h =a 1 a 2 f (t 1 -t 2 ) -a 2 b 1 f ′ v 1 (t 1 -t 2 ) -a 1 b 2 f ′ v 2 (t 2 -t 1 ) -b 1 b 2 f ′′ v 1 ,v 2 (t 1 -t 2 ) ( 24
)
where

f (t) = ρ( t 2 ). Proof. See Appendix A.2. Definition 2.6. Let ν 1 = a 1 δ t 1 + b 1 δ ′ v 1 ,t 1 , ν 2 = a 2 δ t 2 + b 2 δ ′ v 2 ,
t 2 be two generalized dipoles. With the previous Lemma, we define

ν 1 , ν 2 h := lim η 1 ,η 2 →0 ν η 1 1 , ν η2 2 h ( 25
)
where ν η 1 1 and ν η 2 2 are two sequences of dipoles that converge to ν 1 and ν 2 (in the distributional sense) for η 1 , η 2 → 0.

We have the following properties that are immediate consequences of Lemma 2.1.

Lemma 2.2. Let h be a kernel meeting Assumption 2.1. We have the following properties for any t ∈ R:

δ t 2 h = ρ(0) = 1 ( 26
)
δ t , δ ′ t,v h = -ρ ′ (0) = 0 (27) δ ′ t,v 2
h = |ρ ′′ (0)| ( 28
)
Proof. See Appendix A.2.

From [19, Lemma 6.5], we have the following Lemma:

Lemma 2.3. Suppose for all two ǫ-separated dipoles, π 1 , π 2 h ≤ µ π 1 h π 2 h (mutual coherence). Then for k, ǫ-separated dipoles π 1 , ...π k such that max i π i h > 0, we have 1 -(k -1)µ ≤ i=1,k π i 2 h i=1,k π i 2 h ≤ 1 + (k -1)µ. ( 29
)
We can generalize the previous result to generalized dipoles.

Lemma 2.4. Let two ǫ-separated generalized dipoles ν 1 , ν 2 . Suppose for all two ǫseparated dipoles π 1 , π 2 , π 1 , π 2 h ≤ µ π 1 h π 2 h (mutual coherence). Then we have:

ν 1 , ν 2 h ≤ µ ν 1 h ν 2 h (30) Proof. See Appendix A.2.
A consequence of the previous result is the following Lemma:

Lemma 2.5. Suppose for all two ǫ-separated generalized dipoles,

ν 1 , ν 2 h ≤ µ ν 1 h ν 2 h (mutual coherence). Then for k ǫ-separated generalized dipoles ν 1 , ...ν k such that max i ν i h > 0, we have 1 -(k -1)µ ≤ i=1,k ν i 2 h i=1,k ν i 2 h ≤ 1 + (k -1)µ. ( 31
)
Proof. See Appendix A.2.

We are now able to define the Restricted Isometry Property (RIP). The secant set of the model set Σ is Σ -Σ := {x -y : x ∈ Σ, y ∈ Σ}.

Definition 2.7 (RIP).

A has the RIP on Σ -Σ with respect to • with constant γ if for all x ∈ Σ -Σ:

(

1 -γ) x 2 ≤ Ax 2 2 ≤ (1 + γ) Ax 2 . ( 32
)
In the following we will suppose that A has RIP γ on Σ k,ǫ -Σ k,ǫ with respect to • h , i.e. for r=1,k a r δ tr -r=1,k b r δ sr ∈ Σ k,ǫ -Σ k,ǫ , we have

(1 -γ) r=1,k (a r δ tr -b r δ sr ) 2 h ≤ A r=1,k (a r δ tr -b r δ sr ) 2 2 (33) ≤ (1 + γ) r=1,k a r δ tr -b r δ sr 2 h .
From [START_REF] Gribonval | Compressive Statistical Learning with Random Feature Moments[END_REF], with a Gaussian kernel h it is possible to build a random A with RIP constant γ. With this choice of A, the ideal minimization (2) yields a stable and robust estimation of x 0 with respect to the • h .

In [START_REF] Candès | Super-resolution from noisy data[END_REF], stable recovery for ǫ-separated Diracs is guaranteed on the Torus with the metric K hi * • L 1 where K hi * is the convolution with a Fejér kernel. From [5, IV.A], this guarantees a lower RIP with respect to this metric. Indeed, the L 1 -norm of trigonometric polynomials (on [0, 1]) is lower bounded by their L 2 -norm, i.e. there is an absolute constant D > 0 depending on K hi such that [26, p. 230]). Applying Lemma A.1 from the Annex on the Fejér kernel shows that there exists a kernel metric • h K that lower bounds K hi * • L 1 for sums of Diracs. This guarantees the existence of a lower RIP with respect to a kernel metric for the conventional deterministic spike super-resolution setting.

K hi * • L 1 ≥ D K hi * • L 2 (see
The RIP on Σ k,ǫ -Σ k,ǫ implies a RIP on ǫ-separated generalized dipoles.

Lemma 2.6 (RIP on generalized dipoles). Suppose A has the RIP on Σ k,ǫ -Σ k,ǫ with constant γ. Let (ν r ) r=1,k , k ǫ-separated dipoles supported in rintB 2 (R), we have

(1 -γ) r=1,k ν r 2 h ≤ A( r=1,k ν r ) 2 2 ≤ (1 + γ) r=1,k ν r 2 h . ( 34
) Proof. See Appendix A.2.
Finally, we will need a last estimate. To state it, we need first to introduce the following definition: Definition 2.8. Let A such that the α l are in C 2 (B 2 (R)). We define

D A,R := sup 1≤l≤m;v∈R d ,w∈R d : v 2 = w 2 =1;t∈B 2 (R) |α ′′ l,v,w (t)|. ( 35
)
The constant D A,R is finite, and it is thus a bound of the directional second derivatives of the α l over B 2 (R).

Lemma 2.7. Let A such that the α l are in C 2 (B 2 (R)). Then, for any t ∈ B 2 (R), with directions v 1 , v 2 , we have

Aδ ′′ t,v 1 ,v 2 2 ≤ √ mD A,R . ( 36
)
where D A,R is defined in Equation (35).

Proof. See Appendix A.2.

Control of the conditioning of the Hessian with the restricted isometry property

We We can control the conditioning of the Hessian matrix κ(H) at a global minimum as the term Aφ(θ) -Aφ(θ * ) 2 vanishes in the control from Theorem 2.1. Particularly, in the noiseless case we have the following Corollary. The lower bound is useful to confirm the dependency on the ratio of amplitudes when it converges to +∞. For this next result, we make the additional assumption that min r |a r | > 0. In practice, this amounts to assuming that when estimating the Diracs, we do not over-estimate their number (which will often be the case, in particular in the presence of noise). When the number of Diracs is overestimated, the minimizers of ( 7) are points that are not isolated, the notion of basin of attraction would have to be generalized to a basin of attraction of a set of minimizers (when a r = 0, g(θ) does not depend on t r ), which is out of the scope of this article for clarity purpose.

sup u 2 =1 u T Hu ≤ 2(1 + γ)(1 + (k -1)µ) max(1, (a 2 r |ρ ′′ (0)|) r=1,l ) + ξ; (37) inf u 2 =1 u T Hu ≥ 2(1 -γ)(1 -(k -1)µ) min(1, (a 2 r |ρ ′′ (0)|) r=1,l ) -ξ ( 38
)
where ξ = 2(d+1) max(max r |a r | √ mD A,R , √ 1 + γ |ρ ′′ (0)|)( Aφ(θ)-Aφ(θ * ) 2 + e 2 ), the constant D A,
Corollary 2.1. Let x 0 = r=1,k a r δ tr ∈ Σ k,ǫ = φ(θ 0 ) and e = 0. Suppose h follows Assumption 2.1. Let H the Hessian of g at θ 0 . Suppose A has RIP γ on Σ k,ǫ -Σ k,ǫ , and that min r |a r | > 0. We have

(1 -γ) max(1, (a 2 r |ρ ′′ (0)|) r=1,l ) (1 + γ) min(1, (a 2 r |ρ ′′ (0)|) r=1,l ) ≤ κ(H) ≤ (1 + γ)(1 + (k -1)µ) max(1, (a 2 r |ρ ′′ (0)|) r=1,l ) (1 -γ)(1 -(k -1)µ) min(1, (a 2 r |ρ ′′ (0)|) r=1,l ) . ( 39
)
Proof. See Appendix A.3.

It is easy to see that for a noise e with small enough energy (i.e. such that ξ is strictly lower than 2(1 -γ)(1 -(k -1)µ) min(1, (a 2 r |ρ ′′ (0)|) r=1,l ), if min r |a r | > 0, then the Hessian at a global minimum is strictly positive. Of course, this may require a very small noise since the ratio of amplitudes at the global minimum can be large.

Remark 2.3. We remark that for a same maximal ratio of amplitudes in θ * , a better conditioning bound is achieved when max r=1,l a 2 r |ρ ′′ (0)| ≥ 1 ≥ min r=1,l a 2 r |ρ ′′ (0)|. We attribute this to the fact that we estimate amplitudes and locations at the same time. The amplitudes must be appropriately scaled to match the variations of g with respect to locations. Intuitively, alternate descent with respect to amplitudes and locations might be better than the classical gradient descent for easily setting the descent step.

Remark 2.4. As g is C 2 , ensuring the strict positivity of the Hessian at the global minimum guarantees the existence of a basin of attraction as emphasized in Section 1.3. In the next Section, we give an explicit formulation of a basin of attraction.

Explicit basin of attraction of the global minimum

Let θ 1 ∈ R d . Can we guarantee, for some notion of distance d, that d(θ 1 , θ * ) ≤ C and θ 1 = θ * , with C an explicit constant, implies ∇g(θ 1 ) = 0 ? The following theorems show that it is in fact the case. With a strong RIP assumption, we can give an explicit basin of attraction of the global minimum for minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF] without separation constraints.

Uniform control of the Hessian

In the noiseless case, a global minimum θ * of the constrained minimization of g over Θ k,ǫ is also a global minimum of the unconstrained minimization because g(θ * ) = 0. In the presence of noise, we can no longer guarantee that the minimizer of the constrained problem θ * is a global minimum of the unconstrained problem. However, the shape of the constraint guarantees that it is a local minimum (see next Lemma). Lemma 3.1. Suppose θ * = (a 1 , .., a k , t 1 , .., t k ) is a result of constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF] with t i ∈ rintB 2 (R). Then θ * is a local minimum of g.

Proof. let θ * = (a 1 , .., a k , t 1 , .., t k ). As for all i = j, t i -t j ∞ > ǫ, there exists η > 0 such that for all θ = (b 1 , .., b k , s 1 , .., s k ) such that s i -t i ∞ < η, we have θ ∈ Θ k,ǫ . Hence, θ * + B ∞ (η) ⊂ Θ k,ǫ , and θ * ∈ arg min θ∈θ * +B∞(η) g(θ).

Hence we can still calculate a basin of attraction of θ * (for the unconstrained minimization). The expression of the basin in the next Section is a direct consequence of the following Theorem that uniformly control the Hessian of g in an explicit neighbourhood of θ * .

Theorem 3.1. Suppose A has RIP γ on Σ k, ǫ 2 -Σ k, ǫ 2
and that h follows Assumption 2.1 and has mutual coherence constant µ on ǫ 2 -separated dipoles. Let θ * = (a 1 , .., a k , t 1 , .., t k ) ∈ Θ k,ǫ be a result of constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]

such that t i ∈ rintB 2 (R). Suppose 0 < |a 1 | ≤ |a 2 |... ≤ |a k |. Let 0 ≤ β ≤ ǫ 4 and Λ θ * ,β := {θ : θ -θ * 2 < β}. ( 40
)
If θ ∈ Λ θ * ,β , then H the Hessian of g at θ has the following bounds :

sup u 2 =1 u T Hu ≤ 2(1 + γ)(1 + (k -1)µ) max(1, (|a k | + β) 2 |ρ ′′ (0)|) + ξ; (41) inf u 2 =1 u T Hu ≥ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 | -β) 2 |ρ ′′ (0)|) -ξ ( 42
)
where ξ = 2(d + 1) max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|)(sup θ∈Λ θ * ,β Aφ(θ) -Aφ(θ * ) 2 + e 2 ), the constant D A,R is given in (35
) and e is the finite energy measurement noise.

Proof. See Appendix A.4.

Remark 3.1. We observe that we require a stronger RIP than the usual one on Σ k,ǫ -Σ k,ǫ to guarantee that unconstrained minimization converges in the basin of attraction Λ θ * ,β .

The set Λ θ * ,β is an open ℓ 2 ball centered on θ * . The choice of this set, besides its simplicity, is useful to guarantee the convergence of the gradient descent. We could garantee the positivity of the Hessian on bigger sets with more complicated formulations. Guaranteeing that iterates of the gradient descent stay in such sets would become much harder then. When the separation constraint is added for the basin of attraction (we look for potential critical points in Σ k,ǫ ), we can provide better bounds. We will discuss what we could expect from constrained descent algorithms in Section 4. Theorem 3.2. Suppose A has RIP γ on Σ k,ǫ -Σ k,ǫ and that h follows Assumption 2.1 and has mutual coherence constant µ on ǫ-separated dipoles. Suppose 0

< |a 1 | ≤ |a 2 |... ≤ |a k |. Let θ * = (a 1 , ..., a k , t 1 , ..t k ) ∈ Θ k,ǫ be a result of constrained minimization (7) such that t i ∈ rintB 2 (R). Let β ≥ 0 and Λ θ * ,β := {θ : θ -θ * 2 < β}. ( 43
)
Then for θ ∈ Θ k,ǫ ∩ Λ θ * ,β , then H the Hessian of g at θ has the following bounds:

sup u 2 =1 u T Hu ≤ 2(1 + γ)(1 + (k -1)µ) max(1, (|a k | + β) 2 |ρ ′′ (0)|) + ξ; (44) inf u 2 =1 u T Hu ≥ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 | -β) 2 |ρ ′′ (0)|) -ξ ( 45
)
where ξ = 2(d + 1) max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|)(sup θ∈Λ θ * ,β Aφ(θ) -Aφ(θ * ) 2 + e 2 ), the constant D A,R is given in (35
) and e is the finite energy measurement noise.

Proof. See Appendix A.4.

Explicit basin of attraction in the noiseless and noisy case

With the help of this uniform control of the Hessian we give an explicit (yet suboptimal) basin of attraction.

Corollary 3.1 (of Theorem 3.1, noiseless case). Under the hypotheses of Theorem 3.1, let θ * ∈ Θ k,ǫ be a result of constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]. Let a * = (a 1 , a 2 ..., a k ). Take

β max := min c h , |a 1 | 2 , C 1 C 2 where C 1 = (1-γ)(1-(k-1)µ) (d+1) √ 1+γ √ 1+(k-1)µ and C 2 = min(1,|a 1 | 2 |ρ ′′ (0)|/4) max(|a k | √ mD A,R , √ 1+γ √ |ρ ′′ (0)|) √ 1+2|ρ ′′ (0)| a * 2 2
Then the set Λ θ * ,βmax is a basin of attraction of θ * .

Proof. See Appendix A.4.

The parameter β controls the distance between a parameter and the optimal parameter. When the RIP constant γ decreases (and generally as the number of measurement increases), the size of the basin of attraction increases. In both the context of regular Fourier sampling and random Fourier sampling, the constant D A,R is bounded when m increases. When the mutual coherence constant µ decreases, the basin of attraction also increases. The size of the basin also decreases as the ratio of amplitudes a 1 a k decreases. We observe again that performing the descent with respect to amplitudes and positions at the same time yields pessimistic bounds for the basin of attraction. Finally, we note that the smaller β is, the smaller is the upper bound on the operator norm of the Hessian.

When the noise contaminating the measurements is small enough, we have similar results with a smaller basin of attraction. Corollary 3.2 (of Theorem 3.1, noisy case). Under the hypotheses of Theorem 3.1, let θ * ∈ Θ k,ǫ be a result of constrained minimization [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]. . Let a * = (a 1 , a 2 ..., a k ). Take

β max := min c h , |a 1 | 2 , C 1 C 3 where C 1 = (1-γ)(1-(k-1)µ) (d+1) √ 1+γ √ 1+(k-1)µ and C 3 = min(1,|a 1 | 2 |ρ ′′ (0)|/4) max(|a k | √ mD A,R , √ 1+γ √ |ρ ′′ (0)|)(1+ √ 1+2|ρ ′′ (0)| a * 2 2 )
Suppose e 2 ≤ √ 1 + γ 1 + (k -1)µβ. Then the set Λ θ * ,βmax is a basin of attraction of θ * .

Proof. See Appendix A.4.

4 Towards new descent algorithms for sparse spike estimation?

We have shown that, given an appropriate measurement operator for separated Diracs, a good initialization is sufficient to guarantee the success of a simple gradient descent. Such gradient descent is used is in the practical setting of compressive statistical learning [START_REF] Keriven | Compressive k-means[END_REF]. Our result on unconstrained minimization explains why the use of such gradient descent is valid in this setting. If we could guarantee additionally that by greedily estimating Diracs, we fall within the basin of attraction, we would have a full nonconvex optimization technique with guarantees of convergence to a global minimum.

In other works [START_REF] Duval | Sparse regularization on thin grids i: the lasso[END_REF][START_REF] Duval | Sparse spikes super-resolution on thin grids ii: the continuous basis pursuit[END_REF], it has been shown that discretization (on grids) of convex methods have a tendency to produce spurious spikes at Dirac locations. Our results seem to indicate that merging spikes that are close to each other when performing a gradient descent might break the barrier between continuous and discrete methods. Theorem 3.2 brings another question as the Hessian of g is more easily controlled in Θ k,ǫ . More generally, can we build a simple descent algorithm that stays in Θ k,ǫ to get larger basins of attraction? Consider the problem for d = 1 in the noiseless case for the sake of clarity. We want to use the following descent algorithm:

θ i+1 = P Θ k,ǫ (θ i -τ ∇g(θ i )) (46)
Where P Θ k,ǫ is a projection onto the separation constraint. Notice that since Θ k,ǫ is not a convex set, we cannot easily define the orthogonal projection onto it (it may not even exists).

If we suppose that the gradient descent step decreases g (i.e. g(θ i -τ ∇g(θ i )) < g(θ i )), is it possible to guarantee that applying projection step keeps decreasing g? Consider:

P Θ k,ǫ (θ) ∈ arg min θ∈Θ k,ǫ Aφ( θ) -y 2 -Aφ(θ) -y 2 | (47)
First consider the following Lemma:

Lemma 4.1. Let d = 1. Let θ 0 , θ 1 ∈ Θ k,ǫ . Let g(θ) = Aφ(θ) -Aφ(θ 0 )
. Then for all α such that 0 = g(θ 0 ) ≤ α ≤ g(θ 1 ), there exists θ * ∈ Θ k,ǫ such that g(θ * ) = α.

Proof. See Appendix A.5.

Lemma 4.1 essentially guarantees that is is possible to continuously map the interval [0, g(θ 1 )] by g with elements of Θ k,ǫ . Hence, at a step i + 1, we have

|g(θ i+1 ) -g(θ i )| = |g(θ i -τ ∇g(θ i )) -g(θ i )|. (48)
The projection P Θ k,ǫ defined by (47) is not easy to calculate (in fact, it is a similar optimization problem as the main problem). Other more "natural" projections on Θ k,ǫ could be defined as :

P Θ k,ǫ (θ) ∈ φ -1 (arg inf x∈Σ k,ǫ Ax -Aφ(θ) 2 ) ( 49
) or P Θ k,ǫ (θ) ∈ φ -1 (arg inf x∈Σ k,ǫ x -φ(θ) h ). ( 50
)
However they suffer from the same calculability drawback. This suggests to build a new family of heuristic algorithms of spike estimation where we propose heuristics to approach the projection of θi+1 on Θ k,ǫ . Recovery guarantees would be obtained by guaranteeing that the projection heuristic does not increase the value of g by too much compared to the gradient descent step.

A Annex

A.1 Proofs for Section 2.2

Proof of Proposition 2.1.

∂g(θ) ∂a r = ∂ ∂a r m l=1 k i=1 a i α l (t i ) -y l 2 = m l=1 2Re   α l (t r,j )   k i=1 a i α l (t i ) -y l     = 2Re Aδ tr , Aφ(θ) -y . (51)
Similarly,

∂g(θ) ∂t r,j = ∂ ∂t r m l=1 k i=1 a i α l (t i ) -y l 2 = m l=1 2Re   a r ∂ j α l (t r )   k i=1 a i α l (t i ) -y l     = -2a r Re Aδ ′ tr ,j , Aφ(θ) -y . ( 52
)
Proof of Proposition 2.2. For H 1,r,s ,

∂ 2 g(θ) ∂a r ∂a s = ∂ ∂a s m l=1 2Re   α l (t r )   k i=1 a i α l (t i ) -y l     = m l=1 2Re α l (t r )α l (t s ) . (53)
For H 2,r,j 1 ,s,j 2 ,

∂ 2 g(θ) ∂t r,j 1 ∂t s,j 2 = ∂ ∂t s,j 1 m l=1 2Re   a r ∂ j 1 α l (t r )   k i=1 a i α l (t i ) -y l     = m l=1 2Re a r ∂ j 1 α l (t r ) a s ∂ j 2 α l (t s ) + 1(r = s) m l=1 2Re   a r ∂ j 2 ∂ j 1 α l (t r )   k i=1 a i α l (t i ) -y l     . (54) For H 12,r,s,j ∂ 2 g(θ) ∂a r ∂t s,j = ∂ ∂t s,j m l=1 2Re(α l (t r ))   k i=1 a i α l (t i ) -y l   = m l=1 2Re α l (t r ) a s ∂ j α l (t s ) + 1(r = s) m l=1 2Re   ∂ j α l (t r )   k i=1 a i α l (t i ) -y l     .
(55)

A.2 Proofs for Section 2.3

Proof of Lemma 2.1. First remark that a generalized dipole ν = aδ t +bδ ′ t,v with v 2 = 1 is the limit in the distributional sense of the dipoles ν η = aδ t -b

δ t+ηv -δt η when η → 0. Now let two generalized dipoles ν 1 = a 1 δ t 1 + b 1 δ ′ t 1 ,v 1 , ν 2 = a 2 δ t 2 + b 2 δ ′ t 2 ,v 2
. The ν i are the limit (in the distributional sense) of a family of dipole ν η i i for η i → 0 + . Let f (t) = ρ( t 2 ). We have

ν η 1 1 , ν η 2 2 h = R d R d f (t -s) dν η 1 1 (t) dν η 2 2 (s). ( 56
)
Remark that by construction g η 1 (s

) := R d f (t -s) dν η 1 1 (t) → η 1 →0 + g(s) := a 1 f (t 1 - s) + b 1 δ ′ t 1 ,v 1 , f (• -s)
< +∞ where g η 1 is in C 2 and g is in C 1 thanks to the assumption on h and ρ. Hence by boundedness of the integrals and the dominated convergence theorem, for any η 2 ,

ν η 1 1 , ν η 2 2 h → η 1 →0 + R d g(s) dν η 2 2 (s). (57)
Moreover, by construction of ν η 2 2 , and symmetry of f (i.e. f (t

1 -t 2 ) = f (t 2 -t 1 )), R d g(s) dν η 2 2 (s) → η 2 →0 + a 1 a 2 f (t 1 -t 2 ) + a 2 b 1 δ ′ t 1 ,v 1 , f (• -t 2 ) + a 1 b 2 δ ′ t 2 ,v 2 , f (t 1 -•) -b 1 b 2 δ ′ t 2 ,v 2 , f ′ v 1 (t 1 -•) = a 1 a 2 f (t 1 -t 2 ) -a 2 b 1 f ′ v 1 (t 1 -t 2 ) -a 1 b 2 f ′ v 2 (t 2 -t 1 ) -b 1 b 2 f ′′ v 1 ,v 2 (t 1 -t 2 ) (58) We define ν 1 , ν 2 h := a 1 a 2 f (t 1 -t 2 )-a 2 b 1 f ′ v 1 (t 1 -t 2 )-a 1 b 2 f ′ v 2 (t 2 -t 1 )-b 1 b 2 f ′′ v 1 ,v 2 (t 1 -t 2 ). We just showed that ν η 1 1 , ν η 2 2 h → η 1 →0 + ,η 2 →0+ ν 1 , ν 2 h . (59)
Note that the value of ν 1 , ν 2 h only depends on ρ, ν 1 , ν 2 .

Proof of Lemma 2.2. Using Lemma 2.1 with

t 1 = t 2 = t, b 1 = b 2 = 0 and a 1 = a 2 = 1 gives δ t 2 h = ρ(0). (60)
Using Lemma 2.1 with

t 1 = t 2 = t, b 1 = a 2 = 0 and a 1 = b 2 = 1 gives δ t , δ ′ t,v h := -f ′ v (0) = -lim η→0 + ρ(η v ) -ρ(0) η = -ρ ′ (0) = 0. ( 61
)
Using Lemma 2.1 with

t 1 = t 2 = t, b 1 = b 2 = 1 and a 1 = a 2 = 0 gives δ ′ t,v 2
h := -f ′′ v (0) = |ρ ′′ (0)|. ( 62
)
Proof of Lemma 2.4. Using the construction from the proof of Lemma 2.1, let two ǫseparated generalized dipole ν 1 , ν 2 . The ν i are the limit (in the distributional sense) of a family of ǫ-separated dipole ν η i i for η i → 0 + . With the hypothesis, we have

ν η 1 1 , ν η 2 2 h ≤ µ ν η 1 1 h ν η 2 2 h . (63) Furthermore, ν η 1 1 , ν η 2 2 h → η 1 →0 + ,η 2 →0+ ν 1 , ν 2 h . ( 64
) Let ν = aδ t + bδ ′ t,v with v 2 = 1 and ν η = aδ t -b δ t+ηv -δt η = a + b η δ t -b δ t+ηv η .We have ν 2 h = a 2 + b 2 |ρ ′′ (0)| (with Lemma 2.2) and ν η 2 h = a + b η 2 + b η 2 -2 a + b η b η ρ(η) = a 2 + 2 b η 2 + 2 ab η -2 ab η ρ(η) -2 b η 2 ρ(η) = a 2 + 2 ab η (1 -ρ(η)) + 2 b 2 η 2 (1 -ρ(η)). ( 65
) But 1-ρ(η) η = ρ(0)-ρ(η) η → -ρ ′ (0) when η → 0 + , and ρ ′ (0) = 0. Moreover, ρ(η) = h(0) + ηρ ′ (0) + η 2 2 ρ ′′ (0) + o(η 2 ) = 1 -η 2 2 |ρ ′′ (0)| + o(η 2 ). Hence 1-ρ(η) η 2 → η→0 + 1 2 |ρ ′′ (0)|. We thus deduce that ν η 2 h → a 2 + b 2 |ρ ′′ (0)| = ν h when η → 0 + . Hence, with such choice of ν η 1 1 ν η 2
2 , we can take the limit η 1 , η 2 → 0 in Equation (63) to get the result.

Proof of Lemma 2.5. Using Lemma 2.4, and the same proof as in Lemma 2.3, we get the result. (1 -γ)

r=1,k ν η r 2 h ≤ A( r=1,k ν η r ) 2 2 ≤ (1 + γ) r=1,k ν η r 2 h . ( 66
) Now remark that g 1 (η) = r=1,k ν η r 2 h and g 2 (η) = A( r=1,k ν η r ) 2 2 are continu- ous functions of η that converge to r=1,k (a r δ tr + b r δ ′ tr,v ) 2 h and A( r=1,k (a r δ tr + b r δ ′ tr,v )) 2
2 when η → 0:

• For g 1 , use the same proof as in Lemma 2.4 with the linearity of the limit.

• For g 2 :

g 2 (η) = l=1,m r=1,k α l (t)(a r dδ tr (t) - b r η (dδ tr +ηv (t) -dδ tr (t))) 2 = l=1,m r=1,k α l (t r )a r - b r η (α l (t r + ηv) -α l (t r )) 2 → η→0 + l=1,m r=1,k α l (t r )a r -b r (α l ) ′ v (t r ) 2 = A( r=1,k a r δ tr + b r δ ′ tr,v ) 2 2
.

(67)

Taking the limit of Equation (66) for η → 0 yields the result.

Proof of Lemma 2.7. We have

Aδ ′′ t,v 1 ,v 2 2 2 = l=1,m |(Aδ ′′ t,v 1 ,v 2 ) l | 2 = l=1,m |α ′′ l,v 1 ,v 2 (t)| 2 ≤ m sup l=1,m;t∈B 2 (R) |α ′′ l,v 1 ,v 2 (t)| 2 ≤ mD 2 A,R (68)
where D A,R is given in (35), i.e. D A,R is the supremum of directional second derivatives of the α l over B 2 (R). We have D A,R < +∞ because the α l are supposed to be in

C 2 (B 2 (R)). Lemma A.1. Let K be a symmetrical convolution kernel in C 2 and h K : (t 1 , t 2 ) → h K (t 1 , t 2 ) = [K * K](t 1 -t 2 ) (the convolution of K by itself ) then for any x ∈ Σ k,ǫ -Σ k,ǫ , we have x 2 h K = K * x 2 L 2 . ( 69
)
Then using Lemma 2.2:

u T Gu ≤ 2(1 + γ)(1 + (k -1)µ) r=1,k |u r | 2 + a 2 r u k+r 2 2 |ρ ′′ (0)| ≤ 2(1 + γ)(1 + (k -1)µ) sup u 2 =1 r=1,k |u r | 2 + u k+r 2 2 a 2 r |ρ ′′ (0)| = 2(1 + γ)(1 + (k -1)µ) max(1, (a 2 r |ρ ′′ (0)|) r=1,l ). ( 83
)
Proof of Theorem 2.1. Let θ * a minimizer of [START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]. Consider H the Hessian of g at θ. We recall that H = G + F (see Proposition 2.2). Using Lemma A.3, we just need to bound the operator norm of F and then to combine it with the bounds on the eigenvalues of G to get bounds on eigenvalues of H = G + F . We use Lemma 2.7, the Cauchy-Schwartz and triangle inequalities. We have Aδ ′′ tr ,j 1 ,j 2 2 ≤ √ mD A,R and

|F 2,r,j 1 ,s,j 2 | ≤ 1(r = s)2|a r | Aδ ′′ tr ,j 1 ,j 2 2 Aφ(θ) -y 2 . ≤ 1(r = s)2|a r | √ mD A,R Aφ(θ) -Aφ(θ * ) + Aφ(θ * ) -y 2 . ≤ 1(r = s)2|a r | √ mD A,R ( Aφ(θ) -Aφ(θ * ) 2 + e 2 ). (84)
Similarly, with Lemma 2.6,

F 12,r,s,j ≤ 1(r = s)2 1 + γ δ ′ tr ,j h Aφ(θ) -y 2 ≤ 1(r = s)2 1 + γ |ρ ′′ (0)|( Aφ(θ) -Aφ(θ * ) 2 + e 2 ). (85)
Let • op be the ℓ 2 operator norm of a matrix. With Gerschgorin circle theorem [START_REF] Golub | Matrix computations[END_REF], we have

F op ≤ max l F l,: 1 (86)
where F l,: is the l-th row of F . We get (91

)
where we wrote θ * = i a i δ t i and θ = i b i δ s i such that |s i -t i | ≤ ǫ/4. We now bound the term i a i δ t i -b i δ s i 2 h :

i a i δ t i -b i δ s i 2 h = i a 2 i + b 2 i -2a i b i ρ( s i -t i 2 ) = i ρ( s i -t i 2 )|a i -b i | 2 + (1 -ρ( s i -t i 2 )) i a 2 i + b 2 i ( 92
)
Using the hypothesis that θ -θ * 2 ≤ β A.5 Proofs for Section 4

Proof of Lemma 4.1. Remark that g(θ) does not depend on the ordering of the positions. Reorder θ 0 = (a, t) and θ 1 = (b, s) such that t 1 < t 2 ... < t k and s 1 < s 2 ... < s k . Consider the function g 1 (λ) = g(θ λ ) with θ λ = (1 -λ)θ 0 + λθ 1 . Remark that g 1 is a continuous function of λ taking values g 1 (0) = g(θ 0 ) and g 1 (1) = g(θ 1 ). Hence, with the intermediate value theorem, there is λ such that g(θ λ ) = g 1 (λ) = α. Moreover, denoting θ λ = (a λ , t λ ), we have, using the sorting of t and s, for 1 ≤ i < k,

|t λ,i+1 -t λ,i | = |(1 -λ)t i+1 + λs i+1 -(1 -λ)t i -λs i | = (1 -λ)|t i+1 -t i | + λ|s i+1 -s i | > (1 -λ)ǫ + λǫ = ǫ. (100)
Hence θ λ ∈ Θ k,ǫ .

Proof of Lemma 2 . 6 .

 26 Let ν r = a r δ tr + b r δ ′ tr ,v the ǫ-separated generalized dipoles. Similarly to Lemma 2.4, take ν η r = (a r + br η )δ tr -b r δ tr +ηv η . For sufficiently small η the ν η r are ǫ-separated dipoles, hence ν η r ∈ Σ -Σ and

F

  op ≤ max(d max r,s,j |F 12,r,s,j |, max r,s,j|F 12,r,s,j | + d max r,j 1 ,s,j 2 |F 2,r,j 1 ,s,j 2 |) ≤ (d + 1) max(max r,s,j |F 12,r,s,j |, max r,j 1 ,s,j 2 |F 2,r,j 1 ,s,j 2 |) ≤ 2(d + 1) max(max r |a r | √ mD A,R , 1 + γ |ρ ′′ (0)|)( Aφ(θ) -Aφ(θ * ) 2 + e 2 ).(87)Hence, using Weyl's perturbation inequalities on H = G + F , i.e. λ min (H) ≥ λ min (G) -λ max (F ) and λ max (H) ≤ λ max (G) + λ max (F ), we get the result.Hence we just need to show thatξ ≤ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 | -β) 2 |ρ ′′ (0)|).Let θ ∈ Λ, we have, with the RIP hypothesis,ξ(θ) := 2(d + 1) max(max r |a r | √ mD A,R , 1 + γ |ρ ′′ (0)|) Aφ(θ) -Aφ(θ * ) 2 ≤2(d + 1) max(|a k | √ mD A,R , 1 + γ |ρ ′′ (0)|) 1 + γ φ(θ) -φ(θ * ) h ≤2(d + 1) max(|a k | √ mD A,R , 1 + γ |ρ ′′ (0)|) 1 + γ 1 + (k -1)µ i a i δ t i -b i δ s i 2 h

2 2 h ≤β 2

 222 and β ≤ |a 1 |/2, we have |b i | ≤ |a i | + β ≤ 3 2 |a i |.With the assumption on h (and ρ),i a i δ t i -b i δ s i a * = (a 1 , ..., a k ). The fact that β ≤ |a 1 |/2 implies ξ(θ) min(1, (|a 1 | -β) 2 |ρ ′′ (0)|) ≤ 2(d + 1) √ 1 + γ 1 + (k -1)µ max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|) 1 + 2|ρ ′′ (0)| a * 2 2 β min(1, |a 1 | 2 |ρ ′′ (0)|/4)(94)Hence using the hypothesis thatβ ≤ (1 -γ)(1 -(k -1)µ) min(1, |a 1 | 2 |ρ ′′ (0)|/4) (d + 1) √ 1 + γ 1 + (k -1)µ max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|) 1 + 2|ρ ′′ (0)| a * 2 2 we have ξ(θ) ≤ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 |(1 -β)) 2 |ρ ′′ (0)|). (95)Proof of Corollary 3.2. Following the same argument as Corollary 3.2, we just need toshow that ξ ≤ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 | -β)) 2 |ρ ′′ (0)|). Let θ ∈ Λ θ * ,β ,we have, with the RIP hypothesis, ξ(θ) := 2(d + 1) max(max r |a r | √ mD A,R , 1 + γ |ρ ′′ (0)|)( Aφ(θ) -Aφ(θ * ) 2 + e 2 ) ≤2(d + 1) max(|a k | √ mD A,R , 1 + γ |ρ ′′ (0)|)( 1 + γ φ(θ) -φ(θ * ) h + e 2 ) ≤2(d + 1) max(|a k | √ mD A,R , 1 + γ |ρ ′′ (0)|)( 1 + γ 1 + (k

2 h

 2 ≤β 2 (1 + 2|ρ ′′ (0)| a * 2 2 ) (97)The fact thatβ ≤ |a 1 |/2 and e 2 ≤ √ 1 + γ 1 + (k -1)µβ implies ξ(θ) min(1, (|a 1 | -β) 2 |ρ ′′ (0)|) ≤ 2(d + 1) √ 1 + γ 1 + (k -1)µ max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|)(1 + 1 + 2|ρ ′′ (0)| a * 2 2 )β min(1, |a 1 | 2 |ρ ′′ (0)|/4)(98)Hence using the hypothesis thatβ ≤ (1 -γ)(1 -(k -1)µ) min(1, |a 1 | 2 |ρ ′′ (0)|/4) (d + 1) √ 1 + γ 1 + (k -1)µ max(|a k | √ mD A,R , √ 1 + γ |ρ ′′ (0)|)(1 + 1 + 2|ρ ′′ (0)| a * 2 2 ) , we have ξ(θ) ≤ 2(1 -γ)(1 -(k -1)µ) min(1, (|a 1 |(1 -β)) 2 |ρ ′′ (0)|).(99)

  t 2 and π 2 = a 3 δ t 3 -a 4 δ t 4 are ǫ-separated if their support are strictly ǫ-separated (with respect to the ℓ 2 -norm on R

d ), i.e. if t 1 -t 3 2 > ǫ, t 2 -t 3 2 > ǫ and t 1 -t 4 2 > ǫ and t 2 -t 4 2 > ǫ.

  can now give a lower (resp. upper) bound for the highest (resp. lowest) eigenvalues of the Hessian matrix H of g (computed in Proposition 2.2). Theorem 2.1 (Control of the Hessian). Let θ = (a 1 , .., a k , t 1 , ..t k ) ∈ Θ k,ǫ with t ∈ rintB 2 (R) and θ

* ∈ Θ k,ǫ a minimizer of

[START_REF] Cambareri | Through the haze: a non-convex approach to blind gain calibration for linear random sensing models[END_REF]

. Suppose h follows Assumption 2.1. Let H the Hessian of g at θ. Suppose A has RIP γ on Σ k,ǫ -Σ k,ǫ . We have

  -1)µ i a i δ t i -b i δ s i = i a i δ t i and θ = i b i δ s i such that |s i -t i | ≤ ǫ/4.Similarly as in Corollary 3.2, we bound the term i a i δ t i -b i δ s i

	2 h + e 2 )
	(96)
	where we wrote θ 2 h :

* i a i δ t i -b i δ s i

Proof of Lemma A.1. Write x = a i δ t i and use the symmetry of K:

A.3 Proofs for Section 2.4

We will use the following Lemma on directional derivatives of Diracs.

Lemma A.2. Let u, t 0 ∈ R d . Suppose u = 0. Then, i=1,d u i δ ′ t 0 ,j = u 2 δ ′ t 0 , u u 2

.

Proof. Let f a function in C 2 (R d ), we have

To prove Theorem 2.1, we control first the eigenvalues of G in the decomposition

where G is defined in Proposition 2.2.

Proof. Let u ∈ R k(d+1) such that u 2 = 1. We index u as follows:

Thus we have

We use the lower RIP in Lemma 2.6,

Then the hypothesis on • h and Lemma 2.5 yields

and

Then using Lemma 2.2:

Similarly, using the upper RIP in Lemma 2.6:

Then the hypothesis on • h yields (Lemma 2.5)

(81) and

Proof of Corollary 2.1. First, observe that at θ 0 , F = 0. The upper bound is a direct consequence of Theorem A.3. We show the result in the case max(1, (a 2 r |ρ ′′ (0)|) r=1,l ) = 1 and min(1, (a 2 r |ρ ′′ (0)|) r=1,l ) = 1 (the proof is similar in the other case). For the lower bound let v ∈ R k(d+1) and i 0 = arg max r=1,l (a 2 r |ρ ′′ (0)|), set v i 0 2 = 1 and v j = 0 for j = i 0 . With Equation (75), we have sup

Similarly, let v ∈ R k(d+1) and i 0 = arg min((

A.4 Proofs for Section 3

First notice that θ -θ * 2 2 ≤ β 2 implies that for any j, we have |a j -b j | 2 ≤ β 2 and

We also have s j -t j 2 < β ≤ ǫ 4 . Hence for i = j we have s i -s j 2 = s i -t i + t i -t j + t j -s j 2 ≥ t i -t j 2 -t i -s i 2 -t j -s j 2 > ǫ -2ǫ/4 = ǫ/2 and φ(θ) ∈ Σ k, ǫ 2 . We use Theorem 2.1 to get the bound on the min and max eigenvalues of the Hessian. We can then plug Inequality (90) into the one of Theorem 2.1. Finally we notice the fact that sup θ∈Λ θ * ,β Aφ(θ) -Aφ(θ * ) 2 exists because Λ θ * ,β is bounded.

Proof of Theorem 3.2. This is a direct consequence of Theorem 2.1. The proof follows the same lines as the one of Theorem 3.

In this case g is convex on Λ. Theorem 3.1 also gives a uniform bound for the operator norm of the Hessian: H op ≤ 2(1+γ)(1+(k -1)µ) max(1, (|a k |+β) 2 |ρ ′′ (0)|)+ ξ and g has Lipschitz gradient. Moreover the gradient descent on Lipschitz smooth convex functions guarantees that θ n -θ * 2 decreases, where θ n are the iterates of the gradient descent (this is proved using direct consequences of the nonexpensiveness of τ ∇g(θ), • [1, Proposition 4.2 (iv)]). Hence the iterates θ n stay in Λ and we deduce from Corollary 1.1 that Λ is a basin of attraction.


S Turgis

N Azemard

D Auvergne

EXPLICIT EVALUATION OF SHORT CIR-CUIT POWER DISSIPATION FOR CMOS LOGIC STRUCTURES

For supply voltage standards such as Vdd > V TN + |V TP | short-circuit power dissipation significantly contributes to the total power dissipation in ICs. We propose a new alternative for the estimation of the short-circuit power dissipation, Psc, in CMOS structures. A first order calculation results in an explicit formulation for Psc, which clearly shows up the design and load parameters. Validations are performed on different configurations of inverters by comparison with HSPICE simulations. Discussions on the relative importance of short-circuit and dynamic power dissipation is given, together with considerations allowing an easy extension to gates.

I -INTRODUCTION

Design for low power implies facilities in exploring tradeoffs between area performance and power. Area and performances of CMOS structures have been the subject of large investigations [START_REF] Fishburnand | TILOS: A posynomial programming approach to transistor sizing[END_REF][START_REF] Sapatnekar | An exact solution to the transistor sizing problem for CMOS circuits using convex optimization[END_REF][START_REF] Chaudary | Anear optimal algorithm for technology mapping minimizing area under delay constraints[END_REF]. Power estimation of CMOS gates is considered in recent papers [START_REF] Chandrasakan | Low power CMOS digital design[END_REF][START_REF] Liu | Trading speed for low power by choice of supply and threshold voltages[END_REF][START_REF] Sp | Estimation of typical power of synchronous CMOS circuits using a hierarchy ofsimulator[END_REF]. Due to the major difficulties in clearly defining the components involved in power estimation of CMOS structures, efforts on low power design address mostly alternatives at logical synthesis level [START_REF] Tsui | Power efficient technology decomposition and mapping under an extended power consumption model[END_REF]. Basically, three components of power have to be considered: -one static component caused by junction leakage currents, which is negligible as long as V DD > V TN + |V TP |, -two components arising during input signal transitions : the dynamic and the short circuit power dissipations. Dynamic power dissipation, Pd, is the power necessary to charge and discharge the output load of the gate. It is given by : Pd = η CL V DD 2 . f

(1) where f is the clock frequency, η the gate activity and CL the output load, constituted of the gates connected to the output and of the parasitic capacitances : CL(i) = Σ j C j IN + Cwire + Cpar(i)

(2) where Cin, Cwire, Cpar respectively represent the gate input capacitance, the parasitic interconnect and diffusion capacitances of each gate (i).

If the dynamic power dissipation is independent of the input signal transition time, it depends upon the design of the logic gate (i) (the sizes of the transistors constituting the gate) through Cpar(i) and the design strategy used for the gates, through the active fanout term, Σ j C j IN . The short circuit power dissipation, Psc, is due to the simultaneous conduction of the P and N blocks, during the time spent by the input signal to vary from VTN to VDD-|VTP| (and vice versa), causing a direct current to flow between the supply rails. This short circuit current has been observed dependent on the input ramp, the load and transistor sizes of the gate. Different formulae [START_REF] Veendrick | Short circuit power dissipation of static CMOS circuitry and its impact on the design of buffer circuits[END_REF][START_REF] Hedenstierna | CMOS circuit speed and buffer optimization[END_REF][START_REF] Al-Khalili | A module generator for optimized CMOS buffers[END_REF] have been derived for Psc evaluation, with different accuracy levels, depending on the approximations used to model the currents and to estimate the input signal dependency. If these formulae can be used in computer programs for short circuit power estimation [START_REF] Vemuru | Short circuit power dissipation for CMOS logic gates[END_REF], they don't allow a direct comparison of dynamic and short circuit components with respect to design parameters. We present here a first order formulation for short circuit power dissipation in CMOS inverters, showing up explicitely design and performance parameters, such as transistor widths, gate input and output rise and fall times, allowing a direct comparison of the power dynamic and short-circuit components. Using a circuit technique proposed by Kang and Yacoub [START_REF] Kang | Accurate simulation of power dissipation in VLSI circuits[END_REF][START_REF] Yacoub | An enhanced technique for simulating short-circuit power dissipation[END_REF], we will first define a simulation reference for average short circuit power dissipation in CMOS inverters and illustrate the Psc dependencies with respect to the design parameters. We will then propose an alternative definition for the short circuit power dissipation, through an equivalent short circuit capacitance, that we will validate with respect to the reference term defined in the preceding part. In the same way that we proposed an explicit formulation for delays [START_REF] Deschacht | Explicit formulation of delays on CMOS data path[END_REF][START_REF] Auvergne | Input waveform slope effects in CMOS delays[END_REF], used to modelize the time variation of the inverter input output voltages, we finally establish a first order evaluation of the short circuit power dissipation, showing clearly up the design and performance parameters. Validations are obtained with respect to the reference terms, for various configurations. Discussion is then given on the extension to gates and the possibility of definition of low power design criteria.

II -SHORT CIRCUIT POWER DISSIPATION SIMU-

LATIONS

We first define a reference for short circuit power dissipation in CMOS gates. We use for that SPICE simulations on the powermeter arrangement shown in figure 1, and proposed by Kang and Yacoub [START_REF] Kang | Accurate simulation of power dissipation in VLSI circuits[END_REF][START_REF] Yacoub | An enhanced technique for simulating short-circuit power dissipation[END_REF].

Cload Vin (t)

P1 P2

Fig. 1 : Circuit with the powermeters of [START_REF] Kang | Accurate simulation of power dissipation in VLSI circuits[END_REF][START_REF] Yacoub | An enhanced technique for simulating short-circuit power dissipation[END_REF] to simulate short-circuit power dissipation in CMOS inverters. Let us consider a gate (i), controlled by a gate (i-1) delivering a periodic waveform of period T, with identical rise and fall times, defined as 2t LH (i-1) and 2t HL (i-1), respectively, as shown in figure 2. We assume that the period of the controlling signal is large enough to allow the output to reach a stable state before T.

ÉÉ

i V DD -V TP C L ÉÉ ÉÉ Cin (i-1) Vin delay T/2 T 2tlh(i-1) 2thl(i-1) V DD Dt SC Dt SC Vout Cin (i) V TP i-1
Fig. 2 : Specifications of the input and output voltages used for power dissipation estimation. Under those conditions the powermeter indications at time T/2 and T reflect the short circuit and dynamic power dissipation in N and P blocks of the gate, as detailed below :

P 1 ( T 2 ) + ( P SC ) HL P 1 (T) + (P SC ) HL ) ( P d ) LH ) ( P SC ) LH (3) P 2 ( T 2 ) + ( P SC ) HL ) ( P d ) LH P 2 (T) + (P SC ) HL ) (P d ) HL ) ( P SC ) LH
Average short circuit power dissipation at T, is then directly obtained from the combination :

P SC (T) + (P SC ) HL ) (P SC ) LH (4 ) + P 1 (T)-P 2 ( T 2 ) ) P 1 ( T 2 ) P SC (T)
We first simulate power dissipation in an inverter with different internal configuration ratio (k=W P /W N ), load and input control conditions. Simulations are performed with HSPICE, the input signal period has been imposed equal to 200ns, much greater than the different switching times involved. The internal set up of the powermeter parameters has been chosen in agreement with the conditions defined in [START_REF] Kang | Accurate simulation of power dissipation in VLSI circuits[END_REF][START_REF] Yacoub | An enhanced technique for simulating short-circuit power dissipation[END_REF]. The resulting short circuit power dependency to the design parameters is illustrated in figures 3-5. Figures 3 and4 give the Psc dependency to the load for different internal configuration ratio and input transition time values, respectively. The N transistor width of stage (i) has been used as a reference (C N(i) =5fF for all investigations). Figure 5 enlightens the Psc dependency to the input transition time for constant load. In order to clarify the comparisons we specify the different transition times involved by the different loads and control signals, as ratio of the circuit capacitances such as :

C L /C IN(i) = ratio between the output load of inverter (i) and its input capacitance, represents the fanout factor of the (i) th stage and determines the output transition time.

C IN(i )/C IN(i-1)

= ratio between the input capacitance of (i) th and (i-1) th stages, represents the fanout factor of the (i-1) th stage and determines the input transition time on the (i) th stage. These capacitance ratios have been recognized significative and are widely used to represent trends of switching times [START_REF] Chandrasakan | Low power CMOS digital design[END_REF][START_REF] Deschacht | Explicit formulation of delays on CMOS data path[END_REF]. Cl/Cin (i)

Cin (i) / Cin (i-1) =3 k=1 k=2
Psc(mW) Cl/Cin (i)

Fig3 : Short-circuit power dependency to the load for different internal configuration ratio values and a constant input voltage ramp defined by Cin

(i) /Cin (i-1) = 3 (2thl i-1 = 2tlh i-1 =0.4ns).
Cin (i) / Cin (i-1) =3 k=1
Psc(mW)

Cin (i) / Cin (i-1) =2
Cin (i) / Cin (i-1) =0.75

Fig. 4 :

Short-circuit power dependency to the load for different input voltage ramps ranging from 0.1 to 0.4ns (Cin (i )/Cin (i-1) =0.75-3, respectively), the internal configuration ratio is chosen equal to the value corresponding to the lowest power dissipation.

0 1 0 1 2 3 Cl/Cin (i) =1 Cin (i) / Cin (i-1) k=1 Psc(mW) Cl/Cin (i) =5
Cl/Cin (i) =12

Fig. 5 : Illustration of the short-circuit power dependency to the input transition time for constant load. We observe that Psc dissipation decreases when the load increases, and Psc increases with the internal configuration ratio value increase ie with the strength of the transistors in short circuit (fig. 3) as expected. Psc also increases with the input transition time increase ie when the ratio 4). This trend is enlightened in figure 5 where we plot for constant load the Psc variation with the duration of the input ramp. These variations, initially observed by Veendricks [START_REF] Veendrick | Short circuit power dissipation of static CMOS circuitry and its impact on the design of buffer circuits[END_REF], are illustrated here with respect to the design parameters and represent the trends to be reproduced by any short circuit power dissipation modelization. This is what we will try to get in the next part. To conclude this part, figure 6 represents for different transition times the load dependency of the ratio Psc / Pd ( with η=1 ). This illustrates the relative influence of the short circuit component, which, for specific design conditions, is far to be negligible. 0 0,060 0,120 0,180 0,240 0,300 0,360 0,420 0,480 0,540 0,600

C IN(i) /C IN ( i-1) increases (fig.
1 2 4 6 8 12
Cl/Cin (i) k=1

Psc(mW)

Cin (i) /Cin (i-1) = 3
Cin (i) /Cin (i-1) = 2 Cin (i) /Cin (i-1) = 0.75 Fig. 6 : Illustration of the ratio (Psc/Pd) dependency to the load for different input transition times .

III -EQUIVALENT MODEL FOR AVERAGE SHORT CIRCUIT POWER EVALUATION

As shown in the preceding part, the ratio Psc / Pd can give indications on available design trade offs for low power. For a given operating frequency and power supply, the dynamic power depends on the total load capacitance involved. This capacitive load, constituted of the layout parasitic and almost of the gate input capacitances, is a direct consequence of the synthesis and design choices : it completely controls the speed performance of the design.

In order to easily compare Psc and Pd we propose here an alternative to modelize short circuit power dissipation through an equivalent short circuit capacitance. Physically the short circuit power dissipation is produced by the current flowing from V DD to ground, through P and N blocks, during the time spent by the input voltage to vary from V TN to V DD -|V TP |. Let us call ∆tsc this time interval. We can equivalently consider this current conduction process as a charge transfer: ∆Q1 = I LH . ∆tsc for the input rising edge (I LH = I P ),(5) ∆Q2 = I HL . ∆tsc for the input falling edge (I HL =I N ),

where I LH and I HL represent the average short circuit currents evaluated in N and P transistors respectively. Let us define ∆Q = ∆Q1 +∆Q2 the total charge transfer during a period of the input signal. An expression for an equivalent short circuit capacitance can then be obtained from:

C SC = ∆Q / ∆V (6)
where ∆V = V DD -V TN -|V TP | represents the input voltage swing during ∆tsc. Note that C SC has no physical meaning, and is just an equivalent way to represent the charge transfer. An interesting expression is then obtained in writing short circuit power dissipation in the same way than the dynamic one, using the C SC parameter. This results in : 2 . f (7) where the different coefficients have been defined in the introduction.

P SC = η C SC V DD
To validate this result, we replace the powermeters of figure 1 by amperemeters and simulate the short circuit current for the different conditions examined in the preceding part. From these simulated values of currents it is then easy to calculate CSC and PSC from equ. 6 and 7.

: Comparison between the short-circuit power values calculated from the simulated values of the average currents (Psc cal ) and the simulated values of the short-circuit power (Psc sim ).

In figure 7 we compare the values of the short circuit power calculated (equ. 7) from the simulations of average currents, to the values obtained in the preceding part from the simulations through the powermeters. The good agreement obtained confirms the validity of the preceding approach in defining equivalent short circuit capacitance. The next step consists now in calculating the values of C SC . It is for that just necessary to calculate the average value of the short circuit current crossing N and P transistors (for input falling and rising edges respectively). Let us give here some details about this calculation, we choose the input rising edge as an example. We calculate <I P (t)> = I LH as follows :

I LH+ 1 D SC ȧ ȡ Ȣ ŕ t l t (V IN +V TN ) I Plin (t)dt ) ŕ t (V IN +V DD *|V TP |) t l I Psat (t)dt ȧ ȣ Ȥ (8)
where the summations are bounded by the significative times of the short circuit operating mode. Taking for convenience the origin of times at the beginning of the short circuit (t for V IN = V TN ), equation ( 8) leads to :

I LH+ 1 D SC ȧ ȡ Ȣ ŕ t lȀ t 0 I Plin ( t ) dt ) ŕ t END t lȀ I Psat ( t ) dt ȧ ȣ Ȥ (9)
To solve this equation, input/output waveforms and current laws must be considered.

In order to get practical expressions we consider, as shown in figure 2, linear input/output waveforms with slopes defined by the loading factors, as discussed in part II, such as:

V IN + V TN ) V DD 2 t LH(i*1)
. t

V OUT + V DD ǒ 1 * t 2 t HL(i) Ǔ (
t lȀ + 2 (1 * b) t LH(i*1) 1 ) t LH(i*1) t HL(i) t END + D t SC + 2 (1 * b) . t LH(i*1) (12) with b = ( |V TP | + V TN ) / V DD .
For the current expressions we use the standard Shichman and Hodges model, which appears to be sufficient for average calculations, short channel effects being later introduced through calibration coefficients on the effective mobility length ratio as discussed in [START_REF] Coll | Process characterisation with dynamic test structures[END_REF]. After some tedious but not complicated calculations, equ. 9 gives : [START_REF] Yacoub | An enhanced technique for simulating short-circuit power dissipation[END_REF] and an equivalent form for the average short circuit current calculated during the input falling transition is given in 14 :

t I p (t) u + b P 6 V DD 2 (1 * b) 2 t LH(i*1) t LH(i*1) ) t HL(i)
t I N (t) u + b N 6 V DD 2 (1 * b) 2
t HL(i*1) t HL(i*1) ) t LH(i) [START_REF] Deschacht | Explicit formulation of delays on CMOS data path[END_REF] where β N and β P are the usual conductance factors ( β N,P = µ Cox ( W / L ) N,P ) Using these equations it is then easy to evaluate from equ.5-7 the short circuit power as :

P SC + hf V DD 4 (1 * b) 2 6 ǒ a Ȁ 1 b P t LH(i*1) t LH(i*1) ) t HL(i) ) a ȀȀ 1 b N t HL(i*1) t HL(i*1) ) t LH(i) Ǔ
where the b value is limited to the range b < 1. As shown in [START_REF] Deschacht | Explicit formulation of delays on CMOS data path[END_REF] the slope factors between brackets can be expressed as a function of design and loading parameters such as :

t HL(i) t LH(i*1) + a Ȁ 2 C L C N(i) m N m P (1)k) i k (i*1) W N( W N(i* (16) t LH(i) t HL(i*1) + a ȀȀ 2 m N m P C L k i C N(i) (1)k) i W N(i) W N(i*1) ( 17
)
where k is the internal configuration ratio, C L the output load of the cell under consideration and W N(i) /W N(i-1) characterizes the input slope.

As given in equations 15 and 16, the short circuit power dependence on design parameters appears explicitly and the trends obtained correspond to the simulated one derived in part II :

-no P SC for b greater than 1 ie for V DD < V TN + |V TP |, -for constant input transition time ( t HL , LH(i-1) = Ct ), P SC decreases when the load increases ( t HL , LH(i) ie C L increases), P SC increases with the increase of configuration ratio values ( k, β N ,β P ), and with the input transition time increase ( t HL , LH(i-1) or W N(i) / W N(i-1) ). This partly confirms the interest of this approach. Comparison of the values of the short-circuit power dissipation calculated (eq. [START_REF] Auvergne | Input waveform slope effects in CMOS delays[END_REF] to the values obtained from simulations, the input voltage ramp is 0.3ns and the internal configuration ratio = 2. Figures 8 &9 give a more complete validation in comparing for different internal configuration ratios the values of the short-circuit power dissipation calculated from eq.15 to the values of the short-circuit power dissipation obtained in part II. Let us remind here that simulations have been performed with a 1.2mm process. In order to correct the approximation level used to obtain the explicit expression for Psc, we use calibration coefficients on :

b P , b N ( a1 ), to take into account the short channel effects in the definition of effective mobilities and transistor length, -tlh(i) & thl(i) (a2), to take into account the input slope effects [START_REF] Auvergne | Input waveform slope effects in CMOS delays[END_REF]. Results shown on fig. 8 & 9 have been obtained with : a1=1.4, a2 = 0.09 for the P transistor, and a1 = 0.5, a2 = 0.07 for the N transistor, these values being directly derived from calibration on small and large load configurations.

Despite the low approximation level used here, the agree-ment between calculated and simulated Psc values is quite good and justifies the effort made to get explicit expression.

IV -DISCUSSION AND CONCLUSION

In designing structures for low power applications, one of the main relevant features is the evaluation of the relative short-circuit and dynamic power dissipation contribution versus design and synthesis choices. This point is illustrated on fig. 10 and11, where we plot the ratio Psc / Pd dependency to the load for both calculated and simulated Psc values with respect to the cases shown on fig. 8 &9. Load dependency of the relative importance of the short-circuit power dissipation with respect to the dynamic one; calculated (Psccal) and simulated (Pscsim) values are compared for an input voltage ramp=0.3ns and an internal configuration value of 2. For relatively fast input transition ( ie : k=1, Cin (i) /Cin (i-1) =3 represents medium load conditions for real cases ) the short-circuit component is quite important if we consider load conditions such as Cl / Cin (i) < 3 which corresponds to a usual physical design fanout factor for speed. Note here that we just considered configurations of invert-ers. Extension to gates is straightforward : we only need to modify the short-circuit current expression. Since it corresponds to a "static" current, gates can be reduced to equivalent inverters that are easely defined by width of transistors ( N or P ) equal to the average width of the transistors ( N or P ) (or to the sum of the parallel transistor W for the critical cases) and length equal to the length of the transistors belonging to the parallel array or equal to the sum of the length for transistors belonging to the serial array. Under those conditions the resulting equivalent inverter for a given gate will be defined with different internal configuration ratio : k<1 for Nor gates and k>1 for Nand gates. However, short channel effects will be more difficult to approximate especially in serial arrays of transistors and this part will be later extensively investigated. An interesting application will then be to evaluate alternatives in logical decomposition for speed trading serial transistors with logical depth. As a summary we have proposed a new approach to calculate the short-circuit power dissipation in CMOS structures.We first defined a virtual short-circuit capacitance as an indicator of short-circuit power dissipation in CMOS inverters which appeared to be an efficient way of comparing short-circuit and dynamic power dissipation in terms of design parameters.Validations of this concept have been obtained through a standard measurement circuit technique for low power. And finally, using the concept of the equivalent short-circuit capacitance, and low level models for currents and variations of input/output voltages, calculations have been successful in obtaining an explicit formulation for the short-circuit power dissipation showing up clearly design, technology, load and control parameters. We validate this expression for inverters in different situations by comparing calculated values of Psc to simulated ones. The quality of the results reinforce us in further investigations to gates and complex decomposition.

  Fig.7 :Comparison between the short-circuit power values calculated from the simulated values of the average currents (Psc cal ) and the simulated values of the short-circuit power (Psc sim ). In figure7we compare the values of the short circuit power calculated (equ. 7) from the simulations of average currents, to the values obtained in the preceding part from the simulations through the powermeters. The good agreement

Fig. 8 :

 8 Fig.8: Comparison of the values of the short-circuit power dissipation calculated ( Psccal eq.[START_REF] Auvergne | Input waveform slope effects in CMOS delays[END_REF], to the values obtained from simulations (Pscsim), the input voltage ramp is 0.4ns and the internal configuration ratio=1.

Fig. 10 :

 10 Fig.10 :Load dependency of the relative importance of the short-circuit power dissipation with respect to the dynamic one; calculated (Psccal) and simulated (Pscsim) values are compared for an input voltage ramp=0.4ns and an internal configuration value of 1.