Cosme Louart
email: cosme.louart@ens.fr

Romain Couillet
email: romain.couillet@gipsa-lab.grenoble-inp.frurl

Concentration of Measure and Large Random Matrices with an application to Sample Covariance Matrices *

Keywords: Concentration of the Measure, Talagrand Theorem, Davis Theorem, Stieltjes transform, Deterministic equivalent, Spectral distribution, Central limit Theorem

The present work provides an original framework for random matrix analysis based on revisiting the concentration of measure theory for random vectors. By providing various notions of vector concentration (qexponential, linear, Lipschitz, convex), a set of elementary tools is laid out that allows for the immediate extension of classical results from random matrix theory involving random concentrated vectors in place of vectors with independent entries. These findings are exemplified here in the context of sample covariance matrices but find a large range of applications in statistical learning and beyond, starting with the capacity to easily analyze the performance of artificial neural networks and random feature maps.

Integer part of x ∈ R, x ∈ N and verifies x ≤ x ≤ x + 1 = x . E Typical normed vector space over R, endowed with the norm • .

C

Set of complex numbers. E * Dual space of E (the set of linear maps from E to R).

A

Typical non commutative algebra endowed with the algebra norm • , the possibly non commutative product is written without operation character, we have ∀x, y ∈ A, xy ≤ x y . ∂A Boundary of A ⊂ E, if Ā is the closure of A and Å, the interior of A, ∂A = Ā \ Å.

Conv(A) Convex hull of A ⊂ E (i.e., Conv(A) = ∩{C ⊂ E, C convex, C ⊃ A}). A * A \ {0} 1 A Indicator function of A ⊂ E, 1 A : E → {0, 1} and 1 A (x) = 1 ⇔ x ∈ A.
If A is not a set but an assertion (like A = A(t) = (t ≥ 1)), 1 A = 1 if A is true and 1 A = 0 if A is false. If 1 presents no index, it designates a vector full of one with a convenient size for the context. Transpose operator on M p , ∀M ∈ M p,n , [M T ] i,j = M j,i , 1 ≤ i ≤ p, 1 ≤ j ≤ n. I p

Identity matrix of M p , ([I p ] i , j = 0 if i = j and [I p ] i,i = 1, 1 ≤ i, j ≤ j). Sp(M ) Spectrum of the matrix M .

Q C Resolvent of the matrix C ∈ M p . For z ∈ C \ Sp(C), Q C (z) = (C + zI p ) -1 . Diag Diagonal operator. If M ∈ M p,n , Diag(M ) = (M i,i ) 1≤i≤min(p,n) ; if x ∈ R p , Diag q,n (x) ∈ M p,n , [Diag p,n (x)] i,i = x i if 1 ≤ i ≤ min(p, q, n) and [Diag p,n (x)] i,j = 0 if i = j, for 1 ≤ i ≤ p, 1 ≤ j ≤ n.

S p

Set of symmetric matrices of M p : S ∈ S n ⇔ S i,j = S i,j , 1 ≤ i ≤ p ; S ∈ S + p ⇔ ∀u ∈ R p , u T Su ≥ 0 ; S ∈ S - p ⇔ -S ∈ S + p . Given S 1 , S 2 ∈ S p , we say that S 1 is greater than S 2 and we note S 1 ≥ S 2 if S 1 -S 2 ∈ S + p . S 1/2 Square root of the nonnegative symmetric matrix S ∈ S + p (with the diagonalization S = P T ΛP , P ∈ O p , Λ ∈ D p , we define S 1/2 = P T Λ 1/2 P where [Λ 1/2 ] i,i = Λ 1/2 i,i ).

P p

Set of permutation matrices of M p : P ∈ P p ⇔ P ∈ O n and (∃σ ∈ S p , P i,j = 1 ⇔ σ(i) = j) ; we also define P p,n = {(U, V ) ∈ P p × P n | U I p,n V T = I p,n } where I p,n = Diag p,n (1).

• q q -norm on R p for two integers p, q ∈ N * ; x q = ( p i=1 x q i ) 1/q .

• Classical norm of the vector space E one is working on : if E = R p , the euclidean norm • 2 ; if E = M p,n , the spectral norm (∀M ∈ M p,n : sup u =1 M u ). • 1 on R p , the 1 ; on M p,n , the nuclear norm (∀M ∈ M p,n , M 1 = Tr((M M T ) 1/2 )).

• F Frobenius norm, ∀M ∈ M p,n : {y ∈ E xy ≤ t}, the index • could be of course a distance d or simply unspecified when we implicitly consider the classical norm of E.

M F = √ Tr M M T = p i=1 n j=1 M 2 i,j . • * Dual norm on E * . If f ∈ E * , f * = sup x ≤1 f (x).
A t If A ⊂ E, A t is the closed set {x ∈ E | d(x, A) ≤ t} ⊃ A. S t f Level set of f : E → R. For t ∈ R, S t f = {x ∈ E | f (x) ≤ t}. S p
Sphere of R p+1 (S p = {x ∈ R p+1 | x ≤ 1}). η (E, • ) Norm degree, see Definition 9.

P

We implicitly suppose all over the paper that there exists a probability space (Ω, F, P) where F is a sigma-algebra of the set Ω and P, a probability measure defined on the elements of F. The random vectors we consider are then P-measurable applications defined on Ω and taking value in normed vector spaces endowed with the Borel σ-algebra.

In that setting, given a random vector X ∈ E (i.e. X : Ω → E), for any Borel set A ⊂ E, we note P(X ∈ A) = P({ω ∈ Ω, X(w) ∈ A}) and for any measurable function f : E → R and t ∈ R, we note P(f (X) ≥ t) = P({ω ∈ Ω, f (X(ω)) ≥ t})...

E

The expectation operator. For any random vector X ∈ E and any measurable function f : E → R, we define E[f (X)] = Ω f • XdP. When E has finite dimension, it is possible to define EX by integrating all the coordinates of X. σ(X) If X ∈ M p,n , σ(X) ∈ R min(p,n) + is the vector constituted of the singular values of X in increasing order (i.e. the eigenvalues of (XX T ) 1/2 ). If X ∈ E is a random vector, σ(X) is the σ-algebra generated by X (i.e., the σ-algebra of sets of Ω containing all the sets X -1 (B) when B is a Borel set of E). a.s.

Almost surely, an event (i.e., an element of F) A is true almost surely iff P(A) = 1. We will often abusively mix up random vectors and classes of almost surely equal random vectors. i.i.d. "independent and identically distributed".

Introduction

Sample covariance matrices are key quantities in applied statistics in that they allow for the estimation of structural information in the second order statistics of the sampled vectors, and find a wide range of applications in fields as diverse as applied statistics (e.g., financial statistics, biostatistics), signal or data processing, wireless communications, etc. Precisely, for a set of n independent random vectors x 1 , . . . x n ∈ R p stacked in a matrix

X = [x 1 , • • • x n ] ∈ M p,n , the sample covariance matrix S = 1 n n i=1 x i x T i = 1 n XX T ∈ M p provides an estimator for Σ = 1 n E[XX T ].
If the number of independently sampled vectors n is large compared to the dimension p of the vectors, then under usually mild assumptions S converges to Σ. When p and n have the same order of magnitude though, again under classical assumptions, the operator norm difference S -Σ usually does not vanish and S is thus not a consistent estimator for Σ. In their now famous article [START_REF] Marcenko | Distribution of eigenvalues for some sets of random matrices[END_REF], Marcenko and Pastur proved that, if the vectors x i , in addition to being independent, have independent entries of zero mean and unit variance, then, as n, p → ∞ with p/n → c ∈ (0, ∞), the normalized counting measure of the eigenvalues of S converges a.s. to a limiting distribution having a continuous density, and now referred to as the Marcenko-Pastur distribution. From this article on, many works have provided generalizations of [START_REF] Marcenko | Distribution of eigenvalues for some sets of random matrices[END_REF]. This is the case for instance of [START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large dimensional random matrices[END_REF], where the authors assume that the x i can be written under the form x i = Σ 1 2 z i for z i a vector with independent zero mean and unit variance entries. It is to be noted that the independence [START_REF] Marcenko | Distribution of eigenvalues for some sets of random matrices[END_REF], linear dependence [START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large dimensional random matrices[END_REF], or vanishing dependence [START_REF] Adamczak | On the marchenko-pastur and circular laws for some classes of random matrices with dependent entries[END_REF] between the entries of X is key in the approach pursued in these articles as it provides a necessary additional degree of freedom in the derivation of the proofs.

These earlier results thus found many practical applications in scientific fields involving large dimensional matrix models with mostly linearly dependent entries, most notably in applied statistics, electrical engineering and computer science. But the renewed interest for machine learning applications, spurred by the big data era, has recently brought forward the need to understand and improve algorithms and methods relying on random matrix models involving non-linear relations between their entries. In some scenarios, as with kernel matrices (that is, matrices K ∈ R n×n with entries of the type K ij = f (x T i x j ) for some nonlinear function f ), an asymptotic equivalence between these matrices and classical matrices with linearly dependent entries can be proved [El 10, CB16, KC17], thereby transferring the asymptotic analysis of the former to that of the latter. In imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 other scenarios though, such asymptotic equivalences are not available. This is in particular the case of so-called random feature maps and neural networks. In random feature maps, the vectors x i can be expressed under the form x i = σ(W z i ) for some non-linear (referred to as the activation) function σ : R → R, here applied entry-wise, W a given matrix, and z i yet another random vector. The randomness in random feature maps arises from the fact that W is usually chosen at random, often with independent and identically distributed entries (this way allowing to produce p independent non-linear "features" of the vector z i ). Prior to training, neural networks (in particular feedforward neural nets) may usually be seen as a cascade of such random feature maps. In evaluating the performance of algorithms and methods based on random feature maps and neural networks, it is often of importance to understand the statistical behavior of S.

Still in the scope of the statistical analysis of data processing algorithms, where sample covariance matrices built upon real data vectors x i are considered, it is also quite restrictive, if not disputable, to assume that x i can be written as x i = µ + Σ 1 2 w i for some deterministic µ and with w i having independent entries.

As we shall see in the course of the article, a very convenient assumption to be made on x i in order (i) to answer the aforementioned controversial real dataset modeling, (ii) to properly model random feature map and neural network and (iii) to largely generalize the Marcenko-Pastur and related results, is to propose that x i satisfies a vector-concentration inequality. In a nutshell, concentration inequalities being stable under (bounded) linear operations and non-linear Lipschitz operations, the framework proposed in this study allows for a natural study of models of S with independent x i of the form σ(W z i ) with z i itself a concentrated random vector (so for instance itself of the type σ 2 (W 2 y i ) with y i concentrated, and so on).

The objective of the article is precisely to provide a consistent method for the analysis of S with x i independent concentrated random vectors based on elementary concentration inequality principles, particularly suited to practical applications in large dimensional machine learning. The article notably extends the results of El-Karoui in [El 09], who first exploited concentration of measure arguments in place of independence in the classical proof approaches of [START_REF] Marcenko | Distribution of eigenvalues for some sets of random matrices[END_REF][START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large dimensional random matrices[END_REF]. The technical arguments and findings of [El 09] are nonetheless quite specific and treated lemma after lemma, some of the main results being valid only for a restricted class of concentrated random vectors (such as elliptically distributed random vectors). We rather aim here at a self-contained generic framework for the manipulation of a large class of random matrix models using quite generic concentration identities. For instance, in the present article, we provide a very simple expression of the concentration of quantities of the type x T Ax when x is normally concentrated and A a deterministic matrix, with a very synthetic proof (see Lemma 1.1.9 and Theorem 1.2.52). The present work also follows after a previous article by the same authors [START_REF] Louart | Harnessing neural networks: a random matrix approach[END_REF], in which a par-ticular model of concentrated random vectors x i = σ(W z i ) was studied in the aim of analysing the performances of a one hidden-layered non-linear random neural network, commonly referred to as an extreme learning machine [START_REF] Huang | Extreme learning machine: theory and applications[END_REF]. Concentration was there induced by the randomness of W and the Lipschitz character of σ. Yet, not imposing that the input data z i are themselves concentrated random vectors led to restrictions in the results of [START_REF] Louart | Harnessing neural networks: a random matrix approach[END_REF], to which the present article easily circumvents. In a subsequent companion article, applications of the present results to the asymptotic classification and regression performance of extreme learning machines will be devised.

The present article is also quite general in that it allows to handle sample covariance matrices for data x i arising from either of the two standard classes of concentrated random vectors, that is (i) uniformly continuous (so in particular Lipschitz) transformations of standard Gaussian random vectors, and (ii) affine transformations of random vectors with independent and bounded entries; the latter setting follows from the works of Talagrand [START_REF] Talagrand | Concentration of Measure and Isoperimetric Inequalities in product spaces[END_REF] and requires a more subtle approach since vector concentration of this kind is only stable through Lipschitz and convex functionals.

The remainder of the article is structured as follows. We introduce in the first section a somewhat original (but convenient to our analysis) approach to the notion of concentration of measure, probabilistically oriented and based on a collection of efficient lemmas concerning random variables and subsequently exported to the case of random vectors and matrices (one original specificity of our approach is to study the stability of the concentration through basic operations like sums and products in algebras). The aim of this section is not only to prepare the ground for the study of the sample covariance but also to offer a generic toolbox beyond our present scope; for this reason we maintain as general hypotheses as possible in this section. In the second section we then devise socalled deterministic equivalents for the sample covariance matrix model under study and we eventually illustrate the robustness of our results to both artificial and real datasets.

Preamble

Remark 0.0.1 (Definition of S). As a first remark, note that we abusively define the sample covariance matrix S as S = 1 n XX T rather than the conventional 1 n XX T -1 n EXEX T . This choice is not completely marginal in that not subtracting the matrix EXEX T from S in general brings additional complications (because this matrix will in general have unbounded norm as p, n → ∞); our concentration of measure approach however efficiently deals with this term. From a practical standpoint, the removal of EXEX T means that this matrix can be computed, which is in general not the case. Alternatively, centering S by the empirical average 1 n X1 n 1 T n X T presumes that the x i are identically distributed which, as is common in classification applications in machine learning, is also not a desirable assumption.

In the course of the article, we will be particularly interested in the eigenvalues l 1 , . . . , l p of S. More precisely, we will consider the spectral distribution F of S defined as the following normalized counting measure of the eigenvalues of S (a random probability measure):

F = 1 p p i=1 δ li ,
where δ x is the Dirac measure centered at x. As is conventional in large dimensional random matrix theory, we shall retrieve information of F through an approximation of its Stieltjes transform m F , defined as:

m F (z) = w 1 w -z dF (w) = 1 p Tr (S -zI p ) -1
where z ∈ C belongs to the complementary of the support of F . Since the matrix S is nonnegative definite, it suffices to study m F (z) for z ∈ R -to recover m F by analytic extension. For convenience, rather than working on R -we shall consider m F (-z) for z in R + .

The random matrix Q S (z) = (S + zI p ) -1 , referred to as the resolvent of S, will thus be an object of fundamental importance in the remainder. It shall be denoted Q when non-ambiguous. The convenience of the resolvent Q as a cornerstone of random matrix theory analysis is due in part to its simple boundedness properties: Lemma 0.0.2. Given a matrix R ∈ M p,n , a nonnegative definite symmetric matrix C ∈ M p and z ∈ R + , we have the following bounds:

Q C (z) ≤ 1 z Q C (z)C ≤ 1 Q 1 n RR T (z)R ≤ √ n √ z .
Proof. The upper bound for Q C (z) follows from the smallest eigenvalue of C + zI p being larger than z. The second result is a consequence of the simple identity Q C (z)C + zQ C (z) = I p and the fact that Q C (z) is symmetric positive definite. Combining the first two results, we have the bound

Q 1 n RR T (z) 1 n RR T Q 1 n RR T (z) ≤ 1 z ,
providing the last result.

Beyond the eigenvalues of S, our interest (also driven by numerous applications in electrical engineering and data processing) will also be on the eigenvectors of S. For U = [u 1 , . . . , u l ] an eigen-basis for the eigenspace associated to the multiplicity-l eigenvalue λ of S, remark that U U T = 1 2πı Γ λ Q(-z)dz for Γ λ a negatively oriented complex contour surrounding λ only. As such, beyond studying the trace of Q (and thus the Stieltjes transform of S), our interest is also on characterizing Q itself. Precisely, we shall study so-called deterministic equivalents for Q, the precise definition of which is given in Definition 8 and that can be described as deterministic matrices Q verifying Tr A(Q -Q) → 0 when A has unit norm (depending on the tightness of the concentration around Q, the norm of A considered will either be the Frobenius norm

A F = √ Tr AA T , either the nuclear norm A 1 = Tr(AA T ) 1 2 ). Note that if we control Tr A(Q -Q), we also control u T (Q -Q)v = Tr vu T (Q -Q) for two deterministic vectors u, v ∈ R p with unit norm (in that case vu T F = vu T 1 = u v ).
In the following lines, we provide an outline for our subsequent development. First, let us note that a naive approach would be to think that (Σ + zI p )

-1 might be a deterministic equivalent for Q. This turns out to be incorrect under general assumptions. Instead, letting Q = (Σ + zI p )

-1 where Σ is some deterministic matrix to determine, we may first compute the difference:

Q -EQ = E Q 1 n XX T -Σ Q = n i=1 1 n E Q(x i x T i -Σ ) Q .
Here, to go further, we need to make explicit the dependence between x i and the matrix Q in order to evaluate the expectation of the product Qx i . Let us denote X -i ∈ M p,n-1 the matrix X deprived of its i-th column, which leads us to defining the matrices

S -i = 1 n X -i X T -i and Q -i = (S X-i + zI p ) -1 (which is not Q S X -i as n is not turned in n -1).
To handle the dependence between x i and Q, we will massively exploit in the paper the classical Schur identities:

Q = Q -i - 1 n Q -i x i x T i Q -i 1 + 1 n x T i Q -i x i and Qx i = Q -i x i 1 + 1 n x T i Q -i x i . (1)
The second inequality allows us to disentangle the relation between Q and x i in the product Qx i with a similar but easier to apprehend product Q -i x i and a factor 1/ 1 + 1 n x T i Q -i x i easily controllable thanks to a first call to concentration inequalities (see subsequently Property 1.2.52). This leads us to:

Q -EQ = n i=1 1 n E Q -i x i x T i 1 + 1 n x T i Q -i x i -Σ Q - 1 n 2 n i=1 E Q -i x i x T i QΣ Q .
We will see that, due to the supplementary factor 1/n, the norm of the rightmost random matrix will be negligible compared to that of the other right-hand side matrix. Thus, if one assumes, say, that the random vectors (x i ) 1≤i≤n follow the same law (not our general assumption in the article), one would choose naturally

Σ = E[x i x T i ]/(1 + δ) where δ = 1 n E[x T i Q -i x i ] = 1 n Tr E[Q -i ]E[x i x T i ]. Then, having established that 1 n E Tr AQ (and thus 1 n E Tr AQ -i ) is close to 1 n Tr A Q, in particular here for A = E[x i x T i ],
one may establish an implicit equation for δ not involving expectations over Q (or Q -i ). The remaining issue, at the core of our present analysis, is now to find a convenient setting in the modeling of the x i for which such a choice of Σ would guarantee that 1 p Tr(EQ -Q) indeed vanishes. That will be related to the concentration of "chaos-like" quantities (see [Ver17, Section 6.1]) such as x T i Q -i x i but also of quantities such as Tr AQ or u T Qv as we shall see.

In the first part of the article, we will show that a comfortable approach is to structure our results as an outgrowth of the concentration of measure phenomenon. To give a brief insight into our approach, let us give the original theorem of the theory that we owe to Paul Pierre Levy in the beginning of the twentieth century and concerns the concentration of the uniform distribution σ p on the sphere S p . To demystify the result we mention that it is closely linked to the isoperimetrical inequality.

Theorem 0.0.3 (Normal concentration of σ p , [Led01, Theorem 2.3]). Given a degree p ∈ N and a random vector Z ∼ σ p , for any 1-Lipschitz function f : R p+1 → R, we have the inequality :

P (|f (Z) -m f | ≥ t) ≤ 2e -(p-1)t 2 /2
(2)

where m f is a median of f (Z) verifying by definition P(f (Z) ≥ m f ), P(f (Z) ≤ m f ) ≥ 1 2 .
There exist plenty of other distributions that verify this inequality like the uniform distribution on the ball, on [0, 1] n , or the Gaussian distribution N (0, I p ) that are presented in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF] ; more generally, for Riemannian manifolds, the concentration can be interpreted as a positive lower bound on the Ricci curvature (see Gromov appendix in [START_REF] Vitali | Asymptotic Theory of Finite Dimensional Normed Spaces[END_REF] or [Led01, Theorem 2.4]). Our study will not evoke the design of such distributions and the validity of their concentration since this work has already been treated in the past; we will rather directly assume a similar concentration inequality to (2) for the data matrix X and then, with the tools developed in Section 1, we will infer the concentration of the Stieltjes transform m F (z) for any z > 0 and devise a good estimator of it. To prepare the applications to come, the dimension p must be thought to be quasi-asymptotic. In that sense the tightening of the concentration when the metric diameter of the distribution stays constant is a remarkable specificity of the concentration phenomenon ; this is furthermore a necessary condition, required for our study in Section 2. The concentration inequality verified on the sphere will structure our paper in a way that we will try to express our result with that form as often as possible to pursue Levy's idea; we will thus choose the short notation f (Z) ∈ m f ± 2e -(p-1) • 2 /2 to express it in a simple way.

The Concentration of Measure Framework

As Milman has advocated from the beginning of the seventies ([MS86]), the concentration of a random object appears to be an essential feature leading immediately to a lot of implications and controls on the object. We do not present here the historical introduction of concentration of the measure. Rather than the geometric, distribution-oriented approach, we directly adopt a probabilistic point of view on the notion. That does not mean that the presentation of the theory will be incomplete. On the contrary, we display here, almost always with their proofs, all the important theorems and propositions necessary to apprehend the theory and set rigorously the study of Section 2 about the sample covariance. The usual approach to the concentration of measure is to start with geometric inequalities ruling high dimensional Banach spaces and then track from these powerful results some probabilistic properties on the real functionals, the "observable world". We propose here a reversed approach where we start from the probabilistic results on R which offer us some interesting reasoning schemes all the same. Then, once the reader convinced by the direct computation improvements offered by the theory, we perform the fundamental step consisting in considering high dimensional concentration properties. Many of the results are derived from the complete presentation of the theory made by Ledoux in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF].

Concentration of a random variable

Definition and first Properties

Definition 1 (Concentration function). Any non-increasing and left continuous function α : R + → [0, 1], is called a concentration function.

Given a random variable Z and a concentration function α, we choose first to express the α-concentration of Z through the introduction of an independent copy Z .

Definition 2 (Concentration of a random variable). The random variable Z is said to be α-concentrated, and we write Z ∝ α, iff for any independent copy Z :

∀t > 0 : P (|Z -Z | ≥ t) ≤ α(t). (3)
In Definition 1, the different properties required for the concentration function (α ∈ [0, 1], non-increasing, left-continuous) are important features of any function t → P (|X| ≥ t) when X is a random variable. In particular, if we often deal with concentration functions α that take values outside of (-∞, 1], it is implicitly understood that we consider in the calculus t → min{α(t), 1} instead of α.

In Definition 2, we see that α basically limits the variations of the random variable Z. The faster α decreases, the lower the variations of Z. Instinctively one might hope that this limitation of the variation would be equivalent to a concentration around some central quantity that will be called a pivot of the concentration in the following sense : Definition 3 (Concentration around a pivot). Given a ∈ R, the random variable Z is said to be α-concentrated around the pivot a, and we write Z ∈ a ± α, iff :

∀t > 0 : P (|Z -a| ≥ t) ≤ α(t).
We call the parameter a a pivot because the concentration around a provides similar concentration around other values close to a. Given θ > 0, let us denote τ θ the operator defined on the set of concentration functions that verifies for any concentration function α :

τ θ • α(t) = 1 if t ≤ θ α(t -θ) if t > θ.
Then we have the simple Lemma :

Lemma 1.1.1. Given a random variable Z ∈ R, a concentration function α, two real numbers a, b ∈ R and θ > 0, we have the implication :

Z ∈ a ± α a -b ≤ θ =⇒ Z ∈ b ± τ θ • α.
At first sight, there exists no pivot a ∈ R such that Definition 2 and Definition 3 are equivalent. We can however find an interesting relation considering the case a = m Z where m Z is a median of Z, verifying by definition

P(Z ≥ m Z ) ≥ 1/2 and P(Z ≤ m Z ) ≥ 1/2.
Proposition 1.1.2 (Concentration around the median, from [Led01, Corollary 1.5]). Given a random variable Z, a median m Z of Z and a concentration function α, we have the implications :

Z ∝ α =⇒ Z ∈ m Z ± 2α =⇒ Z ∝ 4α( • /2)
where α( • /2) is defined as being the function t → α(t/2).

We see here that if Z is α-concentrated, the tail of Z, i.e., the behavior of Z far from the median, is closely linked to the decreasing speed of α.

Proof. We need to consider the fact that P (Z = m Z ) = may be non zero. Therefore there exist 1 , 2 such that = 1 + 2 and :

P (Z < m Z ) = 1 2 -1 P (Z > m Z ) = 1 2 -2 .
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

Let us take t > 0. The first result follows from the inequalities :

P (|Z -Z | ≥ t) = P (|Z -Z | ≥ t, Z < m Z ) + P (|Z -Z | ≥ t, Z > m Z ) + P (|Z -m Z | ≥ t, Z = m Z ) ≥ (1/2 -1 ) P (Z ≥ t + Z | Z < m Z ) + (1/2 -2 ) P (Z ≥ t + Z | Z > m Z ) + P (|Z -m Z | ≥ t) ≥ (1/2 -) (P (Z ≥ t + m Z ) + P (m Z ≥ t + Z)) + P (|Z -m Z | ≥ t) = 1 2 P (|Z -m Z | ≥ t) .
The second result is true for any real a ∈ R replacing m Z :

P (|Z -Z | ≥ t) ≤ P (|Z -m Z + m Z -Z | ≥ t) ≤ 2P (|Z -m Z | ≥ t/2) .
The reason why Definition 2 was presented firstly and thus given the importance of the naturally underlying definition, even though Definition 3 might seem more intuitive, lies in its immediate compatibility to the composition with any Lipschitz function and more generally with any uniformly continuous function. The uniform continuity of a function is sized by its modulus of continuity. Although we presently work on R, we give a general definition of the continuity modulus between two normed vector spaces because it will be useful in the next sections.

Definition 4 (Uniform continuity). Any non decreasing function ω : R + → R + continuous and null in 0 is called a modulus of continuity. Given two normed vector space (E, • E ) and (F, • F ), a function f : E → F is said to be continuous under the modulus of continuity ω if :

∀x, y ∈ E : f (x) -f (y) F ≤ ω( x -y E ).
When ∀t > 0, ω(t) = λt ν for λ > 0 and ν ∈ (0, 1], we say that f is (λ, ν)-Hölder continuous, ν is called the Hölder exponent and λ is called the Lipschitz coefficient ; indeed, if ν = 1, f is said to be λ-Lipschitz. Of course a function admits a modulus of continuity iff it is uniformly continuous.

Lemma 1.1.3. Let us consider a random variable Z, a concentration function α, and a function f : R → R continuous under a modulus of continuity ω.We allow ourselves to write ω -1 the pseudo inverse of ω defined (for ω bijective or not) as : ω -1 (w) = inf{t, ω(t) ≥ w}. We have the implication :

Z ∝ α =⇒ f (Z) ∝ α ω -1 ( • ) .
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

Proof. It is straightforward to write :

P (|f (Z) -f (Z )| ≥ t) ≤ P (ω(|Z -Z |) ≥ t) ≤ P |Z -Z | ≥ ω -1 (t) ≤ α ω -1 (t)
since for any w, t > 0, ω(t) ≥ w =⇒ t ≥ ω -1 (w) by definition of the pseudo inverse.

Remark 1.1.4. Definition 3 is not so compatible with the ω-continuous transformations. Indeed, the simple developments that one finds in the proof above cannot be performed when strictly assuming that Z ∈ m Z ± α. In this case, one would rather combine Lemma 1.1.3 with Proposition 1.1.2 to find :

Z ∈ m Z ± α =⇒ f (Z) ∈ m f Z ± 2α 1 2 ω -1 ( • /2) .
The stability with respect to ω-continuous functions reflects the fact that a ω-continuous function contains the spreading of the distribution up to the modulus of continuity.

One property that we could expect from α-concentration is a stability towards the sum. Up to a multiplying factor of 2, this is the case : Lemma 1.1.5. Given two random variable Z 1 and Z 2 and two concentration functions α, β, we have the implication :

Z 1 ∝ α and Z 2 ∝ β =⇒ Z 1 + Z 2 ∝ α( • /2) + β( • /2).
Proof. Recall that Z 1 and Z 2 are two independent copies respectively of Z 1 and Z 2 . There is no reasons for Z 1 to be independent of Z 2 (resp., Z 2 of Z 1 ). The idea is to decompose the threshold t > 0 in t 2 + t 2 :

P (|Z 1 + Z 2 -Z 1 -Z 2 | ≥ t) ≤ P |Z 1 -Z 1 | ≥ t 2 + P |Z 2 -Z 2 | ≥ t 2 ≤ α t 2 + β t 2 .
Remark 1.1.6. This time the idea of the demonstration works the same with the setting of Definition 3, and we have :

Z 1 ∈ a ± α and Z 2 ∈ b ± β =⇒ Z 1 + Z 2 ∈ a + b ± α( • /2) + β( • /2).
In a first approach, α-concentration performs badly with the product, as it requires a bound on both random variables involved which greatly reduces the number of possible applications.

Lemma 1.1.7. Given two bounded random variable Z 1 and Z 2 such that |Z 1 | ≤ K 1 and |Z 2 | ≤ K 2 and two concentration functions α, β :

Z 1 ∝ α and Z 2 ∝ β =⇒ Z 1 Z 2 ∝ α • 2K 2 + β • 2K 1 .
Proof. Given t > 0 :

P (|Z 1 Z 2 -Z 1 Z 2 | ≥ t) ≤ P |Z 1 (Z 2 -Z 2 )| ≥ t 2 + P |(Z 1 -Z 1 )Z 2 | ≥ t 2 ≤ P |Z 2 -Z 2 | ≥ t 2K 1 + P |Z 1 -Z 1 | ≥ t 2K 2 .
Actually, the setting of Definition 3 is more convenient here than the setting of Definition 2 because it allows us to only require one random variable to be bounded :

Lemma 1.1.8. Given two random variables Z 1 and Z 2 such that |Z 1 | ≤ K 1 , two pivot a, b ∈ R and two concentration functions α, β, if b = 0 one has the implication :

Z 1 ∈ a ± α and Z 2 ∈ b ± β =⇒ Z 1 Z 2 ∈ ab ± α • 2 |b| + β • 2K 1 , if b = 0, then the concentration of Z 1 and Z 2 implies that Z 1 Z 2 ∈ 0 ± β( • K1
). We may even go further and dispense with the bounding hypothesis to get in this case a slightly more complicated concentration form : Proposition 1.1.9. Given two random variable Z 1 and Z 2 , two pivot a, b ∈ R and two concentration functions α, β such that Z 1 ∈ a ± α and Z 2 ∈ b ± β, if a = 0 and b = 0, then Z 1 Z 2 is concentrated around ab with :

Z 1 Z 2 ∈ ab ± α • 3 + α • 3 |b| + β • 3 + β • 3 |a| . If a = 0 and b = 0, we get Z 1 Z 2 ∈ 0 ± α • 2 + α • 2|b| + β • 2 and if a = b = 0, Z 1 Z 2 ∈ 0 ± α √ • + β √ • .
Proof. We just prove the result for a, b = 0 since the other cases are simpler. The idea is to use the algebraic identity :

xy -ab = (x -a)(y -b) + a(y -b) + b(x -a)
and the implication xy ≥ t ⇒ x ≥ √ t or y ≥ √ t (for x, y, t ≥ 0):

P (|Z 1 Z 2 -ab| ≥ t) ≤ P |Z 1 -a| ≥ t 3 + P |Z 2 -b| ≥ t 3 + P |Z 1 -a| |b| ≥ t 3 + P |Z 2 -b| |a| ≥ t 3 .
Proposition 1.1.10. Given m ∈ N and a random variable Z ∈ a ± α with a ∈ R and α, one has the concentration :

Z m ∈ a m ± α • 2 m |a| m-1 + α • 2 1 m
Proof. Let us employ the algebraic identity :

Z m = (Z -a + a) m = m i=0 m i a m-i (Z -a) i = a m + a m m i=1 m i Z -a a i . If Z-a a ≤ 1, for any i ∈ {1, . . . m}, Z-a a i ≤ Z-a a and conversely, if Z-a a ≥ 1, then Z-a a i ≤ Z-a a m
. This entails :

|Z m -a m | ≤ (2 |a|) m Z -a a + Z -a a m
and therefore :

P (|Z m -a m | ≥ t) ≤ P |Z -a| ≥ t 2 m |a| m-1 + P |Z -a| ≥ t 2 1 m .
In the same vein, we can give the concentration of the product of m random variables, we will though obtain better concentration constants in the case of q-exponential concentration that will be studied in the next subsection. For that reason we left the formulation and the proof of this result in Appendix A. In the same appendix, one can find the expression of the concentration of Z r when r ∈ R + * (and Z is concentrated). We conclude this section by setting the continuity of the concentration property. We adopt the classical formalism for the convergence of a random variable (or vector).

Definition 5. We say that a sequence of random variables (or random vectors) Z n converges in law (or "in distribution" or "weakly") to Z if for any real valued continuous function f with compact support :

lim n→∞ E[f (Z n )] = E[f (Z)].
Although we rather find in the literature the definition mentioning continuous and bounded functions, this equivalent definition relying on the class of continuous functions with compact support is more adapted to our needs (see Proposition 1.2.59). We start with the preliminary lemma : Lemma 1.1.11 ([Ouv09], Proposition 14.17). Let us consider a sequence of random variable Z n , n ∈ N, and a random variable Z with cumulative distribution functions respectively noted F Zn , n ∈ N, and F Z . The sequence (Z n ) n≥0 converges in law to Z iff for any t ∈ R such that F Z is continuous on t, (F Zn (t)) n≥0 converges to F Z (t).

Proposition 1.1.12. Consider a sequence of random variables (Z n ) n≥0 that converges in law to a random variable Z, a sequence of pivot (a n ) n≥0 converging to a pivot a ∈ R and a sequence of concentration functions (α n ) n≥0 that pointwise converges to a continuous concentration function α. If we suppose that, for any n ∈ N, Z n ∈ a n ± α n then Z ∈ a ± α.

Proof. For any n ∈ N, let us note Y n = |Z n -a n | and Y = |Z -a|. We wish to show first that (Y n ) n≥0 converges in law to Y . Let us consider for that purpose a continuous function f : R → R with compact support S and ε > 0. We know from the Heine-Cantor theorem that f is uniformly continuous, therefore there exists η > 0 such that :

|x -y| ≤ η =⇒ |f (x) -f (y)| ≤ ε 2 .
Moreover, since lim n→∞ a n = a, there exists n 0 > 0 such that for any n ≥ n 0 , |a n -a| ≤ η. Eventually, if we introduce the function g : x → |x -a|, we know that f • g has a compact support S = a + S ∪ a -S, and thus there exists

n 1 ∈ N such that if n ≥ n 1 : |E[f (|Z n -a|)] -E[f (|Z -a|)]| = |E[f • g(Z n )] -E[f • g(Z)]| ≤ ε 2 .
Therefore if we consider n ≥ max(n 0 , n 1 ) :

|E[f (Y n )] -E[f (Y )]| ≤ |E[f (|Z n -a n |) -f (|Z n -a|)]| + |E[f (|Z n -a|) -f (|Z -a|)]| ≤ ε.
Then we know from Lemma 1.1.11 that for any t such that the cumulative distribution function F Y = P (|Z -a| ≤ • ) is continuous around t :

P (|Z -a| ≥ t) = lim n→∞ P (|Z n -a n | ≥ t) ≤ lim n→∞ α n (t) = α(t).
Since α is continuous and t → P (|Z -a| ≥ t) is decreasing, we recover the preceding inequality for any t > 0, and Z ∈ a ± α.

In the setting of Definition 2, we can show the continuity of the concentration the same way introducing this time the random variables Y n = |Z n -Z n | (Z n being a sequence of independent copies of Z n ). We present the next proposition without proof.

Proposition 1.1.13. In the setting of Proposition 1.1.12, if for any n ∈ N Z n ∝ α n , then Z ∝ α.

Exponential concentration

In [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF], Ledoux defines a random variable as normally concentrated when the concentration function is of the form Z ∝ Ce -( • /σ) 2 for two given constants C ≥ 1 and σ > 0. The form of the concentration function has no real importance on small dimensions since the result ensues from a mere bound on the Gaussian Qfunction; it is however surprising that this form naturally appears for the uniform distribution on the sphere (see Theorem 0.0.3) and others in high dimensions.

In order to present a general picture that will be helpful later (when dealing with products of random variables), let us include the general case of qexponential concentrations that we present with the formalism of Definition 3. Definition 6. Given q > 0, a random variable Z is said to be q-exponentially concentrated with head parameter C ≥ 1 and tail parameter σ > 0 iff there exists a pivot a ∈ R such that Z ∈ a ± Ce -(•/σ) q .

Example 1.1.14. A random variable Z following a Gaussian distribution with zero mean (i.e. zero median) and unit variance is 2-exponentially concentrated with a tail parameter equal to

√ 2 : Z ∈ 0 ± 2e -(•) 2 /2 .
In practice, the random variables will depend on a random vector whose dimension, say p, tends to infinity, the tail parameter is then a function of p that represents the asymptotic speed of concentration since it has the same order as the standard deviation of Z. If the q-exponential concentration functions are employed reasonably, the asymptotic information can be transmitted from the head parameter to the tail parameter so that the head parameter would stay mainly uninformative and close to 1. For that purpose, the following lemma gives us an easy way to bound a given concentration to a close one with a head parameter equal to e.

Lemma 1.1.15. Given x, q > 0 and C ≥ e, we have the inequality :

min(1, Ce -x ) ≤ ee -x/2 log(C)
Proof. If x ≤ 2 log(C) the inequality is clear, and if x ≥ 2 log(C) ≥ 2, we deduce the result of the lemma from the equivalence

log(C) -x ≤ - x 2 log(C) ⇐⇒ x ≥ 2 log(C) 2 2 log(C) -1 , since 2 log(C) 2 2 log(C)-1 ≤ 2 log(C) 2 log(C) ≤ x.
To place ourselves under the hypotheses of Lemma 1.1.15 and as it appears rather convenient in several propositions below we will suppose from now on that the tail parameter C is greater than e.

Exponential concentrations offer simple expressions of the concentration through shifting the pivot thanks to the following lemma.

Lemma 1.1.16. Given the parameters C ≥ e and q, σ, θ > 0 :

∀t > 0 : τ θ • Ce -(•/σ) q
≤ max e (θ/σ) q , C e -(•/2σ) q

Proof. The increasing behavior of t → t q ensures that (tθ) q ≥ (t/2) q when t ≥ 2θ, therefore :

∀t ≥ 2θ : P (|Z -b| ≥ t) ≤ Ce -(t/2σ) q
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

The result is also true when 0 ≤ t ≤ 2θ since :

P (|Z -b| ≥ t) ≤ 1 ≤ e (θ/σ) q e -(2θ/2σ) q .
This lemma, combined with lemma 1.1.1, clarifies the notion of tail parameters. The next corollary shows that it can be seen as the diameter of a "black hole" centered around any pivot of the concentration, in a sense that each value inside this "black hole" can be considered as a satisfactory pivot for the concentration ; this will be called later, in the case of random vectors, the observable diameter of the distribution, following Gromov terminology [START_REF] Gromov | Paul lévy's isoperimetric inequality[END_REF].

Corollary 1.1.17. Given C ≥ e and three positive parameters σ, λ, q > 0, two real a and b such that |a -b| ≤ λσ and a random variable Z, one has the implication :

Z ∈ a ± Ce -(•/σ) q =⇒ Z ∈ b ± C exp - • 2σ q where C = max(C, e λ q ).
Note that the interesting aspect of the result is the independence of the head parameter C = max(C, e λ q ) to the tail parameter σ. Moreover the tail parameter stays unmodified when q < 1.

We now have all the elements to show that, due to the high concentration of exponentially concentrated random vectors, every median plays a pivotal role among the different constants that can localize the concentration.

Proposition 1.1.18 ([Led01, Proposition 1.8]). Given a random variable Z, and a median m Z of Z, if we suppose that Z ∈ a ± Ce -( • /σ) q for a pivot a ∈ R, then :

Z ∈ m Z ± 2C exp - • 2σ q .
Proof. For some ε > 0, we choose t 0 > σ (log(2C) + ε) 1/q . We know that

P (|Z -a| ≥ t 0 ) < 1 2 and consequently |a -m Z | ≤ t 0 . Indeed if we suppose that m Z ≥ a + t 0 , then : 1/2 ≤ P (Z ≥ m Z ) ≤ P (Z -a ≥ t 0 ) ≤ P (|Z -a| ≥ t 0 ) ,
and we get the same absurd result if we suppose that a ≥ m Z + t 0 . We can thus conclude thanks to Corollary 1.1.17 (with C = max(C, exp(

t q 0 σ q )) = 2Ce ε ), letting ε tend to zero.
The tails of q-exponentially concentrated random variables can be controlled rather easily and roughly thanks to the next lemma that is based on the same simple mathematical inequalities that lead to Corollary 1.1.17.

Lemma 1.1.19. Given a random variable Z, two parameters C ≥ e and σ > 0 an exponent q > 0 and a pivot a ∈ R, if Z ∈ a ± Ce -( • /σ) q then ∀t ≥ 2 |a| :

P (|Z| ≥ t) ≤ Ce -(t/2σ) q .
Very interestingly, exponential concentration is of great computation convenience to manage Hölder's inequality. For instance a general issue is to bound :

E [(Z 1 -a 1 ) r1 • • • (Z m -a m ) rm ] . For any θ 1 , • • • , θ m ∈ (0, 1) such that θ 1 + • • • + θ m = 1, Hölder's inequality gives us directly : E [(Z 1 -a 1 ) r1 • • • (Z m -a m ) rm ] ≤ m i=1 E |Z i -a i | r i θ i θi .
(4)

As we will see in the next proposition, the quantities E |Z i -a i | r can be bounded easily when Z i = a i ± Ce -( • /σ) q i , and we will even show in the next proposition that the bounds on E |Z i -a i | r for r > 0 can become a characterization (it is actually a pseudo-characterization since there is no equivalence) of q-exponential concentrations.

Proposition 1.1.20 (Moment characterization of concentration, [Led01, Proposition 1.10]). Given a random variable Z, a pivot a ∈ R, two exponents r, q > 0, and two parameters C ≥ e and σ > 0, we have the implications :

Z ∝ Ce -(•/σ) q ⇒ ∀r ≥ q : E |Z -Z | r ≤ CΓ r q + 1 σ r ⇒ Z ∝ Ce -(•/σ) q e and Z ∈ a ± Ce -(•/σ) q ⇒ ∀r ≥ q : E [|Z -a| r ] ≤ CΓ r q + 1 σ r ⇒ Z ∈ a ± Ce -(•/σ) q e , where Γ : r → ∞ 0 t r-1 e -t dt, (if n ∈ N, Γ(n + 1) = n!).
In both results, the first implication consists in bounding an expectation with a probability; it will involve the Fubini relation, giving for any positive random variable Z :

EZ = Z ∞ 0 1 t≤Z dt dZ = ∞ 0 P (Z ≥ t) dt,
where 1 t≤Z is equal to 1 if t ≤ Z and to 0 otherwise.

The second implication consists in bounding a probability with an expectation; it is a consequence of Markov's inequality, for any non decreasing function f : R → R :

P (Z ≥ t) ≤ Ef (Z) f (t) .
These two key indications given we can start the proof.

Proof. We just prove the first implication, as it will be clear that both can be proved the same way. Let us first suppose that r ≥ q. Knowing that Z ∝ e -(ct) q , we consider Z , an independent copy of Z, and we can bound :

E [|Z -Z | r ] = ∞ 0 P (|Z -Z | r ≥ t) dt = ∞ 0 rt r-1 P (|Z -Z | ≥ t) dt ≤ Cr ∞ 0 t r-1 e -(t/σ) q dt = Cσ r r ∞ 0 t r-1 e -t q dt
and, since r ≥ q :

r ∞ 0 t r-1 e -t q dt = r q ∞ 0 t r q -1 e -t dt = Γ r q + 1
Now, assuming the second term of the implication chain, we know from Markov's inequality that ∀r ≥ q :

P (|Z -Z | ≥ t) ≤ E |Z -Z | r t r ≤ CΓ r q + 1 σ t r ≤ C r q(t/σ) q r/q . If t ≥ e 1 q σ,
we can then set r = qt q eσ q ≥ q, and we get :

P (|Z -Z | ≥ t) ≤ Ce -(t/σ) q /e .
If t ≤ e 1 q σ, we still know that P (|Z -Z | ≥ t) ≤ 1, and we conclude that :

∀t > 0 : P (|Z -Z | ≥ t) ≤ max(C, e)e -(t/σ) q /e .
Remark 1.1.21. In the last proposition, we did not provide a bound on E |Z -Z | r and E [|Z -a| r ] for 0 ≤ r < q since it is irrelevant to the characterization of q-exponential concentration. We may nonetheless easily bound these quantities with Cσ r . Getting inspiration from our previous derivations, we can indeed obtain when 1 ≤ r ≤ q :

E [|Z -Z | r ] ≤ Cσ r ∞ 0 rt r-1 e -t q dt ≤ Cσ r ∞ 0 t r qt q-1 e -t q dt ≤ Cσ r 1 0 qt q-1 e -t q dt + Cσ r ∞ 1 t q qt q-1 e -t q dt = Cσ r ∞ 0 qt q-1 e -t q dt = Cσ r
and when r ≤ 1 ≤ q, we conclude with Jensen's inequality :

E [|Z -Z | r ] ≤ E [|Z -Z |] r ≤ C r σ r ≤ Cσ r .
The following Lemma gives an alternative result to the aforementioned sufficiency of bounds on

E [|Z -a| r ] (or on E [|Z -Z | r ]) for r ∈ N.
Lemma 1.1.22. Given a random variable Z ∈ R + and three parameters C > e, q, σ > 0 one has the implication :

∀m ∈ N, E[Z m ] ≤ C m q m q σ m =⇒ ∀r ≥ 0, E[Z r ] ≤ Ce 1 e r q r q σ q 1 q r
where q = min(q, 1).

Proof. When r ≤ 1, we already know thanks to Jensen's inequality, by concavity of t → t r , that :

E[Z r ] ≤ (E[Z]) r ≤ C 1 q r q σ r ≤ Ce 1 e r q r q σ q 1 q r , since ∀t > 0, t t ≥ 1 e 1 e
. When r ≥ 1, one can invoke the well known result concerning r norms, where in our case, Z r = E [|Z| r ] 1/r . Let us consider the general case where we are given p 1 , p 2 > 0 such that p 1 ≤ r ≤ p 2 and we consider θ ∈ (0, 1) satisfying 1/r = θ/p 1 + (1 -θ)/p 2 . We then have the inequality :

Z r ≤ Z θ p 1 Z 1-θ p 2 .
This implies :

E [Z r ] 1 r ≤ C 1 p 1 σ p 1 q 1 q θ C 1 p 2 σ p 2 q 1 q 1-θ ≤ C 1 r σ q 1 q p θ q 1 p 1-θ q 2 .
We would like to bound p

θ q 1 p 1-θ q 2 with r 1 q . Unfortunately, for θ ∈ ]0, 1[, p θ 1 p 1-θ 2 > 1/(θ/p 1 +(1-θ)/p 2 ) =
r (this is due to the inequality of arithmetic and geometric means, itself a consequence of the concavity of the log function). However, for the particular setting under study :

θ p 1 + 1 -θ p 2 p θ 1 p 1-θ 2 ≤ 1 p 2 + (p 2 -p 1 )θ p 1 p 2 p 2 ≤ 1 + p 2 -p 1 p 1 .
As a consequence, taking p 1 = r and p 2 = r , one obtains :

E [|Z| r ] ≤ Cσ r 2r q r q . Remark 1.1.23. In Proposition 1.1.20, we saw that if Z ∈ a ± Ce -( • /σ) q then |EZ -a| ≤ E |Z -a| ≤ C 1 q 1/q
σ < ∞. Therefore any q-exponentially concentrated random variable admits a finite expectation.

Now that we know it exists, we are going to show that the expectation EZ plays the same pivotal role as any median.

Corollary 1.1.24 ([Led01, Proposition 1.9]). With the notations of the previous proposition, one has :

Z ∈ a ± Ce -( • /σ) q =⇒ Z ∈ EZ ± e C q q e -( • /2σ) q .
Proof. We suppose that Z ∈ Ce -( • /σ) q for a pivot a ∈ R. Proposition 1.1.20 applied in the case r = 1 gives us |a -EZ| ≤ C( 1 q ) 1 q σ. One can then invoke Corollary 1.1.17, to get the concentration :

Z ∈ EZ ± C e -( • /2σ) q , with C = max(C, e C q q
). It is then interesting to note that the function q → C q q has a minimum in 1 log(C) where it takes the value e log C. Then we see that

C = e log C ≤ e e log C ≤ e C q q ,
and we can simplify the head parameter to obtain the result of the corollary.

If Z ∈ a ± Ce -( • /σ) p , we can then employ EZ as a pivot of Z to get a bound on the centered moments :

Corollary 1.1.25. With the notations of Corollary 1.1.24, if we suppose that Z ∈ a ± Ce -( • /σ) q , then we have :

E |Z -EZ| r ≤ e C q q (2σ) r r q r q
.

Provided two identically distributed random variables Z 1 , Z 2 ∈ R, even if Z 1 and Z 2 are not independent, one still intuitively expects that Z 1 + Z 2 and Z 1 Z 2 vary at most like 2Z 1 and Z 2 1 , respectively. This simple intuition can be easily proved valid in the case of q-exponential concentrations thanks to the characterization given by Proposition 1.1.20. But before getting into this aspect, let us introduce the notion of controlling random variables that allows us to handle the case of non identically distributed Z 1 and Z 2 .

Definition 7. Given two random variables Z ∈ R and Y ∈ R + , one says that Y controls Z iif ∀t ≥ 0 : P (|Z| ≥ t) ≤ P (Y ≥ t) .
Given a set of random variables Z 1 , . . . , Z p ∈ R + , any random variable Y admitting the cumulative distribution function :

F Y (t) = P (Y ≤ t) = 1 -sup 1≤i≤p P (|Z i | > t)
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 clearly controls Z 1 , . . . , Z p . If we consider a random variable Z depending on Z 1 , . . . , Z p and want to express the concentration of Z thanks to Proposition 1.1.20, we are led to bound the quantities

E[|Z -Z | r ] or E[|Z -a| r ].
The next lemma gives the central idea allowing to control those quantities with expectations taken on Y only, when r ∈ N and Z = P (Z 1 , . . . , Z p ) is a polynomial functional with positive coefficients. It simply relies on Hölder's inequality and the fact that

E[Z m i ] ≤ E[Y m ] for all m ∈ N, 1 ≤ i ≤ p. Lemma 1.1.26. Given two integers d, p ∈ N, a polynomial P (X 1 , . . . , X p ) = b1+•••+bp≤d c b X b1 1 • • • X bp p with positive coefficients c b = c b1,...,bp ≥ 0, b 1 + • • • + b p ≤ d
E [P (Z 1 , . . . , Z p )] ≤ E [P (Y, . . . , Y )] .
Proof. It is a simple application of Hölder's inequality :

E [P (Z 1 , . . . , Z p )] = b1+•••+bp≤d c b E Z b1 1 . . . Z bp p ≤ b1+•••+bp≤d c b E Z |b| 1 b 1 |b| . . . E Z |b| p bp |a| = b1+•••+bp≤d c b E Y |b| = E [P (Y, . . . , Y )]
where |b| = p i=1 b i ≤ p. Lemma 1.1.22 combined with Lemma 1.1.26 provides us with the concentration of the sum of p random variables with a better tail parameter than the one that would be obtained if we would employ Proposition 1.1.5 p times.

Proposition 1.1.27. Given the parameters C > e, q, σ > 0, p ∈ N, p random variables Z 1 , . . . , Z p ∈ R satisfying, for any i ∈ {1, . . . , m}, Z i ∈ a i ± Ce -(•/σi) q where a i ∈ R and σ i > 0, we have the concentration :

Z 1 + • • • + Z p ∈ a 1 + • • • + a p ± e 1/e C exp - q 2e • σ p q
where σ = p i=1 σ i We will not prove here this proposition since it is a particular case of Proposition 1.2.6 concerning the linear concentration of random vectors. In the same setting, it is also possible to control the concentration of the product

Z 1 • • • Z p .
Proposition 1.1.28. Let us consider three parameters C > e, q, σ > 0, an integer p ∈ N, and p random variables Z 1 , . . . , Z p ∈ R satisfying, for any i ∈ {1, . . . , m}, Z i ∈ a ± Ce -(•/σ) q . Then, if a ≥ σ :

∀m ∈ N : E [|Z 1 • • • Z p -a p | m ] ≤ C(2σa p-1 ) m m q m q + (2σ) pm pm q pm q while, if a ≤ σ : ∀m ∈ N : E [|Z 1 • • • Z p -a p | m ] ≤ 3C(2σ) pm pm q pm q
.

Remark 1.1.29. We did not express as in Proposition 1.1.27 the concentration of

Z 1 • • • Z p around a p since the bounds on E [|Z 1 • • • Z p -a p | m ] are too complex
to allow for simple optimizations of the Chernoff inequalities as in the proof of Proposition 1.1.20. Still, for a ≤ σ, we can infer from Lemma 1.1.22 (and Proposition 1.1.20) :

Z 1 • • • Z p ∈ a p ± 3e 1/e C exp - q 2e • 2 p σ p q p .
Remark 1.1.30. We will prove below a stronger result than Proposition 1.1.28 when in presence of multiple tail parameters and pivots. In the setting of Proposition 1.1.27, we will show that for any λ > 0 :

E [|Z 1 • • • Z p -a 1 • • • a p | m ] ≤ p i=1 |a i | + σ i λ m λ m m q m q
+ λ mp mp q mp q .

(5)

Then when the pivots a 1 , . . . , a p are equal to a and the tail parameters σ 1 , . . . , σ p are equal to σ, one can retrieve the result of Proposition 1.1.28 choosing λ = 1 when a ≤ σ and λ = σ a when a ≥ σ. Proof. Placing ourselves in the general setting of Proposition 1.1.27, we consider a parameter λ > 0 and aim at proving (5). To employ Lemma 1.1.26, let us introduce the polynomial

P (X 1 , . . . , X p ) = (σ 1 X 1 + |a 1 |) • • • (σ p X p + |a p |) -|a 1 • • • a p | = |a 1 • • • a p | p l=1 I⊂{1,...,p} #I=l i∈I σ i X i |a i |
that has positive coefficients and verifies :

|Z 1 • • • Z p -a 1 • • • a p | ≤ P |Z 1 -a 1 | σ 1 , . . . , |Z p -a p | σ p .
Given a random vector Y ∈ R + with the cumulative distribution function 1 -Ce -• q , one knows from Lemma 1.1.26 that for any m ∈ N :

E [|Z 1 • • • Z p -a 1 • • • a p | m ] ≤ E [P (Y, . . . , Y ) m ] ≤ |a 1 • • • a p | m E       p l=1 I⊂{1,...,p} #I=l i∈I σ i |a i | Y l    m   
since P m has positive coefficients (since P does). Let us introduce for all l ∈ {1, . . . , p} the coefficient c l that depends on λ and verifies :

c l = I⊂{1,...,p} #I=l i∈I σ i λ|a i | .
Decomposing the computation of the expectation between the expectation on the set of drawings where λY ≤ 1 and λY ≥ 1, one obtains :

E [|Z 1 • • • Z p -a 1 • • • a p | m ] ≤ |a 1 • • • a p | p l=1 c l m (E [(λY ) m ] + E [(λY ) pm ]) .
We then easily retrieve (5) thanks to Proposition 1.1.20 since :

|a 1 • • • a p | p l=1 c l = P 1 λ , . . . , 1 λ = σ 1 λ + |a 1 | • • • σ p λ + |a p | -|a 1 • • • a p |.
The previous development of q-exponential concentration primarily aims at providing a versatile and convenient "toolbox" (note that most introduced inequalities could have been enhanced, however to the expense of clarity) for the subsequent treatment of large dimensional random vectors, rather than random variables. This analysis will be performed through resorting to concentrated functionals of the random vectors, i.e., real images of through a mapping with different levels of regularity (linear, Lipschitz, convex..). For large dimensional vectors, one is mostly interested in the order of the concentration, thus the various constants appearing in most of the previous propositions and lemmas do not have any particular interest; of major interest instead is the independence of the concentration with respect to the random vector dimension, as observed for instance in Theorem 0.0.3 and that we will extend to other type of random vectors in what follows.

Concentration of a random vector of a normed vector space

In Section 2, the random vectors under study are either in E = R p endowed with the Euclidean norm z = • the spectral norm defined as M = sup z ≤1 M z ,

• the Frobenius norm M F = 1≤k≤p 1≤i≤n M 2 k,i
(where M ∈ M p,n ). Note that the Frobenius norm can be seen as a Euclidean norm on R pn with the bijection that concatenates the column of a matrix.

To generalize the notion of concentration to the case of a random vector of a normed vector space (E, • ), one might be tempted to follow the idea of Definition 3 and say that a vector Z ∈ E is α-concentrated if one has for instance P Z -Z ≥ t ≤ α(t) for a deterministic vector Z, well chosen. This would describe a notion of a concentration around a vector.

However, this basic notion would not be compatible with the fundamental example of the uniform distribution on the sphere of radius √ p presented in Theorem 0.0.3 or the Gaussian vectors of identity population covariance matrices. When the dimension grows, those random vectors concentrate around a growing sphere which is the exact opposite behavior of being concentrated around a point. Yet, they present strong dimension free concentration properties that we will progressively identify through the presentation of three fundamental notions :

1. The linear concentration which is the concentration of u(Z -Z) for some deterministic vector Z ∈ E (the so-called deterministic equivalent) and for any bounded linear form u : E → R. For instance, we know from Theorem 0.0.3 that any random vector Z uniformly distributed on the sphere admits Z = EZ = 0 as a deterministic equivalent. This means that most drawings of Z are close to the equator when the dimension grows. 2. The Lipschitz concentration which is the concentration of f (Z) -f (Z ) for any i.i.d. copy Z of Z and any Lipschitz map f : E → R. 3. The convex concentration which is the concentration of f (Z) -f (Z ) for any Lipschitz and weakly convex map f : E → R. This notion is of course weaker than the Lipschitz concentration, its presentation here is only justified by the fundamental Theorem 1.2.47 owed to Talagrand that provides concentration properties on random vectors with independent and bounded entries. It is less "stable" than the Lipschitz concentration, meaning there exist very few transformations that preserve convex concentration. As a consequence one usually naturally returns to linear concentration after some refinement. For instance, supposing that X is convexly concentrated, only a linear concentration can be obtained for the resolvent

Q = (XX T /n + zI p ) -1 .
Although a seemingly basic notion, linear concentration still has quite interesting features that justify an independent treatment at the beginning of this section.

Linear Concentration

Considering the linear functionals of random vectors allows us, in particular, to introduce the notion of deterministic equivalents, which play the role of the pivots we presented in the concentration of random variables.

Definition 8. Given a random vector Z ∈ E, a deterministic vector Z ∈ E and a concentration function α, we say that Z is linearly α-concentrated around the deterministic equivalent Z if for any bounded linear form u : E → R with a unit operator norm (i.e., ∀z ∈ E, |u(z)| ≤ z ) :

u(Z) ∈ u( Z) ± α.
We note in that case :

Z ∈ Z ± α in (E, • ).
Remark 1.2.1. Definition 8 is clearly compatible with Definition 3 for the case where E = R. Indeed, in R the linear forms are the scalar functions and for any coefficient λ ∈ R * and any random variable Z ∈ R we have the equivalence :

Z ∈ a ± α ⇐⇒ λZ ∈ λa ± α( • /λ).
Remark 1.2.2. The advantage of linear functionals is that they preserve the expectation which gives us the simplest deterministic equivalent. For instance if Z is linearly q-exponentially concentrated, then we know from Corollary 1.1.24 that EZ is a deterministic equivalent for Z since for any continuous linear form

u, E[u(Z)] = u(E[Z]).
For instance, thanks to Theorem 0.0.3, one knows that for any

p ∈ N * , if Z ∼ σ p then Z ∈ 0 ± 2e -• 2 /2 since E[Z] = 0.
Since the Frobenius norm is larger than the spectral norm, for any random matrix M ∈ M p,n , we have the implication :

M ∈ M ± α in (M p,n , • F ) =⇒ M ∈ M ± α in (M p,n , • )
for some deterministic matrix M and some concentration function α. When the choice of the norm is not ambiguous (when E = R p in particular), we will allow ourselves not to specify the norm.

Remark 1.2.3. The same way that linear forms in R p are fully described with the scalar product, in M p,n the linear forms are fully defined by the functions

f A : M → Tr AM for A ∈ M p,n where f A is said to have a unit norm if f A * = 1, i.e., • in (M p,n , • F ) : A F = Tr(AA T ) = 1, • in (M p,n , • ) : A 1 = Tr(AA T ) 1 2 = 1.
Linear concentration is provided by classical concentration inequalities like Bernstein's or Hoeffding's inequalities.

Example 1.2.4. [Bernstein's inequality, [Ver17, Theorem 2.8.2]] Given p independent random variables (Z i ) 1≤i≤p ∈ R p , and three parameters C ≥ e and c, q > 0, we have the implication :

∀i ∈ {1, . . . , p}, Z i ∈ E[Z i ] ± Ce -• /σ ⇒ Z ∈ E[Z] ± 2e -c( • /σ) 2 + 2Ce -c •/σ ,
where c is a numerical constant depending only on C.

Example 1.2.5. [Hoeffding's inequality, [Ver17, Theorem 2.2.6]] Given p independent random variables Z 1 , . . . , Z p ∈ [0, 1], the random vector Z = (Z 1 , . . . , Z p ) ∈ R p is linearly concentrated and verifies

Z ∈ E[Z] ± 2e -2 • 2 in (R p , • ).
We will see in Subsection 1.2.3 about convex concentration a generalization of Hoeffding's theorem with the theorem of Talagrand.

Even if one does not suppose the independence between the random variables Z 1 , . . . , Z p , one can still get a concentration result on the random vector Z = (Z 1 , . . . , Z p ) in the case of q-exponential concentrations. The basic idea is that if Z 1 , . . . , Z p are identically distributed then Z is at least as concentrated as the random vector (Z 1 , . . . , Z 1 ).

Proposition 1.2.6. Given the parameters C > e, q, σ > 0, p ∈ N, p vector spaces (E i , N i ) 1≤i≤p , p deterministic vectors Z1 ∈ E 1 , . . . , Zp ∈ E p and p random vectors Z 1 ∈ E 1 , . . . , Z p ∈ E p (possibly dependent) satisfying, for any i ∈ {1, . . . , m}, Z i ∈ Zi ± Ce -(•/σ) q , we have the concentration :

(Z 1 , . . . , Z p ) ∈ ( Z1 , . . . , Zp ) ± e 1 e C exp - q 2e • σ q , in (E, • ∞ ),
where we introduced on

E ≡ E 1 × • • • × E p the norm • ∞ verifying for any for (z 1 , . . . , z p ) ∈ E : (z 1 , . . . , z p ) ∞ = sup 1≤i≤p N i (z i ),
and we recall that q = min(q, 1).

Proof. Let us consider a linear function u : E → R, such that

u ∞ ≡ sup z ∞ ≤1 |u(z)| ≤ 1.
Given i ∈ {1, . . . , p}, let us note u i : E i → R the function defined as u i (z) = u((0, . . . , 0, z, 0, . . . , 0)) (where z is in the i th entry). For any z ∈ E, one can write :

u(z) = p i=1 N i (u i )u i (z),
where

N i (u i ) = sup Ni(z)≤1 u i (z) and u i = u i /N i (u i ) (N i (u ) = 1). With the convenient notation n i ≡ N i (u i ),
we have the inequality :

p i=1 n i = p i=1 n i sup Ni(zi)≤1 u i (z i ) = sup z ∞ ≤1 u(z) ≤ 1.
With this bound at hand, we plan to employ the characterization with the centered moments. Considering m ∈ N * , we introduce the polynomial

P (X 1 , . . . , X p ) = (n 1 X 1 + • • • + n p X p ) m
: it has positive coefficients which allows us to employ Lemma 1.1.26 in order to bound :

E u(Z) -u( Z) m ≤ E p i=0 n i u i (Z i ) -u i Zi m = E P u 1 (Z 1 ) -u 1 Z1 , . . . , u p (Z p ) -u p Zp ≤ E [P (Y, . . . , Y )] = E p i=1 n i Y m ≤ E [Y m ] ≤ C m q m q σ m ,
where Y ≥ 0 is a nonnegative random variable having a cumulative distribution function equal to 1 -min(1, Ce -(•/σ) q ) (such a variable controls Z 1 , . . . , Z p ). We can then conclude thanks to Lemma 1.1.22 (and Proposition 1.1.20).

Given p random variables verifying Z i ∈ a i ± Ce -(•/σi) q , a i ∈ R and σ i > 0, we can apply Proposition 1.2.6 to the functional u : z → p i=1 σ i z i taken on the p random variables

Z i = Zi σi ∈ ai σi ± Ce -• q : p i=1 Z i = u(Z 1 , . . . , Z p ) ∈ p i=1 u i a i ± e 1 e C exp - q 2e • σ 1 + • • • + σ p q , since u ∞ = p i=1 σ i .
One can recognize here the concentration given by Proposition 1.1.27. The following corollary generalizes this result.

Corollary 1.2.7. Given p ∈ N, two parameters q > 0 and C ≥ e, and p random vectors Z 1 , . . . Z p ∈ E, respectively concentrated around the deterministic equivalents Z1 , . . . , Zp ∈ R p such that ∀i ∈ {1, . . . , p}, Z i ∈ Zi ± Ce -(•/σi) q for some parameters σ 1 , . . . , σ p > 0 :

Z 1 + • • • + Z p ∈ Z1 + • • • + Zp ± e 1 e C exp - q 2e • σ q , where σ = σ 1 + • • • + σ p .
Dealing with q-exponential concentrations, we can get an analogous result to Corollary 1.1.17 that allowed us to interchange the pivot a with any other real in a ball around a with a diameter of the same order as the tail parameter. The tail parameter will be called in the case of a random vector an observable diameter. Given a random vector Z ∈ E, we will say that Z is q-exponentially concentrated around Z with a head parameter C and an observable diameter σ if Z ∈ Z±Ce -( • /σ) q . The observable diameter is the diameter of the "observations" of the distribution that could be seen as linear projections (for other types of concentrations to be introduced subsequently, they will alternatively be related to 1-Lipschitz or quasi-convex maps) on R. Intuitively, it is the diameter of the observation in the "real world" ; refer to [START_REF] Gromov | Metric structures for riemannian and nonriemannian spaces[END_REF] for a both more precise and more general definition.

Lemma 1.2.8. Let us consider a random vector Z ∈ E, two deterministic vectors Z, Z ∈ E and three parameters C ≥ e, λ, σ > 0. If Z -Z ≤ λσ then we have the implication :

Z ∈ Z ± Ce -( • /σ) q =⇒ Z ∈ Z ± max(C, e λ q )e -( • /σ) q .
One might expect for concentrated random vectors a similar proposition to Proposition 1.1.9 giving the concentration of a product of random variables. In the case of vectorial objects, we are looking for the concentration of a scalar product of two random vectors X, Y ∈ E or, closer to our present interest as announced in the preamble, for the concentration of u T Qx where u is deterministic, Q is a concentrated random matrix and x a concentrated random vector. If one looks closely at the proof of Proposition 1.1.9, it becomes obvious that although some steps can be fully adapted, the method gets stuck when trying to bound :

P (|u ((X -EX)(Y -EY ))| ≥ t) .
It is tempting here to invoke the Cauchy-Schwartz inequality :

u ((X -EX)(Y -EY )) ≤ u X -EX Y -EY ,
where u is the operator norm of u. However, as we explained it with the example of spherical and Gaussian vectors in the introduction of this subsection, unlike u(X -EX) and u(Y -EY ) the quantities X -EX and Y -EY are far from being concentrated for concentrated random vectors X and Y of practical use. We will see in Proposition 1.2.10 that it is still possible to express the concentration of the norms and obtain consequently loose bounds for the concentration of (X -EX)(Y -EY ) as presented in Examples 1.2.16 and 1.2.17.

Before that, to present a setting where the concentration is satisfactory, we suppose in addition to the concentration that the two vectors are independent and one is bounded.

Proposition 1.2.9. Let us consider two normed vector spaces (E 1 , • 1 ) and

(E 2 , • 2 ), two independent random vectors Z 1 ∈ E 1 and Z 2 ∈ E 2 and a bilinear form f : E 1 × E 2 → R such that for any (z 1 , z 2 ) ∈ E 1 × E 2 : |f (z 1 , z 2 )| ≤ z 1 1 z 2 2 .
If there exist two concentration functions α, β : R + → R + and two deterministic vectors ( Z1 , Z2 ) ∈ E 1 × E 2 such that :

Z 1 ∈ Z1 ± α in (E 1 , • 1 ) and Z 2 ∈ Z2 ± β in (E 2 , • 2 ),
and if Z 2 2 is bounded by a real K 2 > 0, then :

f (Z 1 , Z 2 ) ∈ f Z1 , Z2 ± α • 2K 2 + β • 2 Z1 1 .
Proof. Given t > 0, we just compute :

P f (Z 1 , Z 2 ) -f ( Z1 , Z2 ) ≥ t ≤ E P f (Z 1 -Z1 , Z 2 ) ≥ t 2 | Z 2 + P f ( Z1 , Z 2 -Z2 ) ≥ t 2 ≤ α t 2K 2 + β t 2 Z1 1 since x → f (x, Z 2
) and y → f ( Z1 , y) are both linear and respectively K 2 -Lipschitz and Z1 -Lipschitz.

If a random vector Z is linearly concentrated around a deterministic equivalent Z, it is possible to control the norm Z -Z if the norm • can be defined as the supremum on a set of linear forms. For instance, in R p endowed with the sup norm

• ∞ ( x ∞ = sup{|x i |, 1 ≤ i ≤ p}), if Z ∈ Z ± α : P Z -Z ∞ ≥ t = P sup 1≤i≤p e T i (Z -Z) ≥ t (6) ≤ p sup 1≤i≤p P e T i (Z -Z) ≥ t ≤ pα(t), (7)
where (e 1 , . . . , e p ) is the canonical basis of R p (e i is a vector full of 0 with 1 on the i th coordinate). To manage the infinity norm, the supremum is taken on a finite set {e 1 , . . . e p }; things are more complex if we look at the Euclidean norm because this time one comes to use the identity x = sup{u T x, u ≤ 1} where the supremum is taken on the unit ball. To tackle this loss of cardinality, it is convenient here to introduce the so-called -nets to discretize the ball in order to approach sufficiently the norm and at the same time find a good bound for the probability (see [START_REF] Tao | Topics in random matrix theory[END_REF]). We leave the proof in the appendix.

Proposition 1.2.10. Let us consider a normed vector space (E, • ) of finite dimension such that there exists a subspace H of the dual space (E * , • * ), and a ball B H = {f ∈ H, f * ≤ 1} ⊂ H verifying for any z ∈ E :

z = sup f ∈B H f (z). (8)
Given a random vector Z ∈ E, a deterministic equivalent Z and a concentration function α, if we suppose that Z ∈ Z ± α then we have the concentration :

Z -Z ∈ 0 ± 8 dim(H) α • 2 (9)
where dim(H) is the dimension of H.

Remark 1.2.11. One always has z = sup f * ≤1 f (z), so one might be tempted to systematically consider H = E * . For instance in (R p , • ), H is taken to be equal to R p and dim(H) = p. The same way, in the Euclidean space (M p,n , • F ), we take H = M p,n (and dim(H) = pn). However, we can reduce greatly the dimension dim(H) in the case of (M p,n , • ) since for any M ∈ M p,n :

M = sup u , v ≤1 u T M v .
Thus it is wise to consider

H = {f vu T , u, v ∈ R p × R n } (see Remark 1.2.3 for a definition of f A ; here, f vu T * = vu T 1 = u v
) and the dimension is then only dim(H) = p + n.

Taking into account the two results (6) and (9), we are led to introduce an indicator characteristic to the norm that gives the speed of the concentration.

Definition 9 (Norm degree). Given a normed vector space (E, • ), and a subset H ⊂ E * , let us define the degree η H of H as :

• η H = log(#H) if H is finite • η H = dim(Vect H) if H is infinite
where #H is the number of elements in H and Vect H is the subspace of E generated by E. We note then η(E, • ) or more simply η • the degree of • that is defined as :

η • = η(E, • ) = inf η H , H ⊂ E * | ∀x ∈ E, x = sup f ∈H f (x)
In the setting of the last proposition :

Z -Z ∈ 0 ± e cη(E, • ) α • 2 , ( 10
)
where c is a numerical constant. In the case of the q-exponential concentration, it is possible to rearrange the concentration of Z -Z to obtain a head parameter of order 1.

Proposition 1.2.12. Given a random vector Z ∈ E, a deterministic vector Z ∈ R p and three parameters C ≥ e, c, σ > 0, we have the implication :

Z ∈ Z ± Ce -( • /σ) q =⇒ Z -Z ∈ 0 ± Ce -( • /2σ) q /2cη • ,
where c is the same numerical constant as in (10).

Reciprocally :

Z -Z ∈ 0 ± Ce -( • /σ) q =⇒ Z ∈ Z ± Ce -( • /σ) q .
The second result of the proposition is trivial (and quite useless) and the first result is just a simple consequence of (10) combined with Lemma 1.1.15.

Example 1.2.13. We can give some examples of norm degrees :

• η (R p , • ∞ ) = log(p)
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

• η (R p , • r ) = p for r ≥ 1 • η (M p,n , • ) = n + p • η (M p,n , • F ) = np.
In the particular case of q-exponential concentrations, the norm degree allows us to bound the expectation of the norm of Z -Z thanks to Proposition 1.2.12.

Corollary 1.2.14. Given a random vector Z ∈ E, if we suppose that Z ∈ Z ± Ce -( • /σ) q and q ≥ 1, we can bound :

E Z -Z ≤ C ση 1/q •
where C is a constant depending on C.

Example 1.2.15. Let Z ∈ R p and M ∈ M p,n be two random vectors. Then,

• if Z ∈ Z ± 2e -t 2 /2 in (R p , • ) : E Z ≤ Z + C √ p • if M ∈ M ± 2e -t 2 /2 in (M p,n , • ) : E M ≤ M + C √ p + n, • if M ∈ M ± 2e -t 2 /2 in (M p,n , • F ) : E M ≤ M + C √ pn.
Now that we can control the quantities Z -Z when Z is a deterministic equivalent of Z, it is tempting to extend Lemma 1.1.8 to the concentration of the product of any linearly concentrated random vectors. The examples presented below are just here to give an idea of what could be obtained, they are not relevant in practice since the bounds are too loose. Unlike Lipschitz concentration as it will be presented in next subsection, linear concentration is not suited to study the concentration of the product of random vectors.

Example 1.2.16. Let us note the product in R p verifying for any x = (x 1 , . . . , x p ) and y = (y 1 , . . . , y p ), x y = (x 1 y 1 , . . . , x p y p ). It gives an algebra structure to R p where • ∞ and • 2 are both algebra norms ( x y 2 ≤ x y 1 = p i=1 |x i y i | ≤ x 2 y 2 thanks to the Cauchy Schwarz inequality). Therefore we have for any vector

Z ∈ Z ± 2e -• 2 /2 in (R p , • 2 ) : • Z 2 p = Z Z p ∈ Z 2 p ± Ce -c• + Ce -c( √ p • / Z ) 2 in (R p , • 2 ) • Z 2 log p ∈ Z 2 log p ± Ce -c• + Ce -c( √ log p • / Z ∞) 2 in (R p , • ∞ ),
where C ≥ e and c > 0 are two numerical constants.

Example 1.2.17 (Concentration of the sample covariance). Given a matrix X ∈ M p,n , and three parameters C, q ≥ 1 and c > 0, if we suppose that X ∈ X ± 2e -• 2 /2 in (M p,n , • F ), then :

• XX T n 2 ∝ Ce -c • /γ + Ce -c(n • / X F ) 2 in (M p,n , • F ) • XX T n ∝ Ce -c • /γ + Ce -c(n • / X ) 2 in (M p,n , • ) • XX T log n ∝ C exp -c • 1+ log p log n + Ce -c( √ log n • / X ∞) 2 in (M p,n , • ∞ ),
where γ = p n , γ = γ + 1 ≥ max(γ, 1) and C ≥ e, c > 0 are two numerical constants.

As rich it could be the notion of linear concentration is insufficient when dealing with the resolvent of random matrices, starting with the resolvent of the sample covariance Q = (XX T /n+I p ) -1 . It is possible to infer the concentration of the sample covariance in (M p , • ) from the concentration of X as we saw in Example 1.2.40, we can even track the concentration of the resolvent since the inverse of a matrix of M p can be written as a polynomial of degree p, but the observable diameter will then be of diverging order. To solve these issues, one needs a stronger notion of concentration to be introduced next : the Lipschitz concentration.

Lipschitz Concentration

Theorem 0.0.3 given in the preamble provides us with the concentration of the Lipschitz and even uniformly continuous functionals of random vectors uniformly distributed on the sphere, that is to say, cases that go far beyond the linear case and that let us hope for interesting inference on the resolvent of random matrices

As firstly evoked in Lemma 1.1.3, the concentration of a random vector Z can be expressed through the concentration of any random variable f (Z) ∈ R when f is Lipschitz. As before, this approach of concentration has the asset of bringing back the concentration on any normed vector space to a mere concentration on R, that we deeply studied at the beginning of the section. The following definition allows us to generalize the notion of concentration to any metric space as presented in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF].

Definition 10 (Lipschitz Concentration of a random vector). Given a concentration function α, a random vector Z is said to be Lipschitz α-concentrated iff one of the following three assertions is verified for any 1-Lipschitz function f : E → R :

• f (Z) ∝ α, and we will note in that case Z ∝ α • f (Z) ∈ m f ± α, and we will note in that case

Z m ∝ α • f (Z) ∈ E[f (Z)]
± α, and we will note in that case

Z E ∝ α, where m f is a median of f (X).
The Lipschitz concentration is the strongest notion of concentration we will present and it is the one that received most of the interest from the scientific community; therefore, we allow ourselves to omit the term "Lipschitz" when mentioning this kind of concentration. In our paper, such Lipschitz concentration of random vectors can only be obtained through Theorem 0.0.3 or Theorem 1.2.20 below, and they are both set on the normed vector space (R p , • ) (or the analogous one (M p,n , • F ). We will thus allow ourselves to omit the precision about the normed vector space on which is made the concentration when we are on (R p , • ), on (M p,n , • F ) or when we are on the formal normed vector space (E, • ).

Remark 1.2.18. We know from Lemma 1.1.3 that Definition 10 is compatible with Definition 2 when E = R, so there are no conflicts between the different uses of the notation ∝ for random vectors and random variables.

Remark 1.2.19. Given a random vector Z ∈ E and a concentration function α, we know thanks to Lemma 1.1.2 :

Z ∝ α =⇒ Z m ∝ 2α =⇒ Z ∝ 4α(•/2).
Also, by definition of the linear concentration :

Z E ∝ α =⇒ Z ∈ EZ ± α,
and we can link this concentration to the other two thanks to Proposition 1.1.18 and Corollary 1.1.24 in the case of a q-exponential concentration :

Z m ∝ Ce (•/σ) q =⇒ Z E ∝ e C q /q e (•/2σ) q =⇒ Z m ∝ 2e C q /q e (•/4σ) q ,
for any q, σ > 0 and C ≥ e.

We thought useful to present the theorem of concentration of Gaussian vectors in our new formalism, to add this setting to the historical example of the concentration on the sphere.

Theorem 1.2.20. A canonical Gaussian vector Z is normally concentrated independently of its dimension. For any p ∈ N :

Z ∼ N (0, I p ) =⇒ Z m ∝ 2e -( • /2) 2 and Z E ∝ 2e -( • /2) 2
where N (0, I p ) is the distribution of the canonical Gaussian vectors of dimension p that have independent zero mean and unit variance Gaussian entries.

A structural proof with a geometrical approach from the Poincaré lemma tracks the concentration of Gaussian vectors from the concentration of the uniform distribution on the sphere. A more functional approach based on the log-Sobolev inequalities can be found in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF]. An alternative proof is found in [START_REF] Tao | Topics in random matrix theory[END_REF], originally proposed by Maurey and Pisier, which does not provide the optimal constants but is more efficient and simple.

Theorem 1.2.20 can be generalized to any random vector X ∈ R p with density dP X (x) = e -U (x) dλ p (x) where U : R p → R is a positive functional with the hessian bounded inferiorly by, say cI p , c > 0. In that case,

X ∝ 2e -c• 2 /2 , (see [Led01, Theorem 2.7])
Let us add for the general picture a result from Talagrand [Tal94, Theorem 2.4] (or [Led01, Proposition 4.18]) concerning the concentration of the exponential distribution, that we shall denote ν p , which is the distribution of random vectors of R p with independent entries having density 1 2 e -|•| dλ 1 . Theorem 1.2.21. [Led01, Proposition 4.18] There exist two numerical constants C ≥ 1 and c > 0, such that for any p ∈ N :

Z ∼ ν p =⇒ Z ∝ Ce -c •
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

As an example of q-exponential concentrations when q ∈ [1, 2], one may consider vectors uniformly distributed on the balls of R p , that is B • q = {x ∈ R p | x q = ( x q i ) 1/q ≤ 1}; let us note β p q this distribution. Theorem 1.2.22. [Led01, Proposition 4.21] Given q ∈ [1, 2], there exist two numerical constants C ≥ 1 and c > 0, such that for any p ∈ N :

Z ∼ β p q =⇒ Z ∝ Ce -c • q
Remark 1.2.23. The independence of the concentration of a random vector to its dimension can be interpreted as a conservation of its observable diameter through dimensionality when the actual diameter increases. This second diameter, that can be referred to as the metric diameter, can be naturally defined as the expectation of the distance between two independent random vectors drawn from the same distribution. Theorem 1.2.20 states that the observable diameter of a Gaussian distribution in R p is of order 1, that is to say 1 √ p times less than the diameter (that is of order √ p). The same result holds for the uniform distribution on the sphere of R p and for any distribution that would be called for that reason concentrated.

Definition 10 only presents the concentration of Lipschitz functionals of Z (if f is λ-Lipschitz then f /λ is 1-Lipschitz and the product with a constant is easy to manage, we find f (Z) ∝ α( • /λ)), but it is possible to show the concentration of any uniformly continuous functional of Z : Proposition 1.2.24 (Concentration of the uniformly continuous transformations). Given two normed vector spaces E and G, a random vector Z ∈ E, a concentration function α, a modulus of continuity ω, a function φ : E → G, ω-continuous, we have the implication :

Z m ∝ α =⇒ φ(Z) m ∝ α(ω -1 ( • )).
Proof. Let us introduce a 1-Lipschitz function g : G → R, we note f = g • φ.

We introduce m f , a median of f (Z) and the sets

A -= {z, f (z) ≤ m f } and A + = {z, f (z) ≥ m f } (they verify by definition P(Z ∈ A + ), P(Z ∈ A -) ≥ 1 2 ). The image through f of the boundary ∂A + = ∂A -= A + ∩A -is equal to {m f }.
Since the boundary is closed, for any z ∈ A + , there exists a sequence

z n ∈ ∂A -such that z -z n -→ n→∞ d(z, ∂A -) = d(z, A -), then since f is uniformly continuous like φ, we can bound : |f (z) -m f | = lim n→∞ |f (z) -f (z n )| ≤ lim n→∞ ω( z -z n ) ≤ ω(d(z, A -)) = ω(|d(z, A -) -d(z, A + )|),
and the same inequality is also verified for any z ∈ A -. This entails :

P (|f (Z) -m f | ≥ t) ≤ P |d(Z, A -) -d(Z, A + )| ≥ ω -1 (t) ,
and we can then conclude since f : z → d(z, A -) -d(z, A + ) is 1-Lipschitz and f (Z) admits 0 as a median.

Remark 1.2.25. Theorems 0.0.3 and 1.2.20 combined with Proposition 1.2.24 give us immediately a q-exponential concentration of all the random vectors F (Z) where F : R p → R d is uniformly continuous and Z ∼ σ p or Z ∼ N (0, I p ). This describes a wide range of random vectors that remarkably do not need to present independent entries.

As for Corollary 1.2.7, in order to show the concentration of the sum X + Y of two random vectors X, Y ∈ E, we first need to prove the concentration of the concatenation (X, Y ) ∈ E 2 . In Proposition 1.2.6, we saw how to show this result when one supposes that X and Y have q-exponential concentration. Interestingly enough, an assumption of independence was not necessary (we saw that if X and Y are identically distributed then (X, Y ) is at least concentrated as (X, X) up to a small change of the tail parameter). In the case of the Lipschitz concentration, the independence between X and Y plays an important role but still not essential as we will see in Theorem 1.2.35. We first present a way to infer the concentration of (X, Y ) when X and Y are independent and we don't make further assumptions on their concentration (the particular case of the q-exponential concentration is studied in Appendix B.4).

To get interesting inferences from the concentration of the measure theory, one has to base its initial inequalities on a theorem of the kind of Theorem 0.0.3, 1.2.20 or 1.2.21 providing distributions with an observable diameter far smaller than the metric parameter (see Remark 1.2.23 for precisions). The following proposition is just a tool that can be some help when one wants to study a limited (with regard to the dimension) concatenation of concentrated vectors. In what follows E and F are two normed vector spaces respectively equipped with the norms • E and • F . We again note • 1 the norm of E × F defined as (x, y) 1 = x E + y F . Proposition 1.2.26. Given two independent random vectors X ∈ E and Y ∈ F , if we suppose that X and Y are concentrated then (X, Y ) is also concentrated. Given two concentration functions α, β : R + → R + , and any λ ∈ (0, 1) :

X ∝ α Y ∝ β =⇒ (X, Y ) ∝ α (λ • ) + β ((1 -λ) • ) ,
If we suppose that α is invertible and piecewise differentiable, we also have the implication :

X ∝ α Y ∝ β =⇒ (X, Y ) ∝ α + β -α * β,
where * is the convolution operator (f * g(t) = R f (u)g(tu)du). Since α and β are only defined on R + , we implicitly compute the convolution with a null continuation of α and β on R -. The implications are also true if we work with concentrations around the medians (X m ∝ α) or around the means (X E ∝ α).

In the second result, be careful that, since the concentration functions are decreasing, α is a negative function.

Proof. For the proof of the first implication, refer to [Led01, Proposition 1.11]. Let us consider a 1-Lipschitz function f : E × F → R. We will work with the concentration around the means since it is easier and we will note for simplicity

Ef = E [f (X, Y )] and E [f |Y ] = E [f (X, Y ) | Y ] ; we can bound : P (|f (X, Y ) -Ef | ≥ t) ≤ E [P (|f (X, Y ) -E [f |Y ]| ≥ t -|Ef -E [f |Y ]| | Y )] ≤ E [α (t -|Ef -E [f |Y ]|)] + P (|Ef -E [f |Y ]| ≥ t) ≤ 1 0 P (α (t -|Ef -E [f |Y ]|) ≥ u) du + β(t) ≤ 1 0 P t -|Ef -E [f |Y ]| ≤ α -1 (u) du + β(t) ≤ 1 α(t) β t -α -1 (u) du + α(t) + β(t) = 0 t α (u)β (t -u) du + α(t) + β(t).
In the first result of Proposition 1.2.26, λ is often chosen to be equal to 1 2 as in Lemma 1.1.5 for instance. However, we allow ourselves to choose small values of λ when we want to maintain almost untouched a concentration as will be done in the following useful example that allows to transmit the absolute continuity of the Gaussian distribution to any random vector, while, at the same time, preserving the concentration (see Theorem 1.2.35 for an effective use).

Example 1.2.27. Given an integer p > 0, a concentration function α, an αconcentrated random vector X ∈ R p , and an independent random vector U ∈ R p verifying 1 √ p-2 U ∼ σ p-1 or U ∼ N (0, I p ), we have the concentration :

X + 1 n U ∝ α 1 + 1 √ n • + 2e -n • 2 /2 .
Remark 1.2.28. The two results of Proposition 1.2.26 can be compared if we consider a generalization of the notion of observable diameters, as defined for the exponential concentration before Lemma 1.2.8, and that is slightly different from the observable diameter introduced by Gromov in [Gro99, Chapter 3.1/2]. Still, it is of the same order when the dimension is large. Given a concentration function α, we note R α = ∞ 0 α, and for any random vector X the observable diameter R X is defined as R X = inf{R α | X ∝ α}. Our definition comes from the fact that if, say, X ∝ α, then for any 1-Lipschitz function f and any independent copy X :

E [|f (X) -f (X )|] = ∞ 0 P (|f (X) -f (X )| ≥ t) dt ≤ ∞ 0 α = R α .
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

With the first result given by Proposition 1.2.26, we find :

R (X,Y ) ≤ R X 1 -λ + R Y λ ,
and with the second result :

R (X,Y ) ≤ R X + 2R Y ,
since for any differentiable concentration functions α, β :

∞ 0 α * β = +∞ -∞ α * β = +∞ -∞ α +∞ -∞ β = -α(0)R β .
The second inequality is clearly better than the first one, however we are far from the stability of the observable diameter that we find in Theorems 0.0.3 and 1.2.20.

One can assert easily that the concentration could be generalized to nonindependent random vectors since we know for instance that (X, f (X)) is concentrated as a 2-Lipschitz transformation of X when f : E → E is 1-Lipschitz. However, there exists a lot of examples where (X, Y ) is far from being concentrated despite X and Y being concentrated.

√ n X + = Y 2 √ n P(X + Y = 0) = 1 2 Fig 1.
The sum of two concentrated random vectors can be non concentrated

Example 1.2.29. Given p ≥ 0, let us consider a random vector Y ∼ σ p . We define the random vector X as being equal to Y on

√ p S p + = √ p S p ∩ (R + × R p )
and equal to -Y on

√ p S p -= √ p S p ∩ (R -× R p ). Note that X ∼ σ p ∼ 21 √ pS p + σ p and Y are both 2e -• 2 /2 -concentrated (see Theorem 0.0.3) and therefore R X ≤ R Y ≤ R Y ≤ ∞ 0 2e -t 2 /2 dt = √ 2π.
As we see on the schematic Figure 1, the distribution of X + Y is completely different from the distribution of X and Y since it is discontinuous. If one looks at the variations of the random variable X + Y that is a 1-Lipschitz functional of (X, Y ), one notes that 0 is a median of X + Y and we have :

P ( X + Y ≥ t) =          1 if t = 0 1 2 if t ∈ 0, 2p 0 if t > 2p.
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

Therefore, with the notation of the observable diameter we introduced in Remark 1.2.28, we see that :

R (X,Y ) ≥ R (X+Y = ∞ 0 P ( X + Y ≥ t) dt = p 2 > 4 √ 2π ≥ 2(R X + R Y )
For p sufficiently large, it contradicts the inequalities given in Remark 1.2.28 and we see in particular that the random vector (X, Y ) has an observable diameter of the same order as the metric diameter which is of order √ p. The vector (X, Y )

is not concentrated in the sense given by Remark 1.2.23.

In this example, X was chosen in a way that its relationship with Y changes dramatically through the plane {0}×R p : there is what we shall call an unlimited defiance of X towards Y . To be able to infer concentration properties on (X, Y ) from the concentration of X and Y one needs to limit this defiance under a modulus of continuity in a way defined below.

Definition 11. [Defiance between random vectors] Given two random variables

X ∈ E and Y ∈ F , and a continuity modulus ω : R + → R + , one says that X defies Y under w iff for any 1-Lipschitz function f : E → R, any t ∈ R and any y 1 , y 2 ∈ F :

P (f (X) ≥ t | Y = y 1 ) ≤ P (f (X) ≥ t -ω( y 1 -y 2 ) | Y = y 2 )
If there exist two parameters λ > 0 and ν ∈ (0, 1] such that ∀t > 0, ω(t) = λt ν , one says that X (λ, ν)-Hölder defies Y and if ν = 1, one says that X λ-Lipschitz defies Y .

We give some basic examples of the notion of defiance in the next lemma.

Lemma 1.2.30. Let us consider four normed vector spaces E, F, G, H, three random vectors X ∈ E, Y ∈ F , Z ∈ G, two continuity modulus ω, ε : R + → R + ; a ω-continuous transformation φ : F → E, a transformation ψ : E×G → H that we suppose to be ω-continuous on the first variable (i.e. ∀z ∈ G : x → ψ(x, z) is ω-continuous) :

• if Z and Y are independent then Z defies Y under 0 • φ(Y ) defies Y under ω • if X defies Y under ε then ψ(X, Z) defies Y under ω • ε.
Example 1.2.31. For ω = 0, the defiance under ω (and in particular the 1-Lipschitz defiance) is a non symmetric relation. For instance if we consider a random variable X ∈ [-1, 1], say, uniformly distributed, we know that Y = max(X, 0) 1-defies X but it is not possible to find a modulus of continuity ω such that X would defy Y under ω. Indeed, if we suppose that such a modulus of continuity exists, we would have for any t > 0 :

1 ≤ P (X ≥ t | Y = t) ≤ P (X ≥ t -ω(t) | Y = 0) ,
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 and since P (X ≥ tω(t) | Y = 0) is null if ω(t) ≤ t and equal to ω(t) -t otherwise, it is necessary that : ∀t > 0 : ω(t) ≥ t + 1, therefore, ω is clearly not continuous at 0. However, the defiance under 0 is a symmetric relation equivalent to the relation of independence.

Proposition 1.2.32. Given two random vectors X and Y : X defies Y under 0 ⇔ Y defies X under 0 ⇔ X and Y are independent.

In Definition 11, it is possible to integrate the inequality on y 2 to get a necessary condition for defiance that might help the understanding of the notion. Lemma 1.2.33. Given two random vectors X ∈ E and Y ∈ F , and a modulus of continuity ω, if we suppose that X defies Y under ω, then for any y ∈ F and > 0 :

P (f (X) ≥ t | Y = y) ≤ P (f (X) ≥ t + ω(s) | Y ∈ B s )
The last point of Lemma 1.2.30 gave us an easy way to build couples (X, Y ) of defiant random vectors from two independent random vectors (X, Z). However, recalling that our goal is to show the concentration of (X, Y ), the example X = φ(Y, Z) with φ ω-continuous is easy to treat since (φ(Y, Z), Y ) is a 2ωcontinuous transformation of the vector (Y, Z) that is concentrated when Y and Z are concentrated thanks to Proposition 1.2.26. To let the reader imagine other kinds of defiant vectors, we present an example of simple uniform distribution in R 2 that could possibly be expressed as the ω-continuous transformation φ(U, V ) of two independent random variables U, V but whose defiance can be shown straightforwardly, without Lemma 1.2.30.

Example 1.2.34. Let us consider the random vector (X, Y ) ∈ R 2 following the uniform distribution on the set {(x, y) ∈ R 2 + | x 2 + y 2 ≤ 1}. We are going to show that X ( √ 2, 1 2 )-Hölder defies Y and for the same reason, since X and Y play symmetric roles, Y ( √ 2, 1 2 )-Hölder defies X. Let us consider y 1 , y 2 > 0, a 1-Lipschitz function f : R → R and a threshold t > 0; we want to bound

P (f (X) ≥ t | Y = y 2 ) with P f (X) ≥ t - √ 2 |y 1 -y 2 | 1 2 | Y = y 1 and we note for simplicity w = √ 2 |y 1 -y 2 | 1 2
and for any y ∈ [0, 1], r y = 1 -y 2 . If y 1 ≥ y 2 , it is easy to see that :

P (f (X) ≥ t | Y = y 2 ) ≤ P (f (X) ≥ t | Y = y 1 ) ≤ P (f (X) ≥ t -w | Y = y 1 ) If y 1 ≤ y 2 , if P (f (X) ≥ t -w | Y = y 1
) is equal to 1, there is nothing to show, we can thus suppose that it is strictly lower than 1. For any x ∈ [0, r y1 ] verifying f (x) < tw, ∀u ∈ [-w, w] :

f (x + u) ≤ f (x + u) -f (x) + f (x) < u + t -w < t, X f (X) Y 1 0 y r y t Fig 2.
An example of ( √ 2, 1 2 )-Hölder defiance. In shaded grey on the right, the uniform distribution on the disk quarter ; on the left of the figure, the graph of a given 1-Lipschitz function f . The red vertical lines on the right of the figure represent the set {f (X) ≥ t, Y = y}. Keep in mind that due to the Lipschitz character of f , when t is shifted by w > 0, the red horizontal dotted boundaries are shifted at least by w. For any

y 1 , y 2 , t ∈ R, P(f (X) ≥ t | Y = y 1 ) ≤ P(f (X) ≥ t - √ 2|y 1 -y 2 | 1/2 | Y = y 2
), the inequality is the tightest when 1 > y 2 ≥ y 1 and when y 1 is close to 1. since f is 1-Lipschitz. Therefore {f < t-w} w ⊂ {f < t} (where A w = {y | ∃x ∈ A, xy ≤ w} is the closed neighborhood of order w of A) and we have the inequality :

ry 1 0 1 f (x)≥t dx + w ≤ ry 1 0 1 f (x)≥t-w dx < 1.
With our hypothesis, r y2 ≤ r y1 , we can then bound :

P (f (X) ≥ t -w | Y = y 1 ) = 1 r y1 ry 1 0 1 f (x)≥t-w dx ≥ 1 r y1 ry 2 0 1 f (x)≥t dx + w r y1 ≥ P (f (X) ≥ t | Y = y 2 ) - r y1 -r y2 r y1 ry 2 0 1 f (x)≥t dx r y2 + w r y1 ≥ P (f (X) ≥ t | Y = y 2 ) + w -(r y1 -r y2 ) r y1 .
Eventually, with the basic inequalities :

r y1 -r y2 = 1 -y 2 1 -1 -y 2 2 ≤ y 2 1 -y 2 2 ≤ 2(y 1 -y 2 ) = w,
we can conclude that X ( √ 2, 1 2 )-Hölder defies Y . Now that we gave some insights into the notion of defiance, we can enunciate our theorem.

Theorem 1.2.35. Given two integers p, q ∈ N and two random vectors (X, Y ) ∈ R p × R q , if we suppose that they are both concentrated, and that X defies Y under a modulus of continuity ω, then the concatenation (X, Y ) is also concentrated in (R p+q , • 1 ), where (x, y) 1 = x 2 + y 2 . More precisely, given two concentration functions α, β, we suppose that X ∝ α and Y ∝ β and we note t 0 > 0 verifying α(t 0 ), β(t 0 ) < 1 -1 √ 2 . Then, with the shifting operator τ t0 introduced in the context of Lemma 1.1.1, we have the implication :

X ∝ α Y ∝ β =⇒ (X, Y ) ∝ τ 2t0 • 2 α • (1 + ω) -1 (•/2) + β(•/2) ,
where (1 + ω) -1 is the pseudo inverse of 1 + w.

Since for any (x, y) ∈ R p × R q , (x, y) 1 ≤ √ 2 (x, y) 2 , we can adapt the result of Theorem 1.2.35 to a mere concentration in R p+q endowed with the Euclidean norm just with a slight modification of the concentration function.

The translation coefficient t 0 appearing in the result arises from the expression of the concentrations around quantiles on which the proof of Theorem 1.2.35 relies. Given a random variable Z, and a parameter θ > 0, we use the notation q Z θ to designate a θ-quantile of Z that verifies by definition P Z ≥ q Z θ ≥ 1 -θ and P Z ≤ q Z θ ≥ θ. Of course there can be several quantiles; we then suppose that the assertions that contains the notation q Z θ are true for all the θ-quantiles of Z. Assuming that a random variable Z is concentrated, it is possible to express the behavior around a quantile. Lemma 1.2.36 ([Led01, Lemma 1.1]). Given a random variable Z, a median m Z of Z, a concentration function α : R + → R + and a threshold θ ∈ (0, 1), we have the implication :

Z ∈ m Z ± α =⇒ Z ∈ q Z θ ± τ t θ • α,
where t θ verifies α(t θ ) < min(θ, 1 -θ) and τ t θ is the translation operator defined before Lemma 1.1.1.

Proof. By definition of the quantile q Z θ , we know that |m Z -q Z θ | ≤ t θ , since the concentration of Z implies when t = t θ :

P (Z ≤ m Z -t θ ) ≤ α(t θ ) < θ P (Z ≥ m Z + t θ ) ≤ α(t θ ) < 1 -θ =⇒ m Z -t θ ≤ q Z θ m Z + t θ ≥ q Z θ .
We can then conclude thanks to Lemma 1.1.1.

Note that if we only suppose α(t θ ) ≤ θ, then we cannot infer any behavior around a quantile because there can be plenty of them and the inequality P (Z ≤ m Z -t θ ) ≤ θ does not entail anything remarkable.

Proof of Theorem 1.2.35. In the proof we need the uniqueness of the quantiles and of the median; we will thus first suppose that the Lebesgue measure λ R p+q is absolutely continuous with respect to µ (X,Y ) , the distribution of (X, Y ), which is classically written as λ R p+q µ (X,Y ) and means that for any Borel set A ⊂ R p+q :

P ((X, Y ) ∈ A) = 0 =⇒ λ R p+q (A) = 0.
That allows us to say that any 1-Lipschitz function f : E × F → R and any a, b ∈ R such that a < b :

P (f (X, Y ) ≤ a) > 0 P (f (X, Y ) ≥ b) > 0 =⇒ P (a ≤ f (X, Y ) ≤ b) > 0.
Indeed, if we suppose that the left assertions are true, then taking We then see that if θ ∈ (0, 1), the θ quantile q f (X,Y ) θ is unique, in particular we note m f the median of f (X, Y ).

(
Let us introduce a parameter θ t ∈ (0, 1) that we will precise later and shall be considered as increasing with t. We start with the decomposition :

P (f (X, Y ) ≥ m f + t) = P (f (x, Y ) ≥ m f + t | X = x) dP(X = x). (11)
It is then tempting to employ Markov-like inequality distinguishing the drawings x of X where P (f (x, Y ) ≥ m f + t | X = x) > 1 -θ t from the others. It is possible to simplify the expression of the two cases noting that for any x ∈ R p :

P (f (x, Y ) ≥ m f + t | X = x) > 1 -θ t =⇒ q x θt > m f + t,
where

q x θt = q f (x,Y ) |X=x θt
is the θ t -quantile of the random variable f (x, Y ) | X = x. We get the inequality :

P (f (X, Y ) ≥ m f + t) < P q X θt > m f + t + 1 -P q X θt > m f + t (1 -θ t ) = P q X θt > m f + t θ t + (1 -θ t ).
Now, to find a lower bound of P q X θt > m f + t , let us first consider the case t = 0 and for that purpose we employ again the decomposition (11) :

1 2 = P (f (X, Y ) > m f ) > P q X θ0 > m f (1 -θ 0 ) .
That leads to the inequality :

P q X θ0 > m f < 1 2(1 -θ 0 ) .
As suggested in the hypothesis of the proposition, it appears natural to introduce

θ 0 = 1 -1/ √ 2 because in that case 1 -θ 0 = 1/2(1 -θ 0 )
and by definition of the quantile, we directly see that m f > q q X θ 0 θ0 . We could have chosen for θ 0 any value in ( 1 2 , 1), but the present choice symmetries and somehow optimizes the concentration -if α = β. Here be careful that due to our choice of notation, q X θ0 is a random variable depending on X and q q X θ 0 θ0 is a constant. When t > 0, the inequality m f > q q X θ 0 θ0 directly implies :

P q X θt > m f + t ≤ P q X θt > q q X θ 0 θ0 + t .
It is interesting to bound the random variable q X θt with q X θ0 to let appear a concentration inequality involving a random variable q X θ0 with its quantile q q X θ 0 θ0 as in Lemma 1.2.36. For that purpose, considering the parameter t 0 introduced in the proposition, we set θ t+2t0 = 1 -β( t 2 ). With that choice of θ t , thanks to Lemma 1.2.36, we know that for any t > 0 and x ∈ R :

P f (x, Y ) ≥ q x θ0 + t 0 + t ≤ β (t) = 1 -θ 2(t+t0) ,
thus ∀t > 0, q x θ0 + t + t 0 ≥ q x θ 2(t+t 0 ) . That entails :

P q X θt+2t 0 > m f + t + 2t 0 ≤ P q X θ0 > q q X θ 0 θ0 + t 2 + t 0 ≤ α • (1 + ω) -1 t 2 .
The last inequality was obtained with Lemma 1.2.36. Indeed, the function x → q x θ0 is (1 + ω)-continuous, given x 1 , x 2 ∈ E :

θ 0 ≤ P f (x 1 , Y ) ≤ q x1 θ0 | X = x 1 ≤ P f (x 2 , Y ) ≤ f (x 1 , Y ) -f (x 2 , Y ) + q x1 θ0 | X = x 1 ≤ P f (x 2 , Y ) ≤ x 2 -x 1 E + q x1 θ0 | X = x 1 ≤ P f (x 2 , Y ) ≤ (1 + ω) ( x 2 -x 1 E ) + q x1 θ0 | X = x 2 , thus (1 + ω) ( x 2 -x 1 E ) + q x1 θ0 ≥ q x2
θ0 and we get the same way the inequality

q x1 θ0 -q x2 θ0 ≤ (1 + ω) ( x 2 -x 1 E ).
Combining our results all together, we can bound :

P (f (X, Y ) ≥ m f + t + 2t 0 ) ≤ 1 -β t 2 α • (1 + ω) -1 t 2 + β t 2 ,
and we get the same bound for the probability P (f (X, Y ) ≤ m f -t -2t 0 ) that eventually gives us the result of the proposition in the case where the distribution of (X, Y ) controls the Lebesgue measure.

In the general case we can approximate (X, Y ) with a sequence of random vectors (X n , Y n ) verifying λ R p+q µ (Xn,Yn) ∀n ∈ N. For that purpose, let us introduce U, V two independent Gaussian random vectors verifying U ∼ N (0, I p )) and V ∼ N (0, I q ) and respectively independent to X and Y . We know from Example 1.2.27 that

       X n = X + 1 n U m ∝ α n where α n (t) = α 1 + 1 √ n t + 2e -nt 2 /2 , Y n = Y + 1 n V m ∝ β n where β n (t) = β 1 + 1 √ n t + 2e -nt 2 /2 ,
and we know that λ R p+q is absolutely continuous under µ (Xn,Yn) . Let us consider a 1-Lipschitz function g : R p+q → R. We note m n the median of g(X n , Y n ),

m + = sup{m, P (g(X, Y ) ≥ m) ≥ 1 2 } and m -= inf{m, P (g(X, Y ) ≤ m) ≥ 1 2 }.
For any ε > 0, there exists δ > 0, such that we can bound :

1 2 + δ ≤ P (g(X, Y ) ≤ m + + ε) ≤ P g(X n , Y n ) - 1 n (U, V ) ≥ m + + ε ≤ P (g(X n , Y n ) ≥ m + + 2ε) + P 1 n (U, V ) ≥ ε .
and if n is large enough, we know from Proposition 1.2.10 (and Proposition 1.2.26 : (U, V ) is concentrated since U and V are independent and concentrated) that P 1 n (U, V ) ≥ ε tends to 0 when n tends to infinity. Therefore we obtain for n large enough the inequality 1 2 ≤ P (g(X n , Y n ) ≥ m -) that directly entails m + +2ε ≤ m n . With similar considerations, we show that the sequence (m n ) n∈N belongs to [m --2ε, m + + 2ε] for all n large; then, replacing ε by the elements of a sequence ε n tending to zero, we can extract a subsequence of (m n ) n∈N that we will still abusively note (m n ) n∈N and that converges to a real value m g ∈ [m -, m + ]. The limit m g we obtain is then clearly a median of g(X, Y ). The hypothesis of Proposition 1.1.12 :

• m n tends to m g • g(X n , Y n ) tends in law to g(X, Y ) • τ 2t0 • 2 α n • (1 + ω) -1 (•/2) + β n (•/2) point-wise converges to γ = τ 2t0 • 2 α • (1 + ω) -1 (•/2) + β(•/2)
are verified, we can thus conclude that (X, Y ) m ∝ γ.

In the case of exponential concentration, we can employ Lemma 1.1.16 to get the simple corollary : Corollary 1.2.37. Given two random vectors X, Y ∈ E and three parameters C ≥ e, σ, q > 0, we have the implication :

X, Y m ∝ Ce -(•/σ) q =⇒ (X, Y ) m ∝ 4Ce -(•/4σ) q .
We can then express the concentration of a sum of two exponentially concentrated random vectors : Corollary 1.2.38. In the setting of Corollary 1.2.37 :

X, Y m ∝ Ce -(•/σ) q =⇒ X + Y m ∝ 4Ce -(•/4σ) q .
If we now consider that X and Y are two vectors of an algebra A endowed with an algebra norm • (verifying XY ≤ X Y ), we can express the concentration of the product XY thanks to Lemma 1.1.8. We present the result in the case of exponential concentration for which the expression is simple, but the proof could be adapted to any other type of concentration function.

Proposition 1.2.39 (Concentration of the vector product). Given two independent random vectors X, Y ∈ A, and three parameters, q ≥ 1, C ≥ e and σ > 0, if X, Y m ∝ Ce -(•/σ) q , then noting X, Ỹ , some deterministic equivalents of respectively X and Y , we have :

(X -X)(Y -Ỹ ) ∝ C 1 e -(•/c1σ 2 η 1/q • ) q + C 2 e -(•/c2σ 2 ) q/2 ,
where C 1 , c 1 , C 2 , c 2 ≥ 1 are four numerical constants depending only on C and η • is the degree of the norm • , presented in Definition 9.

Of course if one (or both) of the random vectors X and Y has a bounded norm, then the concentration is tighter.

Proof. Let us suppose for simplicity that X = Ỹ = 0. Noting m X and m Y , the median of respectively X and Y , we know from Corollary 1.2.14 that

m X , m Y ≤ C ση 1/q • ,
for some numerical constant C ≥ e proportional to C. We note η = C ση

1/q • > 0.
Considering a 1-Lipschitz function f : A → R, we are going to show that f (XY ) is concentrated as the product of two concentrated random variables

Z 1 = X + Y +η and Z 2 = f (XY ) X + Y +η . First, we know from Proposition 1.1.5 that Z 1 ∝ η + m X + m Y ± 2Ce -(•/2σ) q . Second, Proposition B.4.1 gives us the concentration (X, Y ) m ∝ 4Ce -(•/4σ
) q , and we want thus to show that the map g : (x, y) → f (x,y)

x + y +η is Lipschitz. Given (h, k) ∈ A 2 such that h , k ≤ η 2 , let us bound :

|g(x + h, y + k) -g(x, y)| ≤ x -x + h + y -y + k ( x + h + y + k + η)( x + y + η) |f (xy)| + |f ((x + h)(y + k)) -f (xy)| x + y + η ≤ ( h + k ) |f (xy)| x y + 2( h + k ).
Let us suppose without loss of generality that f (0) = 0; the Lipschitz character of f gives us the inequality :

f (xy) ≤ xy ≤ x y .
Therefore g is 2-Lipschitz and we know from Proposition 1.1.9 that there exist two medians m Z1 and m Z2 of respectively Z 1 and Z 2 such that :

f (XY ) = Z 1 Z 2 ∈ m Z1 m Z2 ± Ce -(•/4σ|m Z 2 |) q + 4Ce -(•/16σm Z 1 ) q + Ce -(•/2σ 2 ) q/2 .
That allows us to conclude since m Z1 ≤ 2η and besides, f (xy)

x + y +η ≤ max( x + y ) 2 , and thus m Z2 ≤ η.

Example 1.2.40. We give as in Examples 1.2.16 and 1.2.17 some results for the product in R p and the matricial product in M pn . Therefore we consider a random vector Z ∈ R p and a random matrix X ∈ M pn verifying Z, X ∝ 2e -(•/2) 2 for the Euclidean norm (the Frobenius norm in M pn ) and such that E[Z] = 0 and E[X] = 0 :

• Z 2 √ p = Z Z √ p ∝ Ce -c• 2 + Ce -cp 1/4 • in (R p , • 2 ) • Z 2 √ log p ∝ Ce -c• 2 + Ce -c(log p) 1/4 • in (R p , • ∞ ) • XX T n ∝ Ce -c( •/ √ γ) 2 + Ce -cn•/σ 2 in (M p,n , • F ) • XX T √ n ∝ Ce -c( •/ √ γ) 2 + Ce -c √ n•/σ 2 in (M p,n , • ) • XX T √ log n ∝ C exp -c • 2 1+ log p log n + Ce -c √ log n• in (M p,n , • ∞ ),
where γ = p n , γ = γ + 1 ≥ max(γ, 1) and C ≥ 1 and c > 0 are two numerical constants. One can note in these examples that the Lipschitz concentration preserves the concentration rates better than the linear concentration through the product of random vectors.

Let us pursue our study of the concentration in algebras with the concentration of the power of a random vector as in Proposition B.3.1.

Proposition 1.2.41. Given an integer m ≥ 2, a random vector Z ∈ A and two parameters C ≥ e and σ > 0, if Z ∝ Ce -(•/σ) q , there exist two numerical constants C ≥ e and c > 0 depending on C, q and m such that :

Z m ∝ C exp -c • σE[ Z ] m-1 q + C e -c(•/σ m ) q m + C e -c(•/σ) q .
Remark 1.2.42. If one compares Proposition 1.2.41 with Proposition B.3.1 that gives the linear concentration of Z m when Z is linearly concentrated, one sees that the Lipschitz concentration is more respectful to the power of random vectors since the observable diameter of Z m is η 1/q • smaller (for any m ≥ 2) in the case of Lipschitz concentration. To be more precise, with the notations of the propositions and in the case where EZ ∼ ση 1/q • , the leading tail parameter in the combination of exponential concentrations is σ m η m/q • for linear concentration and σ m η (m-1)/q • for Lipschitz concentrations.

Proof. Given a 1-Lipschitz function f : A → A, we decompose as in Proposition 1.2.39 the functional f (Z m ) into the product of two random variables,

Z 1 = (η + Z ) m where η = E[ Z ]
plays the same role as before and Z 2 = f (Z m )/Z 1 = g(Z). We know from Proposition 1.1.10 that :

Z 1 ∈ (2E[ Z ]) m ± C exp - • 2 2m-1 σE[ Z ] m-1 q + Ce -(•/2σ m ) q/m ,
We are just left to show that g is Lipschitz. Let us consider a parameter ε > 0 that will tend to zero and two vectors x, h ∈ A * such that h ≤ ((1 + ε) 1/m -1) x ), we know that ∀l ≤ m, x + h l ≤ (1 + ) x l and we have :

|g(x + h) -g(x)| ≤ x + h m -x m ( x + h + η) m ( x + η) m |f ((x + h) m )| + |f (x m ) -f ((x + h) m )| ( x + η) m ≤ h ( x m + x m-2 x + h + . . . + x + h m ) ( x + η) m |f ((x + h) m )| ( x + h + η) m + x + h m -x m ( x + η) m ≤ (1 + ε) 2m η h .
As before we suppose, without loss of generality, that f (0) = 0 and therefore that ∀x ∈ A, f (x) ≤ x . Of course, the same inequality holds if x = 0 and h ∈ A is chosen arbitrarily. Therefore, letting ε tend to 0, one sees that g is 2m η -Lipschitz and

Z 2 = g(Z) ∈ E[Z 2 ] ± Ce -(η•/2mσ) 1/q . Besides, knowing that Z 2 ≤ 1, we can deduce the concentration of f (Z m ) = Z 1 Z 2 thanks to Lemma 1.1.8 : f (Z m ) ∈ EZ 1 EZ 2 ± 2C exp - •/2 2m σE[ Z ] m-1 q + Ce -(•/4σ m ) q m + Ce -(•/8mσ) q .
In the preamble, we presented the resolvent as the convenient object that one wants to study to get some insight into the spectrum of the sample covariance of a concentrated random vector. Given a matrix X ∈ M p,n and a positive real number z > 0, recall that the resolvent Q S of the sample covariance matrix S = 1 n XX T is defined as :

Q S (z) = XX T /n + zI p -1 .
We will simply note it Q to lighten the notations. Following Example 1.2.40, it is possible to show that the resolvent is concentrated with the same observable diameter as S (and X). However, it is possible to get a better concentration rate if we take advantage of the fact that Q is a 2 √ z 3 n -Lipschitz transformation of X; we gain this way a factor of order √ n in the concentration that will be vital in Section 2. This suggests why the resolvent is so efficient for the study of the spectral distribution of S.

Proposition 1.2.43. Given z > 0, a random matrix X ∈ M p,n and a concentration function α, we have the implication :

X ∝ α =⇒ Q = 1 n XX T + zI p -1 ∝ α √ nz 3 2 • .
In particular :

X E ∝ α =⇒ Q ∈ E[Q] ± α √ nz 3 2 • .
We need a preliminary lemma before giving the proof to control the Frobenius norm of a product : Lemma 1.2.44. Given A ∈ M pn and B ∈ M np , one has the bound :

AB F ≤ A B F and AB F ≤ A F B .
One must be careful that in most cases AB F = BA F , which is why we need to display both inequalities. Recall in passing that the Cauchy-Schwarz inequality gives us directly AB F ≤ A F B F .

Proof. Lemma 1.2.44 is just a consequence of the computations :

AB 2 F ≤ p j=1 AB •,j 2 2 ≤ A 2 p j=1 B •,j 2 2 ≤ A 2 B 2 F .
The role of A and B could be inverted in the calculus without any problem.

Proof of Proposition 1.2.43. The function φ : M p,n → M p defined as φ(R) = RR T + zI p -1 is 2/z 3/2 -Lipschitz. Indeed, given R, H ∈ M 2 p,n :

φ(R + H) -φ(R) = (R + H)(R + H) T + zI p -1 -RR T + zI p -1 = φ(R + H) (R + H)H + HR T φ(R).
Thus φ(R + H) -φ(R) ≤ 2 H F /z 3/2 because the Frobenius norm controls the spectral one and because of the basic result

φ(R)R ≤ 1/ √ z and φ(R) ≤ 1 z enunciated in Lemma 0.0.2 in the preamble. Now, since Q(z) = φ(X/ √ n),
we recover directly the result of the proposition thanks to the hypothesis on X.

The second implication is just a consequence of Remark 1.2.19.

If we try to characterize geometrically, and roughly speaking, the range of random vectors concerned by Theorem 0.0.3, we would describe the set of respectful modifications of the sphere where bounded dilatations or the removals of some parts are tolerated but any cut is forbidden (we have about the same statement considering Theorem 1.2.20). This represents already a good range of distributions but one might be interested in representing discrete or at least "discontinuous" distributions.

Convex Concentration

With a combinatorial approach, Talagrand showed in the nineties that it is possible to find a weaker notion of concentration to apprehend the concentration of partly discrete distributions. In these cases, to be concentrated the "observation" not only needs to be Lipschitz but also to be quasiconvex, in the sense of the following definition.

Definition 12 (Quasiconvexity). A function f : E → R is said to be quasicon- vex if for any real t ∈ R, the set {z ∈ E : f (z) ≤ t} = {f ≤ t} is convex.
Remark 1.2.45. Quasiconvexity concerns of course convex functions, but also any monotonous function supported on R. More generally, given a convex function f and a non decreasing function g, the composition g • f is quasiconvex.

The class of quasiconvex functions is rather interesting in the sense that it is wider than the class of merely convex functions but still verifies the property of the uniqueness of the minimum.

Definition 13 (Convex concentration). Given a random vector Z ∈ (E, • ) and a concentration function α, we say that Z is convexly α-concentrated if one of the three assertions is verified for any 1-Lipschitz and quasiconvex function f : E → R :

• f (Z) ∝ α, and we will note in that case Z ∝ c α • f (Z) ∈ m f ± α, and we will note in that case

Z m ∝ c α • f (Z) ∈ E[f (Z)]
± α, and we will note in that case

Z E ∝ c α,
where m f is a median of f (X).

Remark 1.2.46. It is clear that the concentration of Definition 10 implies the convex concentration of Definition 13. Those two notions are equivalent when E = R since they are then both equivalent to Definition 2.

Once again, when non ambiguous, we will omit the precision "in (E, • )". We clearly have the implication :

Z ∝ α =⇒ Z ∝ c α.
In the case of a q-exponential concentration, we have the implication chain :

Z E ∝ Ce -( • /σ) q =⇒ Z E ∝ c Ce -( • /σ) q =⇒ Z ∈ EZ ± e -( • /σ) q .
The fundamental example that alone justifies the interest in convex concentration is owed to Talagrand and provides to our study a supplementary setting to the "smooth" scenarios given by Theorems 0.0.3 and 1.2.20.

Theorem 1.2.47 (Convex concentration of the product of bounded distributions, [Tal95, Theorem 4.1.1]). Given a random vector Z ∈ [0, 1] m , m ∈ N, with independent entries :

Z m ∝ c 4e -• 2 /4 .
Considering the example of the preamble, we are tempted to look for a similar theorem where the sets [0, 1] are compact sets of R p bounded by K and m is taken to be equal to n. It is not so interesting however, the issue being that the factor K that would appear in the tail parameter would jeopardize most of the applications since it should be of order 1 while Z i is often of order √ p when Z i ∈ R p . This can however find some use when considering sparse random vectors.

The interesting setting is the case where E = R, and m = pn. Then we do not exactly consider the concentration on R np but the concentration on M p,n (endowed with the Frobenius norm). Theorem 1.2.47 gives us in that case a convenient tool to build convexly q-exponentially concentrated random matrices. In that case, the bound |Z i | ≤ K on the entries of a random vector Z is no more an unreachable hypothesis for applications; however we will need in that case an independence between the entries.

Theorems 0.0.3 and 1.2.20 allow us to track easily concentration properties from a vector Z ∈ R p verifying Z ∼ σ p-1 or Z ∼ N (0, I p ) to any Lipschitz transformation and even to any uniformly continuous transformation f (Z) ∈ R q . Theorem 1.2.47 is not so easy to generalize because the convexity (or the quasiconvexity) of a function is only defined for real-valued functions; indeed, most of the transformations between two vector spaces ruin the subtle structure of convexity. We can still slightly relax the hypothesis of independence in the theorem of Talagrand thanks to affine transformations : Lemma 1.2.48. Given two vector spaces E, F and a quasiconvex (resp., convex) function f : E → R, for any affine function g : F → E, the composition f • g is also quasiconvex (resp., convex).

Remark 1.2.49. Given two convexly concentrated random vectors X, Y ∈ E, it is not possible to adapt the proof of Proposition 1.2.35 to the convex case to show the concentration of (X, Y ). For convex concentration, the independence between X and Y appears as a crucial element to deduce from a concentration on X and Y a concentration on (X, Y ). We advice again the reader to take a look at Proposition B.4.1 in Appendix B.4 to see how to express the convex concentration of (Z 1 , . . . , Z p ) when Z 1 , . . . , Z p are all q-exponentially convexly concentrated. This result is the same for Lipschitz and convex concentration.

We can give a supplementary useful proposition that will allow us to keep the properties of convex concentration when thresholding a random vector. But before let us give an immediate preliminary lemma. We present it without proof since it is a direct consequence of Lemma 1.1.19. Lemma 1.2.50. Given a random vector Z, an exponent q > 0 and two positive constants C ≥ e and σ > 0, if we note m Z a median of Z , we have the implication :

Z m ∝ c Ce -( • /σ) q =⇒ ∀t ≥ 2m Z P ( Z ≥ t) ≤ Ce -(t/2σ) q .
The lemma displays a slight modification of the concentration constants, with here the behavior of the tail only beyond 2E Z . The next proposition allows us to say that the concentration of a q-exponentially convexly concentrated random vector occurs under a threshold of order 2m Z .

Proposition 1.2.51. Given a random vector Z ∈ E a constant K ≥ 2m Z , we introduce the vector Z = min(1, K Z )Z. If there exist an exponent q > 0 and two parameters C ≥ e and σ > 0 such that

Z m ∝ c Ce -( • /σ) q then Z ∝ c 4Ce -( • /4σ) q . If Z ∝ Ce -( • /σ) q , it
is possible to see Z as a 1-Lipschitz transformation of Z that would be naturally concentrated. However the hypothesis of quasiconvexity of the functionals f ( Z) required by the convex concentration cannot be extrapolated so simply.

Proof. Let us consider a function f : E → R quasiconvex and 1-Lipschitz. We know from Proposition 1.1.2 that Z ∝ c 2Ce -( • /2σ) q , thus introducing Z , an independent copy of Z, we can bound :

P f ( Z) -f ( Z ) ≥ t ≤ P f ( Z) -f ( Z ) ≥ t, Z ≤ K and Z ≤ K + P f ( Z) -f ( Z ) ≥ t, Z > K or Z > K ≤ P (|f (Z) -f (Z )| ≥ t) + P ( Z > K or Z > K) ≤ 2Ce -(t/2σ) q + 2Ce -(K/2σ) q .
The last inequality results from the hypothesis on Z and f and Lemma 1.2.50. By construction Z , Z ≤ K, thus Z -Z ≤ 2K and f being 1-Lipschitz :

if t > 2K, P f ( Z) -f ( Z ) ≥ t ≤ P Z -Z ≥ 2K = 0.
Now, for any t ≤ 2K :

exp - K 2σ q ≤ exp - t 4σ q ,
therefore, if we rejoin the different regimes, we obtain :

∀t > 0 : P f ( Z) -f ( Z ) ≥ t ≤ 4C exp - t 4σ q ,
and we can show exactly in the same manner that :

∀t > 0 : P f ( Z) -E f ( Z) ≥ t ≤ 4C exp - t 4σ q .
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 indeed be written :

P Z T AZ -EZ T AZ ≥ t ≤ 2 exp -c min t 2 K 4 A 2 F , t K 2 A ,
where K = max{ z i ψ2 } 1≤i≤p is the maximum of the Orlicz norms defined as :

z ψ2 = inf{t > 0 : Eψ 2 (|z| /t) ≤ 1} with ψ 2 (x) = e x 2 -1.
The tail parameters of the 1-exponential component is the same as the one of Theorem 1.2.52. The tail parameter of the 2-exponential component is propor-

tional to K A F while in our result, it is proportional to A E[ Z ] ∼ √ p A .
Therefore, considering that in most cases, i.e., when A has a high rank and eigenvalues mainly of the same order, A F ∼ √ p A , we see that the result of Theorem 1.2.52 is quite similar to the Hanson-Wright inequality if we do not take into account the hypotheses which are quite different (on the one hand they are stronger because they only require the whole vector Z to be concentrated, on the other hand they are weaker since they do not exploit the independence between the entries).

Although Definition 10 is perfectly adapted to the study of the resolvent Q (= Q S ), the problem is far less immediate in the setting of Definition 13, i.e., when X ∝ c α. Indeed in the setting of convex concentration, there does not exist any analogue to Proposition 1.2.43 since it does not seem clear whether a functional of Q, f (Q), with f 1-Lipschitz and quasiconvex can be written g(X/

√ n) with g verifying the same properties. In this case, the function φ cannot transfer the quasiconvexity and the study must then be conducted downstream directly with the random variables such as Tr Q.

It is interesting to note that Tr Q = Tr(XX T /n + zI p ) -1 stays unmodified if we multiply X on the left or on the right by any orthogonal matrix. More formally, let us introduce the group O p,n = O p × O n where O m , m ∈ N, is the orthogonal group of matrices of M m ; it acts on M p,n following the formula :

for (U, V ) ∈ O p,n , M ∈ M p,n : (U, V ) • M = U M V T . The function f : R ∈ M p,n → Tr φ(R) is O p,n -invariant, in the sense that ∀(U, V ) ∈ O p,n , ∀R ∈ M p,n , f ((U, V ) • R) = f (R).
A result originally owed to Chandler Davis in [START_REF] Davis | All convex invariant functions of hermitian matrices[END_REF], and that can be found in a more general setting in [START_REF] Grabovsky | A generalization of the chandler davis convexity theorem[END_REF], gives us the hint that such an invariance can help us showing that f is quasiconvex.

To present this theorem, we note D + p,n the set of nonnegative diagonal matrices of M p,n :

D + p,n = (M i,j ) 1≤i≤p 1≤j≤n ∈ M p,n | i = j ⇔ M i,j = 0 and ∀i ∈ {1, . . . , d} : M i,i ≥ 0 ,
where d = min(p, n).

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

Theorem 1.2.54.

If a O p,n -invariant function f : M p,n → R is quasiconvex on D + p,n
, then it is quasiconvex on the whole set M p,n . The original Davis' theorem is only concerned with symmetric matrices and we could not find any proof of this theorem for the case of rectangle matrices although it is not so different (it was also aiming at proving the convexity of f and not its quasiconvexity -but it is actually simpler to treat). We provide in Appendix C a rigorous proof of Theorem 1.2.54 with the help of some results borrowed from [START_REF] Bhathia | Matrix Analysis[END_REF].

Let us define the subgroup of row permutations P p = {U ∈ O p | U i,j ∈ {0, 1}, 1 ≤ i, j ≤ p} and the subgroup of full permutations :

P p,n = {(U, V ) ∈ P p × P n |U I p,n V T = I p,n } ⊂ O p,n ,
where I p,n ∈ D p,n is a matrix full of ones on the diagonal. Given a matrix A ∈ M p,n , we note Diag(A) = (A 1,1 , . . . , A q,q ), the vector composed of its diagonal terms. It is tempting to identify the set D + p,n with R d + , and the actions of P p,n on a diagonal matrix A to the actions of the group of permutation S d on the vector Diag(A), where we define the action of S d on R d as :

∀τ ∈ S d , ∀x ∈ R d : τ • x = x τ (1) , • • • x τ (d) .
With these considerations in mind, we see that a direct interesting consequence of Theorem 1.2.54 is that there exists a link between the convex concentration of a matrix X and the convex concentration of the vector of its singular values. Recall that the sequence of singular values verifies σ 1 (A) ≥ • • • σ d (A) ≥ 0 and for 1 ≤ i ≤ d, the i th singular value of M can be defined as :

σ i (A) = max F ⊂R n dimF ≥i min x∈F x =1 M x = min F ⊂R n dimF ≥n-i+1 max x∈F x =1 M x (13)
where the subsets F of R d on which is computed the optimization are subspaces of R n . We introduce the convenient function σ mapping a matrix to the ordered sequence of its singular values :

σ : M p,n → R d + M → (σ 1 (M ), . . . , σ d (M )).
To formalize this transfer of concentration between a matrix X and σ(X) let us introduce a new notion of concentration in a vector space E : the convex concentration transversally to the action of a group G acting on E. Definition 14. Given a normal vector space E, a group G acting on E, a concentration function α and a random vector Z ∈ E, we say that Z is convexly α-concentrated transversally to the action of G and we note Z ∝ T G α iff for any 1-Lipschitz, quasiconvex and G-invariant

function f : E → R, f (Z) is α concentrated.
Remark 1.2.55. In the setting of Definition 14, we have the induction chain :

Z ∝ α =⇒ Z ∝ c α =⇒ Z ∝ T G α.
Definition 14 is perfectly adapted to the next theorem whose proof can also be found in Appendix C (it is a similar result to in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF]Corollary 8.21] that concerns the eigenvalues of a random symmetric matrix).

Theorem 1.2.56. Given a normal vector space E, a concentration function α and a random matrix X ∈ M p,n , we have the equivalence :

X ∝ T
Op,n α ⇐⇒ σ(X) ∝ T S d α. Theorem 1.2.56 can be rather powerful to set the concentration of symmetric functionals of random singular values. For our present interest, we will prove the concentration of the Stieltjes transform m F = 1 p Tr Q of the covariance matrix S = XX T /n when X ∈ M p,n is convexly concentrated (recall that F stands for the normalized counting measure of the eigenvalues of S).

Proposition 1.2.57. Given a random matrix X ∈ M p,n , a concentration function α and z > 0 :

X ∝ c α =⇒ Tr Q ∝ 2α √ nz 3 8d • with d = min(p, n).
Let us introduce a simple preliminary lemma without proof :

Lemma 1.2.58. Given an integer d ∈ N, if a function f : R → R is convex, then the function F : R d → R defined as F (x 1 , . . . , x d ) = d i=1 f (x i ) is also convex.
Proof of Proposition 1.2.57. Assuming X ∝ c α, we know from Remark 1.2.55 and Theorem 1.2.56 that σ(X) ∝ T S d α, where d = min(p, n). Let us introduce the function :

f : s -→ 1 s 2 + z . This function verifies σ i (Q) = f (σ i (X)/ √ n) and Tr Q = d i=1 f (σ i (X)/ √ n). It is also 2 z 3/2 -Lipschitz, for s > 0 : |f (s)| = 2s (s 2 + z) 2 , thus f (s) ≤ 2 z 3/2 .
Therefore, the random variable Tr Q is a Lipschitz and S d -invariant transformation of σ(X). However, it is not quasiconvex. The result of convexity can be obtained decomposing f = gh with g and h both convex, then we will be able to conclude thanks to Lemma 1.1.5 giving the concentration of a sum of random variables. Let us set h

(s) = ( s z -1 √ z ) 2 if s ∈ [0, √ z] and h(s) = 0 if s ≥ √ z, and g = f + h. We have : if s ∈ [0, √ z] : g (s) = 6s 2 -2z (s 2 + z) 3 + 2 z 2 ≥ 0 and h (s) = 2 z 2 ≥ 0 if s ≥ √ z : g (s) = 6s 2 -2z (s 2 + z) 3 ≥ 0 and h (s) = 0.
Besides, h is 2 z 3/2 -Lipschitz, therefore g is 4 z 3/2 -Lipschitz. We next introduce as in Lemma 1.2.58 the functions G, H : R d → R defined as :

G(s 1 , • • • s q ) = d i=1 g(s i ) H(s 1 , • • • s q ) = d i=1 h(s i ).
The functions G and H are both S d -invariant and convex from Lemma 1.2.58. Besides, G is 4d z 3/2 -Lipschitz and H is 2d z 3/2 -Lipschitz. Therefore, we know from Lemma 1.1.5 that

Tr Q = G(σ(X)/ √ n) -H(σ(X)/ √ n) ∝ 2α z 3 2 √ n • 8d .
In the case of a convex concentration of X, an analogous to Proposition 1.2.43 setting the convex concentration of Q does not seem obvious, even with the help of Theorem 1.2.54.

It actually seems impossible to construct a quasiconvex and Lipschitz shift of Tr Aφ supported on the whole vector space M p,n as we did in Proposition 1.2.57. On a bounded subset of M p,n , it is always possible to shift a Lipschitz function with a convex one so that the sum verifies quasiconvex and Lipschitz properties. If we place ourselves in a convex q-exponential concentration setting, Proposition 1.2.51 helps us treat first the concentration of Tr AQ for a bounded version of a random vector X and then we can take advantage of the contracting behavior of the resolvent (see Lemma 0.0.2) to generalize our first result to any unbounded concentrated vector X.

Proposition 1.2.59. Given a random matrix X ∈ M p,n , z > 0, an exponent q > 0 and two parameters C ≥ e and σ > 0 :

X ∝ c E ± Ce -( • /σ) q =⇒ Q ∈ EQ ± 2Ce - √ z 3 n • 4σ q in (M p,n , • F ).
Before proving the result we formulate a preliminary lemma :

Lemma 1.2.60. Given a symmetric nonnegative definite matrix A ∈ M p and a matrix B ∈ M p , one has the bound :

| Tr AB| ≤ B Tr A.
Proof. There exits a diagonal matrix Λ = Diag(λ i ) 1≤i≤p and an orthogonal matrix U ∈ O p such that U T AU = Λ. If we note u i the i th column of U , we can write A = p i=1 λ i u i u T i , and for any i ∈ {1, . . . p}, u i = 1, so that :

Tr AB = p i=1 λ i Tr(Bu i u T i ) = p i=1 λ i u T i Bu i ≤ p i=1 λ i B ≤ B Tr A.
We show the other bound the same way ( u ≤ 1 ⇒ u T Bu ≥ -B u ).

f : R -→ Tr Aφ(R).
Given R, H ∈ M p,n , let us differentiate :

∇f R = -φ(R)Aφ(R)R -R T φ(R)Aφ(R) ∇ 2 f R (H, H) = 2 Tr (Aφ(R)Lφ(R)Lφ(R)) -2 Tr(Aφ(R)HH T φ(R)),
with the notation L = RH T + HR T . Let us suppose first that A is nonnegative symmetric. In that case, we know from Lemma 1.2.60 ( A ≤ A F ≤ 1) that :

Tr(Aφ(R)HH T φ(R)) ≤ 2 z 2 Tr HH T ,
and we recognize here the Hessian of the function g : R → 1 z 2 Tr RR T taken in (H, H). If we note h = f + g we know that

∇ 2 h R (H, H) ≥ 2 Tr (Aφ(R)Lφ(R)Lφ(R)) ≥ 0.
Besides, on the set {R ∈ M p,n , R ≤ √ z}, the function g is 2 z 3/2 -Lipschitz and convex. If we suppose first that X ≤ √ n, we know from Lemma 1.1.5 that the sum f

(X/ √ n) = (h -g)(X/ √ n) is concentrated : Tr AQ ∈ Tr AE[Q] ± 2Ce -z 3/2 √ n 4σ • . (14)
Now, if we suppose that there exists a constant K ≥ 1 such that X ≤ z 3 2

√

Kn, then we have thanks to (14)) and Lemma 1.1.3 :

Tr AQ = 1 K Tr A XX T Kn + z K I p -1
.

And since X/ √ Kn E ∝ α( √ Kn • ) the concentration ( 14)) and Lemma 1.1.3 entail :

Tr AQ ∈ Tr AE[Q] ± 2Ce - √ nz 3 4σ • .
In the general case, we consider the sequences of random matrices X (m) whose entries X (m) i,j , 1 ≤ i ≤ p, 1 ≤ j ≤ n, are defined as :

X (m) i,j = min 1, √ nz 3 m X F X i,j .
By construction, X (m) F ≤ √ nz 3 m. Besides we know from Remark 1.1.23 that E X F < ∞ and for m sufficiently large such that 2E X F ≤ √ nz 3 m, we know from Proposition 1.2.51 that X (m) E ∝ c α. Thus, as above :

Tr AQ (m) ∈ Tr AE[Q (m) ] ± 2Ce - √ nz 3 4σ
• , with :

Q (m) = φ X (m) √ n .
imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

If we let m tend to ∞, X (m) tends in law to X and thus Tr AQ (m) tends also in law to Tr AQ and we recover the result of the proposition thanks to Proposition 1.1.12 and Corollary 1.1.24.

We set in Subsections 1.2 the comfortable environment where our subsequent results will easily unfold. We notably introduced most of the expressions of concentrated random variables needed in the subsequent section. We are thus now in position to provide results on the spectral distribution of sample covariance matrices of concentrated random vectors.

Spectral distribution of the sample covariance

Setup and notations

We consider here a general case of the example presented in the preamble where the n independent random vectors x 1 , . . . , x n are distributed in k classes represented by k distributions µ l , 1 ≤ l ≤ k, supposedly different from one another.

All results presented below (with the exception of Propositions 2.2.8, Theorem 2.2.9 and Corollary 2.2.10) are valid for any choice of p and n, but they will of course gain more value when p and n are sufficiently large for the convergence to arise. This is the reason why we will call this study quasi-asymptotic. What we call a constant is supposed to be independent of the two quasi asymptotic quantities p and n and a bounded quantity is simply a quantity lower than a constant.

We place ourselves under an hypothesis of convex q-exponential concentration :

Assumption 1 (Concentration of X). There exist three constants C ≥ e, c > 0 and q > 0 such that for any m ∈ N, any l ∈ {1, . . . , k}, and any family of independent vectors y 1 , . . . , y m , each one following the law µ l , we have the concentration :

(y 1 , . . . , y m ) ∝ c Ce -• q /c where the concentration occurs in the normed vector space M p,m endowed with the Frobenius norm.

The parameters of the concentration C and c cannot be preserved throughout the different concentrations of the quantities that will be mentioned in this paper. However to lighten the expression of the result we will abusively keep the notations C and c to designate slight modifications of the original C and c by numerical constants.

Remark 2.1.1. Assumption 1 is in particular verified for the distributions concerned by Theorems 0.0.3, 1.2.20 and 1.2.47. For l ∈ {1, . . . , k}, the law µ l can respect one of the two settings :

• Setting 1 : µ l is a pushforward of the canonical normal distribution on R d , or of the sphere S d+1 through the mapping of a uniformly continuous function (see Proposition 1.2.24).

• Setting 2 : µ l is an affine pushforward of a product of distributions on R with support belonging to [-1, 1] (see Lemma 1.2.48).

Note that µ l can also be the sum of two independent distributions, each one coming from a different setting. In the literature, it is possible to find plenty of other cases of q-exponential concentration with q = 2 (and still with Euclidean norm!); their presentation goes far beyond the objectives of our paper and we invite the reader to refer to [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF] for more information. We will see at the end of this paper that our results are still valid on different types of practical data. Thus we come to think that convex q-exponential concentration is a general hypothesis that can be adopted in a large range of applications where the data have a satisfactory entropy compared to the diameter of their distribution (the link with entropy is explored once again in [START_REF] Ledoux | The Concentration of Measure Phenomenon[END_REF]).

The behavior of the sample covariance matrix S = 1 n n i=1 x i x T i = XX T /n clearly depends on the frequency each distribution µ l is drawn to form the different columns of the matrix X. To take into account this important feature, for l ∈ {1, . . . , k}, we introduce the set I l ⊂ {1, . . . , k} to index the random vectors x i following a distribution µ l ; the cardinality of the set I l is denoted n l . We further denote X I l ∈ M p,n l the matrix composed of the columns of X indexed by I l . Assumption 1 gives us directly the concentrations X I l ∝ c Ce -• q /c , that directly entail the concentration of the whole matrix X.

Assumption 2. The number of classes k is bounded.

With this last assumption, and Proposition B.4.1, we can state that the observable diameter of the random matrix X = [x 1 , . . . , x n ] is bounded.

Proposition 2.1.2. There exist two constants C ≥ e and c > 0 such that :

X ∝ c Ce -• q /c .
With this proposition, we have access to the results of the propositions and remarks of Subsection 1.2 concerning the matrix X but also those concerning the random vectors x i and the resolvent Q. To begin with, we can rewrite the first result of Proposition 1.2.59 to get the concentration of the Stieltjes transform of F , the spectral distribution of S :

m F (z) = 1 p Tr Q(-z) where Q = Q(z) = XX T /n + zI p -1 .
We saw in Proposition 1.2.59 that Q ∈ EQ ± Ce -( √ zn • ) q /c in (M p,n , • F ), for some constants C ≥ e, c > 0. Since the linear form M ∈ (M p,n , • F ) → 1 p Tr M has an operator norm equal to 1 p I p F = 1/ √ p, the linear concentration of Q implies directly the concentration of the Stieltjes transform with a tail parameter of order z 3 np.

Proposition 2.1.3. There exist two numerical constants C ≥ e and c > 0 such that for every z > 0, m F (-z) ∈ 1 p Tr EQ ± Ce -(

Now that we know that the Stieltjes transform is concentrated in R, we expect to find a deterministic quantity localizing this concentration. The deterministic equivalent we presented in the preamble can inspire us for a choice of a deterministic equivalent in this more general setting. We need for that some notations.

Given a class l, 1 ≤ l ≤ k, we introduce a generic random vector equal to one of the x i following the law µ l that will be noted y l . All the y l are supposed to be independent and we write by ȳl the mean of the distribution µ l . When computing an expectation involving the matrix X, this notation allows us to group the different terms depending only on their class l ∈ {1, . . . , k} and not on their index in the matrix i ∈ {1, . . . , n}. We note C -y l or even abusively C -l when l ∈ {1, . . . , k} the sample covariance S deprived of the contribution of one vector of the l th class (n l is supposed in that case to be greater than 1). That leads to the notations

Q -l = Q -y l = Q C-y l .
Finally, given l ∈ {1, . . . , k}, we note Σ l the population covariance matrix of µ l and :

Σ = k l=1 n l n Σ l .
To complete the lacuna of the concentration notion that does not give any information on the order of a random vector X, as concentrated it could be, one needs to give restrictions to the size of the quantities ȳl , 1 ≤ l ≤ k. The practical assumption that we need for our result is :

Assumption 3. ∀l ∈ {1, . . . , k} : 1 √ p E y l is bounded.

However, thanks to Corollary 1.2.14, it is possible to make a simpler hypothesis concerning directly the mean ȳl if we suppose that q ≥ 2 (then p 1/q ≤ √ p).

Assumption 3 bis. q ≥ 2 and ∀l ∈ {1, . . . , k} : 1 √ p ȳl is bounded.

Assumption 3 (or 3 bis) allows us to control Tr Σ l .

Proposition 2.1.4. For any l ∈ {1, . . . , k}, 1 p Tr Σ l is bounded. Proof. Since y l ∈ Ce -• q /c , we know from Proposition 1.1.28 that :

Tr Σ l = E y l 2 = (E y l ) 2 + E ( y l -E y l ) 2 ≤ Cp,
for some constant C > 0.

Estimation of the spectral distribution of the sample covariance

With the general setting presented above and assuming Assumptions 1, 2 and 3 (or 3 bis) we will show that the deterministic matrix :

Qδ = Q Σ δ = (Σ δ + zI p ) -1 with Σ δ = k l=1 n l n Σ l 1 + δ l and z > 0 is a deterministic equivalent for the resolvent Q(z) if δ = (δ 1 , . . . , δ k ) ∈ R k is chosen correctly.
One must be careful that the notation Σ x does not have the same meaning whether x is an integer of the set {1, . . . , k} or a vector of R k + . Following the calculus of the preamble in this more general case, one gets :

Qδ -EQ = k l=1 n l n E [∆ l + l ] with :          ∆ l = 1 1 + y T l Q -l y l /n - 1 1 + δ l Q -y l y l y T l Qδ l = - 1 n E Q -y l y l y T l QΣ l Qδ 1 + δ l
where we took advantage of the independence between Q -l and y l to say that

E[Q -y l Σ l Qδ /(1+δ l )] = E[Q -y l y l y T l Qδ /(1+δ l )].
The two matrices ∆ l and l will be used several times in our proof arguments; we thus invite the reader to remember their definition. The form of ∆ l entices us to set δ = ( 1n Tr(Σ l EQ -y l )) 1≤l≤k to show that Qδ is a deterministic equivalent for Q. We will show afterwards that the same result holds for Qδ with δ ∈ R + chosen as a solution of the system (see Proposition 2.2.7 for the validity of this definition) :

δ l = 1 n Tr   Σ l k h=1 n h n Σ h 1 + δ h + zI p -1   1 ≤ l ≤ k.
The first choice δ can seem unsatisfactory because it relies on the computation of EQ -i which is uneasy to treat. On the contrary, the second option δ is much more interesting as it can be approximated by iteration of the fixed point equation as we will see in Proposition 2.2.7. In particular, this second choice reveals that the deterministic equivalent can be chosen in a way that it only depends on z and on the covariances and the means of the laws µ l , 1 ≤ l ≤ k, as will be fully explained in Remark 2.2.11.

Design of a first deterministic equivalent

Let us first show the concentration of the random variable y T l Q -y l y l /n around its mean δ l . To simplify the concentration bounds, we introduce the real 1 > z 0 > 0, and from now on, z is supposed to be greater than z 0 . Proposition 2.2.1. Given z > z 0 , there exists two numerical constants C, c > 0 such that :

y T l Q -y l y l /n ∈ δ l ± Ce -(z0n • ) q 2 /c + Ce -( √ z 3 0 n • /γ) q /c
where γ = p n , and γ = γ + 1 ≥ max(γ, 1).

Proof. This proposition looks like Theorem 1.2.52 and Proposition 1.2.59 applied with independent random objects, respectively y l and Q -y l that we know to be concentrated thanks to the initial concentration on X given by Proposition 2.1.2. The independence allows us to consider Q -y l as deterministic when we bound a probability involving y l and conversely.

P 1 n y T l Q -y l y l - 1 n Tr(Σ l EQ -y l ) ≥ t ≤ E P y T l Q -y l y l -Tr Σ l Q -y l ≥ nt 2 | X -y l + P 1 n Tr Σ l (Q -y l -EQ -y l ) ≥ t 2 ≤ Ce -(znt) q 2 /c + Ce -(zn 3 2 t/p) q /c + Ce -((zn) 3 2 t/p) q /c ,
for some C, c > 0. We employed Theorem 1.2.52 together with Lemma 0.0.2 to control the variation of y T l Q -y l y l | X -y l ; and to control the variation of 1 n Tr Σ l Q -y l , we employed Proposition 1.2.59 thanks to the fact that Σ l F ≤ Tr Σ l = E y l 2 ≤ p.

We are interested in bounding the first centered moments of 1 n y T l Q -y l y l , thus the exponent m is considered to be a constant of the problem and that simplifies the expression of the bound. Assumption 3 allows us to simplify the bound : Proposition 2.2.2. Given l ∈ {1, . . . , k} and r > 0, there exists a constant C ≥ e such that :

E y T l Q -y l y l n -δ l r ≤ C γ2 z 3 0 n r/2 .
Proof. It is a simple consequence of Proposition 1.1.28 applied to the concentration of 1 n y T l Q -y l y l given by Proposition 2.2.1 :

E y T l Q -y l y l n - 1 n Tr(Σ l Q -y l ) r ≤ C γ2 z 3 0 n r/2 + C (z 0 n) r ,
and we recover the bound of the proposition thanks to :

C γ2 z 3 0 n r/2 ≥ C (z 0 n) r
(recall that z 0 ≤ 1).

To show the concentration of the Stieltjes transform around 1 p Tr Qδ (we already know from Proposition 2.1.3 that it concentrates around 1 p Tr EQ) but also to bound δδ , it is important to control EQ -Qδ . This quantity being defined as the maximum of u T (EQ -Qδ )u for u on the unit sphere, we will see in Proposition 2.2.5 that we naturally need to consider the concentration of objects like u T Qδ y l and u T Q -y l y l .

for some constant parameters C ≥ e and c > 0 since E y l ≤ √ p (the inclusion between combination of q-exponential concentration functions is defined in Subsection 1.1.2). Now that we set the concentrations, we know from Corollary 1.1.25 that for any r > 0 there exists a constant C such that :

E u T Q(y l -ȳl ) r ≤ C z r 0 E u T (Q -y l y l -EQ -y l ȳl ) r ≤ C γr/2 z 3r/2 0 .
Therefore, we know from the convexity of t → t r (because r ≥ 1) that :

E u T Qy l r ≤ 2 r-1 C z r 0 + u T Qȳ l r u T Q -y l ȳl r ≤ 2 r-1 C γr/2 z 2r 0 + u T EQ -y l ȳl r .
We thus conclude that all the centered moments are bounded as soon as we find a real s

≥ 1 such that E[|u T Qy l | s ] is bounded since we know from Jensen's inequality that |u T Qȳ l | r ≤ E[|u T Qy l | s ] r s . This is the case of Eu T Qy l y T l Qu = u T QΣ l Qu ≤ nγ n l z 2 0 (see Lemma 2.2.4
). The case of u T Q -y l l is harder to control and we need to employ the Schur formula (1) :

E u T Q -y l y l = E u T Qy l (1 + y l Q -y l y l /n) ≤ E u T Qy l y T l Qu E [(1 + y l Q -y l y l /n) 2 ] ≤ γ z 0 n n l E 1 n u T QX I l X T I l Qu ≤ n n l γ z 2 0 ,
where we recall that X I l ∈ M p,n l is the matrix composed of the columns of X indexed by I l (of cardinality n l ). The inequalities are consequences of Proposition 2.2.1 and Lemma 0.0.2.

Proposition 2.2.5. There exist a constant C > 0 such that :

EQ -Qδ ≤ C γ2 z 4 0 √ n .
Proof. As already mentioned, it is sufficient to bound for any vector u ∈ R p of unit norm the quantities |u T (EQ -Qδ )u| since EQ and Qδ are both symmetric matrices. Recall from the heuristic approach displayed at the beginning of this subsection the set matrices ∆ l and l verifying :

u T (EQ -Qδ )u = k l=1 n l n u T ∆ l u + u T l u .
Proof. The scheme of the proof follows the formalism of standard interference functions as presented in [START_REF] Yates | A framework for uplink power control in cellular radio systems[END_REF]. Following the ideas of Yates, we introduce the function :

I : R k + -→ R k + (δ l ) 1≤l≤k -→ 1 n Tr Σ l Qδ ,
where Qx = (Σ x + zI p ) -1 , and

Σ x = k l=1 n l n Σ l 1+x l for x = (x 1 , . . . , x k ) ∈ R k . Given x, y ∈ R k ,
we note x ≤ y iff ∀l ∈ {1, . . . , k}, x l ≤ y l . The function I is increasing in the sense that :

x ≤ y =⇒ I(x) ≤ I(y). This is simply due to the fact that for any l ∈ {1, . . . , k}, Σ l is symmetric nonnegative definite and x → Qx is increasing (with the classical order relation defined on the set of symmetric matrices see [Bha97, Section V] for more details). Besides, we know from Lemmas 0.0.2 and 1.2.60 that for any x ∈ R k , I(x) ≤ Tr Σ l nz . Therefore the vector

x 0 = Tr Σ 1 nz , • • • , Tr Σ k nz verifies I(x 0 ) ≤ x 0 .
Then the monotonicity of I implies that the sequence (I n (x 0 )) n≥0 is decreasing and since I takes its values in R + , it converges to a fixed point δ ≥ 0.

Let us now show the uniqueness of this fixed point. Let us suppose that there exists ν = δ such that I(ν) = ν. Given l ∈ {1, • • • , k}, we have the identity :

ν l -δ l = 1 n Tr k h=1 n h n γ h -δ h (1 + δ h )(1 + γ h ) Σ l Qδ Σ h Qν ,
and if we introduce the vector = ( l ) 1≤l≤k defined as This allows us to write for any x ∈ R + such that I

l = |νl-δ l | √ (1+ν l )(1+δ l ) : |ε l | = 1 n Tr k h=1 n h n Σ 1 2 l Qδ Σ 1 2 h (1 + δ h )(1 + δ l ) Σ 1 2 h Qν Σ 1 2 l (1 + γ h )(1 + ν l ) |ε h | ≤ 1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l 1 n Tr Σ l Qν Σ ν Qν 1 + ν l ε ∞ (
(x) = ( 1 n Tr(Σ l Qx )) 1≤l≤k = x : 1 n Tr Σ l Qx Σ x Qx = x l - z n Tr Σ l Q2 x < 1 + x l .
Therefore, we know from the inequality (16), true for every l ∈ {1, . . . , k}, that ε ∞ = 0, in other words δ = ν, the fixed point is unique.

Proposition 2.2.8. If γ and 1 z0 are bounded and n is large enough, there exists a constant C > 0 such that :

δ -δ ∞ ≤ C √ n and Qδ -Qδ ≤ C √ n .
Proof. Let us employ as in the proof of Proposition 2.2.7 a vector ε = δδ . Given l ∈ {1, . . . , k}, we compute :

|ε l | = 1 n Tr Σ l (EQ -Qδ ) ≤ γ EQ -Qδ + 1 n Tr Σ l ( Qδ -Qδ ) ≤ C γ3 z 4 0 √ n + 1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l 1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l ε ∞ ,
where we employed for the first inequality the result of Lemma 1.2.60 and in the second inequality the intermediate result ( 16)) of the proof of Proposition 2.2.7. We already know that :

1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l < 1 and 1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l ≤ δ l 1 + δ l + C γ3 z 4 0 √ n ,
and we know from (15) that δ l 1+δ l ≤ 1 -z0 γ . Therefore since z0 γ is bounded from below and C γ3 z 4 0 is bounded from above, if n is large enough :

1 n Tr Σ l Qδ Σ δ Qδ 1 + δ l < 1 and thus ε ∞ ≤ C γ3 z 4 0 √ n .
Now, let us bound the spectral norm of the difference Qδ -Qδ :

Qδ -Qδ ≤ k l=1 n l n |δ l -δ l | (1 + δ l )(1 + δ l ) Qδ Σ l Qδ ≤ δ -δ ∞ z 0 ≤ C γ3 z 5 0 √ n ,
for some C ≥ e.

We now have all the elements to set the linear concentration of Q around the second deterministic equivalent Qδ with the same arguments as those given to justify Proposition 2.2.6. Theorem 2.2.9. If γ and 1 z0 are bounded and n is large enough, there exist two numerical constants C ≥ e and c > 0 such that :

Q ∈ Qδ ± Ce -( √ n • ) q /c in (M p,n , • ) .
As for Proposition 2.1.3, we can directly deduce that 1 p Tr Qδ is a pivot of the Stieltjes transform. This time the linear form M → 1 p Tr M is seen as a 1-Lipschitz transformation from (M p,n , • ) to R (see Lemma 1.2.60).

Corollary 2.2.10 (Estimation of the Stieltjes transform). In the setting of Theorem 2.2.9, for z > 0 :

m F (-z) ∈ 1 p Tr Qδ (z) ± Ce -( √ n • ) q /c .
Remark 2.2.11 (Central limit theorem for covariance matrices). Let us define :

X N = (Σ k(1) x N 1 + ȳk(1) , • • • , Σ k(n) x N n + ȳk(n) )
where x N 1 , • • • x N n are independent Gaussian vectors with zero mean and unit variance entries and for a given i ∈ {1, . . . , n}, k(i) ∈ {1, . . . , k} designates the class of x i .

From the definition of δ and Qδ we can remark that the deterministic equivalent Qδ is the same for a resolvent Q constructed with the sample covariance of X or of the matrix X N . This implies that the asymptotic spectral distribution of the sample covariance matrix of X strictly depends on the means and the covariances of the laws µ l , 1 ≤ l ≤ k, but not at all on the intrinsic distribution of those laws. In that sense, the Gaussian case describes all the possible asymptotic spectral distributions of sample covariances of any concentrated data respecting our two assumptions.

In a future paper this remark will be the key idea to show a theorem of central limit for some quantities depending on the resolvent (with applications to random neural networks, such as extreme learning machines [HZS06]).

Illustration of the results

In this section, we are interested in the asymptotic spectral distribution of S, in the sense that if we index with n all the quantities characteristic to the matrix X (that we write for instance X n ), we wish here to express the limit of the spectral distributions F n when the number of data n tends to ∞. The size p of the data can then be seen as a function p n of n that cannot grow too fast to maintain the validity and the strength of our results. Corollary 2.2.10 requires in particular γ = pn n to be bounded, and this will be from now on a supplementary assumption. Regarding the convergence, it appears convenient to work with the notion of the weak convergence of distributions that was essentially presented in Definition 5 through the convergence in law of random variables. We shall say indeed that a sequence of measures (H n ) n∈N tends weakly to a measure H if for any function f : R → R with compact support :

lim n→∞ R f (t)dH n (t) = R f (t)dH(t),
and we write H n w -→ H. Now, it is important to keep in mind that the distributions F n are random objects and, therefore, we will be looking for a weak convergence almost surely. Let us note X the sequence of random matrices (X n ) n∈N that we suppose to be independent. If we note σ

(X ) = σ(X 1 ) × • • • σ(X n ) × • • • ,
the sigma-algebra generated by X , we look for an event (i.e., an element of σ(X )) of probability 1 on which happens the weak convergence. As we could expect from the different results of the last sections, the convergence of the spectral distribution is a consequence of the convergence of the Stieltjes transforms. This is a classical results of the field of random matrices, we provide in Appendix D a proof inspired from the paper [START_REF] Couillet | A deterministic equivalent for the analysis of correlated MIMO multiple access channels[END_REF]. (Recall that Qn is the matrix Qδ indexed with the number of data n)

If we go back to the original task we presented in the preamble, we need to evaluate the limit distribution H appearing in the result of Theorem 2.3.1. We can be helped by a basic proposition of the theory of large random matrices : Proposition 2.3.2. Given a probability distribution H in R, we note m H : z → R dH(t) t-z , the Stieltjes transform of H. Given t, s ∈ R, we have the identities :

• H({t}) = lim y→0 + yIm[m H (x + iy)] • H([t, s]) = 1 π lim y→0 + s t
Im[m H (x + iy)]dx. In Figure 3, we compare the spectral distribution of different sample covariance matrices with their asymptotic profile as described by Theorem 2.3.1. Inspired by Proposition 2.3.2, we basically computed 1 p Tr Qδ (x + iy) for small values of y to obtain the density of F . We see that the prediction is valid for different values of γ = p n and for data constructed as a mixture between Gaussian and Bernoulli random vectors.

The range of validity of our results seems to be rather wide since one can see on Figure 4 that our predictions are rather good for "raw" data as the one of the MNIST data base (left graph) or even more refined data as some feature vectors imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 of traffic sign images (right graph). Be careful that we drew the distribution of a push-forward of the spectral distribution dilated around zero, otherwise the distribution would be huddled against 0 and at the same time sparsely spread up to high values. The refined feature dataset satisfies our prediction better that the MNIST dataset. This statement allows us to think that in the concentration of the measure framework, the treatment of the signal though the diverse neurons tends to "normalize" the data. Then the product Z 1 • • • Z p is concentrated in the sense of Definition 3, and we have :

Z 1 • • • Z p ∈ a p ± pα • 2 p |a| p-1 + pα • 2 1 p
Note that in the case of q-exponential concentration, if, say, α = Ce -(•/σ) q , C ≥ e, σ, q > 0, we can employ Proposition 1.1.20 and obtain ∀r ≥ q the bound :

E [|Z 1 • • • Z p -a p |
r ] ≤ Cp(2|a| p-1 σ) r r q r q + Cp(2σ p ) r rp q rp q which is looser than the one obtained in Proposition 1.1.28 (when r ∈ N).

Proof. Let us bound : and we recover the result.

Z 1 • • • Z p -a p =
One can be interested in the concentration of Z r when r is not an integer. If we write r = r r r where r is the integer part of r plus 1, we see that thanks to Proposition 1.1.10 our problem can be reduced to the concentration of Z r when 0 < r ≤ 1. That can be managed easily thanks to the following lemma : Interestingly, when r ≤ 1, the concentration of Z r is easier to show in the formalism of Definition 2. Indeed we can employ Lemma 1.1.3 since we know from Lemma A.0.2 that t → t r is (1, r)-Hölder continuous.

Proposition A.0.3. Given an exponent r ∈ (0, 1] and a concentration function α, if a non-negative random variable Z ≥ 0 is α-concentrated in the sense of Definition 2 then Z r ∝ α(• 1 r ).

Remark A.0.4. Thanks to Proposition 1.1.2, we can adapt the result of Proposition A.0.3 to the formalism of Definition 3. This gives us when r ∈ (0, 1], with the upper notations :

Z ∈ m Z ± α =⇒ Z r ∈ m r Z ± 4α • 1 r 2 ,
where m Z is a median of Z (note that implicitly mentioned in the upper implication, m r Z is a median of Z r since the function t → t r is monotonous). One can then look at the concentration of any power Z r where r ∈ R * + :

Z ∈ m Z ± α ⇒ Z r ∈ m r Z ± 4α   1 2 r +1 • |m Z | r -1 r r   + 4α 1 2 • 2 1 r
For any linear function u with an operator norm bounded by 1, we have :

u(XY -X Ỹ ) ≤ X -X Y -Ỹ + u Ỹ (X -X) + u Ỹ (Y -Ỹ )
where for any z ∈ A we defined u z : x → u(zx). To conclude, we just have to note that u z is a linear function the operator norm of which is bounded by z (since u(zx) ≤ u z x ).

B.3. Linear concentration of the power

Let us adapt Proposition 1.1.10 to get the linear concentration of a power of a random vector, we leave to the reader the expression of the concentration of the product of m linearly concentrated random vectors.

Proposition B.3.1. Given m ∈ N * , a random vector Z ∈ A, a deterministic vector Z ∈ A * and three parameters C ≥ e, σ, q > 0, if we suppose that Z ∈ Z ± Ce -( • /σ) q , then :

Z m ∈ Zm ± C exp   -   c • 2 m ση 1 q • Z m-1   q   + exp   -c   • 2σ m η m q •   q m    ,
where c is a numerical constant depending only on q and m. Since we know from Proposition 1.2.12 that Z -Z ∈ 0 ± Ce -(c • /σ) q /η • for some numerical constant c > 0, we get the concentration :

Z m -Zm ∈ 0 ± C exp   -   c/2 m • ση 1 q • Z m-1   q   + C exp   -   c m • 2σ m η m q •   q m   
and we get the same concentration for Z thanks to the second result of Proposition 1.2.12.

B.4. Concatenation of convexly concentrated random vectors

Through the characterization with the centered moments given by Proposition 1.1.20, the q-exponential concentration allows to explore the concentration of a random vector constructed as a concatenation of p independent random vectors (Z 1 , . . . , Z p ). This approach is indifferently adapted to the Lipschitz or convex concentration. We use the index (c) under the sign ∝ to specify that the proposition is valid in both settings (for Lipschitz or convexly concentrated random vectors).

Proposition B.4.1. Given p normed vector spaces (E 1 , N 1 ), . . . , (E p , N p ), consider p independent random vectors (Z 1 , . . . , Z p ) ∈ E = E 1 × • • • × E p verifying for any i ∈ {1, . . . , p} that Z i ∝ (c) Ce -( • /σ) q , for two given parameters C ≥ e, σ > 0. The space E can then be seen as a normed vector space endowed with the norm • 1 defined as : ∀z = (z 1 , . . . , z p ) ∈ E 1 × • • • × E p : z 1 = N 1 (z 1 ) + . . . + N p (z p ). Then the concatenation Z = (Z 1 , . . . , Z p ) is q-exponentially concentrated in (E, • 1 ) with an observable diameter lower than pσe Z ∝ (c) Ce -( • /pσ) q /e .

Proof. Let us consider a function f : E → R, 1-Lipschitz (resp. 1-Lipschitz and quasiconvex), and Z an independent copy of Z. We plan to employ the characterization with the centered moments given by Proposition 1.1.20. Given i ∈ {0, . . . , p}, we note Z (i) = (Z 1 , . . . Z i , Z i+1 , . . . , Z p ) (with this notation : Z (0) = Z and Z (p) = Z ). For any r ≥ max(q, 1), let us exploit the convexity of t → t r to bound :

E |f (Z) -f (Z )| r ≤ p r-1 p i=1 E f Z (i-1) -f Z (i) r .
Therefore, since for any (z 1 , . . . , z p ) ∈ R p and for any i ∈ {1, . . . , p}, z → f (z 1 , . . . , z i-1 , z, z i+1 , . . . z p ) is Lipschitz (resp. Lipschitz and quasiconvex), we can employ Proposition 1.1.20 to bound :

E |f (Z) -f (Z )| r ≤ Cp r r q r q σ r .
If q ≤ r ≤ 1, the concavity of t → t r allows us to write thanks to Jensen's inequality :

E |f (Z) -f (Z )| r ≤ (E [|f (Z) -f (Z )|])
r ≤ C r p r 1 q r q σ r ≤ p r r q r q σ r since r ≤ 1 ≤ C q . The last implication of Proposition 1.1.20 then gives us the desired result: f (Z) ∝ Ce -( • /pσ) q /e .

Of course, it is important that the vectors σ(A) and σ(B) are both ordered when we sum them.

Proof. Given a symmetric matrix S ∈ M q , there exists (U S , V S ) ∈ O p,n such that U A AV T A = Diag p,n σ(S), thus : We know from Theorem C.1.4 that for any U ∈ D + p,n , L(U ) = {Diag Z ≺ Diag U } and therefore, since for any t ∈ [0, 1], tX + (1 -t)Y ∈ L(X, Y ), we obtain the first inclusion K(x, y) ⊂ L(X, Y ).

To prove the converse inclusion, let us show that K(x, y) is convex (we already know that O p,n • K(x, y) ∩ D + p,n = P p,n • K(x, y) = K(x, y) by definition of the relation ≺).

We consider A, B ∈ K(x, y), t ∈ [0, 1] and we set C = tA+(1-t)B. Therefore, We know that there exists t z , t w ∈ [0, 1] such that Diag A ≺ λx + (1 -λ)y and Diag B ≺ µx + (1 -µ)y, therefore :

Diag C ≺ (tλ + (1 -t)µ) x + (t(1 -λ) + (1 -t)(1 -µ)) y ∈ [x, y].
In conclusion, since X, Y ∈ K(x, y) and K(x, y) is P p,n -invariant and convex we recover the second inclusion K(x, y) ⊂ L(X, Y ).

Thus we are left to show that O p,n • K(x, y) is convex. We consider this time A, B ∈ O p,n • K(x, y), t ∈ [0, 1], and we introduce C = tA + (1 -t)B. We know from Theorem C.1.6 that : We can apply Proposition C.1.2 to get the hypothesis of Theorem C.1.1 that entails Theorem 1.2.54 in our setting.

C.2. Proof of Theorem 1.2.56

Let us first show the Lipschitz character of σ, it is a well known result that can be found for instance in [START_REF] Golub | Matrix computations[END_REF] : Lemma C.2.1 (Theorem 8.1.15 in [START_REF] Golub | Matrix computations[END_REF]). The function σ is 1-Lipschitz.

Proof. Given M, H ∈ M p,n , and i ∈ {1, . . . d} (where as before, d = min(p, n), we know from formula (13)) that :

λ i (A + H) = min F ⊂R n dimF ≥n-i+1

Contents

  Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Preamble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1 The Concentration of Measure Framework . . . . . . . . . . . . . . . . 10 1.1 Concentration of a random variable . . . . . . . . . . . . . . . . . 11 1.1.1 Definition and first Properties . . . . . . . . . . . . . . . . 11 1.1.2 Exponential concentration . . . . . . . . . . . . . . . . . . 17 1.2 Concentration of a random vector of a normed vector space . . . 26 1.2.1 Linear Concentration . . . . . . . . . . . . . . . . . . . . . 27 Nomenclature iif "if and only if" R Set of real numbers; R + = {x ∈ R | x ≥ 0} ; R -= -R + . If x ∈ R p , one notes [x] i ,or more simply x i , 1 ≤ i ≤ p, the i th entry of the vector x (a, b] Considering an interval I ⊂ R, we employ the sign "(" if left border of I is open and "[" if it is closed ; the same rule works for the right border. To give an example, given a, b ∈ R : (a, b] = {x | a < x ≤ b} x

  O p Set of orthogonal matrices of M p : P ∈ D p,n ⇔ P -1 = P T ; O p,n = O p × O n . D p,n Set of diagonal matrices of M p,n : D ∈ D p,n ⇔ D = Diag p,n (Diag(D)) ; D ∈ D + p,n ⇔ D i,i ≥ 0, 1 ≤ i ≤ min(p, n) ; D ∈ D - p,n ⇔ -D ∈ D + p,n .When n = p, we simply note D p = D p,n .

  d • Distance associated to the norm • . Given two vectors x, y ∈ E and two setsA, B ⊂ E, d • (x, y) = xy , d • (x, A) = inf{d • (x, y), y ∈ A} and d • (A, B) = inf{d • (x, B), x ∈ A}. B t Closed ball of E of size t > 0, B t = {0} t = {x ∈ E | x ≤ 1}, when t =1, we note B = B 1 . We also use the notation B • (x, t) = {x} t = imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

•q

  E[•|•] Conditional expectation. Given a random variable X ∈ R and G, a sub σ-algebra of F, E[X|G] is the unique random variable that P(•|•) Conditional probability. Given a Borel set A ⊂ R and a random variable X ∈ R, P(A|X) = E[1 A |X]. ∈, ± Concentration around a pivot or around a deterministic equivalent, see Definitions 3 and 8. ∝ Lipschitz concentration, see Definitions 2 and 10. ∝ c Convex concentration, see Definition 12. R X Observable diameter, see Remark 1.2.28 ∝ T Transversal concentration, see Definition 14. dµ If µ is a probability law defined on E, for any function f : E → R, such that µ(f ) = f dµ = 1, we note f dµ the measure verifying for all Borel set B : f dµ(B) = 1 B f dµ. λ p Lebesgue measure on R p . β p Uniform measure on the ball B • q of R p . σ p Uniform measure on S p . p Exponential measure. If p = 1 ν 1 = e | •| 2 dλ 1 , for p ≥ 1, ν p = ν 1 ⊗ . . . ν 1

p i=1 z 2 i

 2 or the 1 -norm z 1 = p i=1 |z i |, or in E = M pn , p, n ∈ N, endowed with two possible norms : imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

  x a , y a ) ∈ {f ≤ a} and (x b , y b ) ∈ {f ≥ b}, the intermediate value theorem states that there exists a point (x 0 , y 0 ) ∈ [(x a , y a ), (x b , y b )] belonging to the open set {a < f < b}. The set {a ≤ f ≤ b} has then a positive Lebesgue measure as it contains a non empty open subset and P (a ≤ f (X, Y ) ≤ b) > 0 by hypothesis made on (X, Y ).

  Theorem 2.3.1. With the above notations and hypotheses, if we suppose that there exists a complex function m : C → C such that :∀z > 0 : 1 p n Tr Qn (z) -→ m(z),then there exists a measure H in R such that : ∀z ∈ D, m(z)

Fig 3 .

 3 Fig 3. Spectral distribution of the empirical covariance matrix of a sum of Gaussian and Bernoulli data. On the left, n = 2000, p = 500 and Σ has two eigenvalues : 1 and 12 with the repartition ( 1 4 , 3 4). On the right, p = 2000, n = 1000 and Σ is a symmetric Toeplitz matrix whose first line is (0.4, 0.4 2 . . . 0.4 p ) ; since p > n, we removed the p -n zero eigenvalues of S to simplify the graphs.

Fig 4 .

 4 Fig 4. Distribution of the push forward of the spectral distribution of the covariance matrix of real datasets through the map λ → λ 0.1 ; the population covariance and the mean are empirically computed from a larger and independent dataset. On the left, images the digit 0 of the MNIST data set ([LCB98]); p = n = 784. On the right, "HOG" features (Histograms of Oriented Gradients) of a class of traffic sign images presented in the paper [SSSI11] ; p = n = 700 (just the first p features are considered)

.

  ver. 2014/10/16 file: output.tex date: February 14, 2019where Z s is the random variable verifying Zs-a a As in the proof of Proposition 1.1.10 distinguishing the cases Zs-a a ≥ 1 and Zs-a a ≤ 1, we obtain the bound :|Z 1 • • • Z p -a p | ≤ (2 |a|) p Z s -a a + Z s -a a p ,and we are left to express the concentration around 0 of the random variable |Z s -a| :P (|Z s -a| ≥ t) ≤ p i=1 P (|Z i -a| ≥ t) ≤ pα (t)

  Lemma A.0.2. Given a, b ∈ R and r ∈ [0, 1], |a| r -|b| r ≤ |a -b| r . Proof. When a, b > 0, it is just a consequence of the triangular inequality verified by the 1 r -norm on R. If a or b are negative, it is just a consequence again of the triangular inequality of the absolute value : ||a| -|b|| ≤ |a -b|.

Proof.

  As in the proof of Proposition 1.1.10, we bound :Z m -Zm = m k=1 i1+...+i k ≤m-k (Z -Z) i1 Z . . . (Z -Z) i k Z(Z -Z) m-i k -...-i1

  where given x ∈ R d and k ∈ {1, . . . d},k x = k i=1 x ↓ i .Besides, since σ(U SV T ) = σ(S), we know from Proposition C.1.5 that :k σ(S) = sup (U,V )∈Op,n k Diag(U SV T ).(17)Now, if we suppose that we are given a general matrix AM p,n and(U A , V A ) ∈ O p,n such that U A AV T A = Diag p,n σ(A).If we introduce the matrices : , with D = Diag p,n (σ(A)).Depending on the relation between p and n, we introduce the invertible matrices :if d = n : Q =   I d (0) I d (0) I d (0) -I d (0) I d   and if d = p : Q =   I d I d (0) -I d I d (0) (0) (0) I d   , then if d = n, QP Ã(P Q) T = Diag(σ(A), 0 • • • 0, -σ(A)) and if d = p, QP Ã(P Q) T = Diag(σ(A), -σ(A), 0 • • • 0).Thus in both cases, we obtain a diagonalisation of à that allows us to generalize the identity (17)) for any matrix A ∈ M p,n and with 0 ≤ k ≤ d. The supremum of a sum being lower than the sum of a supremum, for any pair of matrices A, B ∈ M p,n :σ(A + B) ≺ σ(A) + σ(B).Now that the picture is clearer, we can prove Theorem 1.2.54 : Proof of Theorem 1.2.54. To employ Theorem C.1.1, let us show the convexity conservation property of O p,n from D + p,n . Inspired by Proposition C.1.2, we consider two non-negative diagonal matrices X, Y ∈ D + p,n , and we note L(X, Y ) = L D + p,n Op,n ({X, Y }). We want to show that O p,n • L(X, Y ) is convex. imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 / 82 Noting x = Diag X and y = Diag Y , let us first show that L(X, Y ) = K(x, y), with : K(x, y) = {Z ∈ D + p,n , Diag Z ≺ λx + (1 -λ)y, 1 ≤ λ ≤ 1}.

  σ(C) ≺ tσ(A) + (1 -t)σ(B),and as we saw before, that implies that Diag σ(C) ∈ K(x, y). We can then conclude with the relationsC ∈ O p,n • {Diag σ(C)} ⊂ O p,n • K(x, y) = O p,n • L(X, Y ).

  ≤ λ i (A) + λ 1 (H),imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

  Set of permutations of {1, . . . , p} ; S p,n = S p × S n .x ↓ Decreasing version of x ∈ R p , ∃σ ∈ S p such that ∀i ∈ {1, . . . , p},[x ↓ ] i = x σ(i) and [x ↓ ] i ≤ [x ↓ ] i-1 for i ≥ 2. ≺ Majorizationrelation, see Definition 15 M p,n Set of real matrices of size p × n. If M ∈ M p,n , one notes [M ] i,i or more simply M i,j the entry at the line i and column j. If n = p, we simply note M p = M p,n . Tr Trace operator on M p , ∀M ∈ M p , Tr M =

	• T	p i=1 M i,i .

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 S p

  imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 Proof of Proposition 1.2.59. With the function φ introduced in Proposition 1.2.43 and given A ∈ M p verifying A F ≤ 1, let us note :

  Qx = Q Σx , we have the identityQx Σ x + z Qx = I p .

				16)
	where for any x ∈ R k + , we recall that Σ x =	k h=1	n h n	Σ h 1+x h . Recall that by
	definition of the resolvent

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 Louart & Couillet/Concentration of Measure and Large Random Matrices

Contrarily to the linear and Lipschitz concentrations, convex concentration does not seem to be preserved through the product. To derive any results on the product from a convex concentration, we will thus develop the habit of returning on the linear concentration configuration which is weaker but in a sense "stable" on algebra, like the Lipschitz concentration.

If we fail to maintain the concentration of the vectorial product, as implicitly evoked Lemma 1.2.50, we still have the concentration of the norm as it is a Lipschitz and convex map. That makes a fundamental difference with the linear concentration which entices an important result on quadratic forms quite similar to the Hanson-Wright inequality as found in [Ver17, Theorem 6.2.1] for instance. It is also a good improvement to [El 09, Lemma 8] :

Theorem 1.2.52. Let us consider two integers q, m ∈ N and a random vector Z ∈ R p , two positive constants C ≥ e and σ > 0 and a matrix A ∈ M p . If we suppose that Z E ∝ c Ce -( • /σ) q then we have :

It is possible to replace the mean with the median if needed.

Proof. Let us first consider the case where A is symmetric nonnegative definite; in this case, Z T AZ = A 1 2 Z 2 . Theorem 1.2.52 is a particular case of Proposition 1.1.10 that gives the concentration of the r-power of a random variable u(Z) when u is quasiconvex and 1-Lipschitz and r ≥ 1 :

The function z → A 1 2 z is A 1 2 -Lipschitz and convex. Therefore :

and we can then conclude thanks to (12). Now if we consider a general matrix A ∈ M p , let us decompose A = A + -A -+ A 0 where A + is nonnegative symmetric, A -is non positive symmetric and A 0 is antisymmetric. We have clearly Z T AZ = Z T A + Z -Z T A -Z and we can conclude thanks to Lemma 1.1.5.

Remark 1.2.53. The original Hanson-Wright inequality does not take as hypothesis the concentration (or the convex concentration) of the whole vector Z = (z 1 , . . . , z p ) but just the concentration of each one of its coordinates z i . However, it assumes that the different coordinates of Z are independent which is quite a strong hypothesis and also that their means are equal to zero. The concentration result obtained under these hypotheses is not exactly the same, and relies on a quantity K that could be seen as the maximum tail parameter of the {z i } 1≤i≤p (K = σ in our case). The Hanson-Wright concentration can Proposition 2.2.3. Given z ≥ z 0 , there exist two numerical constants C ≥ e and c > 0 such that for any l ∈ {1, . . . , k} and for any u ∈ R p of unit norm, we have the concentrations :

where as above, γ = p n and γ = 1 + γ. Moreover, there exists a numerical constant C such that for any r ≥ 1 :

The relation between y l and Q -y l is characterized by the multiple appearance of vectors x i following the law µ l in the matrix X -y l . Similarly, Qδ lets appear in its definition the matrix Σ l characteristic of the distribution of y l . These relations allow us to bound the moments

and explains the appearance of the coefficient n l n . Without these structural relations we could consider instead of y l any random vector y with an expected norm of order √ p. In that case Eu T Qy and Eu T Q -y l y would be rather of order √ p like the norm of y. The next preliminary lemma explains how this control can be realized when we deal with the deterministic equivalent Qδ .

Lemma 2.2.4. Given l ∈ {1, . . . , k},

Proof. The result is similar to the result of Lemma 0.0.2. Recall the notation

1+δ h and the definition Qδ = (Σ δ + zI p ) -1 . With the order relation on the set of symmetric matrices, we deduce from the inequality

). We know from Lemma 1.2.60 and Assumption 3 that :

We can then conclude thanks to the bound (1+δ l ) ≤ γ z0 (recall that z 0 ≤ 1). Proof of Proposition 2.2.3. Let us introduce the bilinear form :

-Lipschitz linear form on y l , it thus concentrated as y l . Since Q -y l ∈ EQ -y l + e -( √ z0 n• ) q /c and y l ∈ Ce -• q /c are independent, and Q -y l ≤ 1/z 0 , we know from Proposition 1.2.9 that :

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019

Thanks to Hölder's inequality and Properties 2.2.2, 2.2.5, we can bound :

For the same reasons :

Therefore if we sum on l ∈ {1, . . . , k}, we see that there exists a constant C ≥ e such that :

and that gives us directly the bound on EQ -Qδ thanks to Assumption 2 (k is bounded).

This last proposition together with Proposition 1.2.59 and Lemma 1.2.8 implies that Qδ is a deterministic equivalent for Q.

so in particular :

But since EQ -Qδ ≤ C γ2 z 4 0 √ n , Lemma 1.2.8 entails the result of the proposition.

A second deterministic equivalent

Let us introduce a substitute for δ that we note δ and that will only depend on the means and covariances of the laws µ l and on the cardinality coefficients n l n of the different classes.

Proposition 2.2.7 (Definition of δ ). The system of equations :

∀l ∈ {1, . . . , k} :

Appendix B: Results of linear concentration

We consider here N 1/2 , a maximal 1 2 -net of B H with respect to inclusion. We know that the balls of radius 1 4 centered on the points of N 1/2 are all disjoint by hypothesis, and their volume is equal to V B H /4 p (where V B H is the volume of B H ). Since they all belong to the ball of radius 2 and centered at the origin, we know that their number cannot exceed 8 dim (H) .

Besides, given a drawing of Z, there exists

). Furthermore :

Therefore :

and this inequality being true for any drawing of Z, we have then by hypothesis :

B.2. Linear concentration of the product

We place ourselves in an algebra A endowed with an algebra norm • (verifying xy ≤ x y ). To simplify the result we place ourselves in the exponential concentration setting, the reader is required to adapt the proof for generalization if needed. Proposition B.2.1. Given two random vectors X, Y ∈ A and three parameters C ≥ e and σ, q > 0, if X and Y follow the same concentration X ∈ X ± Ce -( • /σ) q and Y ∈ Ỹ ± Ce -( • /σ) q , then XY is also concentrated :

where c is a numerical constant independent of C and σ.

Proof. As for Lemma 1.1.8, we employ the identity : Let us first present basic notions to set the theorem. Given a vectorial space E and a group G acting on E, for any subset A ⊂ E, we note

In the same vein, we say that a set

the smallest convex subset of T containing U and G-invariant in T . We give here an adaptation of one of the result of Grabovsky and Hijab to the case of quasiconvex functions.

Theorem C.1.1 (cf. [START_REF] Grabovsky | A generalization of the chandler davis convexity theorem[END_REF], Theorem 4). Let us consider a vector space E, a group G acting on E, and a convex and transversal subset T ⊂ E. We suppose that for any U ⊂ T , the set G • L G T (U ) is convex ; we call this property the convexity conservation of G from T. Then any G-invariant function f is quasiconvex iff its restriction to T is quasiconvex.

Intuitively, this theorem states that the quasiconvexity (or the mere convexity as in [START_REF] Grabovsky | A generalization of the chandler davis convexity theorem[END_REF]) of any function G-invariant is "transversal" to the action of G when G preserves the convexity from T . A curious reader might be interested in simplifying the convexity conservation property as we presented it from a transversal subset T ⊂ E to a mere conservation of the convexity of any convex subset U ⊂ E (i.e., for any convex set U ⊂ E, f (U ) is convex). This would be indeed an hypothesis more than sufficient for the result of the theorem. However, in practice, and in particular for the applications we want to consider, it cannot be verified.

Proof. Let us note note f T the restriction of f on T . Given any t ∈ R, we know that the set {f when X ∈ D + p,n . We know that D + p,n is invariant under the action of the subgroup of permutations P p,n . Given a subset U of a vector space, we note Conv(U ) the convex hull of U .

Proof. We know from the uniqueness of the singular value decomposition that for any

Consequently, since the convexity is stable under the action of P p,n (they are linear transformations), L(X) = Conv(P p,n • {X}).

Here the tools of majorization as presented for instance in [START_REF] Bhathia | Matrix Analysis[END_REF] are perfectly adapted to the description of Conv(S p,n • {x}) that we identify with

Majorization appears to be the pertect tool to control the singular decomposition of a sum of matrices as we will see in Theorem C.1.6. This is the core argument to justify the convexity consevation of O p,n from D + p,n that we need to prove Theorem 1.2.54. Let us first give an intermediate result that we originally owe to Schur and whose proof can be found in [START_REF] Marshall | Inequalities: Theory of Majorization and Its Applications[END_REF] or [START_REF] Bhathia | Matrix Analysis[END_REF].

Proposition C.1.5 (Schur's Theorem, B.1. in [START_REF] Marshall | Inequalities: Theory of Majorization and Its Applications[END_REF]). Given a symmetric matrix S ∈ M p , we have the majorization Diag(S) ≺ σ(S).

This proposition entails a kind of triangular inequality for the set of singular values. and the same way, we can show that λ i (A + H) ≥ λ i (A) -λ n (H). Therefore, we get :

Proof of Theorem 1.2.56. It is a simple corollary of Theorem 1.2.54. If X ∝ T Op,n α, and given a 1-Lipschitz, convex and S n -invariant function f : R d → R, one can introduce the function F defined as :

The function F is 1-Lipschitz thanks to Lemma C.2.1 and O p,n -invariant because of the uniqueness of the singular decomposition. Besides we can identify the set D + p,n with R d and introduce a function f :

In that case, since f is S d -invariant and convex, f is also convex and since f = F D + p,n , Theorem 1.2.54 allows us to set that F is also convex. Therefore, the random variable f (σ(X)) = F (X) is α-concentrated by hypothesis on X.

Reciprocally, let us suppose that we are given a random matrix X ∈ M p,n such that σ(X) ∝ T S d α, and let us consider a 1-Lipschitz, convex and O p,ninvariant function F : M p,n → R. The restriction F D + p,n is also 1 Lipschitz, convex and P p,n -invariant. Thus, with the same identification as before between D + p,n and R d , we can assert by hypothesis that F (X) = F D + p,n (σ(X)) is αconcentrated (we defined

Appendix D: Proof of Theorem 2.3.1 : convergence of the spectral distribution of the sample covariance Corollary 2.2.10 states that for any z > z 0 :

Then if we introduce the events of σ(X ) :

imsart-generic ver. 2014/10/16 file: output.tex date: February 14, 2019 / Thus the Borel-Cantelli lemma ensures that

Therefore, a.s., for any ε > 0, there exists an integer n 0 ≥ 1 such that for any n ≥ n 0 :

In other words, a.s., the Stieltjes transform of F n taken in z converges to then there exists a measure H in R such that :

For any k ∈ N * , let us note z k = z 0 + 1 k , and A k the event of probability one "m Fn (z k ) -1 p Tr Qδ (z k ) → 0". We know that the event A = ∩ k≥1 A k has probability one as a countable intersection of events of probability one. Therefore, if we consider the set D = {z 0 + 1 k , k ∈ N}, we know that a.s., for all z ∈ D, m Fn (z k ) -1 p Tr Qδ → 0. To be able to exploit Theorem D.0.1, and prove Theorem 2.3.1 one ultimately needs to show that 1 p Tr Qδ is a Stieltjes transform. This is given by the next proposition. where X (1) , . . . , X (m) are m independent copies of X. We know that X (m) and all its intrinsic parameters verify the different hypothesis of Proposition 2.2.6 and we have :

note that we implicitly used the identity

As in Corollary 2.2.10, it can be shown that :

where F (m) is the spectral distribution of S (m) . Therefore, if we let m tend to infinity, for reasons that we exposed above this Proposition, we know thanks to the first result of Theorem D.0.1, that 1 p Tr Qδ is a Stieltjes transform as a limit of Stieltjes transforms on a set with an accumulative point (e.g. [z 0 , ∞)). To treat the case of 1 p Tr Qδ , one needs a similar result to (18) -it is immediate considering the definition of δ .