Gilles Puy

Mike E Davies

Rémi Gribonval

Recipes for stable linear embeddings from Hilbert spaces to R m

Keywords: Compressed sensing, restricted isometry property, box-counting dimension

We consider the problem of constructing a linear map from a Hilbert space H (possibly infinite dimensional) to R m that satisfies a restricted isometry property (RIP) on an arbitrary signal model, i.e., a subset of H. We present a generic framework that handles a large class of low-dimensional subsets but also unstructured and structured linear maps. We provide a simple recipe to prove that a random linear map satisfies a general RIP with high probability. We also describe a generic technique to construct linear maps that satisfy the RIP. Finally, we detail how to use our results in several examples, which allow us to recover and extend many known compressive sampling results.

I. INTRODUCTION

T HE restricted isometry property (RIP) is at the core of many theoretical developments in compressive sensing (CS). It allows ones to show that sparse signals can be "captured" by few linear and non-adaptive measurements and recovered by non-linear decoders [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF]. In a finite dimensional space, a matrix A ∈ R m×n satisfies the RIP on a general set S ⊂ R n , if there exists a constant δ ∈ (0, 1), such that for all x ∈ S,

(1 -δ) x 2 2 Ax 2 2 (1 + δ) x 2 2 .
(

) 1
Random matrices with independent entries drawn from the centered Gaussian distribution with variance m -1 are examples of matrices that satisfy the RIP with high probability for many low-dimensional sets such as S = Σ 2k , associated to k-sparse signals [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF], S = Σ 2r , associated to rank-r matrices [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of random measurements[END_REF], or S = {x 1x 2 |x 1 , x 2 ∈ Σ}, associated to a compact Riemannian manifold Σ [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF]. In these scenarios, the RIP holds for a number of measurements m essentially proportional to a measure of intrinsic dimension of S.

In this work, we extend the construction of linear maps that satisfy the RIP in a finite-dimensional ambient space to linear maps that satisfy the RIP on subsets of a possibly infinitedimensional space. This extension of the CS theory to infinitedimensional spaces is important to properly apply CS in an

The RIP is a very convenient tool when one wants to prove that a signal x ∈ H can be reconstructed from its compressed measurements Ax when it belongs to a given model set, i.e., x ∈ Σ ⊂ H. If A satisfies the RIP on the set of 2k-sparse vectors then every k-sparse vector x can be accurately and stably recovered from its noisy measurements Ax + n by solving the Basis Pursuit problem [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF]. For more general low-dimensional signal models Σ, one can prove that a signal x ∈ Σ can be stably recovered from its compressed measurements if the matrix A satisfies the RIP on the secant set S = Σ -Σ, [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF], [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems[END_REF], i.e., if there exists a constant δ ∈ (0, 1) such that

(1 -δ) x 1 -x 2 2 2 A(x 1 -x 2 ) 2 2 (1 + δ) x 1 -x 2 2 2 .
for all x 1 , x 2 ∈ Σ. When this condition is satisfied, we say that the matrix A stably embeds the set Σ in R m .

Let us recall that the secant set of Σ is defined as

Σ -Σ := y = x 1 -x 2 x 1 , x 2 ∈ Σ .
One can remark that the above condition for stable recovery is equivalent to

sup z∈S(Σ) Az 2 2 -1 δ, (2)
where

S(Σ) := z = y/ y 2 y ∈ (Σ -Σ) \ {0}
is the normalised secant set of Σ. This indicates that the set of interest to prove that a matrix A stably embeds the set Σ is not directly Σ, but rather its normalised secant set S(Σ).

From now on, we concentrate on proving a generalised version of (2) for an arbitrary set S lying on the unit sphere in the ambient space. If one wants to prove that a matrix or, more generally, a linear map stably embeds a set Σ, one just needs to substitute S(Σ) for S in the following results.

In this paper, we consider that the ambient space is an infinite-dimensional Hilbert space denoted by H. The inner product in H is denoted by •, • and the associated norm by

• . Vectors in H are given a bold letter while vectors in R n are given a regular letter. We denote by S the unit sphere in H. We assume everywhere S ⊂ S: x = 1 for all x ∈ S.

B. Measuring the dimension of S

All the developments in this work are based on the assumption that S has a small intrinsic dimension. In the literature, several definitions of dimension exist. The reader can refer to, e.g., the monograph of Robinson [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF], for an exhaustive list of definitions. In an infinite-dimensional space, one should be careful with the definition of dimension used. Indeed, as described in [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF], there are examples of sets for which no stable linear embedding to a finite dimensional space exists even though their dimension is finite (according to some definition). Therefore, there is no hope to construct a linear map that satisfies the RIP for these sets.

In this paper, we use the upper box-counting dimension as our measure of dimension. The upper box-counting dimension is also at the centre of most of the developments in [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF].

Definition I.1 (Covering number). Let > 0. The covering number N S ( ) of S is the minimum number of closed balls of radius , with respect to the norm • , with centres in S needed to cover S. The set of centres of these balls is a minimal -net for S. From the above definition, one can remark that if d > dim(S) then there exists S > 0 such that N S ( )

-d for all S . In this paper, we make the following assumption on S. Assumption A. The set S ⊂ S has a finite upper box-counting dimension dim(S) which is strictly bounded by s 1: dim(S) < s.

Therefore, there exists a model-set dependent constant S ∈ (0, 1/2) such that N S ( )

-s for all S .

In many well-behaved cases, the upper-box counting dimension of the normalised secant set S = S(Σ) of Σ is simply twice the upper-box counting dimension of Σ (or Σ ∩ S if Σ is not bounded). For example, the set of normalised k-sparse vectors in R n has dimension k and its secant set has dimension 2k. The same results holds for low-rank matrices and lowdimensional manifolds. However, this is not always the case as we will see in Section V-B.

C. Contributions and organisation of the paper

This work has four main contributions.

• First, given a set S that satisfies Assumption A and a random linear map L : H → R m , we factorise the proof of the RIP for L on S into a small number of steps. We separate the steps that are problem-specific from the ones that are common to most problems and do not need to be repeated every time. This allows us to provide a simple recipe for the proof of the RIP, with techniques similar to those of, e.g., [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], [START_REF] Talagrand | Majorizing measures: the generic chaining[END_REF]- [START_REF] Dirksen | Tail bounds via generic chaining[END_REF]. This is the subject of Section II. • Second, given an arbitrary set S that satisfies Assumption A, we propose a generic construction of linear maps that satisfy the RIP on S. This construction is made of two steps. In the first step, we show that one can always find a finite-dimensional subspace of large but finite dimension that accurately approximates S. We then use this subspace to build a linear functional that maps the vectors in S into finite but potentially large dimension while preserving their norm to a prescribed accuracy. The second step consists in reducing the embedding dimension further with a random matrix. This construction is detailed in Section III. • Third, we show how to use the developed techniques to recover and extend many known CS results. In particular, we show that our recipe is general enough to handle structured measurement strategies such as the ones proposed in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF], [START_REF] Chen | Exact and stable covariance estimation from quadratic sampling via convex programming[END_REF]. These examples are presented in Section IV.

• Fourth, we show that while it is sufficient to have a set S of finite upper-box counting dimension to guarantee the existence of linear maps that have the RIP on S, this condition is not necessary. This fact is discussed in Section V-B. We discuss related works in Section V and conclude in Section VI. All technical proofs can be found in the appendices.

II. RECIPE TO PROVE THAT THE RIP HOLDS

In this section, we give a generic recipe to prove that a random linear map L : H → R m preserves the norm of all vectors in the set S ⊂ S.

We suppose that L is built by drawing at random m vectors (l 1 , . . . , l m ) in H m using a probability measure µ on H m :

L : H -→ R m x -→ ( l i , x ) 1 i m . (3)
Notice that L is a continuous linear map.

In the following, we start by introducing a generalised form of RIP. Then we detail generic properties of the probability measure µ which are sufficient to prove that L preserves the norm of all vectors in S with high probability, provided that m is sufficiently large. Finally, we give a recipe to show that a random linear map preserves the norm of all vectors in S with high probability.

A. Generalised form of the RIP

Let us come back to the usual form of the RIP (1), which involves the Euclidian norms in the ambient spaces. First, we notice that it can be rewritten in the following equivalent form:

Ax 2 2 -x 2 2 δ x 2 2 .
(4)

Second, we remark that for typical random matrices A satisfying this RIP, one has E Ax

2 2 = x 2 2
. This property is satisfied, e.g., for random matrices A ∈ R m×n whose entries are independent Gaussian variables with zero-mean and variance 1/m, for ±1/ √ m Bernoulli random matrices, or for (rescaled) sensing matrices constructed by selecting independently m vectors from an orthonormal basis using the uniform distribution. For all these cases, inequality (4) becomes

Ax 2 2 -E Ax 2 2 δ x 2 2 . (5)
In this form, we see that the right-hand side of (5) characterises how much Ax 2 2 deviates from its mean. In [START_REF] Adcock | Breaking the coherence barrier: a new theory for compressed sensing[END_REF], this deviation is proportional to x 2 2 , the square of the Euclidean norm in the ambient space. We replace here the Euclidean norm by the norm • in the considered Hilbert space. Finally, instead of concentrating only on the 2 -norm in the measurement space, we will consider arbitrary p -norms, p 1.

We define the following semi-norm for all x ∈ H,

x µ,p := E µ L(x) p p 1/p
. Gathering all the above remarks and adapting them to the case of random linear maps from H to R m , we consider the following general form for the desired RIP: To simplify notations, we substitute δ p , δ p , and δp for δ S,µ,p , δ S,µ,p , and δS,µ,p , respectively, but one should keep in mind that these quantities depend on S, p and µ.

L(x) p p -x p µ,p δ, ∀x ∈ S ⊂ S.
We remark that if L satisfies the RIP on S with constant δ then

δ p -δ L(x) p p δp -δ,
for all x ∈ S. The condition δ < δ p ensures that no vector in x ∈ S is in the null space of L. Indeed, we have

L(x) p p δ p -δ > 0,
for all x ∈ S.

In the remaining part of this section, we give generic sufficient conditions to ensure that the RIP holds with high probability. We will see how to recover classical RIP results in finite dimensions with p = 2 in Section IV-A.

B. Concentration inequalities and main result

If Assumption A holds, the only other ingredients needed to prove that a random linear map L of the form of (3) satisfies the RIP with high probability are concentration inequalities. The choice of the probability distribution µ is thus important to ensure a preservation of the norm of the vectors in S by L. In this section, we assume that the following general concentration inequalities hold.

Assumption B. Define the function

h L,µ,p : H -→ R x -→ L(x) p p -x p µ,p .
There exist two constants c 1 , c 2 ∈ (0, ∞] such that for any fixed y, z ∈ S ∪ {0},

P {|h L,µ,p (y) -h L,µ,p (z)| λ y -z } 2e -c1mλ 2 , (7)
for every 0 λ c 2 /c 1 , and

P {|h L,µ,p (y) -h L,µ,p (z)| λ y -z } 2e -c2mλ , (8)
for every λ c 2 /c 1 .

To simplify notations, we substitute h p for h L,µ,p in the remaining part of the paper.

We remark that we can have c 1 = ∞ or c 2 = ∞. This is to handle the case where one of the above bounds hold for all λ 0. If c 1 = ∞ then (8) holds for all λ 0. Similarly, if c 2 = ∞ then [START_REF] Thaper | Dynamic multidimensional histograms[END_REF] holds for all λ 0.

We can now state our main theorem from which all the following results are derived.

Theorem II.2. Let L : H → R m be a random linear map constructed as in (3) using a probability distribution µ. If Assumption A and Assumption B hold, then for any ξ, δ ∈ (0, 1), we have: δ p δ with probability at least 1ξ provided that

m C min(c 1 , c 2 ) δ 2 max s log 1 S , log 6 ξ , (9)
where C > 0 is an absolute constant.

Inequality [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF] above involves the natural logarithm. The proof of this theorem is available in Appendix A. The proof is based on a chaining argument which is a powerful technique to obtain sharp bounds for the supremum of random processes, see, e.g., [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], [START_REF] Talagrand | Majorizing measures: the generic chaining[END_REF]- [START_REF] Dirksen | Tail bounds via generic chaining[END_REF]. This technique can be viewed as a refinement of the classical -net argument such as used in, e.g., [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF], [START_REF] Baraniuk | A simple proof of the restricted isometry property for random matrices[END_REF].

C. Proof recipe for the RIP

We can now deduce the following recipe to show that a random linear map L of the form of (3) satisfies the RIP on S.

The result of this recipe is that the random linear map L satisfies the RIP on the set S with constant δ ∈ (0, δ p ) and probability at least 1ξ provided that (9) holds.

In many practical scenarios, such as the ones discussed in next sections, the concentration inequalities [START_REF] Thaper | Dynamic multidimensional histograms[END_REF] and [START_REF] Bourrier | Compressive gaussian mixture estimation[END_REF] in Step 3 are easy to obtain using well-known concentration Recipe 1 Recipe to prove that L satisfies the RIP on S 1: Prove that the set S has finite upper box-counting dimension (Assumption A). 2: Compute δ p := inf x∈S E µ L(x) p p . 3: Prove that the concentration inequalities ( 7) and ( 8) hold (Assumption B). 4: Choose m such that (9) holds.

inequalities for the sum of independent random variables, see, e.g., [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF], [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF]. We will also see that the estimation of δ p simplifies in these cases. Therefore, the main difficult step in the recipe is most often the computation of the upper boxcounting dimension of S.

III. A GENERIC CONSTRUCTION OF L WITH THE RIP

In the previous section, we provided a recipe to prove that a random linear map satisfies the RIP once the probability distribution µ is given. In this section, we give a generic way of constructing a random linear map which has the RIP on a set S that satisfies Assumption A, i.e., we give a generic construction of µ.

We divide our construction into two steps. In the first step, we build a continuous linear functional b that maps the vectors in S to finite but potentially large dimension while essentially preserving their norm. In the second step, we further reduce the embedding dimension by multiplication with a random matrix.

A. Mapping to a finite-dimensional subspace

In this section, we prove that it is always possible to design a continuous linear map b : H → R d , where d is potentially large but finite, such that b(x) b

x , ∀x ∈ H,

(x) b 1 - * , ∀x ∈ S, (10) and b
for some * ∈ (0, 1) and a well-chosen norm • b . One can remark that the above properties ensure that b already satisfies a RIP but for a potentially large dimension d. We will see how to further reduce the dimension in Section III-B.

In the following subsections, we detail a generic method to construct b. This construction uses the fact that we can cover S with precision * as Assumption A holds. Note that this construction can be computationally expensive in practice. Yet, we would like to highlight that one does not have to use such a covering in practice. Indeed, the only required property in the following results is that b satisfies [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems[END_REF] and [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF]. The way b is constructed is not important as long as these properties hold. In practice, one can use other properties of S to construct b efficiently. For example, we will see in Section V-A that, for signals sparse in the Haar wavelet basis of L 2 ([0, 1]), such a linear map can be built easily using properties of these wavelets in the Fourier basis.

1) Using an orthonormal basis of a well-chosen subspace:

If Assumption A holds, then we can cover S with a finite number of closed balls. We fix a resolution * , find a minimum * -net for S, and denote the set of points in this net by C( * ). The cardinality of C( * ) is N S ( * ). Let V * ⊂ H be the finite-dimensional linear subspace of H spanned by C( * ), and P V * : H → H be the orthogonal projection onto V * . By construction of V * , we have

sup x∈S x -P V * (x) sup x∈S min x0∈C( * ) x -x 0 * . (12)
The orthogonal projection onto V * thus preserves the norm of all vectors in S with an error at most * , as illustrated in

: H -→ R d x -→ ( b i , x ) 1 i d .
We remark that b(x) 2 = P V * (x)

x , ∀x ∈ H,

and that b(x) 2 x -x -P V * (x) 1 - * , ∀x ∈ S.
To obtain the last inequality, we used inequality [START_REF] Talagrand | Majorizing measures: the generic chaining[END_REF] and the fact that S ⊂ S. We thus proved the desired result with

• b = • 2 .
2) Using an arbitrary basis of V * : The linear map b in the last section was constructed using an orthonormal basis of V * . To provide more flexibility in the design of the linear map L, we propose here to use an arbitrary basis of V * . Let (b 1 , . . . , b d ) be such a basis and define b :

H -→ R d x -→ ( b i , x ) 1 i d .
We also define the following norm

y b = inf z∈H { z | b(z) = y} ,
for all y ∈ R d . We next show that ( 10) and ( 11) hold with this choice of norm.

We denote by y ∈ V * the vector with coordinates y in the basis (b 1 , . . . , b d ). Let V ⊥ * be the orthogonal complement to V * in H. It is easy to notice that the set of vectors that satisfy b

(z) = y is {z = y + y ⊥ | y ⊥ ∈ V ⊥ * },
i.e., the set of vectors whose orthogonal projection on V * is y. Then, by orthogonality, we have

z 2 = y 2 + y ⊥ 2 ,
whose minimum value is y 2 . Therefore, y b = y and we deduce that b(x) b = P V * (x) for all x ∈ H. As we have P V * (x)

x for all x ∈ H, (10) holds. Then the fact that P V * (x)

xx -P V * (x) 1 - * for all x ∈ S shows that (11) holds.

We remark that when (b 1 , . . . , b d ) is an orthonormal basis, we have y b = y = y 2 , i.e., the norm we naturally chose in the previous section. The choice of • b as norm in R d allows us to recover the result of the last section but also to generalise it. Indeed, the result is now independent of the choice of the basis (b 1 , . . . , b d ). As explained in the remark before Recipe 2 below, this result can be useful when the choice of (b 1 , . . . , b d ) is for example fixed by the application.

B. Dimensionality reduction with a random matrix

The linear map b in the previous section maps the vectors in S into finite, but potentially large, dimension with an error at most * on the norm of the vectors. The goal is now to reduce the dimension further without degrading much the norm of the vectors in b(S).

Before continuing, we introduce the following definitions (definitions 5.7 and 5.13 in [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF]).

Definition III.1 (Subexponential random variable).

A subexponential random variable X is a random variable that satisfies

(E |X| q ) 1/q Cq for all q 1,
with C > 0. The subexponential norm of X, denoted by X Ψ1 , is the smallest constant C for which the last property holds, i.e.,

X Ψ1 := sup q 1 q -1 (E |X| q ) 1/q .
Definition III.2 (Subgaussian random variable). A subgaussian random variable X is a random variable that satisfies

(E |X| q ) 1/q C √ q for all q 1,
with C > 0. The subgaussian norm of X, denoted by X Ψ2 , is the smallest constant C for which the last property holds, i.e.,

X Ψ2 := sup q 1 q -1/2 (E |X| q ) 1/q .
To reduce the dimension, we draw m independent random vectors a 1 , . . . , a m ∈ R d according to a probability distribution ν in R d . The measurements a i b(x), i = 1, . . . , m are thus independent and identically distributed random variables. The choice of b and ν defines the probability distribution µ in H m .

To characterise the number of measurements needed to preserve the norm of all vectors in S, we need the following quantities

Λ 1 := sup x∈{S-S}∪S x =0 a i b(x) Ψ1 / b(x) b and (13)
Λ 2 := sup x∈{S-S}∪S x =0 a i b(x) Ψ2 / b(x) b . (14)
Note that these quantities may be infinite. However, we can ensure that Λ 1 and Λ 2 are finite, for example, by drawing a 1 , . . . , a m in the ball of radius 1 with respect to the dual norm of • b defined as

a b * := sup |a x| | x ∈ R d , x b 1 .
Indeed, we have |a b(x)| b(x) b for any x ∈ H in this case, which ensures that Λ 2 1 and Λ 1 1.

We are now ready to give the two main results of this section, which follow from Theorem II.2.

Theorem III.3. Assume that Λ 1 < +∞ and define

L : H -→ R m x -→ a i b(x) m 1 i d . (15)
There exists an absolute constant C > 0 such that if Assumption A holds then, for any ξ ∈ (0, 1) and δ ∈ (0, 1), with probability at least 1ξ,

x µ,1 -δ L(x) 1 x µ,1 + δ, holds for all x ∈ S provided that m C δ 2 max(2Λ 2 1 , Λ 1 ) max s log 1 S , log 6 ξ . (16)
Theorem III.4. Assume that Λ 2 < +∞ and define

L : H -→ R m x -→ a i b(x) √ m 1 i d . ( 17
)
There exists an absolute constant C > 0 such that if Assumption A holds, then, for any ξ ∈ (0, 1) and δ ∈ (0, 1), with probability at least 1ξ,

x 2 µ,2 -δ L(x) 2 2 x 2 µ,2 + δ, holds for all x ∈ S provided that m C δ 2 max(8Λ 4 2 , Λ 2 2 ) max s log 1 S , log 6 ξ . (18)
Both theorems are proved in Appendix C. Let us comment on these results and highlight the situations where they are useful. We will study several examples in the next section.

• First, we remark that

δ p = inf x∈S E ν |a i b(x)| p sup x∈S E ν |a i b(x)| p = δp
with p = 1 in Theorem III.3 and p = 2 in Theorem III.4. By definition of Λ 1 and Λ 2 , we have

E ν |a i b(x)| p p Λ p p b(x) p b p Λ p p , ∀x ∈ S,
for p = 1 and 2. The last inequality follows from [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems[END_REF]. Therefore, 16) holds if p = 1, or such that [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF] holds if p = 2.

δ
• Third, the number of measurements essentially scales with s max(2Λ 2 1 , Λ 1 )/δ 2 in the first case and s max(8Λ 4 2 , Λ 2 2 )/δ 2 in the second case. As we should have δ < δ p (with p = 1 or p = 2) to satisfy the RIP, the results have a practical interest when max(2Λ 2 1 , Λ 1 )/δ 2 1 or max(8Λ 4 2 , Λ 2 2 )/δ 2 2 is small. These ratios are the quantities to optimise when designing L, as illustrated in Section IV-B.

• Finally, it is important to notice that the choice of the basis (b 1 , . . . , b d ) and the choice of the distribution ν for the a i 's interact together in the value of the ratio

max(2Λ 2 1 , Λ 1 )/δ 2 1 or max(8Λ 4 2 , Λ 2 2 )/δ 2 2 .
If one has the flexibility to choose both (b 1 , . . . , b d ) and ν, then one should seek to minimise these ratios in order to minimise m. Even if the choice of b is fixed by the application of interest, one still has the flexibility to optimise the distribution ν to minimise m. In Recipe 2 introduced above, when (b 1 , . . . , b d ) is an orthonormal basis and a i is an isotropic random vector, then δ 2 can be directly estimated using [START_REF] Baraniuk | A simple proof of the restricted isometry property for random matrices[END_REF] as done below in Section IV-A1 for the second step of the recipe. We recall that

a i ∈ R d is isotropic if E |a i x| 2 = x 2 2
for all x ∈ R d . To estimate δ 1 , one can use Lemma D.2 as also done below in Section IV-B2 and Section IV-B4 for the second step of the recipe.

IV. EXAMPLES

In this section, we show how to use our generic recipe on different examples.

A. A linear embedding from

H to R m 1)
The infinite-dimensional case: In Section III-A, we built a linear map b : H → R d which preserves the norm of all vectors in S. For simplicity, we consider the case where (b 1 , . . . , b d ) is an orthonormal basis. We have

(1 - * ) 2 x 2 b(x) 2 b = b(x) 2 2 x 2 , ∀x ∈ S. (19)
Let a 1 , . . . , a m ∈ R d be m vectors whose entries are independent Gaussian random variables with mean 0 and variance 1, and define L as in Theorem III.4. We follow Recipe 2 to prove that L has the RIP. 1: The set S has a finite upper-box counting dimension by assumption. 2: To estimate δ 2 , we first notice that

E |a i b(x)| 2 = b(x) 2 2 . Inequality (19) then yields (1 - * ) 2 x 2 E |a i b(x)| 2 x 2 , ∀x ∈ S.
Therefore, δ 2 (1 - * ) 2 and δ2 1. 3: To estimate Λ 2 , we use the fact that a i x Ψ2 D x 2 , for all x ∈ R d , where D > 0 is an absolute constant (see [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF]). Therefore,

a i b(x) Ψ2 D b(x) 2 , ∀x ∈ H,
and Λ 2 D. 4: The last step of the recipe proves that L satisfies the RIP with constant δ ∈ (0, (1 - * ) 2 ) and probability at least

1 -ξ, i.e., ( 1
- * ) 2 -δ L(x) 2 2 1 + δ, ∀x ∈ S, provided that m C δ 2 max s log 1 S , log 6 ξ ,
where C is an absolute constant. With this example, one can remark that the only difference in the construction of the linear map L between an infinitedimensional setting and a finite-dimensional setting is the presence of the intermediate mapping b. This mapping is built from the projection onto a well-chosen subspace that preserves the norm of all vectors in S. Finally, the number of measurements m is essentially proportional to the intrinsic dimension of S, as usual in CS results.

2) Recovery of known results in finite dimension: The above results holds for any set S that satisfies Assumption A in a Hilbert space H, so it also holds for signal models in R n provided that they have a finite upper box-counting dimension. Let us take one example in finite ambient space.

Consider the set S of 2k-sparse signals with unit 2 -norm in R n . This set can be covered by at most [3en/(2k )] 2k balls of radius ∈ (0, 1) [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF]. Its upper box-counting dimension is thus 2k. Let us compute S and s which appear in Assumption A. We remind that S is a constant such that [3en/(2k )] 2k -s for all S with s > 2k. Writing s = 2k + η with η > 0, we should have (3en/(2k)) 2k

-η for all S , or, equivalently, (3en/(2k)) 2k -η S . We take S = 2k/(3en) and η = 2k. Notice that S 1/2 and that s = 4k. As we are in finite ambient dimension, we can take V * = R n (which implies that * = 0 and d = n) and the canonical basis for (b 1 , . . . , b n ) (which implies that b is the identity). The complete linear map L thus reduces to the matrix A/ √ m which satisfies, with probability at least 1ξ,

(1 -δ) x 2 2 Ax 2 2 m (1 + δ) x 2 2 , (20)
for all 2k-sparse vectors x provided that m satisfies m C δ 2 max 4k log 3en 2k , log 6 ξ .

In particular, this result shows that the set of k-sparse vectors is stably embedded into R m for m satisfying the above inequality.

In comparison, Theorem 9.2 in [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF] shows that A/ √ m satisfies ( 20) with probability at least 1ξ provided that

m D δ 2 2k log en 2k + log 2 ξ ,
where D > 0 is an absolute constant. This condition on m is similar to ours. This shows that we recover results similar to known ones in CS.

Note that we could have chosen any orthonormal basis of R n for (b 1 , . . . , b n ). This illustrates the known universality of subgaussian measurement matrices relative to the sparsity basis [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF].

Following the same procedure, one can easily recover many other similar results for, e.g., the set of low-rank matrices [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of random measurements[END_REF], low-dimensional smooth manifolds [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], or the set of groupsparse signals [START_REF] Ayaz | Uniform recovery of fusion frame structured sparse signals[END_REF]. In all these cases, the only remaining difficulty is estimating the upper box-counting dimension of the set of interest.

B. Embedding of matrices with rank-one projections

As a second example, we propose to use our results to show that one can embed a low dimensional set of matrices using rank-one projections. This scheme was proposed and studied in, e.g., [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF], [START_REF] Chen | Exact and stable covariance estimation from quadratic sampling via convex programming[END_REF], [START_REF] Kueng | Low rank matrix recovery from rank one measurements[END_REF], [START_REF] Bahmani | Sketching for simultaneously sparse and low-rank covariance matrices[END_REF] to embed certain low-dimensional set of matrices: low-rank matrices, sparse matrices, low-rank+sparse matrices, etc. We extend here these results to any set with a low-dimensional normalised secant set that satisfies Assumption A, which, e.g., includes matrix manifolds.

In this section, the ambient space is the space of real matrices of size n 1 ×n 2 , R n1×n2 , equipped with the Frobenius norm, • Frob . We consider that S ⊂ R n1×n2 is a lowdimensional subset of matrices that satisfies Assumption A, with • Frob instead of • .

1) Measurement strategy: As done in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF], [START_REF] Chen | Exact and stable covariance estimation from quadratic sampling via convex programming[END_REF], [START_REF] Kueng | Low rank matrix recovery from rank one measurements[END_REF], [START_REF] Bahmani | Sketching for simultaneously sparse and low-rank covariance matrices[END_REF], we propose to measure a matrix M ∈ R n1×n2 using m rankone projections:

L : R n1×n2 -→ R m M -→ a i Mb i m i=1,...,m , (21)
where a 1 , . . . , a m ∈ R n1 and b 1 , . . . , b m ∈ R n2 are independent random vectors. Note that the main advantage of this measurement strategy is its memory efficiency. Indeed, we only need to store m (n 1 + n 2 ) coefficients to compute the measurements while the measurement strategy proposed in [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of random measurements[END_REF] requires to store m n 1 n 2 coefficients. We will pay attention to two types of random vectors. First, we will focus on the case where the entries of the vectors a i and b i , i = 1, . . . , m, are independent draws of a random variable N ∈ R that has a standard normal distribution. Second, we will discuss the case where the entries of the vectors a i and b i , i = 1, . . . , m, are independent draws of a random variable P ∈ {0, ± √ q} that satisfies

P (P = 0) = q -1 q and P (P = ± √ q) = 1 2q , (22)
where q 1. The larger q is, the sparser (on average) the measurement vectors are, hence improving the computational efficiency of the measurement strategy. In this case, the average sparsity of the vectors a i and b i is n 1 /q and n 2 /q, respectively, and computing one measurement can be done in O(n 1 n 2 /q 2 ) operations. This type of measurement strategy with sparse vectors was proposed in [START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF] for Johnson-Lindenstrauss embeddings and can also be used for compressive sensing [START_REF] Baraniuk | A simple proof of the restricted isometry property for random matrices[END_REF]. We will see that the number of measurements needed to preserve the norm of all vectors in S depends on the parameter q.

2) RIP for rank-one projections with gaussian vectors: In this section, we study the case where the entries of the vectors a i and b i are independent draws of the random variable N . As the linear map L has the form presented in Theorem III.

δ 1 := inf M∈S E |a i Mb i | D.
Then, using the fact that

E |a i Mb i | E |a i Mb i | 2 1/2 = M Frob , ∀ M ∈ R n1×n2 ,
we also deduce that δ1 1. 3: To estimate Λ 1 , we use Lemma D.1 which shows that there exists an absolute constant E > 0 such that

a i Mb i Ψ1 E M Frob ∀ M ∈ R n1×n2 .
Therefore Λ 1 E. 4: The last step of the recipe proves that L satisfies the RIP with constant δ ∈ (0, D) and probability at least 1ξ, i.e.,

D -δ L(M) 1 1 + δ ∀ M ∈ S, provided that m C δ 2 max s log 1 S , log 6 ξ ,
where C > 0 is an absolute constant. The number of measurements m thus scales linearly with s. This result is true for any set S that satisfies Assumption A and is not restricted to the set of low-rank matrices.

Let us highlight that the result presented in this section involves an 1 -norm in the measurement domain, instead of the 2 -norm as in most CS results. The authors of [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF] and [START_REF] Chen | Exact and stable covariance estimation from quadratic sampling via convex programming[END_REF] also chose the 1 -norm in the measurement domain to prove the RIP. In addition, the authors in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF] proved that if one chooses the 2 -norm in the measurement domain for the RIP, then at least O(n 1 n 2 ) measurements are needed to ensure that L satisfies a RIP condition that guarantees the recovery of rank-1 matrices (see Lemma 2.1 in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF] and the discussion thereafter), which is much larger than n 1 + n 2 -1, the number of degrees of freedom for rank-1 matrices. Choosing the 1norm in the measurement domain solves this issue.

3) Recovery of a known result: Let now S be the set of rank-2r matrices with unit Frobenius norm. Lemma 3.1 in [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of random measurements[END_REF] shows that N S ( ) (9/ ) 2r(n1+n2+1) for any > 0. The upper box-counting dimension of S is thus 2r(n 1 +n 2 +1). Using the procedure of Section IV-A2, we can satisfy Assumption A by taking S = 1/9 and s = 4r(n 1 + n 2 + 1). The above result then shows that for δ ∈ (0, E), with probability at least

1 -ξ, E -δ L(M) 1 1 + δ, ∀ M ∈ S provided that m C δ 2 max 2r(n 1 + n 2 + 1) log (9) , log 6 ξ ,
where C > 0 is an absolute constant. In particular, the set of rank-r matrices is stably embedded into R m for m satisfying the above inequality.

Let us compare this result with Theorem 2.2 in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF].

Theorem IV.1 (Theorem 2.2, [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF]). Let L : R n1×n2 → R m be the linear map defined in [START_REF] Kueng | Low rank matrix recovery from rank one measurements[END_REF]. For positive numbers 1 C 1 < 1/3 and C 2 > 1, there exist constants C and δ, not depending on n 1 , n 2 , and r, such that if m Cr(n 1 + n 2 ), then with probability at least 1e -mδ , L satisfies

C 1 M Frob L(M) 1 C 2 M Frob ,
for all rank-2r matrices M ∈ R n1×n2 .

Comparing our result and the theorem above, we notice that we recover the same type of result with a number of measurements that needs to be essentially proportional to the upper box-counting dimension of the set of rank-r matrices in order to guarantee that the Frobenius norm of these matrices is preserved.

4) RIP for rank-one projections with sparse vectors: To improve the computational efficiency of the measurement procedure, one can think of using sparse vectors a i and b i . Let us thus discuss the case where the entries of the vectors a i and b i are independent draws of the sparse random variable P according to [START_REF] Bahmani | Sketching for simultaneously sparse and low-rank covariance matrices[END_REF]. Recipe 2 still works to prove that L has the RIP. 1 These numbers depend on the subgaussian norm of the measurement vectors a i and b i .

1: The set S has a finite upper-box counting dimension by assumption. 2: To estimate δ 1 , we use the result presented after Lemma D.2 which shows that there exists an absolute constant D > 0 such that

δ 1 := inf M∈S E |a i Mb i | D q (1 + log q) ,
for q 2. We also have δ1 1, as with Gaussian random measurement vectors. 3: To estimate Λ 1 , we use Lemma D.1 which shows that Λ 1 E q, where E > 0 is an absolute contant. 4: The last step of Recipe 2 proves that L satisfies the RIP with constant δ ∈ (0, D/(q + q log q)) and probability at least 1ξ, i.e.,

D q -δ L(M) 1 1 + δ ∀ M ∈ S, provided that m C q 2 δ 2 max s log 1 S , log 6 ξ ,
where C > 0 is an absolute constant.

The number of measurements m thus still scales linearly with s but also with q 4 (1 + log q) 2 , when δ < D/(q + q log q). As the (average) cost of computing one measurement is O(n 1 n 2 /q 2 ), this result is too weak in general to prove any benefit of using sparse measurement vectors.

5) Discussion: Let us highlight that the above result is derived without using any properties of S beyond its box counting dimension. In particular, this result also applies for sets S of sparse matrices for which we guess that using very sparse measurement vectors is not an adequate measurement strategy. Indeed, we need the support of the measurement vectors and the support of the vectors in the sparse matrix to both overlap in order to have non-zero measurements. As the measurement vectors get sparser, we increase the chance of having only null measurements, and thus decrease the chance of embedding the original matrix. This fact is reminiscent of the fundamental incoherence property between the sparsity domain and the sampling domain required in compressed sensing: one cannot sample a signal in the domain where it is sparse. More optimistic results might be obtained by exploiting additional structures in S. In that perspective, the work [START_REF] Bourgain | Toward a unified theory of sparse dimensionality reduction in euclidean space[END_REF] on sparse dimensionality reduction in Euclidean space might be particularly useful to obtain more optimistic results. The authors of [START_REF] Bourgain | Toward a unified theory of sparse dimensionality reduction in euclidean space[END_REF] prove that, with high probability, some random sparse measurement matrices satisfy the RIP for a wide class of subsets of the unit sphere. They provide sufficient conditions on the number of measurements and on the sparsity of the measurement matrix to ensure that the RIP is satisfied. These bounds depend on additional properties of S beyond its box-counting dimension. For example, for sparse signals in an orthonormal basis, they further require an incoherence property to ensure that the RIP holds (Section 5.1, [START_REF] Bourgain | Toward a unified theory of sparse dimensionality reduction in euclidean space[END_REF]).

This example illustrates the importance of the ratio max(2Λ 2 1 , Λ 1 )/δ 2 1 in the design of the linear map L. Even though the measurement vectors a i , b i are subgaussian random vectors as in Section IV-B2, the ratio max(2Λ 2 1 , Λ 1 )/δ 2 1 is too large and the result does not predict any gain in the computational efficiency compared to Gaussian rank-one measurements.

V. RELATED WORKS A. Infinite dimensional CS and generalised sampling An extension of the CS theory to an infinite dimensional setting is also studied in [START_REF] Adcock | Breaking the coherence barrier: a new theory for compressed sensing[END_REF]. In their work, the ambient space is a separable Hilbert space H and the authors concentrate on the particular case of sparse signals in an orthonormal basis of H. Their result does not involve a RIP but the linear map used to sense sparse signals shares some similarities with our construction of L.

Let us take the example of s-sparse signals in an orthonormal basis (ψ j ) j∈N of H, e.g., one can think of a wavelet basis. For simplicity, let us consider that the support of the signals in S belongs to {0, . . . , n -1}, hence S has a finite upper boxcounting dimension. In Section IV-A, we measure the signals by first projecting them onto a finite dimensional subspace of large dimension d that approximates the set S. To construct this subspace, we propose here to use another orthonormal basis (φ i ) i∈N of H, e.g., one can think of the Fourier basis. We choose to construct this finite dimensional subspace by using only the first d basis vectors φ i . Let us define the matrix U = (u ij := φ i , ψ j ) i,j∈N . Let α denote the coordinates of x ∈ H in (ψ j ) j∈N . We have b(x) = P d Uα ∈ R d , where P d is the matrix that selects the first d rows of U. According to our recipe, we need to choose d such that

(1 - * ) x b(x) 2 x , ∀x ∈ S,
in order to have the RIP. Here, this condition is equivalent to

(1 - * ) UP n α 2 P d UP n α 2 UP n α 2 , (23)
for all UP n α ∈ S ⊂ S, where P n is the matrix that keeps the first n entries of α and set all the other ones to 0. Using the facts that UP n α 2 = P n α 2 and P n P n = P n P n = P n , taking the square of ( 23) and rearranging the terms, one can notice that the condition

P n U P d P d UP n -P n 2 * , (24)
is sufficient to ensure [START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF].

It is interesting to notice that this condition also appears in the generalised sampling theorem of [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF]. Indeed, when U is an isometry as in the present example, the condition for stable reconstruction presented in [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF] amounts to the control of P n U P d P d UP n -P n 2 (see Section 5 in [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF] and the proofs therein). It is also proved in [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF] that this quantity tends to 0 as d tends to infinity. This shows that to choose d in practice, one just needs to increase it until [START_REF] Bourgain | Toward a unified theory of sparse dimensionality reduction in euclidean space[END_REF] is satisfied. In the particular case where H = L 2 ([0, 1]), (ψ j ) j∈N is the Haar wavelet basis (ordered from coarse to fine scale), and (φ j ) j∈N is the Fourier basis (ordered from low to high frequencies), the authors of [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF] further prove that ( 24) is satisfied for d = O(n 2 ), and their numerical experiments suggest that it is already sufficient to take d = O(n) (see Section 5.4 in [START_REF] Adcock | A generalised sampling theorem for stable rreconstruction in arbitrary bases[END_REF]). This indicates that V * does not always need to be a very large dimensional subspace of H to ensure that the RIP holds.

Finally, we note that condition (24) also appears in the extension of the CS theory to an infinite dimensional setting presented in [START_REF] Adcock | Breaking the coherence barrier: a new theory for compressed sensing[END_REF], involving however another operator norm. This property is called the weak balancing property in [START_REF] Adcock | Breaking the coherence barrier: a new theory for compressed sensing[END_REF].

B. Other measures of dimension?

In his monograph [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF], Robinson studies the problem of embedding a compact subset Σ of an infinite-dimensional (Hilbert or Banach) space into R m . He considers different definitions of dimension, in particular, the Hausdorff dimension (denoted dim H hereafter) and the upper box-counting dimension. He shows that embedding the set Σ into R m is possible as soon as dim H (Σ -Σ) < m but that no modulus of continuity is possible for L -1 , i.e., the embedding is not necessarily stable. One should further assume that the upper box-counting dimension of Σ is finite in order to find linear embeddings with Hölder continuous inverses.

In our work, we show that a stable embedding of a set Σ into finite dimensions exists when the upper box-counting dimension on the normalised secant set of Σ is finite. Compared to [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF] which uses the dimension of the secant set Σ -Σ, we are thus adding another constraint by normalising the secant set. An interesting question is thus whether we can change our measure of dimension and still guarantee the existence of stable linear embeddings or not. A first step in answering this question is checking if a finite upper box-counting dimension of S is a necessary condition to the existence of linear maps that satisfies the RIP. The following example shows that it is only a sufficient condition, which leaves room for a refinement of our results. This example is inspired by the construction of the "orthogonal sequence" in [START_REF] Robinson | Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics[END_REF].

Let H be the space of square-summable sequences, 2 , and define the correlated sequence Σ = {x i } i 1 with x i = r i (e i + b e 0 ), where (e i ) i∈N is the standard orthonormal basis of H, r ∈ (0, 1) and b > 0. Now consider the linear map L : H → R defined by L(x) = x, e 0 . Let us show that the linear map L stably embeds the set Σ. Clearly,

| x i -x j , e 0 |
x ix j for all x i , x j ∈ Σ, so let us consider the lower isometry bound. We want to show the existence of an α > 0 such that

| x i -x j , e 0 | α x i -x j , ∀x i , x j ∈ Σ, j > i 1, or equivalently, b 2 (r i -r j ) 2 α 2 (r 2i + r 2j + b 2 (r i -r j ) 2 ), ∀j > i 1.
Re-arranging the terms gives

b 2 r 2i (1 -r j-i ) 2 α 2 r 2i (1 + r 2(j-i) + b 2 ((1 -r j-i ) 2 ),
for all j > i 1. We can thus choose

α 2 = min j>i 1 b 2 (1 -r j-i ) 2 1 + r 2(j-i) + b 2 (1 -r j-i ) 2 > b 2 (1 -r) 2 (1 + r 2 + b 2 ) > 0.
Hence, L satisfies the RIP on S, the normalised secant set of Σ:

α | y, e 0 | 1, for all y ∈ S.

Consequently, L stably embeds the set Σ. Let us now calculate the upper box-counting dimension of S. Consider the following infinite sequence of vectors from S,

v k := x 2k -x 2k+1 x 2k -x 2k+1 = e 2k -re 2k+1 + b(1 -r)e 0 1 + r 2 + b 2 (1 -r) 2 ,
with k 1. Note that each v k is the only point in the sequence that has a non-zero component in the direction e 2k . Therefore,

v k -v k 1 1 + r 2 + b 2 (1 -r) 2 , ∀k = k .
Thus, for all

< 2 -1 [1 + r 2 + b 2 (1 -r) 2 ] -1/2
, it is impossible to cover the set {v k } k 1 ⊂ S with a finite -cover. Hence, dim(S) = ∞. We thus have a set S of infinite upper boxcounting dimension for which there exists a linear map that satisfies the RIP. A finite upper box-counting dimension of the normalised secant set is thus not necessary for the existence of a stable linear embedding.

Let us terminate this section by highlighting an important fact. We mentioned earlier that the upper box-counting dimension of S is often twice the upper box-counting of Σ (or Σ ∩ S if Σ is not bounded). It is however not always the case. Indeed, let us calculate the upper box-counting dimension of Σ. Let > 0. We note that

x i = r i (1 + b 2 ) 1/2 .
Let i * ( ) be the smallest integer such that r i * ( ) (1 + b 2 ) 1/2

. For small enough, we have i * ( ) 2. Hence, we can cover {x i } i i * ( ) with a single -ball at 0. Then, the remaining i * ( ) -1 points, {x i } i * ( )-1 i=1 can be separately covered by at most i * ( ) -1 balls of radius centered at each x i . This gives N Σ ( ) i * ( ). Then,

log N Σ ( ) -log log i * ( ) -(i * ( ) -1) log r -1 2 log(1 + b 2 )
.

Hence,

dim(Σ) = lim sup →0 log N Σ ( ) -log lim sup i * →∞ log i * -(i * -1) log r -1 2 log(1 + b 2 ) = 0.
Since dim(Σ) cannot be negative, we have dim(Σ) = 0. We thus have an example of a set Σ with a null upper box-counting dimension but whose normalised secant set has an infinite upper box-counting dimension. In general, one cannot directly deduce the dimension of S from the dimension of Σ.

C. Related works with similar proof techniques

A closely related work is the one of Dirksen [START_REF] Dirksen | Dimensionality reduction with subgaussian matrices: a unified theory[END_REF]. In this work, the ambient space is a (possibly infinite) Hilbert space and a generic theory for dimensionality reduction with subgaussian maps is presented. This work allows one to derive embedding results once a random linear map L is given. Theorem III.4 can for example be derived using the generic theory developed in [START_REF] Dirksen | Dimensionality reduction with subgaussian matrices: a unified theory[END_REF]. In our work, we provide in addition a recipe for the construction of the linear map L itself. Let us also note that one cannot directly recover the results presented in Section IV-B with the result presented in [START_REF] Dirksen | Dimensionality reduction with subgaussian matrices: a unified theory[END_REF].

Another related work of Dirksen is [START_REF] Dirksen | Tail bounds via generic chaining[END_REF], that extends results presented in [START_REF] Klartag | Empirical processes and random projections[END_REF], [START_REF] Mendelson | Reconstruction and subgaussian operators in asymptotic geometric analysis[END_REF] and where a technique to obtain tail bounds of the supremum of a stochastic process is presented. Let us highlight that these results can be another approach to obtain our generic theorem (Theorem II.2). From a more technical point of view, [START_REF] Dirksen | Tail bounds via generic chaining[END_REF] provides bounds for all p-th moment of the supremum of a stochastic process. Deviation inequalities immediately follows from these bounds. The proofs use the so-called generic chaining argument and the γ-functionals. Although the approximation of these functionals might not be easy, this method can produce sharper bounds than ours. In our proofs, we use more basic tools of probability theory with a another type of chaining argument to directly obtain the deviation inequalities.

Related works also exist for embeddings of manifolds in finite ambient dimension [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], [START_REF] Clarkson | Tighter bounds for random projections of manifolds[END_REF], [START_REF] Baraniuk | Random projections of smooth manifolds[END_REF]. In particular, the result presented in Section IV-A generalises the result presented in [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] to any model set with finite upper box-counting dimension. The proof technique used in [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] is also based on a chaining argument. In [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], one of the main contribution is also the identification of the manifold properties that allow one to control the covering dimension. In [START_REF] Mantzel | Compressed subspace matching on the continuum[END_REF], the same type of embedding result also appears but for signals that lie on a collection of continuously parameterised low-dimensional subspaces in R n .

Even though the following result applies in a finite dimensional Euclidean space, let us mention that Oymak et al. proved in [START_REF] Oymak | Isometric sketching of any set via the restricted isometry property[END_REF] that certain structured random matrices can embed any low-dimensional set of R n . This is a particularly useful result for practical applications as it shows that matrices for which fast matrix-vector multiplication algorithms exist can be used to embed any set, as long as it has a small intrinsic dimension. It would be interesting in a future work to study how such computationally efficient matrices can be used in the construction of our linear map L.

VI. CONCLUSION

We presented a generic recipe to prove that a random linear map satisfies the RIP on arbitrary low dimensional sets S which lives in a Hilbert space. The proposed framework is general enough to take into account a large class of subsets S as well as structured and unstructured measurement processes. We also explained how to construct random linear maps that satisfy the RIP with high probability in this general setting.

The linear map presented in Section IV-A is built in two steps. The first step consists in a projection onto a wellchosen finite-dimensional subspace V * and the second step uses a random subgaussian matrix to reduce the dimension. In order to obtain linear maps which are computationally more efficient, one can consider replacing the random matrix in the second step by a more structured one. One possibility is to use a variable density sampling technique, as we considered in [START_REF] Puy | Linear embeddings of lowdimensional subsets of a hilbert space to R m[END_REF]. Note that the condition on m presented in [START_REF] Puy | Linear embeddings of lowdimensional subsets of a hilbert space to R m[END_REF] is not optimal. Indeed for k-sparse signals in R n , the condition requires a number of measurements essentially proportional to k 2 to ensure that the RIP is satisfied. To understand the performance of the variable density sampling technique in practical applications, it will be important to determine under which additional structures this condition on m can be improved.

We also saw that a finite upper box-counting dimension of the normalised secant set S(Σ) of Σ is not necessary for the existence of a stable dimension reducing linear embedding of Σ. An interesting question is thus what appropriate measure of dimension of S(Σ) is both necessary and sufficient for the existence of a stable dimension reducing linear embedding of Σ.

APPENDIX A PROOF OF THEOREM II.2

The proof of Theorem II.2 is based on a chaining argument which is a powerful technique to obtain sharp bounds for the supremum of random processes [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF], [START_REF] Talagrand | Majorizing measures: the generic chaining[END_REF]- [START_REF] Rauhut | Compressive sensing and structured random matrices[END_REF]. Before proving Theorem II.2, we need some preparations.

First, we notice that if Assumption A holds then we can cover the set S with a finite number of balls. Furthermore, a bound on the number of balls sufficient to cover S is available for all radius S . In the proof below, for each j 0, • C j ⊂ S, denotes a minimal (2 -j S )-net for S; • π j denotes the mapping π j (x) ∈ argmin z∈Cj xz ; • D j denotes the finite set {(π j+1 (x),

π j (x)) | x ∈ S} ⊂ C j+1 × C j .
One can remark that the cardinality of C j is N S (2 -j S ), that the cardinality of D j is bounded above by N 2 S (2 -j-1 S ), and that sup (y,z)∈Dj yz 2 -j+1 S . Second, we remark that Assumption B implies that for any fixed x ∈ S ⊂ S

P {|h p (x)| λ} 2e -c1mλ 2 , if 0 λ c2 c1 , 2e -c1mλ , if λ c2 c1 . (25)
Indeed, it suffices to take y = x and z = 0 in ( 7) and [START_REF] Bourrier | Compressive gaussian mixture estimation[END_REF]. With these tools in hand, we can prove the following intermediate result from which Theorem II.2 follows.

Lemma A.1. Let (l 1 , . . . , l m ) be m random vectors drawn from H m according to a probability distribution µ, L : H → R m be the linear map defined in (3), δ p be the quantity defined in [START_REF] Vetterli | Sampling signals with finite rate of innovation[END_REF] and ξ ∈ (0, 1). Define If Assumption B holds, then

δ p S 1 ( S , ξ) + S 2 ( S , ξ) S √ c 1 m + S 2 1 ( S , ξ) + S 3 ( S , ξ) S c 2 m
with probability at least 1 -3ξ.

Proof: We begin by establishing the telescopic sum expression:

h p (x) = h p (π 0 (x)) + ∞ j=0 [h p (π j+1 (x)) -h p (π j (x))] .
The above equality holds because the linear maps of the form of L are continuous with respect to • . Therefore, L(•) p p , E L(•) p p , and thus h p are also continuous with respect to • . Then,

h p (x) -h p (π 0 (x)) - N j=0 [h p (π j+1 (x)) -h p (π j (x))] = h p (x) -h p (π N +1 (x)).
As lim N →∞ π N +1 (x)x = 0, we have lim N →∞ |h p (x)h p (π N +1 (x))| = 0 by continuity.

We continue with the triangle inequality which yields

δ p = sup
+ j 0 N 2 S S 2 j+1 • max (y,z)∈Dj P {|h p (y) -h p (z)| a j } . (26)
In the last step, we used the facts that the cardinality of C 0 is N S ( S ), and that the cardinality of D j is bounded above by N 2 S 2 -j-1 S . We now bound the first term on the right-hand side (rhs) of [START_REF] Dirksen | Dimensionality reduction with subgaussian matrices: a unified theory[END_REF]. We recall that C 0 ⊂ S. Inequality (25) thus yields We continue by bounding the infinite sum on the rhs of ( 26). We notice that for (y, z) ∈ D j , we have yz 2 -j+1 S . Assumption B shows that

max x0∈C0 P {|h p (x 0 )| b} 2e -c1mb 2 , if b c2 c1 , 2e -c2mb , if b c2 c1 . If S 2
P {|h p (y) -h p (z)| a j } = P |h p (y) -h p (z)| a j 2 j-1 S • S 2 j-1 P |h p (y) -h p (z)| a j 2 j-1 S y -z 2 e -c1 m (2 j-1 aj / S ) 2 , if aj 2 -j+1 S c 2 /c 1 , 2 e -c2 m 2 j-1 aj / S , if aj 2 -j+1 S c 2 /c 1 . (27)
Define

J := j ∈ N 1 m log 2 j+1 ξ • N 2 S S 2 j+1 c 2 2 c 1 .
We choose

a j := 2 -j+1 S √ c 1 m log 2 j+1 ξ • N 2 S S
2 j+1 , for all j ∈ J , and

a j := 2 -j+1 S c 2 m log 2 j+1 ξ • N 2 S S
2 j+1 , for all j ∈ N \ J . Notice that, by definition of J , we have a j 2 -j+1 S c 2 c 1 for all j ∈ J , and

a j 2 -j+1 S c 2 c 1 ,
otherwise. Replacing a j by its expression in [START_REF] Klartag | Empirical processes and random projections[END_REF] shows that

N 2 S S
2 j+1 max (y,z)∈Dj P {|h p (y)h p (z)| a j } 2 -j ξ for all j ∈ N. Therefore,

j 0 N 2 S S
2 j+1 max (y,z)∈Dj

P {|h p (y) -h p (z)| a j } 2ξ.
In total, the rhs of ( 26) is thus bounded by 3ξ. Finally, we have

j 0 a j = S √ c 1 m j∈J 2 -j+1 log 2 j+1 ξ • N 2 S S 2 j+1 + S c 2 m j∈N\J 2 -j+1 log 2 j+1 ξ • N 2 S S 2 j+1 S √ c 1 m j∈N 2 -j+1 log 2 j+1 ξ • N 2 S S 2 j+1 + S c 2 m j∈N 2 -j+1 log 2 j+1 ξ • N 2 S S 2 j+1 = S S 2 ( S , ξ) √ c 1 m + S S 3 ( S , ξ) c 2 m .
In summary, we have shown that

δ p b + j 0 a j
with probability at least 1 -3ξ. Using the bounds on b and j 0 a j , we have

δ p S 1 ( S , ξ) + S 2 ( S , ξ) S √ c 1 m + S 2 1 ( S , ξ) + S 3 ( S , ξ) S c 2 m
with at least the same probability.

We can now prove Theorem II.2. First, we need to compute the sums S 1 , S 2 , S 3 in the above lemma. It involves uninteresting computations which, for completeness, we detail in Appendix B. For ξ ∈ (0, 1) and S ∈ (0, 1/2), if Assumption A holds, these computations show that The independent random vectors a 1 , . . . , a m ∈ R d are assumed to be such that

S 1 ( S ,
Λ 1 := sup x∈{S-S}∪S x =0 a i b(x) Ψ1 / b(x) b < +∞.
Therefore, for all p 1, we have

E |a i b(x)| p 1/p Λ 1 p b(x) b , (31)
for any x in {S -S} ∪ S.

Let y, z be two fixed vectors in S ∪ {0}. Define X := m i=1 X i where

X i := |a i b(y)| -|a i b(z)| -E(|a i b(y)| -|a i b(z)|).
It is clear that X is a sum of m independent centered random variables. To use Lemma C.1, we need to show that these variables are subexponential and bound their subexponential norm. We have

E |a i b(y)| -|a i b(z)| p 1/p E |a i (b(y) -b(z))| p 1/p = E |a i (b(y -z))| p 1/p Λ 1 p b(y -z) b Λ 1 p y -z .
The second step follows from the linearity of b. The third step follows from [START_REF] Oymak | Isometric sketching of any set via the restricted isometry property[END_REF] and the fact that yz ∈ {S -S} ∪ S. The last step follows from inequality [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems[END_REF]. We deduce that X 1 , . . . , X m are independent centered subexponential random variables with subexponential norm bounded by 2Λ 1 yz . Observe that

h 1 (y) -h 1 (z) = 1 m m i=1 X i . Lemma C.1 with K = 2Λ 1 y -z yields P {|h 1 (y) -h 1 (z)| λ y -z } 2e -c1mλ 2 ,
for every 0 λ 2Λ 1 , and

P {|h 1 (y) -h 1 (z)| λ y -z } 2e -c2mλ , for every λ 2Λ 1 , with c 1 = c/(4Λ 2
1 ) and c 2 = c/(2Λ 1 ). Note that c 2 /c 1 = 2Λ 1 . Hence, Assumption B is satisfied. Theorem II.2 terminates the proof.

C. Proof of Theorem III.4

The independent random vectors a 1 , . . . , a m ∈ R d are assumed to be such that

Λ 2 := sup x∈{S-S}∪S x =0 a i b(x) Ψ2 / b(x) b < +∞
Therefore, for all p 1, we have

E |a i b(x)| p 1/p Λ 2 √ p b(x) b , (32)
for any x in {S -S} ∪ S. Let y, z be two fixed vectors in S ∪ {0}. Define X := m i=1 X i where

X i := |a i b(y)| 2 -|a i b(z)| 2 -E(|a i b(y)| 2 -|a i b(z)| 2 ).
It is clear that X is a sum of m independent centered random variables. To use Lemma C.1, we need to show that these variables are subexponential and bound their subexponential norm. We have

E |a i b(y)| 2 -|a i b(z)| 2 p 1/p = E |a i (b(y) + b(z))| p |a i (b(y) -b(z))| p 1/p E |a i b(y + z)| 2p 1 2p E |a i b(y -z)| 2p 1 2p .
In the last step, we used the Cauchy-Schwarz inequality and the linearity of b. Using (32) and the facts that2 (y ± z) ∈ {S -S} ∪ S, we obtain

E |a i b(y ± z)| 2p 1 2p Λ 2 2p b(y ± z) b Λ 2 2p y ± z 2 √ 2 Λ 2 √ p, for y + z, √ 2 Λ 2 √ p y -z , for y -z.
In the second step, we used inequality [START_REF] Bourrier | Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems[END_REF]. In the last step, we used the fact that y 1 and z 1. We thus have

E |a i y| 2 -|a i z| 2 p 1/p 4Λ 2 2 p y -z .
Therefore, X 1 , . . . , X m are independent centered subexponential random variables with subexponential norm bounded by 8Λ 2 2 yz . Observe that

h 2 (y) -h 2 (z) = 1 m m i=1 X i . Lemma C.1 with K = 8Λ 2 2 y -z yields P {|h 2 (y) -h 2 (z)| λ y -z } 2e -c1mλ 2 ,
for every 0 λ 8Λ 2 2 , and

P {|h 2 (y) -h 2 (z)| λ y -z } 2e -c2mλ , for every λ 8Λ 2 2 with c 1 = c/(64Λ 4
2 ) and c 2 = c/(8Λ 2 2 ). Note that 8Λ 2 2 = c 2 /c 1 . Hence, Assumption B is satisfied. Theorem II.2 terminates the proof.

APPENDIX D RANDOM RANK-ONE PROJECTIONS

A. Estimation of Λ 1 from Section IV-B Let M be a fixed matrix in R n1×n2 and a ∈ R n1 , b ∈ R n2 be vectors whose entries are independent copies of the random variable N or P , defined in [START_REF] Bahmani | Sketching for simultaneously sparse and low-rank covariance matrices[END_REF]. In [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF], the authors show that a Mb is a subexponential random variable. In this section, we estimate the parameter Λ 1 needed in Recipe 2. This estimation follows from the lemma below, whose proof starts from intermediate results presented in [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF].

Before presenting the lemma, we recall the definition of the double factorial for odd numbers: (2k -1)!! = (2k)!/(2 k k!) for all k 1. Using Stirling's formula for the factorial, we obtain

(2k -1)!! = √ 2π2k (2k/e) 2k e λ 2k 2 k √ 2πk (k/e) k e λ k = √ 2 2 k (k/e) k e λ 2k -λ k , (33)
where 1/(12k + 1) λ k 1/(12k).

Lemma D.1. Let a ∈ R n1 and b ∈ R n2 be vectors whose entries are independent copies of a random variable X ∈ R. Define

α X := sup k 1 E X 2k (2k -1)!! 1/(2k)
.

Assume that 1 α X < ∞. For any fixed matrix M in R n1×n2 and all p 1, (E |a Mb| p )

1/p 2 3/(2p) e -1 p α 2 X M Frob . As a consequence, a Mb is a subexponential random variable with subexponential norm bounded by C α 2 X M Frob , where C = 2 3/2 e -1 ≈ 1.04 > 1.

The proof of this lemma is given below. From the above result, we see that we only need to estimate α X with X = N and X = P to estimate the constant Λ 1 in Section IV-B.

• [Case where X = N ] As N is a standard random variable, we have E N 2k = (2k-1)!!. Therefore, α N = 1 and Λ 1 C where C > 1 is an absolute constant. • [Case where X = P ] It is easy to notice that E P 2k = q k /q. Using (33) and the fact that e λ 2k -λ k 1/2, we obtain

EP 2k (2k -1)!! 1/(2k) √ 2 2 -k (k/e) -k q k /q 1/(2k) √ 2 q -1 2 -k (k/e) -k 1/(2k) q 1/2 .
Therefore, α P 1.39 √ q and Λ 1 C √ q where C > 1 is an absolute constant.

Proof: We start with inequality (0.20) in the supplementary material of [START_REF] Cai | Rop: Matrix recovery via rank-one projections[END_REF], which shows that, for all k 1,

E |a Mb| 2k α 4k X [(2k -1)!!] 2 M 2k
Frob . Using (33) and the fact that e λ 2k -λ k 1, we obtain (2k -

1)!! √ 2 2 k (k/e) k . Therefore, E |a Mb| 2k 2 (2α 2 X /e) 2k k 2k M 2k Frob ,
for all k 1. To shorten notations, we define C α X ,M := (2α 2 X /e) M Frob .

We thus have

E |a Mb| 2k 2 C 2k α X ,M k 2k .
We now follow exactly the interpolation technique used in the proof of Corollary 8.7 in [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis[END_REF]

. Let θ ∈ [0, 1]. Then, E |a Mb| 2(k+θ) E |a Mb| 2k 1-θ E |a Mb| 2k+2 θ 2 C 2k α X ,M k 2k 1-θ 2 C 2(k+1) α X ,M (k + 1) 2(k+1) θ = 2 C 2(k+θ) α X ,M k 2k(1-θ) (k + 1) 2(k+1)θ = 2 C 2(k+θ) α X ,M k 1-θ (k + 1) θ 2(k+θ) k + 1 k 2θ(1-θ) 2 C 2(k+θ) α X ,M [k + θ] 2(k+θ) k + 1 k 2θ(1-θ) 2 √ 2 C 2(k+θ) α X ,M [k + θ] 2(k+θ)
Hölder's inequality yielded the first step. In the second step from below, we used the fact that In the first step, we used the fact that for any random variable X, (E |X| p ) 1/p (E |X| q ) 1/q for 0 < p q. The last inequality follows from the fact that the minimum of f (p) = 2 3/(2p) e -1 p is attained at p 0 = 3 log(2)/2 and that α 2 X f (p 0 ) ≈ 1.0397 α 2 X 1. The lemma is thus proved for all p > 0.

B. Bound on δ 1

Let us first introduce the following lemma which bounds E|a x| for isotropic subexponential random vectors a ∈ R n and any fixed vector x ∈ R n . Lemma D.2. Let a ∈ R n be a random vector such that for any fixed vector x ∈ R n , The proof of this lemma is given below. To estimate δ 1 , we thus notice that we only need to estimate the constant C in the above lemma. For rank-one projections, Lemma D.1 indicates that C O(α 2 X ).

E |a x| 2 = x
Proof: The upper bound follows from Jensen's inequality,

E |a x| E |a x| 2 = x 2 .
For the lower bound, we start with Hölder's inequality. Let θ ∈ (0, 1), we obtain .

E
Therefore,

E |a x| x 2/(1-θ) 2 [(1 + θ)/θ • C • x 2 ] (1+θ)/(1-θ) x 2 [C • (1 + θ)/θ] (1+θ)/(1-θ) .
The lower bound is valid for any θ ∈ (0, 1). Therefore, [C • (1 + θ)/θ] (1+θ)/(1-θ) .

E
Let g be the function defined by

g(θ) = 1 + θ 1 -θ log(C) + 1 + θ 1 -θ log 1 + 1 θ .
We have log(β) = inf θ∈(0,1) g(θ). One can check that the minimum of g is attained at θ * satisfying His research has focused on nonlinear time series, source separation, sparse representations and compressed sensing. He has made key contributions to these fields including: the development of signal embedding theorems for nonlinear dynamical time series and the development of new theoretical and algorithmic results in Independent Component Analysis (ICA). Most recently he has pioneered the use of sparse representations as a fundamental tool in signal processing, source separation and compressed sensing. This work includes: the proposal and analysis of the highly popular Iterative Hard Thresholding algorithm for sparse reconstruction; the development of a theory for the sampling of structured sparse signal models as well as the development of a variety of new practical sampling and reconstruction techniques that exploit structured sparsity. He has also explored the application of these ideas to advanced medical imaging and RF based sensing applications. He also has an active interest in the related topics of machine learning, high-dimensional statistics and information theory.

Rémi Gribonval (FM'14) is a Senior Researcher with Inria (Rennes, France), and the scientific leader of the PANAMA research group on sparse audio processing. A former student at Ecole Normale Superieure (Paris, France), he received the Ph. D. degree in applied mathematics from Universite de Paris-IX Dauphine (Paris, France) in 1999, and his Habilitation a Diriger des Recherches in applied mathematics from Universite de Rennes I (Rennes, France) in 2007. His research focuses on mathematical signal processing, machine learning, approximation theory and statistics, with an emphasis on sparse approximation, audio source separation, dictionary learning and compressed sensing. He founded the series of international workshops SPARS on Signal Processing with Adaptive/Sparse Representations. In 2011, he was awarded the Blaise Pascal Award in Applied Mathematics and Scientific Engineering from the SMAI by the French National Academy of Sciences, and a starting investigator grant from the European Research Council.

Definition I. 2 (

 2 Upper box-counting dimension). The upper box-counting dimension of S is dim(S) := lim sup →0 log[N S ( )]/log[1/ ].

Definition II. 1 (

 1 RIP). Let L : H → R m be a linear map. Define δ S,µ,p := sup x∈S The linear map L satisfies the RIP on S ⊂ S with constant δ if δ S,µ,p δ < δ S,µ,p . It will also be convenient to define δS,µ,p := sup x∈S x p µ,p .

Figure 1 .

 1 Figure 1. Construction of V * . Top left: cover of S with N ( * ) balls of radius * . Top right: the centres of the balls, indicated by the red crosses, form a * -net, denoted by C( * ), for S. Bottom left: the linear span of the vectors in C( * ) is V * . Bottom right: V * approximates S with precision * .

Fig. 1 .

 1 Let (b 1 , . . . , b d ) be an orthonormal basis for V * and b be the linear map b

3 ( 2 :

 32 with b the identity and • b = • Frob ), we can follow Recipe 2 to prove that L has the RIP. 1: The set S has a finite upper-box counting dimension by assumption. To estimate δ 1 , we use the result presented after Lemma D.2 which shows that there exists an absolute constant D > 0 such that

S 1 (

 1 S , ξ) := log 2 ξ • N S ( S ) , S 2 ( S , ξ) := j∈N 2

  π j+1 (x))h p (π j (x)|h p (y)h p (z)| .Let a j , b > 0, with j ∈ N, be parameters whose values will be chosen later on. The union bound yieldsP |h p (y)h p (z)| a j N S ( S ) • max x0∈C0 P {|h p (x 0 )| b}

1 (

 1 S ( S ) /ξ) c 2 m , otherwise. This choice yields N S ( S ) • max x0∈C0 P {|h p (x 0 )| b} ξ,

( 1 - 1 / 2 .

 112 θ) log(k) + θ log(k + 1) log ((1θ)k + θ(k + 1)) ,which follows from the concavity of the logarithm. In the last step, we used the facts that (k +1)/k 2 and that 2θ(1-θ) Taking p = 2(k + θ) proves the lemma for p 2.For 0 < p 2, we have(E |a Mb| p ) 1/p (E |a Mb| 2 ) 1/2 = M Frob 2 3/(2p) e -1 p α 2 X M Frob .

2 2

 2 and a x Ψ1 C x 2 , where C 2 is a constant. Then,x 2 2e 3 C (1 + log(C)) E |a x| x 2 .

  C) + log (2 + 2 log(C))] g(θ * ).For C 2, we have3 log(C) + log (2 + 2 log(C)) log(C) .Therefore,2e 3 C (1 + log(C)) β.

  Second, we notice that the RIP is satisfied for δ < δ 1 in the case of Theorem III.3 and for δ < δ 2 in the case of Theorem III.4. Consequently, if L is constructed as in this section, then Recipe 1 can be modified to Recipe 2.

	Recipe 2 Recipe to prove that L in (15) or (17) satisfies the
	RIP on S

p δp p Λ p p with p = 1 in Theorem III.3 and p = 2 in Theorem III.4. • 1: Prove that the set S has finite upper box-counting dimension (Assumption A). 2: Compute δ p = inf x∈S E ν |a i b(x)| p , with p = 1 for L defined in (15) or p = 2 for L defined in (17). 3: Compute Λ 1 or Λ 2 . 4: Choose m such that (

  |a x| 2 = E |a x| 1-θ |a x|Using the fact that a x has a subexponential norm bounded by C x 2 , we obtain

						1+θ
		(E |a x|) 1-θ	E |a x| (1+θ)/θ	θ	.
	Therefore,
		E |a x|	2 (1+θ)/θ 1/(1-θ) E |a x| E |a x| θ/(1-θ)
	E |a x|	(1+θ)/θ	1 + θ θ	(1+θ)/θ	C (1+θ)/θ x	(1+θ)/θ 2

  Mike E. Davies (M'00SM'12F'15) holds the Jeffrey Collins Chair in Signal and Image Processing at UoE, where he also leads the Edinburgh Compressed Sensing Research Group, and is Head of the Institute for Digital Communications (IDCOM). He received an M.A. in engineering from Cambridge University in 1989 where he was awarded a Foundation Scholarship (1987), and a Ph.D. degree in nonlinear dynamics and signal processing from University College London (UCL) in 1993. He was awarded a Royal Society University Research Fellowship in 1993 and was appointed a Texas Instruments Distinguished Visiting Professor at Rice University in 2012. Currently he also leads the University Defence Research Collaboration (UDRC), a U.K. programme of signal processing research in defence in collaboration with the U.K. Defence Science and Technology Laboratory (DSTL).

Remark that S is symmetric. Therefore S + S = S -S.

This work was partly funded by the European Research Council, PLEASE project (ERC-StG-2011-277906). M. E. Davies would like to acknowledge the support of EPSRC grant EP/J015180/1. This work is an extension of the paper [1] presented at the European Signal Processing Conference (EUSIPCO), 2015.

with D := 32/ min(c 1 , c 2 ), holds then [START_REF] Mendelson | Reconstruction and subgaussian operators in asymptotic geometric analysis[END_REF], [START_REF] Baraniuk | Random projections of smooth manifolds[END_REF], [START_REF] Mantzel | Compressed subspace matching on the continuum[END_REF] all hold. Under this condition, we have δ p 10δ, with probability at least 1 -3ξ. Two change of variables (ξ = 3 ξ, δ = 10 δ) prove the theorem with C = 3200.

APPENDIX B EVALUATION

To estimates the sums S 1 , S 2 , S 3 , we start by noticing that j 0 j2 -j = 2 (see, e.g., Section 4.2.3 in [START_REF] Riley | Mathematical methods for physics and engineering[END_REF]). We precompute, for ξ ∈ (0, 1),

Similarly,

We also have, for

Similarly,

If Assumption A holds, we have

for all j ∈ N. Therefore, using the pre-computations above, we obtain We also have S 2 1 ( S , ξ) log (2/ξ) + s log(1/ S ), and

APPENDIX C PROOF OF THEOREM III.3 AND THEOREM III.4

A. Basic tools

In this section, we use several properties of subgaussian and subexponential random vectors/variables (see Definition III.1 and Definition III.2). We let the reader refer to, e.g., [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF] for more information about them. We recall here one useful property.

• If X is a subexponential random variable then so is X -EX, and we have X -EX Ψ1 2 X Ψ1 (Remark 5.18, [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF]). We will also use the following Bernstein-type inequality for subexponential random variables.

Lemma C.1 (Corollary 5.17, [START_REF] Vershynin | Compressed Sensing, Theory and Applications[END_REF]). There exists an absolute constant c > 0 such that for independent centered subexponential random variables X 1 , . . . , X m with subexponential norm bounded by K > 0, we have, for every 0 t K,