Sandrine Dallaporta

Yohann De Castro
email: yohann.decastro@math.u-psud.fr

SPARSE RECOVERY FROM EXTREME EIGENVALUES DEVIATION INEQUALITIES

Keywords: November 5, 2018. 2010 Mathematics Subject Classification. 60F10, 62J05, 62J07, 15A18, 15A42, 65F15 Restricted Isometry Property, Gaussian Matrices, Rademacher Matrices, Deviations Inequalities, Sparse Regression

This article provides a new toolbox to derive sparse recovery guarantees-that is referred to as "stable and robust sparse regression" (SRSR)-from deviations on extreme singular values or extreme eigenvalues obtained in Random Matrix Theory. This work is based on Restricted Isometry Constants (RICs) which are a pivotal notion in Compressed Sensing and High-Dimensional Statistics as these constants finely assess how a linear operator is conditioned on the set of sparse vectors and hence how it performs in SRSR. While it is an open problem to construct deterministic matrices with apposite RICs, one can prove that such matrices exist using random matrices models. In this paper, we show upper bounds on RICs for Gaussian and Rademacher matrices using state-of-the-art deviation estimates on their extreme eigenvalues. This allows us to derive a lower bound on the probability of getting SRSR. One benefit of this paper is a direct and explicit derivation of upper bounds on RICs and lower bounds on SRSR from deviations on the extreme eigenvalues given by Random Matrix theory.

Introduction

Stable and Robust Sparse Recovery (SRSR). The recent breakthrough of Compressed

Sensing [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF][START_REF] Candès | Decoding by linear programming[END_REF][START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF] has shown that one can acquire and compress simultaneously a signal from few linear measurements. This methodology has an important impact in practice since it may be deployed in applied contexts where the time of acquisition is limited-e.g. medical imaging (MRI and functional MRI)-and/or costly-e.g. reflection seismology, one may consult [START_REF] Chafaï | Interaction between Compressed Sensing, Random matrices and High dimensional geometry[END_REF][START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF] and references therein.

More precisely, the problem addressed in recent researches aims at solving under-determined systems of linear equations (with an additive error term e) of the form (1.1)

y = Mx 0 + e
where M is a known (n × p) matrix, x 0 an unknown vector in R p , y and e are vectors in R n and n is (much) smaller than p. This frame fits many interests across various fields of research, e.g. in statistics one would estimate p parameters x 0 from a sample y of size n, M being the design matrix and e some random centered noise. Although the matrix M is not injective, recent advances have shown that one can recover an interesting estimate x of x 0 considering 1 -minimization solutions as

(1.2) x ∈ arg min x 1 s.t. y -Mx 2 ≤ η ,
where η > 0 is a tuning parameter such that the experimenter believes it holds e 2 ≤ η with high probability.

A standard goal is to prove that the estimate x is close to x 0 or more precisely that the norm of the error x -x 0 is small. To this purpose, one says that x satisfies the Stable and Robust Sparse Recovery (SRSR, see [27, page 88]) if the following two error bounds hold

x 0 -x 1 ≤ Cσ s (x 0 ) 1 + D √ sη ( 1 -SRSR) x 0 -x 2 ≤ C √ s σ s (x 0 ) 1 + Dη ( 2 -SRSR)
where C, D > 0 are constants and σ s (x 0 ) 1 denotes the approximation error in 1 -norm by s coefficients, namely σ s (x 0 ) 1 := min x 0 -x 1 , where the minimum is taken over the space Σ s of sparse vectors x, i.e. the set of vectors with at most s nonzero coordinates. SRSR shows that the estimate x recovers the s largest coefficients of the target vector x 0 in a stable 1 and robust (to additive errors e) manner. One can prove that the √ s terms are optimal in the sense of Approximation Theory, one may consult [27, Remark 4.2.3 page 88] for further details. Sufficient condition for SRSR holds whenever the matrix X satisfies some properties, see for instance [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candès | Near-optimal signal recovery from random projections: universal encoding strategies?[END_REF][START_REF] Foucart | Sparsest solutions of underdetermined linear systems via lq-minimization for 0<q<=1[END_REF][START_REF] Bickel | Simultaneous analysis of lasso and Dantzig selector[END_REF][START_REF] Van De Geer | On the conditions used to prove oracle results for the lasso[END_REF][START_REF] Bertin | Adaptive dantzig density estimation[END_REF][START_REF] Juditsky | Accuracy guarantees for l1-recovery[END_REF][START_REF] Castro | A remark on the lasso and the dantzig selector[END_REF] or [START_REF] Chafaï | Interaction between Compressed Sensing, Random matrices and High dimensional geometry[END_REF][START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF].

1.2. Main Result: a Toolbox to get SRSR from Deviation Inequalities. In this paper, we want to guarantee SRSR when the matrix M is chosen at random and x is produced by an 1minimization estimate such as (1.2).

The first random model we assume for M is as follows. Let R be a subset of {1, . . . , p} of size r and denote M R the (n × r) matrix obtained by keeping the columns of M that belongs to R and M R its hermitian adjoint. Assume that all the Gram matrices M R M R satisfies (1.3) ∀r ∈ {1, . . . , 0.1230 n }, ∀R ⊆ {1, . . . , p} s.t.

|R| = r, M R M R ∼ C r,n ,
namely M R M R are identically distributed with respect to the law of the random covariance matrix C r,n of size (r × r) that may depend on the parameter n also. As we will see in the sequel, standard models of covariance matrices C r,n are given by C r,n = (1/n) XX where X ∈ R r×n has iid entries drawn with respect to a law L. Note that we do not require that M has independent entries here, we only assume that the matrices M R M R are identically distributed and that we have access to the rate function of the deviations on its extreme eigenvalues.

Guaranteeing SRSR with sparsity parameter s requires to bound the eigenvalues of M R M R when r = 2s, see for instance Property (SRSR-γ(2s)). We consider the asymptotic proportional growth model where s/n → ρ, i.e. we assume that size of the sparse vectors over number of equations tends to a constant. We also consider the parameter ρ = r/n ∈ (0, 0.1230) and since r = 2s we remark that ρ = 2ρ. We assume that we have access to a deviation inequality on extreme eigenvalues of C r,n with rate function t → W(ρ, t) depending on this ratio. For instance, we will consider that for all n ≥ n 0 (ρ), (1.4) ∀t ∈ [0, 0.6247), P λ 1 -

(1 + √ ρ) 2 ∨ (1 - √ ρ) 2 -λ r ≥ t ≤ c(ρ)e -nW(ρ,t)
where n 0 (ρ) ≥ 2 and c(ρ) > 0 may depend on the ratio ρ, the function t → W(ρ, t) is continuous and increasing on [0, 0.6247) such that W(ρ, 0) = 0, λ 1 and λ r are respectively the largest and the least eigenvalues of C r,n . Remark that the "bulk" bounds (1 ± √ ρ) 2 are prescribed by the Marchenko-Pastur law. Consider the asymptotic proportional growth model for M so that 1 In an idealized situation one would assume that x0 is sparse. Nevertheless, in practice, we can only claim that x0 is close to sparse vectors. The stability is the ability to control the estimation error x0 -x by the distance between x0 and the sparse vectors. The reader may consult [27, page 82] for instance.

Figure 1.

[Bounds on SRSR in the iid Gaussian case] The region below the curves gives pairs of (δ = n/p, ρ = s/n) for which SRSR holds with overwhelming probability when M has iid Gaussian entries. Our new bound (1.6) in blue is comparable to the one of [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF] in red (derived using Foucart and Lai condition [26, Theorem 2.1]) and the one of [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF] in green (derived from symmetric RICs bounds as in (FR-c(2s))). This figure is an update of Figure 3.2 in [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF].

n/p → δ, i.e. the number of equations over number of unknowns tends also to a constant. The main contribution of this paper is to give a bound on (δ, ρ) from the rate function W so that SRSR holds with overwhelming probability.

The second random model covered by this paper is given by matrices M satisfying the following property (1.5) ∀r ∈ {1, . . . , 0.1230 n }, ∀R ⊆ {1, . . . , p} s.t. |R| = r, M R ∼ X r,n , namely M R are identically distributed with respect to the law of the random rectangular matrix X r,n of size (n × r). Standard models of rectangular matrices X r,n are given by X r,n = (1/ √ n) X where X ∈ R r×n has iid entries drawn with respect to a law L. As in the first model, we do not require that M has independent entries here, we only assume that the matrices M R are identically distributed. In this case, we assume that we have a deviation inequality with rate function W on the extreme singular values of X r,n . Again, our result gives a bound on (δ, ρ) from the rate function W so that SRSR holds with overwhelming probability.

The detailed results are presented in Section 2 and we give here the bound one can get in the case where M has iid Gaussian entries. More precisely, we establish a new sufficient condition on SRSR that offers the same lower bound as previous state-of-the-art results such as the results presented in [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF]. Indeed, using Davidson-Szarek's deviation [START_REF] Davidson | Local operator theory, random matrices and banach spaces[END_REF], we prove that if

(1.6) δ > 1 2ρ exp 1 - 1 4ρ 33 -5 √ 41 8 -2ρ 2 ,
then SRSR holds with overwhelming probability when M has iid Gaussian entries, see Section 2.3.2. This bound is comparable to previous state-of-the-art result [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF][START_REF] Rudelson | On sparse reconstruction from Fourier and Gaussian measurements[END_REF], see Figure 1.

1.3. Byproduct Result: New Bounds on the Restricted Isometry Constants. One property for assessing SRSR is the Restricted Isometry Property [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Candès | Near-optimal signal recovery from random projections: universal encoding strategies?[END_REF] of order s and parameter c, referred to as RIP(s, c, M). It is defined by

∀x ∈ Σ s , (1 -c) x 2 2 ≤ Mx 2 2 ≤ (1 + c) x 2 2 .
Denote by c(s, M) the minimum of such c's. One can prove (see Theorem 6.12 in [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF] for instance) that, if RIP such that (FR-c(2s)) c(2s, M) < 4 √ 41 0.625 , holds and x is any solution to (1.2) then SRSR of order s holds with C, D > 0 depending only on c(2s, M). A slightly modified RIP was introduced by Foucart and Lai in [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via lq-minimization for 0<q<=1[END_REF][START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF]. They introduce two constants, called Restricted Isometry Constants (RICs). For a matrix M of size (n × p), the RICs, c min (s, M) and c max (s, M), are defined as

c min := min c -≥0 c -subject to (1 -c -) x 2 2 ≤ Mx 2 2 for all x ∈ Σ s , c max := min c + ≥0 c + subject to (1 + c + ) x 2 2 ≥ Mx 2 2 for all x ∈ Σ s . Hence, it holds (1-c min ) x 2 2 ≤ Mx 2 2 ≤ (1+c max ) x 2
2 for all x ∈ Σ s , where we recall that Σ s denotes the set of vectors with at most s nonzero coordinates. Reporting the influence of both extreme eigenvalues of covariance matrices built from r = 2s columns of M, one can weaken (FR-c(2s)), see for instance Theorem 2.1 in [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via lq-minimization for 0<q<=1[END_REF]. Revisiting [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via lq-minimization for 0<q<=1[END_REF] and [27, Proof of Theorem 6.13 (page 145)], this paper provides the weakest condition to get SRSR in the following theorem, see Appendix A.1 for a proof. Remark. The condition to get SRSR described in [26, Theorem 2.1] can be equivalently written as γ(2s, n, p) < (5

+ √ 2)/(1 + √ 2)
2.657 which is a stronger requirement than Condition (SRSR-γ(2s)). Also, remark that Condition (SRSR-γ(2s)) leads to the inequality (1 + c(2s, M))/(1 -c(2s, M)) < (4 + √ 41) 2 /25 and one can check that this is exactly Condition (FR-c(2s)). From this remark, one can view (SRSR-γ(2s)) as a generalization of (FR-c(2s)) to the frame of asymmetric isometry constants.

Note that RIP constants are involved in other frameworks such as low-rank or group-sparse recovery, see for instance [START_REF] Traonmilin | Stable recovery of low-dimensional cones in hilbert spaces: One rip to rule them all[END_REF][START_REF] Cai | Sparse representation of a polytope and recovery of sparse signals and low-rank matrices[END_REF][START_REF] Ayaz | Uniform recovery of fusion frame structured sparse signals[END_REF]. Our results do not directly apply to those frameworks but the control on RIP constants given by the methodology presented in this paper (namely (2.2), (2.3), (2.6) and (2.7)) may be invoked in these settings. 1.4. From rate functions to SRSR. In this paper, we provide a toolbox to derive upper bounds on RICs (with overwhelming probability) from deviation inequalities on extreme eigenvalues (or extreme singular values) of covariance matrices C r,n . The known asymptotic behavior of these extreme eigenvalues provides an expected behavior for W(ρ, t) in both variables t and ρ. Notably, it appears along our analysis that bounds on SRSR and RICs are extremely dependent on the behavior, for fixed t, of the rate function ρ → W(ρ, t) when ρ is small, and possibly tending to zero. More details will be given in Section 2.3. Unfortunately, this dependence is sometimes unclear in the literature and we have to take another look at state-of-the-art results in this field. Revisiting the paper of Feldheim and Sodin [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] on sub-Gaussian matrices, Appendix B reveals the dependency on ρ as well as bounds on the constant appearing in their rate function W FS for the special case of Rademacher entries. Other important results due to Ledoux and Rider [START_REF] Ledoux | Small deviations for beta ensembles[END_REF], and Davidson and Szarek [START_REF] Davidson | Local operator theory, random matrices and banach spaces[END_REF] are investigated in Appendix A.2. 1.5. Previous works on bounding RIP and RICs. The existence of RIP matrices with bounded RIP constant such as (FR-c(2s)) has been proved using random matrix models, see [START_REF] Baraniuk | A simple proof of the restricted isometry property for random matrices[END_REF][START_REF] Mendelson | Uniform uncertainty principle for Bernoulli and subgaussian ensembles[END_REF][START_REF] Adamczak | Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling[END_REF][START_REF] Chafaï | Interaction between Compressed Sensing, Random matrices and High dimensional geometry[END_REF] ) captures all we need to know about 1 -recovery schemes. In reality, there is a gap between the constants appearing in the upper and lower bounds. A simple way to witness it is to consider the companion problem when there is no additive errors. In this case e = 0 in (1.1) and η = 0 in (1.2), then stable recovery occurs for all target vector x 0 if and only a property called "Null-Space Property" (NSP) holds. As for RIP, one can prove that (1.7) depicts a necessary and sufficient condition on NSP up to a change of constants, see for instance [START_REF] Chafaï | Interaction between Compressed Sensing, Random matrices and High dimensional geometry[END_REF][START_REF] Azaïs | A rice method proof of the null-space property over the grassmannian[END_REF]. Nevertheless, a better description of this property is offered in the works [START_REF] Donoho | Neighborliness of randomly projected simplices in high dimensions[END_REF][START_REF] Donoho | Counting faces of randomly projected polytopes when the projection radically lowers dimension[END_REF][START_REF] Donoho | Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing[END_REF] since the authors provide a phase transition on NSP for large Gaussian matrices with iid entries. Let us also mention the important papers [START_REF] Mccoy | Sharp recovery bounds for convex demixing, with applications[END_REF][START_REF] Amelunxen | Living on the edge: phase transitions in convex programs with random data[END_REF] that give quantitative estimates of "weak" thresholds appearing in convex optimization, including the location and the width of the transition region for NSP. Following this outbreaking result, one can wonder whether a phase transition holds for properties guaranteeing SRSR such as Condition (FR-c(2s)) or the asymmetric (SRSR-γ(2s)). To the best of our knowledge, the first work looking for a phase transition on SRSR can be found in [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF] where the authors considered matrices with independent standard Gaussian entries and used an upper bound on the joint density of the eigenvalues to derive a region where (SRSR-γ(2s)) holds. Their lower bound is not explicit but one can witness in [11, page 119]. Furthermore they provide web forms for the calculation of bounds on RICs, which are available at Jared Tanner's webpage. Shortly after, Bah and Tanner improved these bounds in [START_REF] Bah | Improved bounds on restricted isometry constants for gaussian matrices[END_REF] by preventing the use of union bound over all sub-matrices built from r = 2s columns of M by grouping those which share a substantial number of columns. Their bounds are still implicit but web forms for their calculation are available at the same place. The same authors provided later [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF] explicit bounds for the RICs in extreme asymptotic regime: (a) when ρ → 0 and δ > 0 is fixed, (b) when δ → 0 and ρ > 0 is fixed, (c) when ρ = -1 γ log δ (γ is a fixed parameter) and δ → 0. In the sequel, we may refer to these regimes as Regime (a), (b) and (c) respectively.

We would like to point out recent "off-the-shelf" concentration results, often based on generic chaining, that imply bounds on RIP constants, at least for subgaussian random matrices. The reader may consult for instance [START_REF] Dirksen | Tail bounds via generic chaining[END_REF]Section 5] or [START_REF] Liaw | A simple tool for bounding the deviation of random matrices on geometric sets[END_REF]. From these results, classical bounds on gaussian widths of sparse vectors lead to null space properties or RIP constants, see [START_REF] Liaw | A simple tool for bounding the deviation of random matrices on geometric sets[END_REF]Section 2.6]. We would also point out the interesting results on the "Small Ball Method", see [START_REF] Lecué | Sparse recovery under weak moment assumptions[END_REF][START_REF] Lecué | Regularization and the small-ball method i: sparse recovery[END_REF] for instance, that requires only weak moment assumptions to get sparse recovery guarantees. 1.6. Outline. The paper is organized as follows. Section 2 states the main results: it provides a general method to derive bounds on RICs and phase transition in Condition (SRSR-γ(2s)) from deviation inequalities on eigenvalues or singular values. Subsection 2.3 begins with a discussion on what is expected for such deviation inequalities. The general method described in Subsections 2.1 and 2.2 is then applied to previously known inequalities. Section 2 ends with a summary of the obtained bounds.

The proofs are contained in the appendix. Appendix A.1 provides the proof of Theorem 1, while Appendix A.2 and Appendix A.3 contain the proofs of Theorems 2 and 3. In Appendix B, we follow the steps of [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] to provide an upper bound on the constant in the deviation inequality for extreme singular values of Rademacher matrices.

From deviations to RICs and SRSR bounds

Following the framework of [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF], we provide asymptotic bounds on RICs in the proportional growth model. As previously explained, we suppose that we are able to control the deviation of extreme eigenvalues or singular values. We aim at controlling uniformly the extreme eigenvalues, the combinatorial complexity is standardly [START_REF] Blanchard | Compressed sensing: How sharp is the restricted isometry property?[END_REF] controlled by the quantity δ -1 H e (ρδ) where

H e (t) := -t log t -(1 -t) log(1 -t) for t ∈ (0, 1) ,
denotes the Shannon entropy. The improvement introduced in [START_REF] Bah | Improved bounds on restricted isometry constants for gaussian matrices[END_REF] to deal with this combinatorial complexity could be used here but we chose not to do so as it would have turned our explicit bounds into implicit ones. One may remark that the quantity

t 0 := W -1 ρ, δ -1 H e (ρδ)
governs the order of the deviation in the rate function t → W(ρ, t) when bounding the extreme eigenvalues uniformly over all possible supports S of size r among the set of indices {1, . . . , p}, see (2.4) and (2.8) in the functions Ψ min / max . Here W -1 (ρ, .) denotes the inverse of W with respect to its second variable.

The next theorems gives the probability that the matrix M satisfies (SRSR-γ(2s)). From Theorem 1 note that this event is included in the event such that SRSR holds, namely M satisfies (SRSR-γ(2s)) with s ≤ s 0 ⊂ SRSR holds with s ≤ s 0 where the right hand event means that for any x 0 ∈ R p , any solution x to (1.2) satisfies SRSR for all parameters s such that s ≤ s 0 .

2.1. Using extreme eigenvalues deviations inequalities. Useful constants are ρ 0 := (33 -5 √ 41)/16 0.0615 and √ ρ 0 0.3508. Also, we denote τ 0 := 4/ √ 41 0.6247. The key main result is the following theorem proved in Section A.2.

Theorem 2. Assume that for all 0 < ρ < 2ρ 0 , the largest eigenvalue λ 1 and the smallest eigenvalue λ r of a (r × r) covariance matrix C r,n where r := ρn satisfy for all n ≥ n 0 (ρ),

∀0 ≤ t < τ 0 , P λ 1 -(1 + √ ρ) 2 ∨ (1 - √ ρ) 2 -λ r ≥ t ≤ c(ρ)e -nW(ρ,t)
where n 0 (ρ) ≥ 2 and c(ρ) > 0 may both depend on ρ, the function t → W(ρ, t) is continuous and increasing on [0, τ 0 ) such that W(ρ, 0) = 0. Then for any 0 < δ < 1 and 0 < ρ < ρ 0 such that

(2.1) δ > Ψ (1) 0 (ρ, W) := 1 2ρ exp 1 - 1 2ρ W 2ρ, 2τ 0 ( √ ρ - √ ρ 0 ) √ ρ - 1 2 √ ρ 0 ,
and for any sequence of (n × p) matrices (M (n) ) n≥2 with n/p → δ satisfying (1.3), it holds that

P M (n) satisfies (SRSR-γ(2s)) with s ≤ s 0 = ρn ≥ 1 -2c(2ρ)e -nD 1 (δ,ρ) → 1
for some D 1 (δ, ρ) > 0 that may depend on δ and ρ.

Furthermore, for all ε > 0 and for all ρ and δ such that δ -1 H e (ρδ) belongs to the range of W(ρ, •), it holds

P c min ( ρn , M (n) ) ≥ Ψ (1) min (δ, ρ, W) + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) , (2.2) P c max ( ρn , M (n) ) ≥ Ψ (1) max (δ, ρ, W) + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) , (2.3)
where D 2 (ρ, δ, ε) > 0 and we denote

Ψ (1) min (δ, ρ, W) := √ ρ(2 - √ ρ) + t 0 , (2.4)
Ψ (1) max (δ, ρ,

W) := √ ρ(2 + √ ρ) + t 0 ,
with t 0 := W -1 (ρ, δ -1 H e (ρδ)).

Using extreme singular values deviations.

A similar result can be derived from deviations on singular values, a proof is given in Section A.3.

Theorem 3. Assume that for all 0 < ρ < 2ρ 0 , the largest singular value σ 1 and the smallest singular value σ r of a (n × r) matrix X r,n where r := ρn satisfy for all n ≥ n 0 (ρ),

∀0 < t < 2ρ 0 , P σ 1 -(1 + √ ρ) ∨ (1 - √ ρ) -σ r ≥ t ≤ c(ρ)e -nW(ρ,t)
where n 0 (ρ) ≥ 2 and c(ρ) > 0 may both depend on ρ, the function t → W(ρ, t) is continuous and increasing on [0, √ 2ρ 0 ) such that W(ρ, 0) = 0. Then for any 0 < δ < 1 and 0 < ρ < ρ 0 such that

(2.5) δ > Ψ (2) 0 (ρ, W) := 1 2ρ exp 1 - 1 2ρ W 2ρ, 2ρ 0 -2ρ ,
and for any sequence of (n × p) matrices (M (n) ) n≥2 with n/p → δ satisfying (1.5), it holds that

P M (n) satisfies (SRSR-γ(2s)) with s ≤ s 0 = ρn ≥ 1 -2c(2ρ)e -nD 1 (δ,ρ) → 1
for some D 1 (δ, ρ) > 0 that may depend on δ and ρ.

Furthermore, for all ε > 0 and for all ρ and δ such that δ -1 H e (ρδ) belongs to the range of W(ρ, •), it holds

P c min ( ρn , M (n) ) ≥ Ψ (2) min (δ, ρ, W) + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) , (2.6) P c max ( ρn , M (n) ) ≥ Ψ (2) max (δ, ρ, W) + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) , (2.7)
where D 2 (ρ, δ, ε) > 0 and we denote

Ψ (2) min (δ, ρ, W) := min{1, ( √ ρ + t 0 )(2 - √ ρ -t 0 )} , (2.8)
Ψ (2) max (δ, ρ, W) := (

√ ρ + t 0 )(2 + √ ρ + t 0 ) , with t 0 := W -1 (ρ, δ -1 H e (ρδ)).
Theorems 2 and 3 give a general method to derive bounds on RICs from deviation inequalities satisfied by the extreme eigenvalues or singular values of a random matrix. In the following subsection, three known deviation inequalities are used to provide such bounds for Gaussian and Rademacher matrices.

2.3.

State-Of-The-Art deviation inequalities. The asymptotic behavior of extreme eigenvalues of random covariance matrices with iid entries has been known for some years. From this behavior and the concentration of measure phenomenon, we present what is expected for deviation inequalities for extreme eigenvalues of such matrices with sub-Gaussian entries. This is what we call "ideal deviations". The next two paragraphs are devoted to deviation inequalities for Gaussian matrices due to Davidson and Szarek [START_REF] Davidson | Local operator theory, random matrices and banach spaces[END_REF], and Ledoux and Rider [START_REF] Ledoux | Small deviations for beta ensembles[END_REF]. The last paragraph focuses on a deviation inequality for Rademacher matrices, proved by Feldheim and Sodin [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF].

In what follows, the bounds on RICs are written in terms of parameters ρ = r n and δ = n p . When expressing Condition (2.1) or (2.5), we use parameter ρ = s n , with s = r/2. Note that throughout this paper, it holds that ρ = 2ρ.

Ideal deviations.

The asymptotic behavior of extreme eigenvalues for random covariance matrices was first established for matrices with Gaussian entries [START_REF] Johansson | Shape fluctuations and random matrices[END_REF][START_REF] Borodin | Increasing subsequences and the hard-to-soft edge transition in matrix ensembles[END_REF] and extended to ones with more general entries in [START_REF] Soshnikov | A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices[END_REF][START_REF] Péché | Universality results for the largest eigenvalues of some sample covariance matrix ensembles[END_REF][START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF][START_REF] Pillai | Universality of covariance matrices[END_REF][START_REF] Wang | Random covariance matrices: universality of local statistics of eigenvalues up to the edge[END_REF]. The largest eigenvalue fluctuations are described by the following:

nρ 1/4 (1 + √ ρ) 2 2 3 (λ 1 -(1 + √ ρ) 2 ) (d) → n→∞ F 1 ,
where F 1 is the so-called Tracy-Widom law. As for the smallest eigenvalue, when ρ < 1 (which is true in our setting),

nρ 1/4 (1 - √ ρ) 2 2 3 ((1 - √ ρ) 2 -λ r ) (d) → n→∞ F 1 .
We focus on the largest eigenvalue λ 1 and write:

P(λ 1 ≥ (1 + √ ρ) 2 + t) = P nρ 1/4 (1 + √ ρ) 2
This deviation probability is therefore expected to be close to

1 -F 1 n 2/3 ρ1/6 (1 + √ ρ) 4/3 t ,
where F 1 is the cdf of the Tracy-Widom distribution. Thus it is expected to be close to the tail behavior of F 1 at ∞, which is actually known:

1 -F 1 (x) ∼ x→∞ e -2 3 x 3/2 .
As a consequence, deviation inequalities for the largest eigenvalue are expected to conform to

P λ 1 ≥ (1 + √ ρ) 2 + t ≤ C exp -c ρ1/4 (1 + √ ρ) 2 nt 3/2 ,
at least for t of the order of the spectrum width (which behaves asymptotically as O( √ ρ)). For bigger t, due to the concentration of measure phenomenon, the expected behavior is the following:

P λ 1 ≥ (1 + √ ρ) 2 + t ≤ Ce -cn min(t,t 2 ) .
Similar results should hold for the smallest eigenvalue, except that λ r ≥ 0 almost surely and therefore only moderate deviations can occur. See [START_REF] Ledoux | Deviation inequalities on largest eigenvalues[END_REF] for a detailed survey on this subject and [33, Page 1322] for a specific discussion on the change of behavior occurring around t = O( √ ρ). Considering these expected deviation inequalities, it may be possible to prove the following for sub-Gaussian random matrices.

∀t > 0, P λ 1 -(1 + √ ρ) 2 ≥ t ≤ c(ρ)e -nW TW (ρ,t)
where λ 1 denotes the largest eigenvalue of a (r × r) covariance matrix C r,n with iid sub-Gaussian entries and

W TW (ρ, t) := 1 C ρ 1 4 (1 + √ ρ) 2 t 3 2 1 t≤ √ ρ + t 2 (1 + √ ρ) 2 1 √ ρ<t≤1 + t (1 + √ ρ) 2 1 t>1 , (2.9)
where C > 0. A similar deviation inequality may be established for the smallest eigenvalue λ r with almost a similar W function (the (1 + √ ρ) 2 terms should be replaced by (1 -√ ρ) 2 ). We should obtain

W -1 TW (ρ, u) = C 2/3 (1 + √ ρ) 4/3 ρ 1 6 u 2 3
small deviation part

1 u≤ ρ C(1+ √ ρ) 2 + C 1/2 (1 + √ ρ) √ u moderate deviation part 1 ρ C(1+ √ ρ) 2 <u≤ 1 C(1+ √ ρ) 2 + C(1 + √ ρ) 2 u large deviation part 1 u> 1 C(1+ √ ρ) 2
.

Theorem 2 could then be invoked to get bounds on RICs,

c max ≤ √ ρ(2 + √ ρ) + t 0 , c min ≤ √ ρ(2 - √ ρ) + t 0 ,
where

t 0 = W -1 TW ρ, 1 δ H e (ρδ) .
Remark. Note that in the two asymptotic Regimes (a) and (c) of [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF], 1 δ H e (ρδ) will be larger than

ρ C(1+ √ ρ) 2 .
Therefore it seems that the most important part in the rate function (2.9) for our present use is the moderate and large deviation parts, arising from the concentration of measure phenomenon.

2.3.2.

Davidson and Szarek's deviations. Consider a (r × n) matrix X with iid standard Gaussian entries. In the paper [START_REF] Davidson | Local operator theory, random matrices and banach spaces[END_REF], Davidson and Szarek have shown that for all 0 < ρ < 1 it holds

∀t > 0, P σ 1 (X) √ n -(1 + √ ρ) ∨ (1 - √ ρ) - σ r (X) √ n ≥ t ≤ 2e -nW DS (ρ,t)
where σ i (X) denotes the singular values of X and W DS (ρ, t) := t 2 /2, see [27, page 291] for instance. This inequality relies on the concentration of measure phenomenon. Note that

W -1 DS (ρ, u) = √ 2u.
Theorem 3 applied here gives the following high probability bounds on RICs

c max ≤ ( √ ρ + t 0 )(2 + √ ρ + t 0 ), c min ≤ ( √ ρ + t 0 )(2 - √ ρ -t 0 ),
where t 0 = 2 δ H e (ρδ).

Remark. In the three asymptotic Regimes (a), (b) and (c), these bounds on RICs behave similarly to the ones obtained by Bah and Tanner in [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF], except that constants are better in [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF]. Note that this deviation has been used in the paper [16, Lemma 3.1] to bound the RIP constant.

Furthermore, Theorem 3 states that Condition (SRSR-γ(2s)) is satisfied with high probability whenever

δ > 1 2ρ exp 1 - 1 2ρ ( √ ρ 0 - √ ρ) 2 .
When ρ is small (which is the case in the Regimes (a) and (c)), this condition approximately writes δ > 1 2ρ exp -ρ 0 2ρ .

2.3.3.

Ledoux and Rider's deviations. Ledoux and Rider proved in [START_REF] Ledoux | Small deviations for beta ensembles[END_REF] small deviation inequalities for β Hermite and Laguerre Ensembles. Their work rely on the tridiagonal model for these matrix ensembles and on a variational formulation of the Tracy-Widom distribution. For real covariance matrices, their deviation inequality for the largest eigenvalue is the following. For all 0 < ρ < 1 and for all n ≥ 2, setting r = ρn ,

∀t > 0, P λ 1 -(1 + √ ρ) 2 ≥ t ≤ c(ρ)e -nW max LR (ρ,t)
where λ 1 denotes the largest eigenvalue of a (r × r) covariance matrix C r,n with iid standard Gaussian entries and

W max LR (ρ, t) := ρ 1 4 C LR (1 + √ ρ) 3 t 3 2 1 t≤ √ ρ(1+ √ ρ) 2 + ρ 1 2 C LR (1 + √ ρ) 2 t1 t> √ ρ(1+ √ ρ) 2 ,
where C LR > 0 may be bounded explicitly from [START_REF] Ledoux | Small deviations for beta ensembles[END_REF]. As explained in Section 1.4, the dependency of function W in parameter ρ is of crucial importance in our analysis. Therefore, we choose to write the most precise deviation inequalities the paper reached, even in the case when r/n is bounded. For λ r , we follow the procedure explained in [33, Section 5, page 1338] to write the following

∀t > 0, P (1 - √ ρ) 2 -λ r ≥ t ≤ c(ρ)e -nW min LR (ρ,t)
where

W min LR (ρ, t) := ρ 1 4 C LR (1 - √ ρ) 3 t 3 2 1 t≤ √ ρ(1- √ ρ) 2 + ρ 1 2 C LR (1 - √ ρ) 2 t1 t> √ ρ(1- √ ρ) 2 .
In order to simplify the analysis of the phase transition, observe that W max LR (ρ, t) ≤ W min LR (ρ, t) for all ρ and t. This yields

∀t > 0, P λ 1 -(1 + √ ρ) 2 ∨ (1 - √ ρ) 2 -λ r ≥ t ≤ c(ρ)e -nW LR (ρ,t)
where

W LR (ρ, t) := W max LR (ρ, t) . Therefore W -1 LR (ρ, u) = C 2/3 LR (1 + √ ρ) 2 ρ1/6 u 2/3 1 u≤ ρ C LR + C LR (1 + √ ρ) 2 √ ρ u1 u> ρ C LR .
Theorem 2 applied here gives the following high probability bounds on RICs:

c max ≤ √ ρ(2 + √ ρ) + t 0 , c min ≤ √ ρ(2 - √ ρ) + t 0 ,
where t 0 = W -1 LR (ρ, 1 δ H e (ρδ)). Remark. In the three asymptotic Regimes (a), (b) and (c), it may be shown that 1 δ H e (ρδ) ≥ ρ C LR . These bounds on RICs behave similarly to the ones obtained by Bah and Tanner in [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF] in Regime (a), except that their constants are better. In Regimes (b) and (c), they behave badly compared to those of [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF]. Furthermore, Theorem 2 states that Condition (SRSR-γ(2s)) is satisfied with high probability whenever δ >

1 2ρ exp 1 - 1 2ρ W LR 2ρ, 2τ 0 ( √ ρ - √ ρ 0 ) √ ρ - 1 2 √ ρ 0 .
When ρ is small (which is the case in Regimes (a) and (c)), the second argument in W LR is approximately τ 0 and this condition approximately writes

δ > 1 2ρ exp - τ 0 C LR √ 2ρ .
2.3.4. Feldheim and Sodin's deviations. For all 0 < ρ < 1 and for all n ≥ n 0 , setting r = ρn it follows from [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] that

∀t > 0, P λ 1 -(1 + √ ρ) 2 ∨ (1 - √ ρ) 2 -λ r ≥ t ≤ c(ρ)e -nW FS (ρ,t)
where λ i denotes the eigenvalues of a (r × r) covariance matrix C r,n with iid Rademacher entries and

W FS (ρ, t) := ρ log(1 + t 2 √ ρ ) 3 2 C FS (1 + √ ρ) 2 ,
where 0 < C FS < 837, as shown in Proposition 6. Furthermore

W -1 FS (ρ, u) = 2 √ ρ exp C 2/3 FS (1 + √ ρ) 4/3 ρ2/3 u 2/3 -1 .
Theorem 2 applied here gives the following high probability bounds on RICs:

c max ≤ √ ρ(2 + √ ρ) + t 0 , c min ≤ √ ρ(2 - √ ρ) + t 0 ,
where t 0 = W -1 FS (ρ, 1 δ H e (ρδ)). Furthermore, Theorem 2 states that Condition (SRSR-γ(2s)) is satisfied with high probability whenever

δ > 1 2ρ exp 1 - 1 2ρ W FS 2ρ, 2τ 0 ( √ ρ - √ ρ 0 ) √ ρ - 1 2 √ ρ 0 .
When ρ is small (which is the case in regimes (a) and (c)), the second argument in W FS is approximately τ 0 and this condition approximately writes

δ > 1 2ρ exp - | log ρ| 3/2 2 3/2 C FS .
Remark. In the three asymptotic regimes (a), (b) and (c), these bounds behave badly compared to the ones by Bah and Tanner in [START_REF] Bah | Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices[END_REF] (but note that we consider here entries which are not Gaussian anymore). This is indeed not surprising: from Section 2.3.1, it seems that the most important part in the rate function (2.9) is the moderate and large deviation behavior, whereas Feldheim and Sodin's inequality focuses only on small deviations. For matrices with independent Rademacher entries, concentration of measure phenomenon still occurs and one can use Talagrand's inequality to control large deviations of the largest singular value σ 1 , which is a convex function of the entries. A similar inequality holds for matrices with independent sub-Gaussian entries:

(2.10)

P σ 1 (X) √ n ≥ t(1 + √ ρ) ≤ e -cnt 2 , for all t ≥ C,
where X is a (r × n) matrix with iid sub-Gaussian entries, with mean zero and variance 1. Here c, C > 0 depend on the sub-Gaussian moment of the entries and on ρ (see for example [START_REF] Litvak | Smallest singular value of random matrices and geometry of random polytopes[END_REF]).

Note that these constants might be computed explicitly but we did not pursue on this laborious task here. As far as we know, the more precise moderate and large deviation inequality for the smallest singular value of sub-Gaussian matrices was established by Rudelson and Vershynin (see for example [START_REF] Rudelson | Non-asymptotic theory of random matrices: extreme singular values[END_REF]):

(2.11)

P σ r (X) √ n ≤ t(1 - √ ρ) ≤ (Ct) n(1-ρ) + e -cn , for all t ≥ 0,
where c, C > 0 depend only on the sub-Gaussian moment of the entries. Again, these constants may be computed explicitly. Note that the e -cn term quantifies the fact that X is non singular with probability strictly less than 1.

Combining Feldheim and Sodin's inequality with the preceding ones (2.10) and (2.11) would probably lead to a more accurate deviation inequality. However constants should be computed explicitly and the proof of Theorem 3 modified in order to deal with the additive term e -cn in (2.11). We will not pursue this task here.

Bounds on RICs and SRSR.

We summarize the bounds we obtained in the previous subsections. For sake of readability, we focus on the asymptotic Regime (a), in which ρ → 0 and δ > 0 is fixed, so that the functions Ψ

Inequality by Ψ

(1,2) max

Ψ (1,2) min Davidson-Szarek 2 √ 2 ρ| log ρ| + 2 √ ρ + √ 2(1 -log δ) ρ | log ρ| + o ρ | log ρ| = Ψ (2) max Ledoux-Rider C LR √ ρ| log ρ| + 2 + C LR 1 -log δ √ ρ + o( √ ρ) = Ψ (1) max Feldheim-Sodin 2 √ ρ exp C 2/3 FS | log ρ| 2/3 + o √ ρ exp C 2/3 FS | log ρ| 2/3 = Ψ (1) max
We summarize next the conditions we obtained in the previous subsections on δ and ρ so that Condition (SRSR-γ(2s)) is satisfied with high probability. For sake of readability again, this condition is written assuming that ρ is small.

Inequality by

Condition (SRSR-γ(2s))

Davidson-Szarek δ > 1 2ρ exp -ρ 0 2ρ Ledoux-Rider δ > 1 2ρ exp -τ 0 C LR √ 2ρ
Feldheim-Sodin δ >

= s, v S 2 ≤ κ √ s v S c 1 + τ Mv 2 .
Given v ∈ R p , it is enough to consider S = S 0 the set of the s largest (in magnitude) entries of v, S 1 the set of the s largest (in magnitude) entries of v in S c 0 , S 2 the set of the s largest (in magnitude) entries of v in (S 0 ∪ S 1 ) c , etc. By definition of the RICs, one has

Mv S 0 2 2 = (1+t) v S 0 2 2 with -c min (2s, M) ≤ -c min (s, M) ≤t ≤ c max (s, M) ≤ c max (2s, M) .
We begin with a first lemma. For sake of readability and from now on, c min denotes c min (2s, M) and c max denotes c max (2s, M). Lemma 4. For all k ≥ 1, it holds

| Mv S 0 , Mv S k | ≤ (c max -t)(c min + t) v S 0 2 v S k 2 .
Proof. Set u = v S 0 / v S 0 2 and w = ±v S k / v S k 2 where the sign of w is chosen so that | Mu, Mw | = Mu, Mw . For α, β > 0 to be chosen later, it holds

2| Mu, Mw | = 1 α + β M(αu + w) 2 2 -M(βu -w) 2 2 -(α 2 -β 2 ) Mu 2 2 ≤ 1 α + β (1 + c max ) αu + w 2 2 -(1 -c min ) βu -w 2 2 -(α 2 -β 2 )(1 + t) u 2 2 = 1 α + β (1 + c max )(α 2 + 1) -(1 -c min )(β 2 + 1) -(α 2 -β 2 )(1 + t) = 1 α + β α 2 (c max -t) + β 2 (c min + t) + c max + c min .
Then, chose α = (c min + t)/(c max -t) and β = (c max -t)/(c min + t) to get the desired inequality.

Using Lemma 4, observe that

(1 + t) v S 0 2 2 = Mv S 0 2 2 = Mv S 0 , Mv - k≥1 Mv S 0 , Mv S k ≤ Mv S 0 2 Mv 2 + k≥1 (c max -t)(c min + t) v S 0 2 v S k 2 = v S 0 2 √ 1 + t Mv 2 + (c max -t)(c min + t) k≥1 v S k 2 .
Now, Lemma 6.14 in [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF] gives that

k≥1 v S k 2 ≤ 1 √ s v S c 0 1 + 1 4 v S 0 2 .
We deduce that

v S 0 2 ≤ b 4 v S 0 2 + b √ s v S c 0 1 + Mv 2 √ 1 + t ,
where b := (c max -t)(c min + t)/(1 + t). It follows that

v S 0 2 ≤ 1 √ s 4b 4 -b v S c 0 1 + 4 4 -b Mv 2 √ 1 + t .
It suffices that κ = 4b/(4 -b) < 1 to get the 2 -robust null space property and hence SRSR. This is equivalent to b = (c max -t)(c min + t)/(1 + t) < 4/5. We have the following lemma.

Lemma 5. For any t ∈ [-c min , c max ], it holds

(c max -t)(c min + t) (1 + t) ≤ c min + c max 2 (1 -c min )(1 + c max ) .
Proof. Define f (t) = (c max -t)(c min + t)/(1 + t) 2 whose derivative is given by

f (t) = c max -c min -2c max c min -t(2 + c max -c min ) (1 + t) 3
We easily deduce that the function f is upper bounded by the quantity f (t ) where we denote t = (c max -c min -2c max c min )/(2 + c max -c min ). Now, remark that it holds f (t ) = (c min + c max ) 2 /(4(1 -c min )(1 + c max )). This gives the desired inequality.

It shows that SRSR holds whenever (c min + c max )/ (1 -c min )(1 + c max ) < 8/5. This last condition reads √ γ -1/ √ γ < 8/5 which is equivalent to √ γ < (4 + √ 41)/5, where we denote γ = γ(2s, M). The desired condition follows.

A.2. Proof of Theorem 2. We first prove (2.3). Set ε > 0 and suppose that ρ and δ are such that 1 δ H e (ρδ) is in the range of W(ρ, •). Set t 0 = W -1 ρ, 1 δ H e (ρδ) . Then

P c max ≥ √ ρ(2 + √ ρ) + t 0 + ε = P 1 + c max ≥ (1 + √ ρ) 2 + t 0 + ε = P ∃x ∈ Σ r s.t. Mx 2 ≥ (1 + √ ρ) 2 + t 0 + ε x 2 ≤ Cr,n P λ 1 (C r,n ) ≥ (1 + √ ρ) 2 + t 0 + ε ≤ p r c(ρ)e -nW(ρ,t 0 +ε) ≤ c(ρ)Θ e -nW(ρ,t+ε)+pHe(r/p) ≤ c(ρ)Θ e -nD ,
with

H e (t) = -t log t -(1 -t) log(1 -t) for t ∈ (0, 1), Θ 2 := e 1/2 /(2π[r(1 -r/p)] 1/p ) and D = W(ρ, t 0 + ε) -W(ρ, t 0 ) > 0.
Indeed, note that Stirling formula (see Lemma 10) leads to

p r ≤ e 1/4 √ 2π[r(1 -r/p)] 1/(2p)
e -r log(r/p)-(p-r) log(1-r/p) = Θe pHe(r/p) .

where Θ → e 1/4 / √ 2π when 0 < r/p < 1 and p goes to infinity. Set D 2 (ρ, δ, ε) = D 2 . Observe that D -log(Θ)/n ≥ D 2 (ρ, δ, ε) for large enough n. Then, for n large enough (depending only on ρ, δ and ε), it holds

P c max ≥ √ ρ(2 + √ ρ) + t 0 + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) .
Following the same arguments, we get a similar inequality (2.2) for c min .

We suppose now that (M (n) ) n≥2 is a sequence of (n×p) matrices with n/p → δ satisfying (1.3) and that Condition (2.1) is satisfied, namely

δ > Ψ (1) 0 (ρ, W) := 1 2ρ exp 1 - 1 2ρ W 2ρ, 2τ 0 ( √ ρ - √ ρ 0 ) √ ρ - 1 2 √ ρ 0 . √ 2 √ ρ + 4
√ 41 belongs to (0, τ 0 ). Recall that W(2ρ, .) is increasing on this interval. Applying W -1 (2ρ, .) to (A.1) leads to

0 < t 0 < 8 √ 41 ρ -2 √ 2 √ ρ + 4 √ 41 . Let t 0 < t < t * = 8 √ 41 ρ -2 √ 2 √ ρ + 4 √ 41 . Remark that Condition (SRSR-γ(2s)) is satisfied on the event {c max (2s, M (n) ) < √ 2ρ(2 + √ 2ρ) + t} ∩ {c min (2s, M (n) ) < √ 2ρ(2 - √ 2ρ) + t}. Indeed, denoting γ 0 = (4+ √ 41) 2 25 , γ(2s, M) - (4 + √ 41) 2 25 = 1 + c max (2s, M (n) ) 1 -c min (2s, M (n) ) -γ 0 < (1 + √ 2ρ) 2 + t (1 - √ 2ρ) 2 -t -γ 0 < (1 -γ 0 ) + 2 √ 2(1 + γ 0 ) √ ρ + 2(1 -γ 0 )ρ + (1 + γ 0 )t (1 - √ 2ρ) 2 -t . Note that t < t * = 8 √ 41 ρ -2 √ 2 √ ρ + 4 √ 41 implies that the denominator is positive. Moreover 1 -γ 0 = -8 25 (4 + √ 41) and 1 + γ 0 = 2 √ 41 25 (4 + √ 41) > 0. Therefore (1 -γ 0 ) + 2 √ 2(1 + γ 0 ) √ ρ + 2(1 -γ 0 )ρ + (1 + γ 0 )t = (1 + γ 0 )(t -t * ) < 0 .
As a consequence,

γ(2s, M) < (4 + √ 41) 2 25
.

Invoking (2.3) and (2.2) with ε = t -t 0 and ρ = 2ρ yields the following

P c max (2s, M (n) ) ≥ 2ρ(2 + 2ρ) + t ≤ c(2ρ)e -nD 2 (2ρ,δ,t-t 0 ) , P c min (2s, M (n) ) ≥ 2ρ(2 -2ρ) + t ≤ c(2ρ)e -nD 2 (2ρ,δ,t-t 0 ) , with D 2 (2ρ, δ, t -t 0 ) = W(2ρ, t) -W(2ρ, t 0 ) /2 > 0. Note that t → D 2 (2ρ, δ, t -t 0 ) is continuous and increasing from [t 0 , t * ) ⊂ [0, τ 0 ) onto 0, D 2 (2ρ, δ, t * -t 0 ) .
Choose D 1 (ρ, δ) ∈ 0, D 2 (2ρ, δ, t * -t 0 ) (remark that t * and t 0 depend only on ρ and δ) and define t ρ,δ in (t 0 , t * ) so that D 2 (2ρ, δ, t ρ,δ -t 0 ) = D 1 (ρ, δ). Therefore P M (n) does not satisfy (SRSR-γ(2s)) with s ≤ ρn

≤ P c max (2s, M (n) ) ≥ 2ρ(2 + 2ρ) + t ρ,δ + P c min (2s, M (n) ) ≥ 2ρ(2 -2ρ) + t ρ,δ ≤ 2c(2ρ)e -nD 1 (ρ,δ) ,
which concludes the proof.

A.3. Proof of Theorem 3. We follow the same lines as in the previous proof. We first prove (2.7).

For ε > 0, we get the following.

P c max ≥ ( √ ρ + t 0 )(2 + √ ρ + t 0 ) + ε = P 1 + c max ≥ (1 + √ ρ + t 0 ) 2 + ε = P ∃x ∈ Σ r s.t. Mx 2 ≥ (1 + √ ρ + t 0 ) 2 + ε x 2 ≤ Cr,n P σ 1 ≥ (1 + √ ρ + t 0 ) 2 + ε ≤ Cr,n P σ 1 ≥ 1 + √ ρ + t 0 + f (ρ, δ, ε) , where f (ρ, δ, ε) = (1 + √ ρ + t 0 ) 2 + ε -(1 + √ ρ + t 0 ) > 0. Then P c max ≥ ( √ ρ + t 0 )(2 + √ ρ + t 0 ) + ε ≤ p r c(ρ)e -nW ρ,t 0 +f (δ,ρ,ε) ≤ c(ρ)Θ e -nW ρ,t 0 +f (δ,ρ,ε) +pHe(r/p) ≤ c(ρ)Θ e -nD ,
with

H e (t) = -t log t -(1 -t) log(1 -t) for t ∈ (0, 1), Θ 2 := e 1/2 /(2π[r(1 -r/p)] 1/p ) and D = W ρ, t 0 + f (δ, ρ, ε) -W(ρ, t 0 ). Set D 2 (ρ, δ, ε) = D 2 .
Observe that D -log(Θ)/n ≥ D 2 (ρ, δ, ε) for large enough n. Then, for n large enough (depending only on ρ, δ and ε), it holds

P c max ≥ ( √ ρ + t 0 )(2 + √ ρ + t 0 ) + ε ≤ c(ρ)e -nD 2 (ρ,δ,ε) .
Following the same arguments, we get a similar inequality (2.6) for c min .

We suppose now that (M (n) ) n≥2 is a sequence of (n×p) matrices with n/p → δ satisfying (1.5) and that Condition (2.5) is satisfied, namely

δ > Ψ (2) 0 (ρ, W) := 1 2ρ exp 1 - 1 2ρ W 2ρ, 2ρ 0 -2ρ ,
Using the fact that H e (t) ≤ -t log t + t, this condition implies

0 < 1 δ H e (2ρδ) < W 2ρ, 2ρ 0 -2ρ . Recall that W(2ρ, .) is increasing on [0, √ 2ρ 0 ). Applying W -1 (2ρ, .) leads to 0 < t 0 < 2ρ 0 -2ρ. Let t 0 < t < t * = √ 2ρ 0 - √ 2ρ. Remark that Condition (SRSR-γ(2s)) is satisfied on the event {c max (2s, M (n) ) < ( √ 2ρ + t)(2 + √ 2ρ + t)} ∩ {c min (2s, M (n) ) < ( √ 2ρ + t)(2 - √ 2ρ -t)}. Indeed γ(2s, M) - 4 + √ 41 5 < 1 + √ 2ρ + t 1 - √ 2ρ -t - √ γ 0 < 1 - √ γ 0 + √ 2(1 + √ γ 0 ) √ ρ + (1 + √ γ 0 )t 1 - √ 2ρ -t .
Note that t < t * = √ 2ρ 0 -√ 2ρ implies that the denominator is positive. Moreover

1 - √ γ 0 + √ 2(1 + √ γ 0 ) √ ρ + (1 + √ γ 0 )t = (1 + √ γ 0 )(t -t * ) < 0.
As a consequence,

γ(2s, M) < (4 + √ 41) 2 25 .
Similarly to (2.7) and (2.6), it can be proved that for t > t 0 ,

P c max (2s, M (n) ) ≥ ( 2ρ + t)(2 + 2ρ + t) ≤ c(2ρ)e -nD 3 (2ρ,δ,t) , P c min (2s, M (n) ) ≥ ( 2ρ + t)(2 -2ρ -t) ≤ c(2ρ)e -nD 3 (2ρ,δ,t) , with D 3 (2ρ, δ, t) > 0. Note that t → D 3 (2ρ, δ, t) is continuous and increasing from [t 0 , t * ) ⊂ [0, τ 0 ) onto D 3 (2ρ, δ, t 0 ), D 3 (2ρ, δ, t * ) . Choose D 1 (ρ, δ) ∈ D 2 (2ρ, δ, t 0 ); D 3 (2ρ, δ, t * )
(note that t * and t 0 depend only on ρ and δ) and define t ρ,δ so that D 3 (2ρ, δ, t ρ,δ ) = D 1 (ρ, δ). Therefore P M (n) does not satisfy (SRSR-γ(2s)) with s ≤ ρn

≤ P c max (2s, M (n) ) ≥ 2ρ + t ρ,δ 2 + 2ρ + t ρ,δ + P c min (2s, M (n) ) ≥ 2ρ + t ρ,δ 2 -2ρ -t ρ,δ ≤ 2c(2ρ)e -nD 1 (ρ,δ) ,
which concludes the proof.

Appendix B. Supplement : Deviations for the Rademacher model

In this section we follow the steps of the work [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] to get small deviation inequalities on the extreme eigenvalues of Gram matrices built from the Rademacher law. The paper [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] focuses on the asymptotic distribution of the fluctuations of the extreme eigenvalues, and it proved that the extreme eigenvalues of the sample covariance matrices built from sub-Gaussian matrices asymptotically fluctuate around their limiting values (with proper scaling) with respect to the Tracy-Widom distribution. Their results follow from an interesting estimation of the moments of the fluctuations. While their estimation is interestingly of the right order (namely ε 3/2 ), the authors of [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] did not pursue on giving an upper bound of the constant appearing in their rate function, see Claim Unfortunately, the constant C FS appearing in the rate function is of crucial importance when deriving phase transitions, see Section 2 for instance. Hence, we need to track the proof of [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] in order to provide an upper bound on C FS and its dependence on the ratio ρ of the sizes of the Rademacher matrix. This strenuous hunt necessitates to recast all the asymptotic bounds appearing in [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] into non asymptotic ones as sharp as possible. The benefit of this elementary but non trivial task is the following. It gives, for the first time, an explicit expression of small deviations of extreme eigenvalues of the sample covariance matrices at the sharp rate ε 3/2 . This section is devoted to prove the following result.

P λ M (C) ≥ ( √ M + √ N ) 2 + εN ≤ W 0 (ρ, ε) 1 -ρ M exp(-N W FS (ρ, ε)) P λ 1 (C) ≤ ( √ M - √ N ) 2 -εN ≤ W 0 (ρ, ε) 1 -ρ M exp(-N W FS (ρ, ε))
where ρ = M/N and

W 0 (ρ, ε) := c 0 exp c 0 log 1 + ε 2 √ ρ W FS (ρ, ε) := ρ log(1 + ε 2 √ ρ ) 3 2 C FS (1 + √ ρ) 2
for some universal constants c 0 > 0 and 837 > C FS > 0. Furthermore, for any C > 3242, there exists a constant v := v(ρ, C) > 0 that depends only on ρ = M/N and C such that, for all 0 < ε < √ ρ,

P λ M (C) ≥ ( √ M + √ N ) 2 + εN ≤ v exp -C -1 N ρ 1/4 (1 + √ ρ) 2 ε 3 2 P λ 1 (C) ≤ ( √ M - √ N ) 2 -εN ≤ v exp -C -1 N ρ 1/4 (1 + √ ρ) 2 ε 3 2
.

B.1. Sketch of the proof. The result of [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] is based on a combinatorial proof. Interestingly, this approach is suited for the Rademacher model since, in this case, traces of polynomials of the covariance matrix C can be expressed as the number of non-backtracking paths of given length. In this section, we change notation and we use the notation of the paper [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] to ease readability when referring to this latter. Hence, we consider a Rademacher matrix of size (M × N ) with M < N (referred to as (s × n) with s < n in the rest of this paper). We draw this proof into the following points.

(1) The proof [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] is based on a moment method that captures the influence of the largest and the smallest eigenvalues considering a new centering

C := C -(M + N -2)
2 (M -1)(N -1) .

The authors [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] then use the trace of C 2m + C 2m-1 (resp. C 2m -C 2m-1 ) to estimate the moments of the largest (resp. smallest) eigenvalue. (2) The control of

A m := Etr[ C 2m ] + Etr[ C 2m-1 ] (resp. B m := Etr[ C 2m ] -Etr[ C 2m-1 ]
) is given by a control of traces of polynomials Q n (C) of C. Up to a proper scaling, these polynomials are the orthogonal polynomials of the Marchenko-Pastur law which can be expressed by Chebyshev polynomials U n of the second kind. (3) In the Rademacher model, the aforementioned traces, namely Etr[Q n (C)], are exactly the number Σ1 1 (n) of non-backtracking paths on the complete bi-partite graph that cross an even number of times each edge and end at their starting vertex. This claim can be generalized to general random sub-Gaussian matrices, up to technicalities. (4) To estimate the number of non-backtracking paths Σ1 1 (n), the article [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] begins with a mapping from the collection of non-backtracking paths into the collection of weighted diagrams. Then it provides an automaton which constructs all possible diagrams. The number of diagrams constructed by the automaton ending in s steps is denoted D 1 (s). Proof. We follow Proposition II.2.3 of [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] but we focus on the case (of sample covariance matrices) corresponding to β = 1. In this case, there are three types of transitions from one state to the following one. Let s = 2g + h be the number of steps in the automaton at the end, where h is the number of transition of type 3 and g the number of transition of type 1.

• If h = 0 then the number of ways to order the transitions of the type 1 and 2 is exactly (2g)! g!(g+1)! . Informally, the state of the automaton can be seen as a "thread" made of straight pieces and loops. The total length of this thread changes at each step. These changes of length are encoded by non-negative integers m i . For precise definition of these numbers, see [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] Section II.2 page 103. In the present case, the number of ways to choose the numbers m i is at most 6g-1 4g . The number of diagrams corresponding to a fixed order of transitions and fixed m i is at most (6g -1) 2g (indeed, the following state is then determined by choosing an edge and there are 6g -1 edges in the diagram). As in [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF], we deduce that an upper on D 1 is

(2g)! g!(g + 1)! 6g -1 4g (6g -1) 2g = 2g(6g -1)!(6g -1) 2g g!(g + 1)!(4g)! .
Using Lemma 10, this number is upper bounded by e 2+1/60 π g (6g -1) 8g-1/2 g g+1/2 (g + 1) g+3/2 (4g) 4g+1/2 .

Writing θ = (6g-1) 8g-1/2 g g+1/2 (g+1) g+3/2 (4g) 4g+1/2 in exponential form, we get θ = exp 2g log g + g 8 log(6) -4 log(4) -3 log g -1 2

(3 log 2 + log 3) + γ(g) ,

with γ(g) = 8g - 1 2 log 1 - 1 6g -g + 3 2 log 1 + 1 g .
Note that γ is non decreasing on (1, ∞) and goes to -7 3 when g → ∞. Therefore, the number of diagrams in this case is upper bounded by (recall that s = 2g here)

1 π e 7/2 log(3)-3/2 log(2)+1/60-1/3 (40.5) s-1 s s-2 ≤ 3.84(40.5) s-1 s s-2 .

• If g = 0 then there are only transitions of the third kind. The number of ways to choose the numbers m i is at most 2h-1 h-1 . The number of diagrams corresponding to a fixed order of transitions and fixed m i is at most (3h -1) h (indeed, recall that the number of edges of the diagram is 3h -1). We deduce that an upper bound on D 1 is

(2h -1)! h!(h -1)! (3h -1) h .
Note that this number is 2 when h = 1. For h ≥ 2, using Lemma 10, this number is upper bounded by e 1/12 √ 2π

(2h -1) 2h-1/2 (3h -1) h h h+1/2 (h -1) h-1/2 .
Once again, we write θ = (2h-1) 2h-1/2 (3h-1) h h h+1/2 (h-1) h-1/2 in exponential form. This yields

θ = exp h - 1 2 log h + 2 log(2) + log(3) (h -1) + 3 2 log 2 + log(3) + γ(h) , with γ(h) = 2h - 1 2 log 1 - 1 2h + h log 1 - 1 3h -h - 1 2 log 1 - 1 h .
Note that γ is non increasing on (2, h * ) and non decreasing on (h * , ∞) for some h * > 2. Therefore, γ(h) is bounded by max(γ(2), lim h→∞ γ(h)). This yields γ(h) ≤ -0.33 for all h ≥ 2. Finally, the number of diagrams in this case is upper bounded by (recall that s = h here) e 1/12 √ 2π e 3/2 log(2)+log(3)-0.33 (12) s-1 s s-1/2 ≤ 2.65(12) s-1 s s-1/2 .

• If h = 0 and g = 0 then the number of ways to order the transitions of the three types is exactly

2g + h h (2g)! g!(g + 1)! = (2g + h)! h!g!(g + 1)! .
The number of ways to choose the numbers m i is at most 6g+2h-1 2g+h-1 . The number of diagrams corresponding to a fixed order of transitions and fixed m i is at most (6g + 3h -1) 2g+h (indeed, recall that the number of edges of the diagram is 6g + 3h -1).

We deduce that an upper bound on D 1 is

(2g + h)! h!g!(g + 1)! 6g + 2h -1 2g + h-1 (6g + 3h -1) 2g+h .
Using the fact that s = 2g + h and Lemma 10, this number is bounded by

e 131/126 (2π) 3/2 s s+1/2 (3s -h -1) 3s-h-1/2 (3s -1) s h h+1/2 g g+1/2 (g + 1) g+3/2 (s -1) s-1/2 (2s -h) 2s-h+1/2 . Let t = h/s ∈ [1/s, 1 -2/s] so that an upper bound is e 131/126 (2π) 3/2 s s+1/2 (3s -ts -1) 3s-ts-1/2 (3s -1) s (ts) ts+1/2 (s 1-t 2 ) s(1-t)/2+1/2 (s 1-t 2 + 1) s(1-t)/2+3/2 (s -1) s-1/2 (2s -ts) 2s-ts+1/2 .
Once again, we write this in exponential form and get e 131/126 (2π) 3/2 exp s log s -

5 2 log s + β(t)s + α(t) + γ(s, t) , with α(t) = 2 log 2 - 1 2 log(3 -t) - 1 2 log t -2 log(1 -t) - 1 2 log(2 -t), β(t) = (3 -t) log(3 -t) + log(3) -t log t -(1 -t) log(1 -t) + log(2)(1 -t) -(2 -t) log(2 -t), γ(s, t) = (3 -t)s - 1 2 log 1 - 1 (3 -t)s + s log 1 - 1 3s - 1 2 s(1 -t) + 3 log 1 + 2 s(1 -t) -s - 1 2 log 1 - 1 s .
• We focus first on β. This function is non decreasing on (0, t * ) and non increasing on (t * , 1),

with t * = 3 2 - √ 57 6
≈ 0.24. Therefore, it reaches its maximum at t * . Computing it yields β(t) ≤ 3.985 for all t ∈ (0, 1).

• We focus now on α. This function is non increasing on (0, t ) and non decreasing on (t , 1) with t ∈ (0, 1). Recall that t ∈ (1/s, 1 -2/s). Therefore, α(t) ≤ max(α(1/s), α(1 -2/s)). Computing these two values and using the fact that s ≥ 3 leads to α(t) ≤ α(1 -2/s) for all t ∈ (1/s, 1 -2/s). Consequently

α(t) ≤ 2 log s - 1 2 log 2 + 2 s - 1 2 log 1 - 2 s - 1 2 log 1 + 2 s .
• Let's turn to γ. Recall that t ∈ (1/s, 1 -2/s). Dealing separately with the two terms

(3 -t)s -1 2 log 1 -1 (3-t)s and 1 2 (s(1 -t) + 3) log(1 + 2 s(1-t) ) yields γ ≤ 3s - 3 2 log 1 - 1 3s -1 + s log 1 - 1 3s - 1 2 (s + 2) log 1 + 2 s -1 -s - 1 2 log 1 - 1 s .
Going back to the number of diagrams in this case, it is bounded by e 131/126 (2π) 3/2 exp s log s -

1 2 log s + 3.985s + δ(s) , with δ(s) = - 1 2 log 2 + 2 s - 1 2 log 1 - 2 s - 1 2 log 1 + 2 s + 3s - 3 2 log 1 - 1 3s -1 + s log 1 - 1 3s - 1 2 (s + 2) log 1 + 2 s -1 -s - 1 2 log 1 - 1 s .
This function is non decreasing on (3, ∞) and goes to -4 3 -log 2 2 ≤ -1.67 when s goes to ∞. Therefore, there are at most e 131/126-1.67 (2π)

(n) ≤ C 0, Σn(M N ) n/2 exp C Σ(1 + M/N )n 3/2 √ M
where C 0, Σ = 160.4 and C Σ = 13.3. As a consequence,

E[tr[Q] n (C)] ≤ C 0, Σ(M N ) n/2 n exp C Σ(1 + M/N ) n 3/2 M 1/2 .
Proof. The number of diagrams is D 1 (s) for 1 ≤ s ≤ n. The number of ways to choose the vertices on a diagram constructed in s steps by the automaton is at most

1 2 (M N ) n/2 (1 + M/N )(M -1/2 + N -1/2 ) 2s-2 + (1 -M/N )(M -1/2 -N -1/2 ) 2s-2 ,
see [25, page 117]. The number of ways to choose the weights on a diagram constructed in s steps by the automaton is at most [START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] (3s + 1)

(3s -2)! n -3s + 1 2 + 3s -2 3s-2
.

We deduce that the number Σ1 1 (n) of non-backtracking paths is at most

Σ1 1 (n) ≤ 1 2 (M N ) n/2 1 + M N T 1 + 1 - M N T 2
where 2(s-1) (3s + 1)(n + 3s -3) 3s-2 s s-1/2 (3s -2)!2 3s-2 using Lemma 7. Invoke Lemma 10 to get that (2(s -1))! n 3(s-1)

T 1 := n s=1 D 1 (s)(M -1/2 + N -1/2 ) 2s-2 (3s + 1) (3s -2)! n -3s + 1 2 + 3s -2
(3s + 1)(n + 3s -3) 3s-2 s s-1/2 (3s -2)!2 3s-2

≤ n e s+1/12 2 3s-2 (3s + 1) 2s -2 3s -2 1 + 3s -3 n 3s-2 (2s -2) 2s-2 s s-1/2 (3s -2) 3s-2

≤ ne 1/12 2s -2 3s -2 2 3s-2 (3s + 1) (2s -2) 2s-2 s s-1/2 (3s -2) 3s-2 e s .

But 2 3s-2 (3s + 1) (2s-2) 2s-2 s s-1/2 (3s-2) 3s-2 It may be shown that there exists s * > 2 such that g is positive on (1, s * ) and negative on (s * , ∞). Therefore, g is strictly concave on (s * , ∞) and its curve is below its tangents, which write y = g (s 0 )(s -s 0 ) + f (s 0 ). For s ∈ [1, s * ], g(s) ≤ g(1) = 2 log 2. As a consequence, we are looking for the point s 0 ∈ (s * , ∞) such that the tangent at s 0 goes through the point (1, 2 log 2).

This tangent goes through the point (1, g(s 0 ) + (1 -s 0 )g (s 0 )). Set h(s) = g(s) + (1 -s)g (s). This function is non decreasing and there is a unique point s 0 ∈ (s * , ∞) such that h(s 0 ) = 2 log 2.

It may be shown that s 0 ∈ (39.66; 39.67). As g is non increasing on this interval, g (s 0 ) ≤ g (39.66) ≤ 0.013. This leads to g(s) ≤ 0.013(s -1) + 2 log 2.

Then (2(s -1))! n 3(s-1)

(3s + 1)(n + 3s -3) 3s-2 s s-1/2 (3s -2)!2 Observe that the maximum of -ax 4 + bx 3 is 27b 4 256a 3 . We deduce that

-c 2 n 2 m + C M,N 2

Theorem 1 .

 1 If M satisfies this asymmetric Restricted Isometry Property with RICs such that (SRSR-γ(2s)) γ(2s, n, p) := 1 + c max (2s, M) 1 -c min (2s, and Robust Sparse Recovery (SRSR) property of order s holds with positive constants C and D depending only on c min (2s, M) and c max (2s, M).

  (a) and (b) of Point 2 in [25, Corollary V.2.1].

Proposition 6 .

 6 Let N > M ≥ 54 and consider C := XX where X ∈ {±1} M ×N with i.i.d. Rademacher entries then

B. 2 .Lemma 7 .

 27 Lemma 7 provides an upper bound on this quantity. Summing over s, it yields an upper bound on Σ1 1 (n), see (B.1) in Lemma 8. (5) In the Rademacher model, Σ1 1 (n) is the expectation of the trace of Q n . Hence, we deduce an upper bound on these traces. (6) Using Markov inequality and optimizing over the parameters, we deduce small deviation inequalities on the smallest and largest eigenvalues. Number of diagrams. Recall that D 1 (s) denotes the number of diagrams constructed by the automaton ending in s steps. The description of the automaton can be found in [25] Section II.2 page 101. It holds, for all s ≥ 1, D 1 (s) ≤ C 0,D C s-1 D s s-1/2 where C 0,D and C D can be chosen as C 0,D = 8.31 and C D = 53.8.

D 1 T 1 ≤

 11 (s)(M -1/2 -N -1/2 ) 2s-2 (3s + 1We can bound each term. It reads as follows. C 0,Dn s=1 C s-1 D s s-1/2 (M -1/2 + N -1/2 ) 2s-2 (3s + 1

e 4 + 99s 3 -

 43 s ≤ exp(s + f (s)) where f (s) = (3s -2) log(2) + (2s -2) log(2s -2) + log(3s + 1) + s -1 2 log(s) -(3s -2) log(3s -2).Some elementary computations give the following:f (s) = 1 2 log s + (5 log 2 -3 log 3)s + 3 log 3 -4 log 2 + (2s -2) log 1 -1 s -(3s -2) log 1 -2 -3 log 3)s + 3 log 3 -4 log 2 + g(s), with g(s) = 1 2 log s + (2s -2) log 1 -1 s -(3s -2) log 1 -21s 2 + 11s + 2 2s 2 (s -1)(3s -2)(3s + 1) 2 .

3s- 2 ≤≤ 19 . 4 .Lemma 9 .n(- 1 )(- 1 )ss

 2194911 ne 1/12 2 3 exp (5 log 2 -3 log 3 + 1.013)s + 3 log 3 -2 log 2 -0.013 ≤ ne 1/12 2 3 exp(1 + 3 log 2) exp (5 log 2 -3 log 3 + 1.013)(s -1)≤ 19.3 n (3.27) s-1 .As a consequence,T 1 ≤ 19.3C 0,D n n s=1 1 (2(s -1))! 1.81(1 + M/N )n 3/2 3C 0,D n exp 1.81 C D (1 + M/N ) Bound on the traces. It holds that (B.2) E[tr[ C 2m ]] + E[tr[ C 2m-1 ]] ∨ E[tr[ C 2m ]] -E[tr[ C 2m-1 ]] ≤ ∆ m where Rad (1 + M/N ) 4 m 3 M 2 ,andC 0,Rad = 594C 0, Σ = 95, 278 C Rad = 355.7C 2 D = 830, 415.Proof. Invoke Lemma IV.1.1 page 115 in[START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] and Lemma 8 to get that expC Σ(1 + M/N ) n 3/2 M 1/2 . (B.3) Set s := (M -2) 2 (M -1)(N -1) . For m ≥ 1, let A m = E[tr[ C 2m ]] + E[tr[ C 2m-1 ]].Following pages 95-96 in[START_REF] Feldheim | A universality result for the smallest eigenvalues of certain sample covariance matrices[END_REF] yields:E[tr[U 2n-1 ( C)]]. (B.4) Using the fact that V k,s = U k + √ sU k-1 , it holds k s k/2 E[tr[V 2n-k,s ( C)]] k s k/2 E[tr[V 2n-k-1,s ( C)]].Note that the expectation E[tr[V k,s ( C)]] is non-negative. Indeed, one can check that, up to a multiplicative constant,E[tr[V k,s ( C)]] = E[tr[Q k ( C)]] = Σ1 1 (k). It follows that k E[tr[V 2(n-k),s(C)]] + s n M ) k E[tr[V 2n-2k-1,s ( C)]] (B.5) Invoke (B.3) to get with C M,N = C Σ(1 + M/N ),

3 /2 n 3/ 2 M 1 / 2 ≤

 3212 C Rad (1 + M/N )

  Proposition 2.2.17] that the converse is true for any matrix M. If the SRSR recovery ( 1 -SRSR) or ( 2 -SRSR) (with η = 0) holds then necessarily n ≥ c 1 s log(c 2 p/s) for some universal constants c 1 and c 2 . Since we have lower and upper bounds of the same flavor, it seems that the condition(1.7

		for
	instance. It has been proved that (FR-c(2s)) holds with overwhelming probability for a large class
	of random matrix models as soon as the interplay between sparsity s, number of measurements n
	and number of unknown parameters p satisfies
	(1.7)	n ≥ c 1 s log(c 2 p/s)
	for some universal constants c 1 and c 2 (that might depend on the random matrix model). It should
	be mentioned that finding deterministic matrices satisfying (FR-c(2s)) with n = O(s log(p/s)) is
	one of the most prominent open problem in Compressed Sensing, see [27] for instance. Furthermore,
	it has been shown in [18,

(λ 1 -(1 + √ ρ) 2 ) ≥ n 2/3 ρ1/6 (1 + √ ρ)

4/3 t .

Acknowledgments. We would like to thank Sasha Sodin for his patient answers to our many questions. Moreover, this paper greatly benefited from the comments of anonymous referees on previous version of this paper.

The bound on B m := E[tr [ C 2m ]] -E[tr[ C 2m -1 ]] follows the same lines. The minus in front of E[tr[ C 2m -1 ]] change the line (B.4) to its opposite. The change of indices k leads to the term s k+1/2 E[tr[V 2(n-k-1),s ( C)]] in (B.5). Since we uniformly bound n -k -1 by n in the rest of the proof and s 1/2 < 1, we get the same result. B.5. Small deviation on the largest eigenvalue. Observe that

,

Using Markov inequality, we deduce that

Invoke Lemma 9 to get that

, for all m ∈ N. Using that M ≥ 54 and log(1 + x) ≤ x, we get

where ρ = M/N and

Using that ρ ≤ 1, we derive that

for some universal constant c 0 > 0. We deduce the following useful bound (B.7)

For ε ≤ √ ρ we can deduce a small deviation inequality as follows. Observe that for any η > 0 one can pick a constant c 1 (η) > 0, that depends only on η, such that for all M ≥ 1, it holds M ≤ c 1 (η) exp(ηM ). Note that log(3/2) ε √ ρ ≤ log 1 + ε 2 √ ρ and set

We deduce that for any C > V Rad ≈ 3242 there exists a constant v := v(ρ, C) > 0 that depends only on ρ = M/N and C such that, for all 0 ≤ ε ≤ √ ρ,

.

B.6. Small deviation on the smallest eigenvalue. Observe that

for all N > M ≥ 54. Set g(x) := x 2m -x 2m-1 and note that g(x) = f (-x). It holds

and we recover an upper bound of the form (B.6) for which Lemma 9 can also be applied and we get that

, Proof. See [START_REF] Abramowitz | Handbook of mathematical functions[END_REF] Eq. 6.1.38.

Lemma 11. It holds, for all 1 ≤ n ≤ m,

Proof. If n = m then the result is clear. Otherwise, using Lemma 10, one has

The last term in the right hand side can be upper bounded thanks to the identity x log(1

Let x = n/m and observe that x ≤ 1 -1/m. It holds that the middle term of the aforementioned right hand side can be expressed as

If x ≤ 0.99995 then, using that log(z) ≤ z/e, we have SD is with CMLA, ENS Cachan, CNRS, Université Paris-Saclay, 94235 Cachan, France. E-mail address: sandrine.dallaporta@cmla.ens-cachan.fr


Olivier Sébastien
email: olivier.sebastien@univ-reunion.fr

Fanilo Harivelo
email: fanilo.harivelo@univ-reunion.fr

Didier Sébastien
email: didier.sebastien@univ-reunion.fr

Using general public connected devices

published or not. The documents may come

Introduction

The ten last years saw the dramatic increase of wireless communication and mobile personal devices, that is to say digital terminals that are attached to one person rather than a place (like a home or office phone): mobile phone of course (including smartphones), tablets, laptops, etc. This brought a new opportunity in risk management that can be summed up briefly: if one of these devices is detected in a place where a disaster occurred, there are a lot of chances that there might be people to rescue in that particular place.

Thus, the question is to define ways of identification of such mobile terminals, according to the various technologies they embed. Indeed, most advanced ones provide lots of possibilities to retrieve their users location, such as Android-powered smartphones, which can track and report continuously to the Google Location History service all the places they went [1]. But this approach might not be sufficient because not everyone owns such terminals and of course because of privacy issues.

Detection process overview

The proposal consists in relying on autonomous equipment such as drones or robots [START_REF] Aprille | Indoor Autonomous Navigation of Low-Cost MAVs Using Landmarks and 3D Perception[END_REF] to roam a disaster scene in order to draw a map of possible victims location when no communication infrastructure remains active, as shown in Figure 1. In fact, the idea is more to guide the rescue team to place where chances are higher to find a survivor than to locate him with accuracy and certitude. This approach is complementary to the existing ones and does not aim at replacing them.

To achieve this, the autonomous equipment is fitted with antennas which specifications will be discussed thereafter. It is sent on the terrain looking for response to its broadcast requests. Once a response is detected, identification is attempted to characterize it and finally the GPS position along with all the metadata (time, signal strength, network type…) is sent to the local command centre. The latter thus having information to take appropriate decisions.

Figure 1: overview of the detection principle

Let us focus on the detection part. We are particularly interested in the initial response a connected device gives. Actually, most of them are designed to look for a network medium as soon as they are powered and to perform continuously this search while a connection is not established.

Devices characterization

The principle shown before is possible because the general public now owns a lot of digital wireless devices. Those terminals may be very different in term of usage of course but in term of networking specifications too. That is why we need to list them along with their connectivity.

. Connected objects

Connected objects are more and more common in nowadays society. They consist in very different shaped useful tools to communicate among users or simply ease actual processes. Table 1 presents the main devices and the features relevant to our subject. Most of them can be linked to the presence of at least a single user, regarded to the service they are providing. As humans tend to live in groups, a living space is susceptible to emit a wide spectrum of signals. That is why it is relevant to characterize them quantitatively and qualitatively. The identification of areas emitting a large range of signals from several devices can be a great key to guide rescuers. Of course, as it will be detailed in next part, waves propagation is very different. Thus, several steps could be defined to focus first on low frequency waves, then refine the received information by tracking shorter range signals. Qualitatively, the signal can be characterized by the kind of service offered to define the type of device. For instance the service offered by an ear-flap is more strongly linked to its user than a laptop. That is why it would be more relevant to prioritize researches where this type of device is detected.

. Networks

We present hereafter (Table 2) the commonly available wireless technologies in mobile devices: While Bluetooth exposes interesting feature related to low energy consumption, its short transmission range and weak radiated power limit its use in disaster recovery. WiFi and GSM/UMTS suit best emergency situation in which a robust search and rescue network (RSN) must be quickly operational. Indeed, the potential presence of obstacles coupled with the blind search and scan of victims and survivors impose a high penetration capability of the transmission despite signal attenuation and interferences. Mentioned technologies have proven efficiency in similar situations. Portable Disaster Recovery Network [START_REF] Narayanan | A joint network for disaster recovery and search and rescue operations[END_REF] introduces a network architecture composed of one or more Access Points, Gateway node, DRN Phones dropped from an helicopter and on-site Command Center. Communications use standard wireless and mobile technology such as WiMAX, WiFi, 3G, 2G, or 4G.

Another area pertaining the positioning or location of individuals or objects using WiFi is Device-free Passive (DfP) [START_REF] Moussa | Smart Devices for Smart Environments: Device-free Passive Detection in Real Environments[END_REF] localization. It consists in detecting, identifying and tracking entities that do not carry any device by exploiting indoor WiFi network. A radio map is constructed initially. Then, changes in the environment are detected by monitoring and processing received signals. Indeed, people and entities disturb the pattern of radio waves. Radio planning in mobile networks has to consider obstacles, building and wall traversal as the main part of the mobile traffic is indoors [START_REF] Tolstrup | Indoor Radio Planning: A Practical Guide for GSM, DCS, UMTS and HSPA[END_REF]. The base station and the handset perform well despite the varying wireless conditions (attenuation, signal absorption, interferences, …) thanks to power control. The nature and characteristics of the material in-between, are factors that determine those conditions. For example, authors of [START_REF] Antonini | Shielding Effects of Reinforced Concrete Structures to Electromagnetic Fields due to GSM and UMTS Systems[END_REF] study the effects of the presence of multiple reinforced concrete walls on the shielding effectiveness in GSM and UMTS systems. Two wall configurations are considered: a room between two 0.35m-width reinforced concrete walls and a room between a 0.35m-width ceiling and a perfectly conductive floor. An average attenuation of 5 dB has been found. Thus, the communication is still feasible. While a WiFi network is easily deployable GSM/UMTS-compatible devices are more widespread (the are currently about 3 billions phones). On the other hand, GSM and UMTS requires the support of a heavy infrastructure. The coverage of the whole disaster terrain may be too costly and time-consuming to be feasible within a few hours after the disaster event (more than 50% of deaths occurred in this period [START_REF] Narayanan | A joint network for disaster recovery and search and rescue operations[END_REF]). We suggest a combined approach: the deployment of both small scale and localized WiFi networks and GSM/UMTS network.

Terrain behaviour

One cannot at the theoretical normative aspects because in real conditions, various non-controllable aspects must be taken into account. Therefore our goal in this part is to deal with the constraints that can be encountered and the way to deal with them.

WiFi networks cartography concerns

First of all, the WiFi networks cartography is an operation that must be accomplished before a disaster occur. There is a lack of strategy concerning this point: first of all, it raises legal issues concerning privacy protection and then it is difficult to determine who should be in charge of this action, either public authorities or private companies [START_REF] Blitz | The Right to Map (and Avoid Being Mapped): Reconceiving First Amendment Protection for Information-Gathering in the Age of Geotagging and Google Earth[END_REF]. Technically speaking, many solutions exist to achieve the mapping. Of course, the goal is to make the process the more automatic possible. Once again, our proposal consists in relying on autonomous drones, as defined in [START_REF] Wang | Feasibility study of mobile phone WiFi detection in aerial search and rescue operations[END_REF]. They are now able to crawl indoor [START_REF] Aprille | Indoor Autonomous Navigation of Low-Cost MAVs Using Landmarks and 3D Perception[END_REF] and provided they are equipped with the right interfaces, they can easily map the buildings.

WiFi mapping also raises the question of the efficiency of the pre/post-disaster comparison. Lots of work has already been done in this field [START_REF] Kyrgyzov | [END_REF], for instance by studying automatically the difference between satellite pictures of an area taken before and after a crisis. The main issue is the reliability of the interpretation: there are reasons for the environment to change without implying the occurrence of a disaster. Unless if updates are made regularly, and under the supervision of a human control it is difficult to ensure that the process will deliver a high rate of detection. There are many ways to address this context. The first one consists in multiplying the number of network devices. We are in a favourable context as this is the case since Wireless Local Area Networks (WLAN) have started to become common a decade ago. The second trend is related to the tasks that can be automated by the devices themselves: since they are getting smarter, the cartographic update can be scheduled and sent to a server located far from the area, which is a requisite in any situation.

GSM/UMTS network scan concerns

Lots of parameters can alter the mobile network scan as evoked by [START_REF] Zorn | A novel technique for mobile phone localization for search and rescue applications[END_REF] and [START_REF] Zorn | A power saving jamming system for E-GSM900 and DCS1800 cellular phone networks for search and rescue applications[END_REF] in the context of the I-LOV project. Most of them are related to the energy consumption of the whole process in general and of the devices on the terrain in particular. Indeed, battery life is a major issue, especially for smartphones, which tend to have a more or less 24 hours autonomy, given all the features they have. The solution here depends on the manufacturers policy. They tend to implement energy-saving features, which disable dynamically some interfaces when they are not used. Therefore, situation should be better in a near future. Moreover, we made the hypothesis that no fixed infrastructure was available after the disaster. This allows the area to be clear of "pollution" from a radio point of view. We believe this is mostly the case when a major crisis occurs. But we must keep in mind that if the infrastructure remains active, public authorities along with network carriers have to deal with this particular point, either by shutting it down selectively or by using jamming devices as exposed by [START_REF] Zorn | A power saving jamming system for E-GSM900 and DCS1800 cellular phone networks for search and rescue applications[END_REF].

From the drone/robot crawling perspective, recent research [START_REF] Aprille | Indoor Autonomous Navigation of Low-Cost MAVs Using Landmarks and 3D Perception[END_REF] proved that the autonomous navigation should not be an issue. However, what need to be assessed is the precision of the measurement, especially as far as the geographical positioning is concerned. Indeed, Global Navigation Satellite System (GNSS) is the main resource that may be used. This raises first the question of the selection of the best system (GPS, Glonass, …) for a given place and then the lack of local triangulation assistance can limit the accuracy. A possible solution for this particular point consists in adding an inertial system to the drone/robot and to rely on a synchronised evolution of a fleet instead of an individual device. Thus, each drone/robot is able so compare its measured position to the one estimated from the other ones crawling in the neighbourhood.

Conclusion

The goal of this article was to present a contribution in the detection of victims after a disaster by relying on popular connected devices. They have the advantage to be very common and always located on the terrain. Our proposal blends two approaches that can exist separately but which may dramatically ease victims rescue by allowing a faster response time and by restricting the area where to operate. The next step consists in leading terrain experimentations to acquire data to validate the approach. Indeed, we were not able for the moment to anticipate some behaviours. For instance, a typical mobile phone is supposed to look for a network while none is detected. This search requires the device to use full power, which drain the battery a lot. That is why some manufacturers may decide of a time out to spare it. We thus have to check if this kind of policy is still compliant to the aim we try to reach.

Another aspect concerns the adaptation of the approach considering the geographical area. Of course, it has reasonable chance to work in lots of places with an average standard of life. However, disasters can strike everywhere. So, the question is to determine how such a system can behave in developing countries with emerging networks infrastructure.

Table 1 laptop mobile phone phone smart watch activity tracker ear-flap wireless mouse gamepad Service

		various	various	talk remotely	connection	log moves	connection	computer	console
					with		with	control	control
					smartphone		smartphone
	Usage	office/home	office/home	office/home	home	office/home	office	office/home	home
	Wireless	wifi,	3G, wifi,	DECT/GAP	bluetooth	bluetooth	bluetooth	bluetooth	bluetooth
	Technology	bluetooth	bluetooth

Table 2 Bluetooth v2.0 EDR (class 2) WiFi (IEEE 802.11g) GSM UMTS

 2

	Frequency Band	2.4 GHz	2.4 GHz	900 MHz/1800 MHz	2 GHz
	Max. data rate	3 Mbits/s	54 Mbits/s	9.6 kbits/s	2 Mbits/s
	Max. output power of the handset	2.5 mW (4 dBm)	100mW (20 dBm)	1 W(30 dBm) for 1800 MHz and 2 W(33 dBm) for 900MHz	125 mW(21 dBm) -251 mW (24 dBm)
			Approx. 38 m (interior)
	Max. range	10 m	-Approx. 140 m	35 km	Approx. 8 km
			(exterior)