Jean-Michel Loubes
email: loubes@math.univ-toulouse.fr

Lude Carenne

Ña

PENALIZED ESTIMATORS FOR NON LINEAR INVERSE PROBLEMS

Keywords: 1991 Mathematics Subject Classification. Primary: 60G17, Secondary:62G07 ill-posed Inverse Problems, Tikhonov estimator, projection estimator, penalized Estimation, model selection

In this article we tackle the problem of inverse non linear ill-posed problems from a statistical point of view. We discuss the problem of estimating an indirectly observed function, without prior knowledge of its regularity, based on noisy observations. For this we consider two approaches: one based on the Tikhonov regularization procedure, and another one based on model selection methods for both ordered and non ordered subsets. In each case we prove consistency of the estimators and show that their rate of convergence is optimal for the given estimation procedure.

Introduction

In many problems it is necessary to recover an indirectly observed signal x 0 based on the non linearly transformed and noisy observation model (1.1) y(t i ) = F (x 0 )(t i ) + ε i , i = 1, . . . , n.

We assume F : X → Y is a known non linear operator between X, Y Hilbert spaces, (t i ) is a fixed observation scheme and ε i are i.i.d. realizations of a certain random variable ε.

Throughout the paper, we shall denote y = (y(t i )) n i=1 . We assume that the observations y(t i ) ∈ IR.

When F is linear, two main estimation procedures have been considered. Namely, regularized estimators such as the Tikhonov estimator, see for instance [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF][START_REF] Mair | Statistical inverse estimation in Hilbert scales[END_REF], and non linear threshold estimators [START_REF] Kalifa | Thresholding estimators for linear inverse problems and deconvolutions[END_REF][START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF]. Rates of convergence for regularized estimators are known and are seen to be optimal for an appropriate selection of the regularization parameter which depends on the regularity of the unknown function. Moreover, based on concentration inequalities it is possible to show that the addition of an appropriate penalization term allows selecting the regularization parameter or the projection subspace based on the data, in such a way as to maintain the best possible rates. Optimal choices for the penalty term can be deduced for example from the general results for Gaussian model selection in [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. An application of these penalty methods is considered in [START_REF] Loubes | Adaptive complexity regularization for inverse problems[END_REF] for general regularization methods. The second approach has its most popular version in the wavelet-vaguelet decomposition introduced in [START_REF] Donoho | Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition[END_REF], further developed in [START_REF] Kalifa | Thresholding estimators for linear inverse problems and deconvolutions[END_REF][START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF].

However, scarce statistical literature exists when F is non linear. Among the few papers available, we point out the works [START_REF] O'sullivan | Convergence characteristics of methods of regularization estimators for nonlinear operator equations[END_REF] or [START_REF] Snieder | An extension of Backus-Gilbert theory to nonlinear inverse problems[END_REF] where some rates are given, and that of Bissantz et al. in [START_REF] Bissantz | Consistency and rates of convergence of nonlinear Tikhonov regularization with random noise[END_REF] where they discuss a non linear version of the method of regularization (MOR).

Different approaches are also developed in [START_REF] Chow | Statistical approach to dynamical inverse problems[END_REF] for dynamical inverse problems or in [START_REF] Gamboa | New Bayesian methods for ill posed problems[END_REF] for Maximum Entropy Methods.

Not alike the random setting, the deterministic non linear ill-posed inverse problem literature is extensive. Most commonly, authors propose L 2 regularized Tikhonov type estimators and show that they provide a stable method for approximating the solution. For a general discussion on regularization methods, we refer the reader to [START_REF] Engl | Regularization methods for solving inverse problems[END_REF][START_REF] Tikhonov | Nonlinear ill-posed problems[END_REF]. As in the linear case, the choice of the regularization parameter is crucial. This issue is often practically solved by numerical methodology which relies on grid methods and iterative algorithms, see for instance [START_REF] Neubauer | Tikhonov regularization of nonlinear ill-posed problems in Hilbert scales[END_REF] or [START_REF] Jin | A discrete scheme of Landweber iteration for solving nonlinear ill-posed problems[END_REF]. On the other hand, a priori optimal choices of the smoothing sequence are given in the work of [START_REF] Tautenhahn | Tikhonov regularization and a posteriori rules for solving nonlinear ill posed problems[END_REF], leading to estimators of x 0 which attain the best possible rates, whenever its regularity is known beforehand.

Our main goal here is to provide a data driven estimator of the regularization parameter in the Tikhonov procedure and of the "cutoff" point for projection estimators, that behaves as well as the best possible choice in each case. Namely, we consider choosing the regularization parameter or subspace that minimizes the empirical quadratic loss function plus an appropriate penalty, as in the linear case. The fact that F is non linear requires introducing certain technical restrictions which shall be discussed in Section 2.

Given the Tikhonov regularization procedure, which shall be discussed in detail in Section 3, we consider the following estimator of x 0 ,

xα k = x ⋆ + (T * m 0 T m 0 + α k I m 0 ) -1 T t m 0 y,
where k is selected as the solution of

k := arg min k∈K R α k (y -F (x α k )) 2 + pen(α k ) ,
for an appropriate penalization term pen(α k ). Here T m 0 = T Π Ym 0 , where Y m 0 is a certain subspace of Y and Π Ym 0 stands for the projection over this subspace, T is a certain linear approximation of F and x ⋆ is an "initial guess" for x 0 . We assume that x 0 -x ⋆ belongs to the orthogonal complement of the nullspace of T .

Our main result in this section, Theorem 3.1, establishes that the L 2 risk of this data driven estimator xα k attains the same convergence rates as those obtained for the best possible choice of the regularization parameter α k , which typically depends on the regularity conditions of the unknown signal x 0 .

Our next results deal with projection estimators. Always aiming at constructing data driven estimators of the "cutoff" point, we study two procedures. First, we consider selecting a subspace over a nested collection of linear subspaces Y m , m ∈ M n a collection depending on n. The optimal m is chosen as

m = arg min m∈Mn Π Ym (y -F (x m )) 2 n + pen(m)
where pen(m) is an appropriate penalization term which shall be discussed in Section 4, Π Ym stands for the projection over the subspace Y m , n is the empirical norm based on the observation scheme (t i ), which shall be discussed in Section 2, and

xm := x ⋆ + arg min x∈x ⋆ +T * Ym Π Ym (y -F (x)) 2 n .
Given the "initial guess" x ⋆ , we assume x -x ⋆ < ρ for some ρ, T is an approximation of F ′ (x 0 ) and T * stands for its adjoint. As above, we assume that x 0 -x ⋆ belongs to the orthogonal complement of the nullspace of T . We then show, Theorem 4.1, that this data driven selection of m attains the same convergence rates as those obtained for the best possible choice of the "cutoff" point.

Second, we consider the problem of non ordered model selection, which can be thought of as a threshold estimator for the estimated coefficients of x 0 over a certain linear subspace

X m 0 := T * m 0 Y
, where T m 0 is defined as in the Tikhonov procedure. More precisely, let m 0 be a certain big collection of possible models. Set

xm = x ⋆ + arg min x∈Xm (T t m 0 T m 0 ) -1 T t m 0 Π Ym 0 (y -F (x)) 2 .
The optimal model is chosen as

m = arg min m⊂m 0 (T t m 0 T m 0 ) -1 T t m 0 Π Ym 0 (y -F (x m )) 2 + pen(m),
for a certain penalty function depending on the family of linear operators {F ′ (x), x -x ⋆ < ρ}, for some ρ and an appropriate "initial guess" x ⋆ , which, as above, is assumed such that x 0 -x ⋆ belongs to the orthogonal of the nullspace of T . Our main result in this section, Theorem 4.5 states that this data driven choice of m attains the same convergence rates as those obtained by the best possible model choice.

The article is organized as follows. In Section 2 we describe the general framework. In Section 3 we provide an adaptive estimator for the regularization parameter for Tikhonov like estimators, and show the resulting estimator is consistent. Section 4 is devoted to model selection estimators for non linear inverse problems, first with embedded projection spaces and then with non ordered selection. Some conclusions are drawn in Section 5. Section 6 is devoted to technical lemmas which are useful throughout the paper.

Basic assumptions and notation

In this section we introduce some general notation and assumptions. These include standard concentration assumptions over the observation noise and some restrictions over the class of operators F (.).

Since the operator F is non linear, our convergence analysis will be a local one. Hence it is necessary to start with an initial guess of the solution. We require that this starting point x ⋆ allows us to construct a good approximation of the Fréchet derivative of the operator at x 0 :

F ′ (x 0 ). More precisely, we assume F is Fréchet differentiable and that the range of

DF (x 1 , x 2 ) = 1 0 F ′ (x 1 θ + x 2 (1 -θ))dθ
remains unchanged in a neighborhood of the initial solution x ⋆ , i.e in the ball B ρ (x ⋆ ) = {x, x -x ⋆ ≤ ρ}, for a certain ρ > 0. The above discussion is summarized by the following condition AF control over the non linear part of the differential operator: There exist c T , a fixed linear operator T (generally T = F ′ (x ⋆ )) and a linear operator depending on x and x ′ , written R(x, x ′ ) such that for x, x ′ ∈ B ρ (x ⋆ )

F (x) -F (x ′ ) = T R(x, x ′ )(x -x ′ ), with I -R 2 ≤ c T .
This kind of condition is considered in [START_REF] Kaltenbacher | Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems[END_REF] as an alternative to the tangential cone condition.

The previous author in [START_REF] Bissantz | Consistency and rates of convergence of nonlinear Tikhonov regularization with random noise[END_REF] shows that this AF condition is satisfied, for instance, by the inverse groundwater filtration problem of identifying the transmissivity a in

-∇(a∇u) = f in Ω (2.1) u = g on ∂Ω,
on a C 2 domain Ω ⊂ R 2 , from measurements of the piezometric head u, where F is the parameter-to-solution map F : a → u.

Hence, the non linear operator is replaced by T , a known bounded linear operator that can be viewed as some approximation of F ′ (x) in a neighborhood B ρ (x ⋆ ), which we must be able to use in our computations. In contrast, under AF, operator R is not required explicitly.

Under such restrictions, the non linearity of the problem does not change the rate of convergence and we still are able to build adaptive estimators. We remark that AF is not strictly comparable to the Lipschitz condition required in Theorem 3 in [START_REF] Bissantz | Consistency and rates of convergence of nonlinear Tikhonov regularization with random noise[END_REF], their condition being a global one over the domain of F . However locally AF is stronger.

Recall we want to estimate a function x 0 : IR → IR observed in a inverse model

y(t i ) = F (x 0 )(t i ) + ε i , i = 1, . . . , n.
It is important to stress that the observations depend on a fixed design (t 1 , . . . , t n ) ∈ IR n .

This will require introducing an empirical norm based on this design. Let Q n be the empirical measure of the co-variables

Q n = 1 n n i=1 δ t i , where δ is the Dirac function. The L 2 (Q n )-norm of a function y ∈ Y is then given by y n = ( y 2 dQ n ) 1/2 ,
and the empirical scalar product by < y, ε > n = 1 n n i=1 ε i y(t i ). Note that this empirical norm is defined over the observation space Y . Over the solution space X we will consider the norm given by the Hilbert space structure. For the sake of simplicity, we will write . X = .

when no confusion is possible. Over a finite dimensional space, the norm . will always stand for the Euclidean norm and if v ∈ R d , v t will stand for the transpose vector. Likewise for any matrix A ∈ R d×r A t will stand for the transpose matrix and A + := (A t A) -1 A t for the generalized inverse. Considered as an operator, we will write A * for the adjoint of the corresponding operator. Given any square matrix B, T r(B) and ρ(B) will stand for the trace and the spectral radius respectively.

We also introduce certain standard assumptions on the observation noise AN moment condition for the errors: ε is a centered random variable satisfying the moment condition IE(|ε| q /σ q ) ≤ q!/2 for

all q ≥ 1, with IE(ε 2 ) = σ 2 .
As usual in statistics, assume that X satisfies a certain smoothness condition. In this paper, we assume the following source assumption encountered typically in the inverse problems literature, see for instance [START_REF] Engl | Regularization of inverse problems[END_REF]. We point out that the source condition is assumed with respect to the linear operator T defined in AF.

SC source condition:

There exists 0 < ν ≤ 1/2 such that x 0 ∈ Range((T * T ) ν ) := R((T * T ) ν ) Moreover consider A ν,ρ = {x ∈ X, x = (T * T ) ν ω, ω ≤ ρ}
where 0 ≤ ν ≤ ν 0 , ν 0 > 0 and use the further notation (2.2)

A ν = ρ>0 A ν,ρ = R((T * T ) ν )
These sets are usually called source sets, x ∈ A ν is said to have a source representation.

Estimating over all X is in general not possible because we can only observe the functions over the fixed design (t 1 , . . . , t n ). Thus assume that we are equipped with a sequence of linear subspaces Y m , m ≥ 1, whose union is dense in Y , . We assume dim(Y m ) = d m . We are interested in a sub collection of these spaces generated by a set of indices M n . In this paper, we will use these approximation spaces as projection spaces in order to study the data. So, denote the projection of any space W over any subspace Z by Π Z W . Let Π n Ym stand for the projection in the empirical norm. Set also the corresponding projected operator T m = Π n Ym T . Using a sieve of the space Y , we consider the corresponding approximation spaces in the space X, defined as

X m = T * m Y . By construction Π Xm = (Π n Ym T ) + Π n Ym T.
We point out that both T m and its adjoint operator T * m depend on the observation sequence t i . However, we will usually drop this fact from the notation. To illustrate this assertion, consider the following example.

Example 2.1. If Y m is a collection of nested spaces, generated by some orthonormal basis φ = (φ 1 , . . . , φ dm ), with respect to the L 2 norm over Y , and F = T = Id, then

Π n Ym y = dm j=1 y j,n φ j ,
where y j,n =< Π n Ym y, φ j > n are the solution to the projection problem under the empirical measure Q n . Set G m = (φ j (t i )) i,j , i = 1, . . . , n and j = 1, . . . , d m . Thus, we may write in matrix notation

Π n Ym y = (G t m G m ) -1 G t m (y(t 1 ), . . . , y(t n )).
Remark that, as above, we can always define T m in matrix notation and thus T t m y always makes sense. Moreover, if u ∈ Y , we will use indistinctly T t m u ∈ R dm and T * m u ∈ X m , the latter in operator notation.

In our case we will relate the degree of ill-posedness of T to Π n Ym as follows. IP ill-posedness of the operator: Let M n be an index set. For m ∈ M n there exists p > 0 such that

γ (m) := (I -Π n Ym )T = O(d -p m ).
p is the index of ill-posedness of the operator.

To illustrate this condition we include the following example

Example 2.2. The above assumption can be seen to hold under certain conditions over operator T and matrix G m defined in example (2.1). Let (σ j , φ j , ϕ j ) j be the singular value decomposition of operator T and assume that there exists d > 0 such that σ j = O(j -d ). Let Y m be the linear subspace generated by {ϕ j } 1≤j≤dm and assume that the fixed observation design t i , i = 1, . . . , n is such that this basis is also orthogonal in the empirical norm. Assume also that sup j=1,...,dm ϕ j ∞ < ∞. Then,

I -Π n Ym = I -Π Ym + Π n Ym (I -Π Ym ),
where

I -Π Ym = O(d -p m ) and Π n Ym (I -Π Ym )u = Π n Ym (I -Π Ym )u n ≤ (I -Π Ym )u n ≤ sup j=1,...,jm ϕ j ∞ (I -Π Ym )u .
Define

ν m := T + m Π n Ym .
This quantity controls the amplification of the observation error over the solution space X m .

Consider

γ m := inf v∈Ym, v =1 T * m v ,
which expresses the effect of operator T * m over the approximating subspace Y m . We have as in [START_REF] Neubauer | Tikhonov regularization of nonlinear ill-posed problems in Hilbert scales[END_REF], ν m ≥ γ m .

On the other hand this term is related to the goodness of the approximation scheme. Following the proof in [START_REF] Neubauer | Tikhonov regularization of nonlinear ill-posed problems in Hilbert scales[END_REF], it can be seen that γ m+1 ≤ T * (I -Π n Ym ) = (I -Π n Ym )T . The next assumption requires that γ m and γ (m) are of the same order, which will be written

γ m ∼ γ (m) .
AS amplification error: Assume

(2.3) γ m = O(d -p m ).
Moreover assume there exists a positive constant U such that

γ (m) γ m ≤ √ U.
Remark 2.1. Assumption AS thus establishes that the worst amplification of the error over X m is roughly equivalent to the best approximation over Y m in the empirical norm.

For this fixed m 0 , let (λ j , φ j , ϕ j ), j = 1, . . . , d m 0 be the singular value decomposition of operator T m 0 . For any u ∈ Y we can write T * m 0 u = dm 0 j=1 λ j φ j < u, ϕ j > n , which depends only on u = (u(x 1 ), . . . , u(x n )) t . As previously recall that G m 0 ∈ M dm 0 ,n is defined by G = (ϕ j (x i )) j,i , i = 1, . . . , n, j = 1, , d m 0 . Thus, abusing notation we may write

T t m 0 = D(G m 0 G t m 0 ) -1 G m 0 : R n → R dm 0
, where D = D(λ j ) j=1,...,dm 0 is the diagonal matrix with entries λ j . Since T t m 0 u = T * m 0 u the latter in operator notation, both interpretations will be used indistinctly. On the other hand, for x ∈ X m 0 , identified with a d m 0 dimensional vector, we can think of (T m 0 x(t 1 ), . . . , T m 0 x(t n )) = G t m 0 Dx. So that in matrix notation also

T * m 0 T m 0 = D 2 .

We introduce the following assumptions

SV: There exist positive constants

k 1 < k 2 such that k 1 j -p ≤ λ j ≤ k 2 j -p .
SF: Let ν j , j = 1, . . . , d m 0 be the eigenvalues of matrix G t G, then there exist constants a 1 < a 2 such that a 1 n ≤ ν j ≤ a 2 n.

Remark 2.2. Assumption SV is slightly stronger than AS as it establishes the exact order of the γ m . It is seen to hold, for instance, in example (2.2). Assumption SF is necessary to assure convergence results further on. It holds also in example (2.2).

Assume also, that the images by the linear operator T of x ⋆ and x 0 are close, in the sense that IG identifiability condition:

x 0 -x ⋆ ∈ Ker(T ) ⊥ ,
where Ker(T ) ⊥ is the orthogonal complement of the null space of the operator T .

The following approximation result ( [START_REF] Kaltenbacher | Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems[END_REF]) assures uniqueness of the sought solution if the initial guess is sufficiently close.

Lemma 2.3. Assume AF holds with c T < 1/2 and assume for x,

x ′ ∈ B ρ (x ⋆ ), F (x) = F (x ′ ) and x -x ′ ∈ Ker(T ) ⊥ . Then x = x ′ .
This lemma guarantees the identifiability of the estimation problem (1.1) since the solution is uniquely chosen. We are now ready to build adaptive estimators for non linear inverse problems.

Adaptive Tikhonov Regularization for non linear estimators

A straightforward generalization of the Tikhonov regularization procedure to non linear operators is to seek x m ∈ x ⋆ + X m , in such a way that F (x m ) is close to the data y, in the sense given by the Tikhonov regularization scheme.

To begin with, project the data onto the finite dimensional space, X m 0 , where we assume that

m 0 is such that (I -Π Xm 0 )(x 0 -x ⋆ ) ≤ inf m∈Mn [ (I -Π Xm )(x 0 -x ⋆ ) + d m n 1 γ m ].
This quantity can be chosen so as to not depend on the unknown regularity of the solution x 0 . Under assumption SC the above inequality is satisfied if the dimension of the set is such

that d 2νp m 0 ≥ n 2νp 4νp+2p+1 . Thus it is enough to choose m 0 such that d m 0 ≥ n 1/(2p+1) .
Let K be a set of indices and consider the corresponding smoothing sequences α k , k ∈ K.

Let T be as defined in assumption AF and for a fixed k ∈ K consider the non linear Tikhonov regularized estimator as

(3.1) xα k = x ⋆ + (T * m 0 T m 0 + α k I m 0 ) -1 T t m 0 y.
This estimator belongs to the class of regularized estimators where the regularization operator is given by

R α k = (T * m 0 T m 0 + α k I m 0 ) -1 T t m 0 . Let x α k = x ⋆ + R α k T
x 0 be the regularized true function, which measures the accuracy of the estimation procedure without observation noise. We highlight, that in the non linear case and contrary to the linear case, (3.1) is different from the usual expression for the Tikhonov estimate (3.2)

x ⋆ + arg min

x∈Xm Π n Ym 0 (y -F (x)) 2 + α k x -x ⋆ 2 .
In this part, we consider the problem of selecting a data driven smoothing sequence of the regularized estimator (3.1) achieving the best rate of convergence among the set of all sequences.

Consider the following penalty

pen(α k ) = rσ 2 (1 + L k )[T r(R t α k R α k ) + ρ 2 (R α k )],
with r > 2. Here, L k is a sequence of weights chosen to assure that

(3.3) Σ(d) := k∈K 2 dL k T r(R t k R k ) ρ 2 (R k ) + 1 [ d ρ 2 (nR k ) ] -1 e - √ dL k [T r(R t k R k )+ρ 2 (R k )]/ρ 2 (R k ) < ∞ for d as in Lemma 6.2.
The optimal regularization sequence indexed by k is selected as the solution of , the following inequality holds true

k := arg min k∈K R α k (y -F (x α k )) 2 + pen(α k ) ,
(3.4) IE Π Xm 0 (x α k -x 0 ) 2 ≤ 1 1 -c T inf k∈K [C(1+c T ) Π Xm 0 (x α k -x 0 ) 2 +2pen(α k )]+ Σ(d) (1 -c T )n ,
where Σ(d) was defined in (3.3).

Proof. From condition AF,

F (x 1 ) -F (x 2 ) = T R(x 1 , x 2 )(x 1 -x 2 ) with I -R 2 ≤ c T .
On the other hand, since R α k is a sequence of regularization methods (see [START_REF] Engl | Regularization methods for solving inverse problems[END_REF][START_REF] Tikhonov | Nonlinear ill-posed problems[END_REF]) it follows that there exist constants

C 1 < C 2 , such that C 1 ≤ R α k T ≤ C 2 .
Hence there exists a constant C such that for any k,

(1 -c T ) Π Xm 0 (x 1 -x 2 ) 2 ≤ R α k (F (x 1 ) -F (x 2 )) 2 ≤ C(1 + c T ) Π Xm 0 (x 1 -x 2 ) 2 .
Thus, for any

x ∈ x ⋆ + X m 0 , (1 -c T ) Π Xm 0 (x α k -x 0 ) 2 ≤ C(1 + c T ) Π Xm 0 (x -x 0 ) 2 + 2pen(α k ) + 2 sup k [ R α k ε 2 -pen(α k )].
The result follows directly from Lemma 6.2.

It is important to stress that computing the estimator (3.1) may be complicated in practice since it involves inverting a matrix and recquires a particular attention. But the major drawback in this approach is that the bias term in the oracle inequality Π Xm 0 (x α k -x 0 ) 2 may not be sharp, thus leading to other estimation methods.

Model selection

Ordered selection.

Let M n be a set of indices and consider Y m , m ∈ M n a sequence of nested subspaces. We consider projection estimators and define ordered selection as the problem of choosing the best m based on the observations. For this we will construct penalized estimators that require finding the first m that minimizes

Π n Ym (y -F (x m )) 2 n + pen(m),
where pen(m) is an increasing function. From a deterministic point of view this is essentially equivalent to choosing m based on the discrepancy principle (see [START_REF] Neubauer | Tikhonov regularization of nonlinear ill-posed problems in Hilbert scales[END_REF] for an application of the discrepancy principle to non linear problems). More precisely, for a chosen m, define the projection estimator

xm := x ⋆ + arg min x∈Xm,x∈Bρ(x ⋆ ) Π n Ym (y -F (x)) 2 n .
The optimal m is chosen as

(4.1) m = arg min m∈Mn Π n Ym (y -F (x m )) 2 n + pen(m)
where pen(m) = r(1 + L)σ 2 d m /n, r = 2 + θ, for some θ > 0, and L > 0.

Numerically, minimization in the above expression is more complicated than it would be in the linear case because we must calculate the projection matrix at each step. However, choosing an efficient sampling scheme will do the job, i.e., such that the projection matrix is diagonal or block diagonal.

We will assume the following condition over the sampling scheme holds true CB: There exist constants,

l 1 < l 2 such that for u ∈ Y m 0 l 1 u ≤ u n ≤ l 2 u .
The next theorem provides an oracle inequality which proves optimality of the estimator x m.

Theorem 4.1. Assume AN, IP, AS, IG, AF and CB hold true. There exist constants C(r, σ), and k(r, σ) such that with probability greater than 1 -2e -ku 1/(2(p+1))

(4.2) x m -x 0 2 ≤ C(r, σ) inf m∈Mn ( (I -Π Xm )x 0 2 + pen(m) γ 2 m ) + u n .
Remark 4.2. For each fixed m, the quantity

∆ m := (I -Π Xm )x 0 2 + pen(m) γ 2 m
is of the same order as the MISE for this problem , that is, IE xm -x 0 2 . Hence, the bounds are equivalent to those found in [START_REF] Bissantz | Consistency and rates of convergence of nonlinear Tikhonov regularization with random noise[END_REF] under the appropriate source conditions. We do stress, however, that this knowledge is not required in order to establish our results.

Proof: For each m, assume

x m = x ⋆ + z m , z m ∈ X m , and x m ∈ B ρ (x ⋆ ). Set w(x m ) = Π n Ym (F (x m ) -F (x 0 )) Π n Ym (F (x m ) -F (x 0 )) n .
We divide the proof in a series of steps.

• Control of d m. Recall the penalization is defined by pen(m) = r(1

+ L)σ 2 [d m + 1]/n,
with 2 < r a certain constant.

We have, following standard arguments, that

Π n Y m (F (x m) -F (x 0 )) 2 n + pen( m) ≤ | Π n Ym (F (x m ) -F (x 0 )) 2 n + 2 < Π n Y m (F (x m) -F (x 0 )), ε > n -2 < Π n Ym (F (x m ) -F (x 0 )), ε > n -Π n Y m ε 2 n + Π n Ym ε 2 n + pen(m).
Let 0 < κ < 1. Since 2ab ≤ κa 2 + 1 κ b 2 , for any a, b we have for any m and

x m ∈ X m 2 < Π n Ym (F (x m ) -F (x 0 )), ε > n ≤ κ Π n Ym (F (x m )) -F (x 0 )) 2 n + 1 κ | < w(x m ), ε > n | 2 .
Set for q, x > 0, t(m) = c[d m + 1] + (1 + q) -1 x and assume κ and g, c are chosen in such a way that 1 κ ((1 + g)

+ (1 + 1/g)c) = c 1 < r(1 + L).
Remark, κ can be chosen very close to one. Thus,

(1 -κ) Π n Y m (F (x m) -F (x 0 )) 2 n + (r(L + 1) -c 1 ) σ 2 [d m + 1] n ≤ (1 + κ) Π n Ym (F (x m ) -F (x 0 )) 2 n + 1 κ | < w(x m), ε > n | 2 -c 1 σ 2 ([d m + 1]) n -Π n Y m ε 2 n + Π n Ym ε 2 n + 1 κ | < w(x m ), ε > n | 2 -c 1 σ 2 ([d m + 1]) n + (r(L + 1) + c 1 ) σ 2 [d m + 1] n .
Now since κ < 1 and c 1 = c 1 (q) < r(L + 1), we have,

σ 2 (d m + 1) n ≤ 2 r(1 + L) -c 1 ( Π n Ym (F (x m ) -F (x 0 )) 2 n + pen(m)) + 2 κ(r(1 + L) -c 1 ) sup m, um n=1 (| < u m , ε > n | 2 - c 1 2 κ( σ 2 [d m + 1] n )),
for u m ∈ S m a countable dense subset of X m . Note that

(4.3) sup y∈Ym, y n=1 | < ε, y > n | = Π n Ym ε n .
Hence,

sup um n=1 1 κ < u m , ε > n = c Π n Ym ε n .
Since Π n Ym is a projection, ρ(Π n t Ym Π n Ym ) = 1 and T r(Π n t Ym Π n Ym ) = d m , and by Lemma 6.2 there are constants d and c 2 such that

P sup m sup um =1 | < u m , ε > n | 2 -c 1 /2κ( σ 2 [d m + 1] n ) > x n ≤ m P ( sup um n=1 | < u m , ε > n | 2 -c 1 /2κ( σ 2 [d m + 1] n ) > x n ) ≤ m exp{-d(x + c 2 L[d m + 1])} ≤ C 2 e - √ dx/2 , setting C 2 = m e - √ c 2 L[dm+1]/2 .
Hence with probability greater than 1 -C 2 e - √ dx/2 we have

σ 2 [d m + 1] n (4.4) ≤ inf m inf xm∈x ⋆ +zm 2 r(1 + L) -c 1 ( Π n Ym (F (x m ) -F (x 0 )) 2 n + pen(m)) + x n .
On the other hand let, for any given m, xm stand for the "projection" of x 0 over

x ⋆ + X m , i.e. xm = x ⋆ + z m is such that (4.5) Π n Ym F (x m ) = Π n Ym F (x 0 ). Let K 2 = 1+c T 1-c T for c T defined in AF.
We have the following lemma, the proof of which is exactly as that of Lemma 2 in [START_REF] Kaltenbacher | Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems[END_REF].

Lemma 4.3. Assume K 2 and x ⋆ are such that

K 2 [I -Π Xm ](x 0 -x ⋆ ) + Π Xm (x 0 -x ⋆ ) ≤ ρ.
Then if IP, AF and IG there exists x ∈ x ⋆ + X m , such that (4.5) is satisfied. Now let d mopt be such that

d mopt = arg min dm (γ (m) ) 2 ( 1 + c T 1 -c T ) 2 (I -Π Xm )(x ⋆ -x 0 ) 2 + pen(m) .
Since we are looking at ordered selection,

g(m) = (γ (m) ) 2 ( 1 + c T 1 -c T ) 2 (I -Π Xm )(x ⋆ -x 0 ) 2
is a decreasing sequence, so that the minimizer must be such that g(m) ∼ pen(m).

Hence we have

P (d m + 1 - 4r(1 + L) r(1 + L) -c 1 (d mopt + 1)) + > u ≤ C 2 e - √ du/2 ,
and

d m ≤ 4r(1+L) r(1+L)-c 1 (d mopt + 1) -1 + u with probability greater than 1 -C 2 e - √ du/2 . • Error bounds: Set ∆ = ( Π n Ym (F (x m) -F (x 0 )) 2 n -inf m inf xm 2 1 -κ Π n Ym (F (x m ) -F (x 0 )) 2 n + pen(m)) + .
Lemma 6.2 also yields

P (∆ > x/n) ≤ C 2 e -dx/2 .
• We are now able to prove optimal rates for our estimator. For this we need to bound

Π n Ym (F (x m) -F (x 0 )) n from below. Under CB Π n Ym (F (x m) -F (x 0 )) ≤ Π n Ym (F (x m) -F (x 0 )) n l 1 .
Let Ω dim (u) be the set such that

d m ≤ 4r(1+L) r(1+L)-c 1 [d mopt + 1] + u -1.
Let Ω f it (u) be the set where ∆ < u. In this section we assume we are always in Ω dim (u) ∪ Ω f it (u).

We require the following lemma Lemma 4.4. Let x ∈ R(T * T ) + x ⋆ . There exists a constant C such that

Π n Ym (F (x) -F (x ⋆ + Π Xm (x -x ⋆ ))) ≤ C(1 + c T )γ (m) (I -Π Xm )(x -x ⋆ ) . Proof. Let x -x ⋆ = T * y, with y ∈ R(T ). By definition (I -Π Xm )x = T * (I -Π n Ym )y = T * w, with w ∈ Y ⊥ m . Π n Ym [F (x) -F (x ⋆ + Π Xm (x -x ⋆ ))] ≤ Π n Ym T R((x -x ⋆ ) -(Π Xm (x -x ⋆ ) -x ⋆ ))) = Π n Ym T R(I -Π Xm )(x -x ⋆ ) ≤ sup w∈Y ⊥ m , w =1 Π n Ym T RT * w (I -Π Xm )(x -x ⋆ ) .
The first term in the latter is in turn bounded by

Π n Ym T R sup w∈Y, w =1 T * (I -Π n Ym )w ≤ C(1 + c) sup x∈ker(T ) ⊥ , x =1 (I -Π n Ym )T x since T * is the adjoint operator of T
With this lemma we have, for

x m = x ⋆ + z m , z m ∈ X m Π n Ym (F (x m ) -F (x ⋆ + Π Xm (x 0 -x ⋆ ))) 2 ≥ Π n Ym T RΠ Xm (z m -(x 0 -x ⋆ )) 2 -[C(1 + c T )γ (m) ] 2 (I -Π Xm )(x 0 -x ⋆ ) 2 .
On the other hand, we have

Π n Ym T RΠ Xm (z m -(x 0 -x ⋆ )) 2 ≥ z m -(x 0 -x ⋆ ) 2 ( inf y∈Ym Π n Ym T RT * y T * y ) 2 ≥ z m -(x 0 -x ⋆ ) 2 ( inf y∈Ym < Π n Ym T RT * y, y > n T * y y n ) 2 ≥ z m -(x 0 -x ⋆ ) 2 ( inf y∈Ym < RT * y, T * y > n T * y y n ) 2 ≥ z m -(x 0 -x ⋆ ) 2 ( inf y∈Ym T * y 2 -< (I -R)T * y, T * y > T * y y n ) 2 ≥ z m -(x 0 -x ⋆ ) 2 (1 -c T ) 2 ( inf y∈Ym T * y y n ) 2 = z m -(x 0 -x ⋆ ) 2 (1 -c T ) 2 γ 2 m Thus, since (I -Π Xm )(x 0 -x m ) = (I -Π Xm )(x 0 -x ⋆ ) under assumption AS, (4.6) x m -x 0 2 ≤ l 2 Π n Ym (F (x m ) -F (x 0 )) 2 l 1 (1 -c T ) 2 γ 2 m + (1 + C 2 (1 + c T ) 2 U l 1 (1 -c T ) 2 ) (I -Π Xm )(x 0 -x ⋆ ) .
Inequality (4.6) is true for whatever x m ∈ x ⋆ + X m . Over Ω(u), we know

d m ≤ 4r(1 + L) r(1 + L) -c 1 [d mopt + 1] + u -1.
We distinguish then two cases according to whether m < m opt or not.

-In the first case it is clear that x m ∈ x ⋆ + X mopt and m in (4.6) can be replaced by m opt .

-In the second case we have:

(I -Π X m )(x 0 -x ⋆ ) ≤ (I -Π Xm opt )(x 0 -x ⋆ ) .
In any case we have, over Ω(u

) ∩ Ω f it (u) x m -x 0 2 ≤ (I -Π Xm opt )(x 0 -x ⋆ ) 2 (1 + C 2 (1 + c T ) 2 U l 1 (1 -c T ) 2 ) + 2(pen(m opt ) + u/n) (1 -κ)(1 -c T ) 2 γ 2 m ≤ (I -Π X m opt )(x 0 -x ⋆ ) 2 (1 + C 2 (1 + c T ) 2 l 1 (1 -κ)(1 -c T ) 2 ) + 2(pen(m opt ) + u/n) (1 -κ)(1 -c T ) 2 γ 2 mopt 1 d p mopt 4r(1 + L) r(1 + L) -c 1 [d mopt + 1] + u -1 p ≤ C(r) (I -Π X m opt )(x 0 -x ⋆ ) 2 + pen(m opt ) γ 2 mopt + K(r) u p+1 n ,
for some appropriate constants C(r, σ) and K(r, σ). Thus,

P (( x m -x 0 2 -C(r, σ){ (I -Π X m opt )(x 0 -x ⋆ ) 2 + pen(m opt ) γ 2 mopt }) + > K(r, σ)u p+1 n ) ≤ 2e - √ d/2u
, which ends the proof.

Non ordered selection.

Ordered selection has the advantage of working directly on the observation space. It has the disadvantage that the expansion of the solution x 0 over the resulting subspace X m might not be efficient. This introduces the need for non ordered selection, or equivalently, for threshold methods. The combination of both ill-posedness and non linearity makes this a difficult problem. Indeed, the former yields that it is no longer possible to work on the observation space as this would require simultaneous control of γ m and d m . Working on the solution space requires considering the inverse of a certain matrix. The goodness of fit of the estimator is then defined by the trace and spectral radius of this inverse matrix restricted to the sequence of subspaces, which in turn depends on the degree of non linearity of the problem.

More precisely as in Section 3, let m 0 be such that

(I -Π Xm 0 )(x 0 -x ⋆ ) ≤ inf m [ (I -Π Xm )(x 0 -x ⋆ ) + d m n 1 γ m ].
For this fixed m 0 , let M n be a set of indices such that {Y m } m∈Mn ⊂ Y m 0 be a collection of not necessarily nested subspaces. We will use the notation m ⊂ m 0 to express the embedding of such subsets. Our goal is to find the best subspace along this collection using penalized estimation.

Set A m 0 = T + m 0 Π n Ym 0 . For fixed x, D m (x) := Π Xm 0 R(x)Π Xm is a linear operator, D m (x) : X m → X m 0 . Let S m be the matrix whose entries are defined by

S m (i, j) = sup x∈Bρ(x ⋆ ) |A t m 0 D m (x)(i, j)|. Set ρ m = ρ(S t m S m ) and t m = T r(S t m S m ). Let R m = t m /ρ m .
From the definition of A m 0 under SF and AF both nρ m and nt m do not depend on n. Introduce L m a certain weight factor and in the notation of Lemma 6.2, assume (4.7)

Σ 1 := m⊂m 0 e - √ d/2rLm(Rm+1) < ∞ and for q ≥ 1 Σ 2 (q) (4.8) := m⊂m 0 (nρ m σ 2 /d) q [(d/2rL m (R m + 1)) q-1/2 + (d/2rL m (R m + 1)) q-1 ]e - √ d/2rLm(Rm+1) < ∞.
As before we will consider penalized estimation. The penalty term in this case will be set to

pen(m) = rσ 2 (1 + L m )[t m + ρ m ],
with r > 2. The projection estimator is defined for a fixed m as

x = x ⋆ + arg min x∈Xm A m 0 (y -F (x)) 2 .
The optimal model is chosen as (4.9) m = arg min

m⊂m 0 A m 0 (y -F (x m )) 2 + pen(m).
Then, the following theorem proves optimality of the corresponding model selection estimator x m.

Theorem 4.5. Assume AN, IG, AF and SF are satisfied. Assume (4.7) and (4.8) hold true. Then, if 0 < κ < 1, with probability greater than 1 -

Σ 1 e - √ d/(2nρm 0 )u x m -x 0 2 ≤ (I -Π Xm 0 )(x 0 -x ⋆ ) 2 + 2 (1 -c T -κ) inf m⊂m 0 {arg min xm∈Xm (1 + c T ) x m -x 0 2 + pen(m)} + σ 2 u/n
and for q ≥ 1 there exists a constant C q depending on q such that

IE[ x m -x 0 2 ] q ≤ [ (I -Π Xm 0 )(x 0 -x ⋆ ) 2 + 2 1 -c T -κ inf m⊂m 0 {arg min xm∈Xm (1 + c T ) x 0 -x m 2 + pen(m)}] q + C q Σ 2 (q) n q
The estimator x m looks complicated, but in the linear case, it has a nice expression. Indeed, in this case T = F and x ⋆ = 0, so the minimization problem in (4.9) is similar to a hard thresholding scheme, since it is equivalent to minimizing

x m = arg min m⊂m 0 arg min xm∈Xm {-2 < A m 0 y, A m 0 T x m > + A m 0 T x m 2 } + pen(m) = arg min m⊂m 0 arg min xm∈Xm {-2 < Π Xm A m 0 y, x m > + x m 2 } + pen(m).
Let {e j } j∈m be the canonical base over X m . Define for each m,

x m,j =< A m 0 y, e j >=< y, A t m 0 e j >, j = 1, . . . , m.

Thus, m is selected by minimizing

- j∈m x 2 m,j + rσ 2 (1 + L m )[ j∈m λ m,j + sup j∈m λ m,j ].
In the non linear case the problem is equivalent to minimizing arg min

m⊂m 0 arg min xm∈Xm {-2 < A m 0 (y -F (x ⋆ )), Π Xm 0 R(x m , x ⋆ )(x m -x ⋆ ) > + x m -x ⋆ 2 }+pen(m). Set F(x ⋆ ) = (F (x ⋆ )(t i )) n i=1 . Hence, (x m -x ⋆ ) j =< A m 0 (y -F (x ⋆ )), Π Xm 0 R(x m , x ⋆ )e j > =< y -F(x ⋆ ), A t m 0 Π Xm 0 R(x m , x ⋆ )e j >, j = 1, . . . , m.
Then m is chosen as above. We point out that, in this case, the problem must be solved numerically which is troublesome as A m 0 is a badly conditioned matrix. However practical implementation of the estimator is a difficult task which lies beyond the scope of this paper and will be tackled in a future work.

Remark 4.6. For each fixed m, the quantity

∆ ′ m := x m -x 0 2 + pen(m)
is of the same order as the MISE for this problem, and the same comment as that at the end of Theorem 4.1 applies.

Proof. From the definition for any m and x m ,

A m 0 (F (x 0 ) -F (x m)) 2 ≤ A m 0 (F (x 0 ) -F (x m )) 2 + pen(m) +2 < ε, A t m 0 A m 0 (F (x 0 ) -F (x m)) > n +2 < ε, A t m 0 A m 0 (F (x 0 ) -F (x m )) > n -pen( m).
We have

A m 0 (F (x 1 ) -F (x 2 )) = Π m 0 R(x 1 , x 2 )(x 1 -x 2 ).
Hence, the left hand side is bounded from below by (1

-c T ) Π Xm 0 (x m -x 0 ) 2 and A m 0 (F (x 0 ) -F (x m )) 2 ≤ (1 + c T ) Π Xm 0 (x m -x 0 ) 2 .
Thus,

(1 -c T ) Π Xm 0 (x m -x 0 ) 2 ≤ (1 + c T ) Π Xm 0 (x m -x 0 ) 2 + pen(m) +2 < ε, A t m 0 R(x m, x m )(x m -x m ) > n -pen( m). For any m, m ′ set Π m\m ′ = Π Xm\X m ′ and Π m∩m ′ = Π Xm∩X m ′ . With this notation x m ′ -x m 2 = Π m∩m ′ (x m ′ -x m ) 2 + Π m\m ′ (x m ′ -x m ) 2 + Π m ′ \m (x m ′ -x m ) 2 ,
and

| < ε, A t m 0 R(x m, x m )(x m -x m ) > | = | < ε, A t m 0 R(x m, x m )Π m∩ m(x m -x m ) > n + < ε, A t m 0 R(x m, x m )Π m\ m(x m -x m ) > n + < ε, A t m 0 R(x m, x m )Π m\m (x m -x m ) > n | ≤ κ x m -x m 2 + 2/κ εS m 2 + 1/κ εS m 2 .
The first term in the latter is bounded by

κ[ x m -(Π Xm 0 x 0 + x ⋆ ) 2 + x m -(Π Xm 0 x 0 + x ⋆ ) 2 ].
The proof then follows directly from Lemma 6.2.

Concluding Remarks

Penalized estimation enables to construct estimators which are optimal in the sense that without prior knowledge of the regularity of x 0 they achieve the best estimation error for all the possible choice of tuning sequences. Rates of convergence depend on the choice of the projection spaces and their approximation properties. Under SC we have if ν ≤ 1/2,

(I -Π Xm )x 0 ≤ (I -Π n Ym )T 2ν = O(d -2νp m ).
This leads to the rate

(5.1) x m -x 0 = O P (n -2νp 4νp+2p+1 ).
Interpreting this rate in the statistical literature reads s = 2νp: the regularity depends on the ill-posedness of the problem. Similar rates can be encountered in the statistical literature under similar kind of assumptions, see for instance Bissantz et al. [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF]. Hence, the rates of convergence under source conditions SC are the same as in the case of linear inverse problems.

So, what is the price to pay here for non linearity ? Since we consider the operator T , a linear expansion of the operator F in a neighborhood of x 0 , the introduction of non linearity requires controlling the linear part of the Fréchet differential operator F ′ in balls around the true solution x 0 . As opposed to linear problems, this fact entails the need of finding a "good" initial guess which is denoted by x ⋆ . Moreover, the ill-posedness of the problem requires relating the non linearity to the smoothing properties of F ′ (x ⋆ ), see condition AF. We remark that this kind of condition is at the heart of probabilistic control of noise amplification.

So, the whole procedure, heavily relies on the assumption that there exists this good starting point, namely x ⋆ . Asking for a good initial point is a common requirement in the literature for ill-posed inverse problems in a deterministic setting, see for instance [START_REF] Kaltenbacher | Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems[END_REF]. From a practical point of view, this means that some prior knowledge about the solution is required. Another method to find this initial starting approximation point is to use, either a preliminary estimate, or to iterate the estimation process, starting from a randomly chosen point.

As a corollary, we have the following lemma Lemma 6.2.

• There exists a positive constant d that depends on r such that the following inequality holds P (η 2 (A) ≥ σ 2 [T r(A t A) + ρ(A t A)]r/2(1 + L) + σ 2 u) (6.1) ≤ exp{-d(1/ρ(A t A)u + r/2L[T r(A t A)/ρ(A t A) + 1])}

• Set k 1 = d/(ρ(A t A)σ 2 ) and k 2 = dr/2L[T r(A t A)/ρ(A t A) + 1]. Then, there exists a constant C q , which depends only on q, such that, IE[η 2 (A) -σ 2 [T r(A t A) + ρ(A t A)]r/2(1 + L)] q + (6.2)

≤ C q k -q 1 [k q-1/2 2 + k q-1 2 ]e - √ k 2 holds.
Proof. As a first step we will bound v. Since IEZ ≤ IE 1/2 Z 2 , we have

v ≤ IE n i=1 z i ( ε i σ ) 2 + 2 IE n i=1 z i ( ε i σ ) 2 ≤ (1 + ν)IE n i=1 z i ( ε i σ ) 2 + T r(A t A)/ρ(A t A).
Moreover, following, [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] p. 480, for all q ≥ 2, the following version of Rosenthal's inequality holds:

IE q/2 n i=1 z i ( ε i σ ) 2 ≤ 2 q/2 T r(A t A)/ρ(A t A)IE |ε 1 | q σ q .

Hence, we have v ≤ (1 + ν)T r(A t A)/ρ(A t A) + 1 ν and

v 2 ≤ 2[2 2 (1 + ν) 2 T r(A t A)/ρ(A t A)IE |ε 4 | σ 4 + ( 1 ν ) 2 ].
Set 0 < α < 1. Choose δ and β such that if +r/2L(T r(A t A) + ρ(A t A)) + u)

Set

x ′ = (1 + 1 β ) -1 r 2L ( T r(A t A) ρ(A t A) + 1) + u ρ(A t A)
.

The last term is equal to

P ( η 2 (A) ρ(A t A) ≥ ( T r(A t A) ρ(A t A) (1 + α) + (1 + 1/α)v 2 δ 2 )(1 + β) + r/2L T r(A t A) ρ(A t A) + 1) + u) = P ( η 2 (A) ρ(A t A) ≥ ( T r(A t A) ρ(A t A) (1 + α) + (1 + 1/α)v 2 δ 2 )(1 + β) + (1 + 1/β)x ′ )
Finally, we may bound ,

≤
where we have used repeatedly that for any constant c > 0, ca 2 + 1/cb 2 ≥ 2ab and set g(A) = ((1 + 1/β) -1 (1 + 2/δ) 2 )(r/2L[T r(A t A)/ρ(A t A) + 1] + u/ρ(A t A)).

Set also d = [(1 + 1/β) -1 (1 + 2/δ) 2 ] -1 and b(A) = T r(A t A)/ρ(A t A). Thus we have shown the first part of the lemma.

Moreover, using the above inequality,

Theorem 3 . 1 .

 31 which defines the estimator xα k = x ⋆ + R α k y. The following result provides a control over the estimation error of the estimator xα k . Assume AN, SF, SV, IG and AF are satisfied. For any x ∈ x ⋆ + X m and any k such that d m 0 ≥ α -1/(2p) k

2 2 4

 4 !δ 2 (1 + 1/α)(1 -ν) 2 < c 1 , 2δ 2 (1 + 1/α)( 1 ν ) 2 < c 2 and c = max((1 + β) max(c 1 , c 2 ), (1 + β)(1 + α)), then r/2 > c.Let u > 0 and without loosing generality, assume σ = 1. Thus,P (η 2 (A) ≥ (T r(A t A) + ρ(A t A))r/2(1 + L) + u) ≤ P (η 2 (A) ≥ (T r(A t A)(1 + α) + (1 + 1/α)δ 2 ν 2 ρ(A t A))(1 + β) +[r/2 -c](T r(A t A) + δ 2 v 2 ρ(A t A)) + r/2L(T r(A t A) + ρ(A t A)) + u) ≤ P (η 2 (A) ≥ (T r(A t A)(1 + α) + (1 + 1/α)δ 2 ν 2 ρ(A t A))(1 + β)

Appendix

In this section we give some technical lemmas.

The following result is a deviation inequality based on a functional exponential inequality (Theorem 7.4) due to [START_REF] Bousquet | Concentration inequalities for sub-additive functions using the entropy method[END_REF]

Then,

Proof. Since the application u → A t u is continuous, we have η(A) = sup u∈S n i=1 ε i (A t u) i for S some countable subset of the unit ball. On the other hand,

. Let IE j stand for the conditional expectation given ε i for i = j. Hence, in the proof of Theorem 7.4 in [START_REF] Bousquet | Concentration inequalities for sub-additive functions using the entropy method[END_REF] we may bound

Thus, IE|Z -IE j Z| q ≤ z j q!/2. Finally, note that

Thus, the proof follows from Theorem 7.4 in [START_REF] Bousquet | Concentration inequalities for sub-additive functions using the entropy method[END_REF].

Consider the change of variable w = du/(ρ(

The last expression is in turn bounded by

ending the proof.

We are very gratefull to the anonymous referees for their helpful comments. The second author would thank ECOS Nord and Agenda Petróleo de Venezuela for supporting her work.