Instance Optimal Decoding and the Restricted Isometry Property
Nicolas Keriven Rémi Gribonval



École Normale Supérieure. 45 rue d'Ulm, 75005 Paris, France.
nicolas.keriven@ens.fr

Université Rennes 1, Inria, CNRS, IRISA. F-35000 Rennes, France.
remi.gribonval@inria.fr




In this paper, we address the question of information preservation in ill-posed, non-linear inverse problems, assuming that the measured data is close to a low-dimensional model set. We provide necessary and sufficient conditions for the existence of a so-called instance optimal decoder, i.e., that is robust to noise and modelling error. Inspired by existing results in compressive sensing, our analysis is based on a (Lower) Restricted Isometry Property (LRIP), formulated in a non-linear fashion. We also provide sufficient conditions for non-uniform recovery with random measurement operators, with a new formulation of the LRIP. We finish by describing typical strategies to prove the LRIP in both linear and non-linear cases, and illustrate our results by studying the invertibility of a one-layer neural net with random weights.




§ INTRODUCTION



Inverse problems are ubiquitous in all areas of data science. While linear inverse problems have been arguably far more studied in the literature, some frameworks are intrinsically non-linear <cit.>. In this paper, we aim at giving a characterization of the preservation of information in ill-posed inverse problems, regularized by the introduction of a “low-dimensional” model set close to which the data of interest is assumed to live. We consider a very general context that includes, in particular, measurement operators that are possibly non-linear, and an ambient space that can be any pseudometric set. Our main results show that the existence of a decoder that is robust to noise and modelling error is equivalent to a modified Restricted Isometry Property (RIP), which is a classical property in compressive sensing <cit.>. We thus outline the fundamental nature of the RIP in settings that are more general than previously studied.


The problem is formulated as follows. Let (,) be a set equipped with a pseudometric[A pseudometric d satisfies all the requirements of a metric except d(x,y) = 0 ⇒ x=y.] , the set of data, and (,·) a seminormed[Similarly, a seminorm satisfy the requirements of a norm except that x=0 does not imply x=0.] vector space, the space of measurements. Consider a (possibly non-linear) measurement map :→. The measured vector is:

    =  +

where ∈ is measurement noise and  is the true signal. Our goal is to characterize the existence of any procedure that would allow us to approximately recover the data  from .




  
Regularization. In most interesting problems, the “dimension” of the space  is far lower than that of the set  (in a loose sense: we recall that here none is required to be finite-dimensional, and  is not necessarily a vector space), which makes the problem ill-posed, meaning that there are information-theoretic limits that prevent us from recovering the underlying signal from the measurements, even in the noiseless case. A classical regularization technique is to introduce prior knowledge about the true signal , here we consider a model set ⊂ of “simple” signals, such that  is likely to be close to . For instance, sparsity, i.e. the assumption that the true signal is a linear combination of a few elements in a well-chosen dictionary, is a hugely-studied prior in modern signal processing, in particular in compressive sensing <cit.>.



  
Instance Optimal Decoding. Ideally, a decoder :→ must be able to exactly retrieve  from  when the modelling is exact (i.e. ∈) and the noise is zero (= 0). However, as these conditions are highly unrealistic in practice, it is desirable for this decoding process to be both robust to noise and stable to modelling error. In the literature, such a decoder is said to be instance optimal <cit.> (see Def. <ref>). In this paper, our goal is to characterize necessary and sufficient conditions for the existence of an instance optimal decoder for the problem (<ref>). Note that we will not study the existence of efficient algorithms to solve (<ref>), which is another significant achievement of compressive sensing <cit.>, but only the preservation of information of the encoding process.

In <cit.>, the authors outlined the crucial role played by the Restricted Isometry Property (RIP), and more precisely by the Lower-RIP (LRIP), for the existence of instance optimal decoders in the linear case. 
In this paper, we extend these results to the non-linear case and to non-uniform probabilistic recovery. 






  
Outline of the paper. The structure of the paper is as follows. In Section <ref> we briefly outline some relevant references, keeping in mind that the field is large and we do not pretend to be exhaustive in this short paper. In Section <ref> we state our main results relating instance optimal decoders (Def. <ref>) and the LRIP (Def. <ref>). In Section <ref> we outline how one might typically prove the LRIP by extending a classical proof <cit.>, and illustrate it on a simple example. 



§ RELATED WORK








  
Classical Compressive Sensing: the linear case. Instance optimal decoding and the RIP are well-known notions in compressive sensing <cit.>. We refer to the book of Foucart and Rauhut <cit.> for a review of the field, in particular to Chapters 6 and 11 for the topics of interest here. The interplay between the two notions was in particular studied in <cit.> in the finite-dimensional case. These results were later extended to more general models in <cit.>, and to any linear measurement operators in <cit.>, which is the main inspiration behind the present work.



  
Non-uniform decoding. In compressed sensing the measurement operator  is often designed at random. Typical recovery results are therefore given with high probability. One can then distinguished between uniform guarantees, meaning that with high probability on the draw of  all signals  close to  can be stably recovered, and non-uniform guarantees, i.e. for one fixed signal  close to , with high probability on  the decoding is successful. In <cit.> the authors study non-uniform instance optimality, but only under the light of the classical uniform RIP. In this paper we introduce a non-uniform version of the LRIP and prove that it is sufficient for non-uniform instance optimality.



  
Non-linear inverse problems. Non-linear inverse problems can be found in many areas of signal processing, see e.g. <cit.> for a review of some applications. They have also been considered by the compressive sensing community, often when quantization occurs <cit.>, in the so-called “1-bit” compressed sensing line of work <cit.>.
Another focus is the development of efficient algorithms inspired by the linear case <cit.>. In <cit.>, the author assume that a locally linearized version of  satisfy the classical RIP. In this paper we consider a different, “fully” non-linear RIP. We note that one notion does not imply the other.





§ EQUIVALENCE BETWEEN IOP AND LRIP


In this section we state our main results on instance optimal decoders and the LRIP. We distinguish the case where the operator  is deterministic, or, equivalently, when it is random but one seeks so-called uniform recovery guarantees, and the case of non-uniform recovery.



 §.§ Deterministic operator



Recall that we consider a pseudometric set (,), a seminormed vector space (,·), and measurements of the form =  + where :→. We consider a model set ⊂, and are interested in characterizing the existence of a good decoder (,) that takes  and  as inputs and return a signal ∈ that is close to .  We want this decoder to be stable to modelling error and robust to noise, which is characterized by the notion of instance optimality.


A decoder  satisfies the Instance Optimality Property for the operator  and model  with constants , >0, pseudometrics , on  and error ≥ 0 if: for all signals ∈ and noise ∈, denoting =(,  + ) the recovered signal, it holds that:

    (, ) ≤(,) +  +

where (,) = inf__∈(,_).



As indicated by the r.h.s. of (<ref>), the decoding error between the true signal and the recovered one is bounded by the amplitude of the noise and the distance from  to the model set, which indicates how well  is modelled by . An instance optimal decoder is therefore robust to noise and stable even if  is not exactly in the model set. 
We also include a possible fixed additional error ≥ 0, which may be unavoidable in some cases (due to algorithmic precision for instance). Ideally, one has =0.



Let us now turn to the proposed non-linear version of the LRIP. As described in <cit.>, the LRIP is just one side of the classical RIP, which states that the measurement operator  approximately preserves distances between elements of the model .






The operator  satisfies the Lower Restricted Isometry Property for the model  with constant >0, pseudometric  and error ≥ 0 if: for all ,' ∈ it holds that

    (,') ≤ - ' + .


The LRIP expresses the fact that  must not collapse two elements of the model together. Like the IOP, we allow for a possible additional fixed error ≥ 0 in the LRIP. Note that this type of error is often considered when introducing quantization <cit.>. Ideally, one has =0, however in some cases it can be considerably simpler to prove that the LRIP holds with a non-zero  <cit.>. The reader would note that the classical RIP is often expressed with a constant α = (1-t)^-1 where t<1 is a small as possible.




We now state our main result. The proof, rather direct, can be found in <ref>.


Consider an operator  and a model .


  * If there exists a decoder  which satisfies the Instance Optimality Property for  and  with constants , >0, pseudometrics , and error ≥ 0, then the operator  satisfies the LRIP for  with constant =, pseudometric  and error = 2.

  * If the operator  satisfies the LRIP for the model  with constant , pseudometric  and error ≥ 0, then the decoder  defined as[In this paper we assume that the minimization problem _∈ - has at least one solution, for simplicity (ties can be broken arbitrarily). When this is not the case, it is possible to consider a decoder that returns any element that approaches the infimum with a fixed precision, at the expense of having this precision in the decoding error , as in <cit.>.]

    (,) = _∈ -

satisfies the Instance Optimality Property for the operator  and model  with constants =1 and =2, pseudometrics  and  where  is defined by (,'):=(,') + 2 - ', and error =.



Theorem <ref> states that if the LRIP is satisfied, then the decoder that returns the element in the model that best matches the measurement is instance optimal, with a special metric . On the other hand, if some instance optimal decoder exists, then the LRIP must be satisfied.

In other words, when the LRIP is satisfied, then we know that a negligible amount of information is lost when encoding a signal well-modeled by . Conversely, if the LRIP is not satisfied, one has no hope of deriving an instance optimal decoder. 







 §.§ Random operator, from uniform recovery to non-uniform recovery



In the vast majority of the compressive sensing literature, the measurement process is drawn at random: for instance, in the finite dimensional case, it is an open problem to find deterministic matrices that satisfies the RIP with an optimal number of measurements (<cit.>, pp. 27), while on the contrary many classes of random matrices satisfy the RIP with high probability <cit.>.

A well-studied concept is that of uniform recovery guarantees, where one shows that, with high probability on the draw of , the LRIP holds. It follows by Theorem <ref> that there is a decoder such that, with high probability on the draw of , all signals from  can be stably recovered. There is also a notion of non-uniform recovery, where one considers a decoder  and wonders if, given an arbitrary signal close to , this signal is stably recovered (with high probability on the draw of ) from +.

In this section we introduce a non-uniform version of the LRIP, and show that it is a sufficient condition for the existence of a non-uniform instance optimal decoder. 
We start by discussing a notion of projection on the model.

 As we will see, in non-uniform recovery the distance from  to  is replaced by the distance from  to a particular element _ =, where :→ is a “projection” function with respect to some metric . In full generality, it is not guaranteed that there exists  such that (,) = (,), but one can always define it such that for all , (,) ≤(,)+ε for an arbitrary small ε>0.


Let us now introduce the proposed non-uniform IOP and LRIP.


A decoder  satisfies the non-uniform Instance Optimality Property for the (random) mapping , model  and projection function , 
with constants , >0, pseudometrics ,, probability 1- and error ≥ 0 if: 

    ∀∈,  _[∀∈, (, ) ≤(,) +  + ]≥ 1-ρ

where (,  + ) is denoted by .






Note that in this definition the IOP is non-uniform with respect to the data  but uniform with respect to the noise , meaning that with high probability on the draw of  the (fixed) data can be stably recovered from a measurement vector with any additive noise.





The operator  satisfies the non-uniform LRIP for the model  
with constant >0, pseudometric , probability 1- and error ≥ 0 if: 

    ∀∈,  _[∀'∈, (,') ≤ - ' + ]≥ 1-ρ.



This LRIP is in fact “semi”-uniform: it is non-uniform with respect to one element  but uniform with respect to '. A “fully” non-uniform LRIP would, in fact, be almost always valid for many operators (see Section <ref>), and thus probably too weak to yield recovery guarantees.

Before stating our result, let us remark that the definition of the metric  in Theorem <ref> (ii) involves the operator , which is potentially problematic when it is random. To solve this, <cit.> introduces a so-called Boundedness Property (BP) in the classical sparse setting in finite dimension. We extend this notion in the considered context here. 

 The operator  satisfies the Boundedness Property with constant , pseudometric  and probability 1- if: 

    ∀∈, ∀_∈,  _[-_≤,_]≥ 1-ρ.





We then have the following result, proved in <ref>.


Consider a random operator . 
Assume that:


  * the operator  satisfies the non-uniform LRIP for the model  with constant >0, pseudometric , probability 1-_1 and error ≥ 0 ;

  * the operator  satisfies the non-uniform Boundedness Property with constant , pseudometric  and probability 1-_2 ;

Then, the decoder  defined by (<ref>) satisfies the non-uniform Instance Optimality Property for the operator , model  and any projection function  with constants =1, =2, pseudometrics  and  :=  + 2, probability 1-_1-_2 and error =.


Compared with the result in <cit.>, which proves non-uniform recovery under a uniform LRIP and the BP in the finite-dimensional case, our result holds under weaker hypotheses.

For the converse implication of Theorem <ref>, unlike Theorem <ref>, the non-uniform IOP does not seem to directly imply the non-uniform LRIP. 



§ A TYPICAL PROOF OF THE LRIP


In this section, we outline a possible strategy to prove the LRIP, inspired by the proof for random matrices in <cit.>. 

This relatively simple proof has two steps: first, a pointwise concentration result, and second, an extension by covering arguments. For a set S and a metric d, we denote by Sd∈∪+∞ the minimum number of balls of radius , with centers that belong to S, required to cover S.



 §.§ Linear case




We start with the linear case, which follows closely the proof in <cit.>. We treat the uniform case (Def. <ref>), with no error (= 0).


Assume (,) and (,·) are both vector spaces, and that we have a random linear operator :→ such that 

the following concentration result holds:

    ∀, ' ∈ s.t. (,')>0,  _ - '(,') - 1 ≤ -t ≤ e^-c(t)

for an increasing concentration function c(t)>0. Typically, the “bigger” the space  is (i.e. the more measurements we collect), the higher the concentration function is: often, for m measurements (= ^m or ^m), classical concentration inequalities yield c(t) ∝ mt^2.

This property 
proves a “pointwise” (or “fully” non-uniform) LRIP: for two given ,', the quantity - ' is a good approximation of (,) with high probability. We now invert the quantifiers by covering arguments. 



From the formulation of the concentration (<ref>) we see that a particular set of interest is the so-called normalized secant set <cit.>:

    =  - '(,') | ,'∈, (,')>0⊂



The proof of the following result is in <ref>.

Consider 0<t<1. Assume that the concentration property (<ref>) holds, that  has finite covering numbers, and that for any draw of  and any 𝐬,𝐬'∈ we have 𝐬-𝐬'≤ C(𝐬, 𝐬'). Set = t/2C. Define the probability of failure

    ρ = · e^-c(t/2)

Then the operator  satisfies the uniform LRIP for the model  with constant = (1-t)^-1, metric , probability 1-ρ and error = 0.


This proof of the RIP has been used for instance in classical compressive sensing <cit.> or for random linear embeddings of Radon measures <cit.>. It is also used in a constructive manner to build appropriate operators  in <cit.>.



 §.§ Non-linear case

It is possible to adapt the previous proof to non-linear operators, by distinguishing the case where  and ' are “close”, for which we resort to a linearization of  and properties of the normalized secant set, and the case where  and ' are distant from each other, for which we use directly the covering numbers of the model. We treat here the non-uniform case (Def. <ref>). 


Assume again that (, ) and (, ·) are vector spaces. 
Assume that we have a random map :→ such that the concentration property (<ref>) holds.




Next, suppose that there exists ε_0>0 such that for any fixed ∈:


  * for all '∈ and any draw of , - '≤ C_1 (, ')


  * the model  has finite covering numbers with respect to , 
 and in particular it also has finite diameter M_ = sup_,'∈(,'). 

  * for all 0<ε≤ε_0, the following version of the normalized secant set _ε :=  - '/(,') | ' ∈, 0<(,')≤ε has finite covering numbers. 

  * for all ' ∈ such that (,')≤ε_0, and any draw of , we have
- ' - D_( - ')≤ C_2 (,')^2,
where D_:→ is a linear map such that for all 𝐬,𝐬' ∈_ε_0, D_(𝐬-𝐬')≤ C_3 (𝐬,𝐬').

The following result is proved in <ref>.

Assume that the properties (i)-(iv) above are satisfied. Set ε≤minε_0,t/8C_2, ' ≤t/4C_3 and ≤tε^2/(4C_1)/ε + M_.

Define the probability of failure

    ρ :=  + _ε'· e^-c(t/2)


Then the operator  satisfies the non-uniform LRIP for the model  
with constant = (1-t)^-1, metric , probability 1-ρ and error = 0.




 §.§ Illustration


In this section we illustrate the non-linear LRIP on a simple example; that of recovering a vector from a random features embedding, which is a random map initially designed for kernel approximation, see <cit.>. Such a random embedding can be seen as a one-layer neural network with random weights, for which invertibility and preservation of information have recently been topics of interest <cit.>.

Consider = ^d and define  to be a Union of Subspaces, which is a popular model in compressed sensing <cit.>, with controlled norm: = ⋃_i=1^N (S_i∩ B_M) where B_M = , _2≤ M 
and each S_i is an s-dimensional subspace of ^d. As in <cit.>, we choose a sampling that is a reweighted version of the original Fourier sampling for kernel approximation <cit.>, for the Gaussian kernel with bandwidth σ>0. It is defined as follows: for a number of measurements m, the measurements space is = ^m, the random map is defined as = 1/√(m)φ__j()_j=1^m where φ_() = e^_j^⊤/f() and _j∈^d are drawn i.i.d. from Λ = f()^2 𝒩(0,σ^-2) (where 𝒩 is a Gaussian), with f()^2 = 1/3∑_ℓ=0^2_2^2ℓ/γ_2ℓ and γ_ℓ = _∼𝒩(0,σ^-2)_2^ℓ = d^ℓ/2/σ^ℓ. One can verify that ∫ dΛ() = 1, i.e. Λ is a valid probability distribution. The metric  is here the kernel metric associated to the Gaussian kernel with bandwidth σ:

    (,') := 21 - exp- - '_2^22σ^2

We have the following result, which proof is in <ref>.

If the number of measurements is such that

    m≳ t^-2· s·logMdσ t + log(N) + log1ρ

Then the operator  satisfies the non-uniform LRIP for the model  
with constant = (1-t)^-1, metric , probability 1-ρ and error =0, as well as the BP (Def. <ref>) with constant β=1+t, metric  and probability 1-ρ.

Hence, using Theorem <ref>, we have shown that a reduced number of random features preserves all information when encoding signals that are (in this case) well-modeled by a union of subspaces, with respect to the associated kernel metric. This preliminary analysis may have consequences for classical random feature bounds in a learning context <cit.>.



§ CONCLUSION

In this paper we generalized a classical property, the equivalence between the existence of an instance-optimal decoder and the LRIP, to non-linear inverse problems with possible quantization error or limited algorithmic precision, and data that live in any pseudometric set. We also formulated a version of the result for non-uniform recovery, by introducing a non-uniform version of the LRIP. To further illustrate this principle, we provided a typical proof strategy for the LRIP that one might use in practice, and gave an example of non-linear LRIP on random features for kernel approximation.

Although relatively simple in their proofs, these results may have important consequences for a large class of linear or non-linear inverse problems, where one seeks stable and robust recovery. Naturally, once the LRIP guarantees (or disproves) the existence of an instance optimal decoder, an outstanding question is the existence of efficient algorithms that provide equivalent guarantees, as in classical compressive sensing <cit.> or some of its recent extensions <cit.>.



§ REFERENCES

plain






§ PROOF OF THEOREM <REF>




  * Consider , ' ∈. By triangular inequality we have 

    (,') ≤(,(,') + ((,'),').

Then, by applying the Instance Optimality Property with noise :='- we get (,(,') ≤'- +, and by applying again the Instance Optimality Property it holds that ((,'),')≤, hence the result.

  * Consider any signal ∈ and noise ∈, denote =  + and =(,). Let _∈ be any element of the model. 
We have:

    (,) ≤    (,_) + (_,) 
    LRIP≤    (,_) + _ -  + 
    ≤    (,_) + _ -  +  -  +  .

By definition of the decoder (<ref>) we have - ≤_ - and therefore

    (,) ≤    (,_) + 2_ -  + 
    ≤    (,_) + 2_ -  + 2 -  + 
    ≤    (,_) + 2 +

where (,')=(,') + 2 - '. Since the result is valid for all _∈, we can take the infimum of (,_) with respect to _∈. 




§ PROOF OF THEOREM <REF>


Let ∈ be a fixed signal and denote by _ = ∈.


Applying the non-uniform LRIP, with probability at least 1-_1 on the draw of the operator  we have

    ∀' ∈, (_,') ≤_ - '_ +  .


In the same fashion, 
applying the non-uniform Boundedness Property, with probability at least 1-_2 on the draw of the operator  we have

    -_≤,_ .


Therefore, by a union bound, with probability at least 1-_1-_2, both (<ref>) and (<ref>) are satisfied. If this is the case, for all noise vector ∈, denoting by =  + and =(,), it holds that:

    (,) ≤    (,_) + (_,) 
    (<ref>)≤    (,_) + _ -  + 
    ≤    (,_) + _ -  +  - +  .


Once again by definition of the decoder (<ref>) we have - ≤_ - and therefore

    (,) ≤    (,_) + 2_ - + 
    ≤    (,_) + 2_ -  + 2 - + 
    ≤    (,_) + 2+ .

by applying (<ref>), which is the desired result.



§ PROOF OF PROPOSITION <REF>


From the definition of the normalized secant set, our goal is to prove that with high probability on the draw of , for all 𝐬∈ we have 𝐬≥ 1-t.

Let ,ε>0 be small constants which values we shall define later and N := be the covering numbers of the normalized secant set. Let 𝐬_1,…,𝐬_N be an -covering of the normalized secant set . 

By the concentration property, it holds that, with probability at least 1-Ne^-c(t/2), for all 𝐬_i we have 

    𝐬_i≥ 1-t/2



Now, given any element of the normalized secant set 𝐬∈, one can find an element of the covering 𝐬_i such that 𝐬 - 𝐬_i≤. Assuming (<ref>) holds, we have

    𝐬≥𝐬_𝐢 - 𝐬-𝐬_𝐢≥ 1- t/2 - C

and therefore by choosing = t/(2C)  we obtain the desired result.




§ PROOF OF PROPOSITION <REF>


Fix any _∈.

Let ,',ε>0 be small constants which values we shall define later, such that ε≤ε_0. Define _ε = \∈, (_,)≤ε the model with a ball around _ removed,
and N := _ε, N' := _ε'. Let _1,…,_N and 𝐬_1,…,𝐬_N' be, respectively, a -covering of _ε and a '-covering of _ε, with '_i∈ defined such that 𝐬_i = _ - '_i/(_,'_i) and 0<(_,'_i)≤ε.

By the concentration property, it holds that, with probability at least 1-(N+N')e^-c(t/2), for all = _i or = '_i for all indices i, we have 

    _ - ≥ (1-t/2) ·(_,).

Our goal is to extend this property to any element = in the model .

Let ∈ be any element of the model. We distinguish two cases.
If ∈_ε, i.e. (_,)≥ε, we consider _i ∈_ε an element of the covering of _ε such that (, _i)≤. We have:

    _ - (_,) - _ - _i(_,_i)≤    _ - (_,) - _ - _i(_,) + _ - _i(_,) - _ - _i(_,_i)
    
    =     - _i(_,) + _ - _i1(_,) - 1(_,_i)
    (i),(ii)≤    C_1 ε + C_1 M_(,_i)(_,)(_,_i)
    ≤    C_1 ε1+M_ε

and therefore

    _ - /(_,)≥ 1-t/2-C_1 /ε1+M_/ε


Now, when (_,)≤ε, we define 𝐳 := _-/(_,) and note that 𝐳∈_ε. We approximate it by an element of the covering of the normalized secant set 𝐬_i = _ - '_i/(_,'_i)∈_ε (meaning that (_,'_i) ≤ε) that verifies (𝐳, 𝐬_i) ≤'. Then, we have

    _ - (_,) - _ - '_i(_,'_i)≤    _ - (_,) - D_𝐳 + D_(𝐳 - 𝐬_i) + D_𝐬_i - _ - _i(_,_i)
    (iv)≤    C_2 (_,) + C_3 '+ C_2(_,'_i) ≤ 2C_2 ε + C_3 '

and therefore

    _ - /(_,)≥ 1-t/2-(2C_2 ε + C_3 ')


To conclude, we set ε≤minε_0,t/8C_2, ' ≤t/4C_3, ≤tε^2/(4C_1)/ε + M_ to obtain the desired result.




§ PROOF OF PROPOSITION <REF>




  
Concentration property. The concentration result is based on the fact that - _2^2 ≈_φ_() - φ_(')^2 = (,')^2 by definition of the random features. Using simple function studies and a Bernstein concentration inequality with a control on moments of all orders, it is possible to show (see <cit.>, eq. (160) then Prop. 6.11) that the concentration result (<ref>) is valid with c(t) ∝m t^2/1+t (we do not reproduce the detailed proof here for brevity). 

Since this Berstein inequality is in fact valid for all vectors (not necessarily in the model), as a consequence the Boundedness Property is also satisfied with constant β=1+t, metric  and probability 1-e^-c(t).

We now check hypotheses (i)–(iv) in Proposition <ref>. We are going to repeatedly use the fact that for ,'∈, since _2≤ M, we have

    ℓ - '_2 ≤(,') ≤ L  - '_2

where ℓ := 2·1-exp-M^2/(2σ^2)/M and L = M/σ^2.


  
(i) Using a first-order Taylor expansion we have - '_2 ≤∑_j=1^m _j_2^2/m f(_j)^2^1/2 - '_2≲√(γ_2) - '_2 hence by (<ref>) hypothesis (i) is valid with C_1 ∝√(γ_2)/ℓ.



  
(ii) It is immediate that M_ = ML. Then, using the well-known fact that for each S_j we have S_j∩ B_M·_2 = M/^s, by a union bound and (<ref>) we have ≤NLM/^s.



  
(iii) Similar to the model, for all ε the normalized secant set is included in a union of subspace _ε⊂⋃_i,j=1^N S_ij∩ B_M/ℓ, with norm controlled by M/ℓ by (<ref>), and where S_ij = S_i + S_j (sum of subspaces). Hence, since S_ij∩ B_M/ℓ·_2 = M/ℓ^2s, by a union bound and (<ref>) we have _ε≤N^2LM/ℓ^2s.



  
(iv) Finally, by a Taylor expansion we have

    φ_() - φ_(') = ^⊤/f()( - ') e^^⊤ - 1/2·(^⊤(-'))^2/f()e^^⊤”

where ” = θ + (1-θ)'. Hence hypothesis (iv) is satisfied with C_2 = C_1 and C_3 = √(γ_4)/ℓ^2, which concludes the proof.
