Walid Hachem

Philippe Loubaton

Pascal Vallet

ON BILINEAR FORMS BASED ON THE RESOLVENT OF LARGE RANDOM MATRICES

Keywords: AMS 2000 subject classification: Primary 15A52, Secondary 15A18, 60F15 Random Matrix, empirical distribution of the eigenvalues, Stieltjes Transform

Consider a N × n non-centered matrix Σn with a separable variance profile:

Matrices Dn and Dn are non-negative deterministic diagonal, while matrix An is deterministic, and Xn is a random matrix with complex independent and identically distributed random variables, each with mean zero and variance one. Denote by Qn(z) the resolvent associated to ΣnΣ * n , i.e. Qn(z) = (ΣnΣ * n -zI N ) -1 . Given two sequences of deterministic vectors (un) and (vn) with bounded Euclidean norms, we study the limiting behavior of the random bilinear form:

as the dimensions of matrix Σn go to infinity at the same pace. Such quantities arise in the study of functionals of ΣnΣ * n which do not only depend on the eigenvalues of ΣnΣ * n , and are pivotal in the study of problems related to non-centered Gram matrices such as central limit theorems, individual entries of the resolvent, and eigenvalue separation.

Introduction

The model. Consider a N × n random matrix Σ n = (ξ n ij ) given by:

Σ n = D 1 2 n X n D 1 2 n √ n + A n △ = Y n + A n , (1.1)
where D n and Dn are respectively N × N and n × n non-negative deterministic diagonal matrices. The entries of matrices (X n ), (X n ij ; i, j, n) are complex, independent and identically distributed (i.i.d.) with mean 0 and variance 1, and A n = (a n ij ) is a deterministic N × n matrix whose spectral norm is bounded in n.

The purpose of this article is to study bilinear forms based on the resolvent Q n (z) of matrix Σ n Σ * n , where Σ * n stands for the hermitian adjoint of Σ n :

Q n (z) = (Σ n Σ * n -zI N ) -1 ,
Date: August 23, 2011.

1 as the dimensions N and n grow to infinity at the same pace, that is:

0 < lim inf N n ≤ lim sup N n < ∞ , (1.2)
a condition that will be referred to as N, n → ∞ in the sequel.

A lot of attention has been devoted to the study of quadratic forms y * Ay, where y = n -1/2 (X 1 , • • • X n ) T , the X i 's being i.i.d., and A is a matrix independent from y. It is wellknown, at least since Marcenko and Pastur's seminal paper [18, Lemma 1] (see also [START_REF] Bai | No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices[END_REF]Lemma 2.7]) that under fairly general conditions, y * Ay ∼ ∞ n -1 Tr A.

Such a result is of constant use in the study of centered random matrices, as it allows to describe the behavior of the Stieltjes transform associated to the spectral measure (empirical distribution of the eigenvalues) of the matrix under investigation, see for instance [START_REF] Silverstein | Strong convergence of the empirical distribution of eigenvalues of large-dimensional random matrices[END_REF], [START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large-dimensional random matrices[END_REF], [START_REF] Hachem | The empirical distribution of the eigenvalues of a Gram matrix with a given variance profile[END_REF][START_REF] Hachem | Deterministic equivalents for certain functionals of large random matrices[END_REF], etc. Indeed, the Stieltjes transform of the spectral measure writes:

f n (z) = 1 N Tr Q n (z) = 1 N N i=1 [Q n (z)] ii (z) ,
where the [Q n (z)] ii 's denote the diagonal elements of the resolvent. Denote by ηi the ith row of Σ n and by Σ n,i matrix Σ n when row ηi has been removed, then the matrix inversion lemma yields the following expression:

[Q n (z)] ii = - 1 z 1 + ηi (Σ * n,i Σ n,i -zI) -1 η * i .
In the case where Σ n = n -1/2 X n , the quadratic form that appears in the previous expression can be handled by the aforementioned results. However, if Σ n is non-centered and given by (1.1), then the quadratic form writes:

ηi Qi (z)η * i = ỹi Qi (z)ỹ * i + ãi Qi (z)ỹ * i + ỹi Qi (z)ã * i + ãi Qi (z)ã * i , where Qi (z) = (Σ * n,i Σ n,i -zI) -1 , and ỹi and ãi are the ith rows of matrices Y n and A n . The first term can be handled as in the centered case, the second and third terms go to zero; however, the fourth term involves a quadratic form ãi Qi (z)ã * i based on deterministic vectors.

It is of interest to notice that, due to some fortunate cancellation, the particular study of bilinear forms of the type u * n Q n (z)v n or their analogues of the type ũn Qn (z)ṽ * n can be circumvented to establish first order results for non-centered random matrices (see for instance [START_REF] Dozier | On the empirical distribution of eigenvalues of large dimensional information-plus-noise-type matrices[END_REF], [START_REF] Hachem | Deterministic equivalents for certain functionals of large random matrices[END_REF]). However, such a study has to be addressed for finer questions such as: Asymptotic behavior of individual entries of the resolvent (see for instance [START_REF] Erdös | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF]Eq. (2.16)] where such properties are established in the centered Wigner case to describe fine properties of the spectrum) , Central Limit Theorems [START_REF] Kammoun | On the Fluctuations of the Mutual Information for Non Centered MIMO Channels: The Non Gaussian Case[END_REF][START_REF] Hachem | A CLT for information-theoretic statistics of non-centered gram random matrices[END_REF], behavior of the extreme eigenvalues of Σ n Σ * n , behavior of the eigenvalues and eigenvectors associated with finite rank perturbations of Σ n Σ * n [START_REF] Benaych-Georges | The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices[END_REF], behavior of eigenvectors or projectors on eigenspaces of Q(z) (see for instance [START_REF] Bai | On asymptotics of eigenvectors of large sample covariance matrix[END_REF] in the context of sample covariance (centered) model), etc.

In a more applied setting, functionals based on individual entries of the resolvent [START_REF] Artigue | On the precoder design of flat fading mimo systems equipped with mmse receivers: A large-system approach[END_REF] naturally arise in the field of wireless communication (see for instance Section 2.1). Moreover, the asymptotic study of the quadratic forms u * n Q n (z)u n is important in statistical inference problems. In the non-correlated case (where D n = I N and Dn = I n ), it is proved in [START_REF] Vallet | Improved Subspace Estimation for Multivariate Observations of High Dimension: The Deterministic Signal Case[END_REF] how such quadratic forms yield consistent estimates of projectors on the subspace orthogonal to the column space of A n in the Gaussian case (see also Section 2.2). Such projectors form the basis of MUSIC algorithm, very popular in the field of antenna array processing. A similar approach has been developed in [START_REF] Mestre | Improved Estimation of Eigenvalues and Eigenvectors of Covariance Matrices using their Sample Estimates[END_REF], [START_REF] Mestre | On the asymptotic behavior of the sample estimates of eigenvalues and eigenvectors of covariance matrices[END_REF] for sample covariance matrix models.

It is the purpose of this article to provide a quantitative description of the limiting behavior of the bilinear form u * n Q n (z)v n , where u n and v n are deterministic, as the dimensions of Σ n go to infinity as indicated in (1.2).

Assumptions, fundamental equations, deterministic equivalents. Formal assumptions for the model are stated below, where • either denotes the Euclidean norm of a vector or the spectral norm of a matrix.

Assumption A-1. The random variables (X n ij ; 1 ≤ i ≤ N, 1 ≤ j ≤ n , n ≥ 1) are complex, independent and identically distributed. They satisfy EX n ij = 0 and E|X n ij | 2 = 1. Assumption A-2. The family of deterministic N × n matrices (A n , n ≥ 1) is bounded for the spectral norm as N, n → ∞:

a max = sup n≥1 A n < ∞ .
Notice that this assumption implies in particular that the Euclidean norm of any row or column of A n is uniformly bounded in N, n.

Assumption A-3. The families of real deterministic N × N and n × n matrices (D n ) and ( Dn ) are diagonal with non-negative diagonal elements, and are bounded for the spectral norm as N, n → ∞:

d max = sup n≥1 D n < ∞ and dmax = sup n≥1 Dn < ∞ .

Moreover,

d min = inf N 1 N Tr D n > 0 and dmin = inf n 1 n Tr Dn > 0 .
We collect here results from [START_REF] Hachem | Deterministic equivalents for certain functionals of large random matrices[END_REF].

The following system of equations:

       δ(z) = 1 n Tr D n -z(I N + δ(z)D n )I N + A n I n + δ(z) Dn -1 A * n -1 δ(z) = 1 n Tr Dn -z(I n + δ(z) Dn ) + A * n I N + δ(z)D n -1 A n -1 , z ∈ C -R + (1.
3) admits a unique solution (δ, δ) in the class of Stieltjes transforms of nonnegative measures 1 with support in R + . Matrices T n (z) and Tn (z) defined by

       T n (z) = -z(I N + δ(z)D n ) + A n I n + δ(z) Dn -1 A * n -1 Tn (z) = -z(I n + δ(z) Dn ) + A * n I N + δ(z)D n -1 A n -1
(1.4)

1 In fact, δ and δ are the Stieltjes transforms of measures with respective total mass n -1 Tr Dn and n -1 Tr Dn.

are approximations of the resolvent Q n (z) and the co-resolvent Qn (z) = (Σ * n Σ n -zI N ) -1 in the sense that ( a.s.

--→ stands for the almost sure convergence):

1 N Tr (Q n (z) -T n (z))
a.s.

-----→ N,n→∞ 0 , which readily gives a deterministic approximation of the Stieltjes transform N -1 Tr Q n (z) of the spectral measure of Σ n Σ * n in terms of T n (and similarly for Qn and Tn ). Matrices T n and Tn will play a fundamental role in the sequel.

Nice constants and nice polynomials. By nice constants, we mean positive constants which depend upon the limiting quantities d min , dmin , d max , dmax , a max , lim inf N n and lim sup N n but are independent from n and N . Nice polynomials are polynomials with fixed degree (which is a nice constant) and with non-negative coefficients, each of them being a nice constant. Further dependencies are indicated if needed.

Statement of the main result. Let δ z be the distance between the point z ∈ C and the real nonnegative axis R + :

δ z = dist(z, R + ) . (1.5)
Here is the main result of the paper:

Theorem 1.1. Assume that N, n → ∞ and that assumptions A-1, A-2 and A-3 hold true. Assume moreover that there exists an integer p ≥ 1 such that

sup n E|X n ij | 8p < ∞ and let (u n ) and (v n ) be sequences of N × 1 deterministic vectors. Then, for every z ∈ C -R + , E |u * n (Q n (z) -T n (z)) v n | 2p ≤ 1 n p Φ p (|z|)Ψ p 1 δ z u n 2p v n 2p , (1.6)
where Φ p and Ψ p are nice polynomials depending on p but not on (u n ) neither on (v n ).

Remark 1.1. Apart from providing the convergence speed O(n -p ), inequality (1.6) provides a fine control of the behavior of E|u * (Q -T )v| 2p when z is near the real axis. Such a control should be helpful for studying the behavior of the extreme eigenvalues of Σ n Σ * n along the lines of [START_REF] Bai | No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices[END_REF] and [START_REF] Bai | Exact separation of eigenvalues of large-dimensional sample covariance matrices[END_REF].

Remark 1.2. Influence of the eigenvectors of AA * on the limiting behavior of u * Qu. Consider a matrix Σ with no variance profile (D = I N , D = I n ) and let T be given by (1.4). Matrix T writes in this case:

T = -z(1 + δ)I + AA * 1 + δ -1
.

Denote by V ∆V * the spectral decomposition of AA * , and by T ∆ :

T ∆ = -z(1 + δ)I + ∆ 1 + δ -1 . Obviously, T = V T ∆ V * and by Theorem 1.1, u * Qu -u * V T ∆ V * u → 0 .
Clearly, the limiting behavior of u * Qu not only depends on the spectrum (matrix ∆) of AA * but also on its eigenvectors (matrix V ).

Contents. In Section 2, we describe two important motivations from electrical engineering. In Section 3, we set up the notations, state intermediate results among which Lemma 3.6, which is the cornerstone of the paper. Loosely speaking, this lemma whose idea can be found in the work of Girko [START_REF] Girko | An introduction to statistical analysis of random arrays[END_REF] states that quantities such as

n i=1 u * Q i a i a * i Q i u
are bounded. This control turns out to be central to take into account Assumption A-2. An intermediate deterministic matrix R n is introduced and the proof of Theorem 1.1 is outlined.

Basically, the quantity of interest u * (Q -T )v is split into three parts:

u * (Q -T )v = u * (Q -EQ)v + u * (EQ -R)v + u * (R -T )v ,
each being studied separately.

In Section 4, the proof of estimate of u * (Q-EQ)v is established, based on a decomposition of Q -EQ as a sum of martingale increments. Section 5 is devoted to the proof of estimate of u * (EQ -R)v; and Section 6, to the proof of estimate of u * (R -T )v.

Acknowledgment. This work was partially supported by the Agence Nationale de la Recherche (France), project SESAME n • ANR-07-MDCO-012-01.

Two applications to electrical engineering

Apart from the technical motivations already mentionned in the introduction, Theorem 1.1 has further applications in electrical engineering. In this section, we present an application to Multiple Input Multiple Output (MIMO) wireless communication systems, and an application to statistical signal processing.

2.1. Optimal precoder in MIMO systems. A bi-correlated MIMO wireless Ricean channel is a N × n random matrix H n given by

H n = B n + R 1/2 n V n √ n R1/2 n ,
where B n is a deterministic matrix, V n is a standard complex Gaussian matrix, and where R n and Rn represent deterministic positive N × N and n × n matrices. An important related question is the determination of a precoder maximizing the so-called capacity after mininum mean square error detection (for more details on the application context, see [START_REF] Artigue | On the precoder design of flat fading mimo systems equipped with mmse receivers: A large-system approach[END_REF]).

Mathematically, this problem is equivalent to the evaluation of a deterministic N × N matrix K n maximizing the function I mmse (K n ) defined on the set of all complex valued N × N matrices by

I mmse (K n ) = E N j=1 log (I + K n H n H * n K * n ) -1 j,j (2.1)
under the constraint 1 N Tr(K n K * n ) ≤ a (a > 0)
. This optimization problem has no closed form solution and one must rely on numerical computations. However, direct numerical attempts such as optimization by steepest descent algorithms or Monte-Carlo simulations to evaluate I mmse (K n ) before optimization, or any combination of these techniques, face major difficulties, among which: Hardly tractable expressions for I mmse (K n ), and for its first and second derivatives, computationally intensive algorithms when relying on Monte-Carlo simulations.

If N and n are large enough, an alternative approach consists in deriving a large system approximation I mmse (K n ) of I mmse (K n ) which, hopefully, is simpler to optimize w.r.t. K n . This idea has been successfully developed in [START_REF] Artigue | On the precoder design of flat fading mimo systems equipped with mmse receivers: A large-system approach[END_REF], in the case where B n = 0, and in [START_REF] Dumont | On the Capacity Achieving Covariance Matrix for Rician MIMO Channels: An Asymptotic Approach[END_REF] in a slightly different context, where the functional under consideration is the Shannon capacity

I s (K n ) = E log det (I + K n H n H * n K * n ).
In the remainder of this section, we consider the case where B n = 0 and briefly indicate how Theorem 1.1 comes into play. First remark that for every deterministic matrix K n , the random matrix K n H n writes:

K n H n = K n B n + (K n R n K * n ) 1/2 W n √ n R1/2 n where W n is standard Gaussian random matrix (notice that (K n R n K * n ) -1/2 K n R 1/2 n is uni- tary).
Using the eigenvalue/eigenvector decomposition of matrices K n R n K * n and Rn , the unitary invariance of the canonical equations (1.3), and Theorem 1.1, one can easily check that the diagonal entries of (I + K n H n H * n K * n ) -1 have the same asymptotic behaviour (when (n, N ) → ∞) as those of the deterministic matrix T n (K n ) defined by:

T n (K n ) = (I + δ(K n )K n R n K * n ) + K n B n (I + δ(K n ) Rn ) -1 B * n K * n -1
, where δ(K n ) and δ(K n ) are the (unique) positive solutions of the system:

     δ(K n ) = 1 n TrK n R n K * n (I + δ(K n )K n R n K * n ) + K n B n (I + δ(K n ) Rn ) -1 B * n K * n -1 δ(K n ) = 1 n Tr Rn (I + δ(K n ) Rn ) + B * n K * n (I + δ(K n )K n R n K * n ) -1 K n B n -1
.

(2.2) From this, it appears that I mmse (K n ) can be approximated by I mmse (K n ) given by:

I mmse (K n ) = N j=1 log (I + δ(K n )K n R n K * n ) + K n B n (I + δ(K n ) Rn ) -1 B * n K * n -1 j,j
Although the values taken by function K n → I mmse (K n ) are defined through the implicit equations (2.2), the first and second derivatives of I mmse are easy to compute, and the minimization of I mmse instead of I mmse certainly leads to a computationally attractive algorithm.

A number of important related questions remain to be addressed, e.g. the accuracy of the approximation I mmse (K n ), its impact on the error on the optimum solution, the derivation of a more accurate approximation as in [START_REF] Artigue | On the precoder design of flat fading mimo systems equipped with mmse receivers: A large-system approach[END_REF], the development of an efficient algorithm to compute the optimal K * n , etc.; however this already underlines promising applications of Theorem 1.1 in the context of wireless communication.

Statistical signal processing applications.

There are many important applications such as source localization using antenna arrays, communication channel estimation, detection of signals corrupted by additive noise, etc. where the observations are stacked into a matrix Σ n given by (1.1) in which A n is a non observable deterministic matrix modelling the information to be retrieved and where Y n is due to an additive noise. It is therefore often relevant to estimate certain functionals of matrix A n from Σ n . In this section, we show how Theorem 1.1 is valuable and relevant in the context of subspace estimators when N and n are of the same order of magnitude.

Subspace estimation. Assume that N n < 1, D n = I N and Dn = I n (white noise); assume also that matrix Rank(A n ) = r < N where r may scale or not with the dimensions n and N . Denote by Π n the orthogonal projection on the kernel of matrix A n . The subspace estimation methods are based on the estimation of quadratic forms u * n Π n u n where (u n ) n∈N represents a sequence of unit norm deterministic N -dimensional vectors.

If N if fixed while n → +∞, it is well known that Σ n Σ * n -(A n A * n + I) → 0.
Hence, if Πn represents the orthogonal projection matrix on the eigenspace associated to the N -r smallest eigenvalues of Σ n Σ * n , then Πn -Π n → 0 and thus

u * n Πn u n -u * n Π n u n ---------→ n→∞, N fixed 0 . (2.3)
In order to model situations in which n and N are large and of the same order of magnitude, it is relevant to look for estimators consistent in the regime given by (1.2). Unfortunately, (2.3) is no longer valid in this context.

An estimator for large N, n. The starting point of the estimator proposed in [START_REF] Vallet | Improved Subspace Estimation for Multivariate Observations of High Dimension: The Deterministic Signal Case[END_REF], inspired by [START_REF] Mestre | Modified subspace algorithms for doa estimation with large arrays[END_REF], is based on the observation that Π n writes:

Π n = 1 2iπ C - (A n A * n -λI) -1 dλ ,
where C -is a clockwise oriented contour enclosing 0 but not the non-zero eigenvalues of

A n A * n .
In the white noise case, matrix T n (z) writes:

T n (z) = (1 + δ n (z)) (A n A * n -w n (z)I) -1
, where w n (z) is the function defined by w n (z) = z(1 + δ n (z))(1 + δn (z)). It is shown in [START_REF] Vallet | Improved Subspace Estimation for Multivariate Observations of High Dimension: The Deterministic Signal Case[END_REF] that (under additional assumptions) such a contour C -is the image under w n of the boundary ∂R y of the rectangle R y = {z = x + iv, x ∈ [x -, x + ], |v| ≤ y} for well-chosen x - and x + . A simple change of variable argument therefore yields the following formula for Π n :

Π n = 1 2iπ ∂R - y (A n A * n -w n (z)I) -1 w ′ n (z)dz = 1 2iπ ∂R - y T n (z) w ′ n (z) 1 + δ n (z) dz .
Hence, u * n Π n u n is given by:

u * n Π n u n = 1 2iπ ∂R - y u * n T n (z)u n w ′ n (z) 1 + δ n (z) dz . (2.4)
Eq. (2.4) is particularly interesting because all the terms in the integrand admit consistent estimators: Quantities δ n (z) and δn (z) can be estimated by δn

(z) = 1 n Tr(Q n (z)) and δn (z) = 1 n Tr( Qn (z)), w ′ n (z) can be estimated by the derivative of ŵn (z) = z(1 + δn (z))(1 + δn (z)); finally, Theorem 1.1 implies that u * n Q n (z)u n -u * n T n (z)u n → 0 for N, n → ∞. A reasonnable estimator for Π n should therefore be Πn = 1 2iπ ∂R - y Q n (z) ŵ′ n (z) 1 + δn (z) dz (2.5)
and it should be expected that u

* n Πn u n -u * n Π n u n → 0 for N, n → ∞.
Remaining mathematical issues. The full definition of Πn requires to prove that none of the poles of the integrand of the r.h.s. of (2.5) can be equal to x -or x + . Otherwise, the mere definition of Πn does not make sense. This problem has been solved in the Gaussian case in [START_REF] Vallet | Improved Subspace Estimation for Multivariate Observations of High Dimension: The Deterministic Signal Case[END_REF]. In the non Gaussian case, partial results concerning "no eigenvalue separation for the signal plus noise model" [START_REF] Bai | No Eigenvalues Outside the Support of the Limiting Spectral Distribution of Information-Plus-Noise Type Matrices[END_REF] together with Theorem 1.1 tend to indicate that the estimator u * n Πn u n is also consistent.

3. Notations, preliminary results and sketch of proof

As usual, R + = {x ∈ R : x ≥ 0} and C + = {z ∈ C : Im(z) > 0}; similarly C -= {z ∈ C : Im(z) < 0}; i = √ -1; if z ∈ C
, then z stands for its complex conjugate. Denote by P -→ the convergence in probability of random variables and by D -→ the convergence in distribution of probability measures. Denote by diag(a i ; 1 ≤ i ≤ k) the k × k diagonal matrix whose diagonal entries are the a i 's. Element (i, j) of matrix M will be either denoted

m ij or [M ] ij depending on the notational context. if M is a n × n square matrix, diag(M ) = diag(m ii ; 1 ≤ i ≤ n).
Denote by M T the matrix transpose of M , by M * its Hermitian adjoint, by Tr (M ) its trace and det(M ) its determinant (if M is square). We shall use Landau's notation: By

a n = O(b n ), it is meant that there exists a nice constant K such that |a n | ≤ K|b n | as N, n → ∞.
Recall that when dealing with vectors, • will refer to the Euclidean norm; in the case of matrices, • will refer to the spectral norm.

Due to condition (1.2), we can assume (without loss of generality) that there exist 0 < ℓ

-≤ ℓ + < ∞ such that ∀N, n ∈ N * , ℓ -≤ N n ≤ ℓ + .
We may drop occasionally subscripts and superscripts n for readability.

Denote by Y the N × n matrix n -1/2 D 1/2 X D1/2 ; by (η j ), (a j ), (x j ) and (y j ) the columns of matrices Σ, A, X and Y . Denote by Σ j , A j and Y j , the matrices Σ, A and Y where column j has been removed. The associated resolvent is

Q j (z) = (Σ j Σ * j -zI N ) -1 .
Denote by E j the conditional expectation with respect to the σ-field F j generated by the vectors (y ℓ , 1 ≤ ℓ ≤ j). By convention, E 0 = E. Denote by E yj the conditional expectation with respect to the σ-field generated by the vectors (y ℓ , ℓ = j).

Classical and useful results.

We remind here classical identities of constant use in the sequel. The first one expresses the diagonal elements of the co-resolvent; the other ones are based on low-rank perturbations of inverses (see for instance [START_REF] Horn | Topics in matrix analysis[END_REF]Sec. 0.7.4]).

Diagonal elements of the co-resolvent; rank-one perturbation of the resolvent.

qjj (z) = - 1 z(1 + η * j Q j (z)η j ) , (3.1)
Q(z) = Q j (z) - Q j (z)η j η * j Q j (z) 1 + η * j Q j η j , (3.2)
Q j (z) = Q(z) + Q(z)η j η * j Q(z) 1 -η * j Qη j , (3.3
) 1 + η * j Q j η j = 1 1 -η * j Qη j . (3.4)
A useful consequence of (3.2) is:

η * j Q(z) = η * j Q j (z) 1 + η * j Q j (z)η j = -z qjj (z)η * j Q j (z) . (3.5) Recall that δ z = dist(z, R + ). Considering the eigenvalues of Q(z) immediately yields Q(z) ≤ δ -1 z .
Taking into account the fact that

- 1 z(1 + n -1 dj Tr Q j + a * j Q j a j ) and - 1 z(1 + η * j Q j η j )
are Stieltjes transforms of probability measures over R + , and based on standard properties of Stieltjes transforms (see for instance [15, Proposition 2.2]), we readily obtain the following estimates:

1 1 + dj n Tr DQ j + a * j Q j a j ≤ |z| δ z and 1 1 + η * j Q j η j ≤ |z| δ z , ∀z ∈ C -R + . (3.6)
The following lemma describes the behavior of quadratic forms based on random vectors (see for instance [4, Lemma 2.7]).

Lemma 3.1. Let x = (x 1 , • • • , x n ) be a n×1 vector where the x i 's are centered i.i.d. complex random variables with unit variance; consider p ≥ 2 and assume that E|x 1 | 2p < ∞. Let M = (m ij ) be a n × n complex matrix independent of x. Then there exists a constant K p such that

E |x * M x -Tr M | p ≤ K p (Tr M M * ) p/2 . Let u ∈ C n be deterministic, then E|x * u| p = O( u p ). Moreover, E x p = O(n p/2 ) . Note by D = diag(d i ; 1 ≤ i ≤ N ) and D = diag( di ; 1 ≤ i ≤ n).
Gathering the previous estimates yields the following useful corollary:

Corollary 3.2. Let z ∈ C -R + ,
and let p ≥ 2. Denote by ∆ j the quantity:

∆ j = η * j Q j η j - dj n Tr DQ j -a * j Q j a j .
Then

E yj |∆ j | p = O 1 n p/2 δ p z .
Theorem 3.3 (Burkholder inequality). Let (X k ) be a complex martingale difference sequence with respect to the filtration (F k ). For every p ≥ 1, there exists K p such that:

E n k=1 X k 2p ≤ K p E n k=1 E |X k | 2 | F k-1 p + n k=1 E|X k | 2p .
A result on holomorphic functions: Lemma 3.4 (Part of Schwarz's lemma, Th.12.2 in [START_REF] Rudin | Real and Complex Analysis[END_REF]). Let f be an holomorphic function on the open unit disc U such that f (0) = 0 and

sup z∈U |f (z)| ≤ 1. Then |f (z)| ≤ |z| for every z ∈ U .
Rules about nice polynomials and nice constants. Some very simple rules of calculus related to nice polynomials will be particularly helpful in the sequel:

If (Φ k , 1 ≤ k ≤ K) and (Ψ k , 1 ≤ k ≤ K) are
nice polynomials, then there exist nice polynomials Φ and Ψ such that:

K k=1 Φ k (x)Ψ k (y) ≤ Φ(x)Ψ(y) for x, y > 0. (3.7) Take for instance Φ(x) = K k=1 Φ k (x) and Ψ(x) = K k=1 Ψ k (x).
If Φ 1 and Ψ 1 are nice polynomials, then there exist nice polynomials Φ and Ψ such that:

Φ 1 (x)Ψ 1 (y) ≤ Φ(x)Ψ(y) for x, y > 0. ( 3.8)
Take for instance Φ = 2 -1 (1 + Φ 1 ) and Ψ = (1 + Ψ 1 ) and note that:

Φ 1 (x)Ψ 1 (y) ≤ 1 2 (1 + Φ 1 (x)Ψ 1 (y)) ≤ (1 + Φ 1 (x)) 2 (1 + Ψ 1 (y)) .
The values of nice constants or nice polynomials may change from line to line within the proofs, the constant or the polynomial remaining nice.

Important estimates.

Lemma 3.5. Assume that the setting of Theorem 1.1 holds true. Let u be a deterministic complex N × 1 vector. Then, for every z ∈ C -R + , the following estimates hold true:

E   n j=1 E j-1 u * Qa j a * j Q * u   p ≤ K p u 2p δ 2p z , (3.9)
E   n j=1 E j-1 u * Qη j η * j Q * u   p ≤ Kp |z| p u 2p δ 2p z , (3.10)
where K p and Kp are nice constants depending on p but not on u .

Proof of Lemma 3.5 is postponed to Appendix A.

Lemma 3.6. Assume that the setting of Theorem 1.1 holds true. Let u be a deterministic complex N × 1 vector. Then, for every z ∈ C -R + , the following estimates hold true:

n j=1 E u * Q j a j a * j Q * j u 2 ≤ Φ(|z|)Ψ 1 δ z u 4 , (3.11) E   n j=1 E j-1 u * Q j a j a * j Q * j u   p ≤ Φ(|z|) Ψ 1 δ z u 2p , (3.12)
where Φ, Ψ, Φ and Ψ are nice polynomials not depending on u .

Proof of Lemma 3.6 is postponed to Appendix A.

In order to proceed, it is convenient to introduce the following intermediate quantities

(z ∈ C -R + ): α n (z) = 1 n Tr D n EQ n (z), αn (z) = 1 n Tr Dn E Qn (z), (3.13) R n (z) = -z(I N + α(z)D n )I N + A n I n + α(z) Dn -1 A * n -1 , (3.14)
Rn (z) = -z(I n + α(z) Dn ) + A * n (I N + α(z)D n ) -1 A n -1 . (3.15)
A slight modification of the proof of [15, Proposition 5.1-(3)] yields the following estimates:

R n (z) ≤ 1 δ z , Rn (z) ≤ 1 δ z for z ∈ C -R + .
The same estimates hold true for T n (z) and Tn (z) .

3.4. Main steps of the proof. In order to prove Theorem 1.1, we split the quantity of interest u * (Q -T )u into three parts:

u * (Q -T )v = u * (Q -EQ)v + u * (EQ -R)v + u * (R -T )v ,
and handle each term separately in the following propositions:

Proposition 3.7. Assume that the setting of Theorem 1.1 holds true. Let (u n ) and (v n ) be sequences of N × 1 deterministic vectors. Then, for every

z ∈ C -R + , E |u * n (Q n (z) -EQ n (z)) v n | 2p ≤ 1 n p Φ p (|z|)Ψ p 1 δ z u n 2p v n 2p ,
where Φ p and Ψ p are nice polynomials depending on p but not on (u n ) nor on (v n ).

Proposition 3.7 is proved in Section 4.

Proposition 3.8. Assume that the setting of Theorem 1.1 holds true.

(i) Let (u n ) and (v n ) be sequences of N × 1 deterministic vectors. Then, for every z ∈ C -R + , |u * n (EQ n (z) -R n (z)) v n | ≤ 1 √ n Φ(|z|)Ψ 1 δ z u n v n ,
where Φ and Ψ are nice polynomials, not depending on (u n ) nor on (v n ).

(ii) Let M n be a N × N deterministic matrix. Then, for every z ∈ C -R + ,

1 n Tr M n EQ n (z) - 1 n Tr M n R n (z) ≤ 1 n Φ(|z|)Ψ 1 δ z M n ,
where Φ and Ψ are nice polynomials, not depending on M n .

Proposition 3.8-(i) is proved in Section 5; proof of Proposition 3.8-(ii) is very similar and thus omitted. Proposition 3.9. Assume that the setting of Theorem 1.1 holds true. Let (u n ) and (v n ) be sequences of N × 1 deterministic vectors.

Then, for every

z ∈ C -R + , |u * n (R n (z) -T n (z)) v n | ≤ 1 n Φ(|z|)Ψ 1 δ z u n v n ,
where Φ and Ψ are nice polynomials, not depending on (u n ) nor on (v n ).

Proposition 3.9 is proved in Section 6.

Theorem 1.1 is then easily proved using these three propositions together with inequality |x + y + z| 2p ≤ K p (|x| 2p + |y| 2p + |z| 2p ) and (3.7).

Proof of Proposition 3.7

Recall the decomposition:

u * (Q -T )v = u * (Q -EQ)v + u * (EQ -R)v + u * (R -T )v .
In this section, we establish the estimate:

E |u * (Q(z) -EQ(z)) v| 2p ≤ 1 n p Φ p (|z|)Ψ p 1 δ z u 2p v 2p , ∀z ∈ C -R + . (4.1)
4.1. Reduction to unit vectors and quadratic forms. Using a polarization identity, it is sufficient in order to establish estimate (4.1) for the bilinear form u * (Q -EQ)v to establish the related estimate for the quadratic form u * (Q -EQ)u and for unit vectors u (just consider u/ u if necessary):

E |u * (Q(z) -EQ(z)) u| 2p ≤ 1 n p Φ p (|z|)Ψ p 1 δ z . (4.2)
4.2. Martingale difference sequence and Burkholder inequality. We first express the difference u * (Q -EQ)u as the sum of martingale difference sequences:

u * (Q -EQ)u = n j=1 (E j -E j-1 )(u * Qu) = n j=1 (E j -E j-1 )(u * (Q -Q j )u) = - n j=1 (E j -E j-1 ) u * Q j η * j η j Q j u 1 + η * j Q j η j △ = - n j=1 (E j -E j-1 )Γ j .
One can easily check that ((E j -E j-1 )Γ j ) is the sum of a martingale difference sequence with respect to the filtration (F j , j ≤ n); hence Burkholder's inequality yields:

E n j=1 (E j -E j-1 )Γ j 2p ≤ K   E n j=1 E j-1 |(E j -E j-1 )Γ j | 2 p + n j=1 E |(E j -E j-1 )Γ j | 2p   . (4.3)
Recall the definition of ∆ j = η * j Q j η j -n -1 dj Tr DQ j -a * j Q j a j . In order to control the right-hand side of Burkholder's inequality, we write Γ j as:

Γ j = u * Q j η * j η j Q j u 1 + η * j Q j η j = u * Q j η * j η j Q j u 1 + η * j Q j η j × 1 + dj n Tr DQ j + a * j Q j a j 1 + dj n Tr DQ j + a * j Q j a j = u * Q j η * j η j Q j u 1 + η * j Q j η j × 1 + η * j Q j η j -∆ j 1 + dj n Tr DQ j + a * j Q j a j △ = Γ 1j -Γ 2j ,
where

Γ 1j = u * Q j η j η * j Q j u 1 + dj n Tr DQ j + a * j Q j a j and Γ 2j = Γ j ∆ j 1 + dj n Tr DQ j + a * j Q j a j . (4.4)
In the following proposition, we establish relevant estimates.

Proposition 4.1. Assume that the setting of Theorem 1.1 holds true. There exist nice polynomials (Φ i , 1 ≤ i ≤ 4) and (Ψ i , 1 ≤ i ≤ 4) such that the following estimates hold true:

E n j=1 E j-1 |(E j -E j-1 )Γ 1j | 2 p ≤ 1 n p Φ 1 (|z|)Ψ 1 1 δ z , (4.5)
n j=1 E |(E j -E j-1 )Γ 1j | 2p ≤ 1 n p Φ 2 (|z|)Ψ 2 1 δ z , (4.6)
E n j=1 E j-1 |(E j -E j-1 )Γ 2j | 2 p ≤ 1 n p Φ 3 (|z|)Ψ 3 1 δ z , (4.7
)

n j=1 E |(E j -E j-1 )Γ 2j | 2p = 1 n p Φ 4 (|z|)Ψ 4 1 δ z . (4.8)
It is now clear that the proof of Proposition 3.7 directly follows from Burkholder's inequality together with the estimates of Proposition 4.1. The rest of the section is devoted to the proof of Proposition 4.1.

4.3.

Proof of Proposition 4.1: Estimates (4.5) and (4.6). We split Γ 1j as Γ 1j = χ 1j + χ 2j + χ 3j , where:

χ 1j = u * Q j y j y * j Q j u 1 + dj n Tr DQ j + a * j Q j a j , χ 2j = y * j Q j uu * Q j a j 1 + dj n Tr DQ j + a * j Q j a j + a * j Q j uu * Q j y j 1 + dj n Tr DQ j + a * j Q j a j , χ 3j = u * Q j a j a * j Q j u 1 + dj n Tr DQ j + a * j Q j a j .
Notice that (E j -E j-1 )(χ 3j ) = 0, hence χ 3j will play no further role in the sequel. As Q j is independent from column y j , we have:

(E j -E j-1 )(χ 1j ) = dj n E j   x * j D 1/2 Q j uu * Q j D 1/2 x j -Tr DQ j uu * Q j 1 + dj n Tr DQ j + a * j Q j a j   , (4.9)
and

E j-1 |(E j -E j-1 )(χ 1j )| 2 (a) ≤ d 2 max n 2 × E j-1 x * j D 1/2 Q j uu * Q j D 1/2 x j -Tr DQ j uu * Q j 1 + dj n Tr DQ j + a * j Q j a j 2 , (b)
≤ d 2 max n 2 |z| 2 δ 2 z × E j-1 E yj x * j D 1/2 Q j uu * Q j D 1/2 x j -Tr DQ j uu * Q j 2 (c) ≤ K d 2 max n 2 |z| 2 δ 2 z × E j-1 Tr D 1/2 Q j uu * Q j D 1/2 D 1/2 Q * j uu * Q * j D 1/2 = O |z| 2 n 2 δ 6 z , (4.10)
where (a) follows from Jensen's inequality, (b) from estimate (3.6), and (c) from Lemma 3.1. Thus

E n j=1 E j-1 |(E j -E j-1 )(χ 1j )| 2 p = O |z| 2p n p δ 6p z . (4.11)
We now turn to the contribution of χ 2j . Arguments similar as previously yield:

E j-1 |(E j -E j-1 )(χ 2j )| 2 = E j-1 |E j χ 2j | 2 ≤ E j-1 |χ 2j | 2 ≤ 2 n E j-1    x * j D 1/2 Q j uu * Q j a j 1 + dj n Tr DQ j + a * j Q j a j 2 + a * j Q j uu * Q j D 1/2 x j 1 + dj n Tr DQ j + a * j Q j a j 2    , ≤ 2 n |z| 2 δ 2 z E j-1 E yj (x * j D 1/2 Q j uu * Q * j D 1/2 x j ) × u * Q j a j a * j Q * j u +E yj (x * j D 1/2 Q * j uu * Q j D 1/2 x j ) × u * Q * j a j a * j Q j u , ≤ K n |z| 2 δ 4 z E j-1 u * Q * j a j a * j Q j u + E j-1 u * Q j a j a * j Q * j u . (4.12)
Now, using Eq. (3.12) in Lemma 3.6 yields:

E n j=1 E j-1 |(E j -E j-1 )(χ 2j )| 2 p ≤ 1 n p Φ(|z|)Ψ 1 δ z . (4.13)
Hence, gathering (4.11) and (4.13) yields estimate (4.5).

We now establish estimate (4.6). As previously, consider identity (4.9); take it this time to the power p. Using the same arguments as for (4.10), we obtain:

E |(E j -E j-1 )(χ 1j )| 2p = O |z| 2p n 2p δ 6p z ,
hence:

E n j=1 |(E j -E j-1 )(χ 1j )| 2p = O |z| 2p n 2p-1 δ 6p z .
(4.14)

Similarly, using the same arguments as in (4.12), together with elementary manipulations, we obtain:

E j-1 |(E j -E j-1 )(χ 2j )| 2p ≤ K n p |z| 2p δ 4p z E j-1 u * Q * j a j a * j Q j u p + E j-1 u * Q j a j a * j Q * j u p .
Due to the rough estimate (A.1), we obtain

E |(E j -E j-1 )(χ 2j )| 2p ≤ K n p |z| 2p δ 6p-4 z E u * Q * j a j a * j Q j u 2 + E u * Q j a j a * j Q * j u 2 ,
which after summation, and the estimate obtained in Lemma 3.6, yields:

E n j=1 |(E j -E j-1 )(χ 2j )| 2p ≤ 1 n p Φ ′ (|z|)Ψ ′ 1 δ z , ( 4
χ 1j = ∆ j × u * Q j a j a * j Q j u (1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j ) , χ 2j = ∆ j × u * Q j y j y * j Q j u (1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j ) , χ 3j = ∆ j × u * Q j y j a * j Q j u + u * Q j a j y * j Q j u (1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j )
.

Consider first:

E j-1 |(E j -E j-1 )(χ 1j )| 2 ≤ 2E j-1 |χ 1j | 2 (a) ≤ K|z| 4 δ 4 z E j-1 u * Q j a j a * j Q j u y * j Q j y j -n -1 dj Tr DQ j 2 + K|z| 4 δ 4 z E j-1 u * Q j a j a * j Q j u y * j Q j a j + a * j Q j y j 2 , (b) ≤ K|z| 4 n 2 δ 6 z E j-1 u * Q j a j a * j Q * j u E yj x * j D 1/2 Q j D 1/2 x j -Tr DQ j 2 + K|z| 4 n δ 6 z E j-1 u * Q j a j a * j Q * j u E yj (x * j D 1/2 Q j a j a * j Q * j D 1/2 x j ) + K|z| 4 n δ 6 z E j-1 u * Q j a j a * j Q * j u E yj (x * j D 1/2 Q * j a j a * j Q j D 1/2 x j ) (c) ≤ K|z| 4 n δ 8 z E j-1 (u * Q j a j a * j Q * j u) ,
where (a) follows from (3.6), (b) from the fact that

|u * Q j a j a * j Q j u| ≤ Kδ -2 z and |u * Q j a j a * j Q * j u| ≤ Kδ -2
z , and (c) from Lemma 3.1. From this and Lemma 3.6, we deduce that:

E   n j=1 E j-1 |(E j -E j-1 )(χ 1j )| 2   p ≤ 1 n p Φ(|z|)Ψ 1 δ z . (4.16)
Consider now: Hence,

E j-1 |(E j -E j-1 )(χ 2j )| 2 (a) ≤ 2E j-1 |χ 2j | 2 (b) ≤ K|z| 4 δ 4 z E j-1 y * j Q j u 4 |∆ j |
E   n j=1 E j-1 |(E j -E j-1 )(χ 2j )| 2   p = O |z| 4p n 2p δ 10p z .
Similarly, one can prove that:

E   n j=1 E j-1 |(E j -E j-1 )(χ 3j )| 2   p = O |z| 4p n p δ 10p z .
Gathering the previous results yields the bound:

E   n j=1 E j-1 |(E j -E j-1 )(Γ 2j )| 2   p ≤ 1 n p Φ ′ (|z|)Ψ ′ 1 δ z .
We now evaluate the second part of Burkholder's inequality (and may re-use notations Φ and Ψ for different polynomials).

n j=1 E |(E j -E j-1 )(χ 1j )| 2p ≤ K|z| 4p δ 4p z n j=1 E u * Q j a j a * j Q * j u 2p E yj |∆ j | 2p (a) ≤ K|z| 4p n p δ 6p z n j=1 E u * Q j a j a * j Q * j u 2 u * Q j a j a * j Q * j u 2p-2 ≤ K|z| 4p n p δ 10p-4 z n j=1 E u * Q j a j a * j Q * j u 2 ≤ 1 n p Φ(|z|)Ψ 1 δ z ,
where (a) follows from Corollary 3.2 and the last estimate, from Lemma 3.6. Similar computations yield:

n j=1 E |(E j -E j-1 )(χ 2j )| 2p ≤ 1 n 3p-1 Φ ′ (|z|)Ψ ′ 1 δ z , n j=1 E |(E j -E j-1 )(χ 3j )| 2p ≤ 1 n 2p-1 Φ ′′ (|z|)Ψ ′′ 1 δ z ,
the first of these inequalities requiring the assumption sup n E|X n ij | 8p < ∞ in the statement of Theorem 1.1. Gathering these three results yields:

n j=1 E |(E j -E j-1 )(Γ 2j )| 2p ≤ 1 n p Φ(|z|) Ψ 1 δ z ,
and Proposition 4.1 is proved.

Proof of Proposition 3.8

Recall the decomposition:

u * (Q -T )v = u * (Q -EQ)v + u * (EQ -R)v + u * (R -T )v .
In this section, we establish the estimate:

|u * (EQ(z) -R(z)) v| ≤ 1 √ n Φ(|z|)Ψ 1 δ z u v ,
The argument referred to in Section (4.1) still holds true here; therefore it is sufficient to establish, for z ∈ C -R + and for a unit vector u:

|u * (EQ(z) -R(z)) u| ≤ 1 √ n Φ(|z|)Ψ 1 δ z , (5.1)
Recalling that R = -z(I + αD) + A(I

+ α D) -1 A * -1
, the resolvent identity yields:

u * (R -Q)u = u * R(Q -1 -R -1 )Qu , = u * R ΣΣ * -A(I + α D) -1 A * Qu + z αu * RDQu , = u * R   n j=1 η j η * j - n j=1 a j a * j 1 + α dj   Qu + z αu * RDQu , (a) = n j=1 u * Rη j η * j Q j u 1 + η * j Q j η j - n j=1 u * Ra j a * j Q j u 1 + α dj + n j=1 u * Ra j a * j Q j η j η * j Q j u (1 + η * j Q j η j )(1 + α dj ) - n j=1 dj n E 1 1 + η * j Q j η j u * RDQu , △ = n j=1 Z j .
where (a) follows from (3.2) and (3.5), together with the mere definition of α.

As usual, we now write η j = y j + a j , group the terms that compensate one another and split Z j accordingly:

Z j = Z 1j + Z 2j + Z 3j + Z 4j ,
where

Z 1j = y * j Q j uu * Ry j 1 + η * j Q j η j - dj n E 1 1 + η * j Q j η j u * RDQu , Z 2j = (α dj -y * j Q j y j )u * Ra j a * j Q j u (1 + η * j Q j η j )(1 + α dj ) , Z 3j = y * j Q j ua * j Q j y j × u * Ra j (1 + η * j Q j η j )(1 + α dj ) , Z 4j = u * Ry j a * j Q j u + u * Ra j y * j Q j u 1 + η * j Q j η j - y * j Q j a j u * Ra j a * j Q j u + a * j Q j y j u * Ra j a * j Q j u (1 + η * j Q j η j )(1 + α dj ) + u * Ra j a * j Q j a j y * j Q j u + u * Ra j a * j Q j y j a * j Q j u (1 + η * j Q j η j )(1 + α dj )
Now, the estimate (5.1) immediately follows from similar estimates for the terms E n j=1 Z ℓj , 1 ≤ ℓ ≤ 4. The rest of the section is devoted to establish such estimates.

5.1. Convergence to zero of j EZ 1j . We have

EZ 1j = E y * j Q j uu * Ry j 1 + η * j Q j η j - dj n E 1 1 + η * j Q j η j E(u * RDQu) = E y * j Q j uu * Ry j 1 + η * j Q j η j - dj n u * RDQ j u 1 + η * j Q j η j + dj n E u * RDQ j u 1 + η * j Q j η j -E 1 1 + η * j Q j η j E(u * RDQ j u) + dj n E 1 1 + η * j Q j η j E(u * RD(Q j -Q)u) △ = χ 1j + χ 2j + χ 3j .
We first handle χ ij . Recall that ∆ j = η * j Q j η j -n -1 dj Tr DQ j -a * j Q j a j . Since E yj (y * j Q j uu * Ry j ) = dj n -1 u * RDQ j u, we get:

χ 1j = E y * j Q j uu * Ry j 1 + η * j Q j η j - dj n u * RDQ j u 1 + η * j Q j η j , = E     1 1 + η * j Q j η j - 1 1 + dj n Tr DQ j + a * j Q j a j   y * j Q j uu * Ry j - dj n (u * RDQ j u)   , = E   ∆ j y * j Q j uu * Ry j -dj n (u * RDQ j u) (1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j )   .
Hence,

|χ 1j | ≤ |z| 2 δ 2 z E|∆ j | 2   E y * j Q j uu * Ry j - dj n (u * RDQ j u) 2   1/2 , ≤ |z| 2 δ 2 z × 1 √ nδ z × 1 nδ 2 z = O |z| 2 n 3/2 δ 5 z .
Summing over j yields the estimate

j |χ 1j | = O |z| 2 n -1/2 δ -5 z .
We now handle χ 2j . Using the inequality cov(XY ) ≤ var(X)var(Y ), we get:

|χ 2j | ≤ K n |z| δ z E |u * RD(Q j -EQ j )u| 2
Hence, applying Proposition 3.7 to |u * RD(Q j -EQ j )u| 2 and summing over j yields the

estimate j |χ 2j | = n -1/2 Φ(|z|)Ψ(δ -1 z ).
Let us now handle the term χ 3j . Using the decomposition of Q j -Q, Schwarz inequality and the fact that

√ ab ≤ 2 -1 (a + b) yields |χ 3j | = dj n E 1 1 + η * j Q j η j E(u * RD(Q j -Q)u) , ≤ K n |z| 2 δ 2 z E|u * RDQ j η j | 2 + E|η * j Q j u| 2 . (5.2)
Now, as:

E|u * RDQ j η j | 2 = Eu * RDQ j y j y * j Q * j DR * u + Eu * RDQ j a j a * j Q * j DR * u , E|η * j Q j u| 2 = Eu * Q * j y j y * j Q j u + Eu * Q * j a j a * j Q j u ,
it remains to sum over j and to apply Lemma 3.6 to get the estimate

j |χ 3j | = n -1 Φ(|z|)Ψ(δ -1 z ).
Gathering the partial estimates yields:

E j Z 1j ≤ Φ(|z|)Ψ(δ -1 z ) √ n . (5.3)
5.2. Convergence to zero of j EZ . Recall that

Z 2j = (α dj -y * j Q j y j )u * Ra j a * j Q j u (1 + η * j Q j η j )(1 + α dj )
.

We have:

|EZ 2j | (a) ≤ |z| 2 δ 2 z |u * Ra j |E (α dj -y * j Q j y j )a * j Q j u ≤ |z| 2 δ 2 z |u * Ra j | E|a * j Q j u| 2 E α dj -y * j Q j y j 2 ≤ |z| 2 δ 2 z u * Ra j a * j Ru + Eu * Q j a j a * j Q j u 2 E α dj -y * j Q j y j 2 , (5.4)
where (a) follows from (3.6). In order to estimate the remaining square root, we decompose the difference as:

α dj -y * j Q j y j = dj n Tr D(EQ -Q) + dj n Tr D(Q -Q j ) + dj n Tr DQ j -y * j Q j y j .
Hence,

E|α dj -y * j Q j y j | 2 ≤ K   1 n 2 E |Tr D(EQ -Q)| 2 + 1 n 2 E|Tr D(Q -Q j )| 2 + E dj n Tr DQ j -y * j Q j y j 2   . Writing E|n -1 Tr D(Q-EQ)| 2 ≤ ℓ + sup j≤n E|e * j D(Q-EQ)e j | 2
where e j represents canonical vector number j and using the result of Section 4, the first term of the right hand side is of order n -1 Φ(|z|)Ψ(δ -1 z ). The second term is of order (nδ z ) -2 (minor modification of [24, Lemma 2.6] to encompass the case Re(z) < 0). Finally, the third term is of order n -1 δ -2 z by Lemma 3.1. Collecting these results, we obtain:

E|α dj -y * j Q j y j | 2 ≤ K √ n Φ 1 Ψ 1 + Φ 2 Ψ 2 n + Φ 3 Ψ 3 1/2 ≤ K √ n (Φ 1 Ψ 1 + Φ 2 Ψ 2 + Φ 3 Ψ 3 ) 1/2 (a) ≤ K √ n Φ Ψ (b) ≤ K √ n ΦΨ ,
where the Φ's are nice polynomials with argument |z| and the Ψ's are nice polynomials with argument |δ -1 z |, and where (a) follows from (3.7) and (b) from (3.8). It remains to plug this estimate into (5.4), to sum over j and to use Assumption 2 together with Lemma 3.6 to obtain:

E n j=1 Z 2j ≤ K|z| 2 √ nδ 2 z   u * RAA * Ru + n j=1 Eu * Q j a j a * j Q j u   Φ(|z|)Ψ(δ -1 z ) , ≤ 1 √ n Φ ′ (|z|)Ψ ′ (δ -1 z ) . (5.5)
5.3. Convergence to zero of j EZ 3j . Recall that

Z 3j = y * j Q j ua * j Q j y j × u * Ra j (1 + η * j Q j η j )(1 + α dj )
.

We have:

E|Z 3j | (a) ≤ |z| 2 δ 2 z |u * Ra j | × E|y * j Q j ua * j Q j y j | ≤ |z| 2 δ 2 z |u * Ra j | E|y * j Q j u| 2 E|a * j Q j y j | 2 (b) ≤ K n |z| 2 δ 4 z |u * Ra j | ,
where (a) follows from (3.6), and (b) from Lemma 3.1. Hence,

n j=1 EZ 3j ≤ K n |z| 2 δ 4 z n j=1 |u * Ra j | ≤ K n |z| 2 δ 4 z √ n × n j=1 u * Ra j a * j R * u = O |z| 2 √ n δ 5 z . (5.6)
5.4. Convergence to zero of j EZ 4j . Write Z 4j as

Z 4j = W 4j (1 + η * j Q j η j )(1 + α dj ) with W 4j = (1 + α dj )(u * Ry j a * j Q j u + u * Ra j y * j Q j u) -y * j Q j a j u * Ra j a * j Q j u -a * j Q j y j u * Ra j a * j Q j u + u * Ra j a * j Q j a j y * j Q j u + u * Ra j a * j Q j y j a * j Q j u Write 1 1 + η * j Q j η j = 1 1 + dj n Tr DQ j + a * j Q j a j - ∆ j (1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j )
.

Plugging this identity into Z 4j and taking into account the fact that E yj W 4j = 0, we obtain:

|EZ 4j | = E   ∆ j W 4j (1 + α dj )(1 + η * j Q j η j )(1 + dj n Tr DQ j + a * j Q j a j )   ≤ |z| 3 δ 3 z E|∆ j | 2 E|W 4j | 2 ≤ K √ n |z| 3 δ 4 z E|W 4j | 2 .
Hence,

E j Z 4j ≤ K √ n |z| 3 δ 4 z j E|W 4j | 2 ≤ K|z| 3 δ 4 z j E|W 4j | 2 . (5.7)
We therefore estimate j E|W 4j | 2 . First, write:

E|W 4j | 2 ≤ K n 1 + 1 δ z 2 E|a * j Q j u| 2 u * RDR * u + |u * Ra j | 2 E(u * Q * j DQ j u) + K n |u * Ra j | 2 E |a * j Q j u| 2 a * j Q * j DQ j a j + a * j Q j DQ * j a j + K n |u * Ra j | 2 E |a * j Q j a j | 2 u * Q * j DQ j u + |a * j Q j u| 2 a * j Q j DQ j a j .
Now, summing over j yields:

n j=1 E|W 4j | 2 ≤ K n   n j=1 E(u * Q * j a j a * j Q j u)   1 + 1 δ z 1 δ 2 z + K n   n j=1 E(u * Ra j a * j R * u)   1 δ 4 z + 1 δ 2 z 1 + 1 δ z ≤ 1 n Φ(|z|)Ψ(δ -1 z ) .
Plugging this into (5.7) yields the estimate

E j Z 4j ≤ 1 √ n Φ ′ (|z|)Ψ ′ (δ -1 z ) . (5.8)
5.5. End of proof. Recall that:

|u * (R -EQ)u| ≤ E n j=1 Z 1j + E n j=1 Z 2j + E n j=1 Z 3j + E n j=1 Z 4j .
It remains to gather estimates (5.3), (5.5), (5.6) and (5.8) to get the desired estimate:

|u * (R -EQ)u| ≤ 1 √ n Φ(|z|)Ψ(δ -1 z ) .
6. Proof of Proposition 3.9

Recall the decomposition:

u * (Q -T )v = u * (Q -EQ)v + u * (EQ -R)v + u * (R -T )v .
As mentioned in Section 4.1, it is sufficient to establish the estimate:

|u * (R(z) -T (z)) u| ≤ 1 n Φ(|z|)Ψ 1 δ z , (6.1)
for z ∈ C -R + in the case where u has norm one.

6.1. The estimate for u * (R -T )u. Recall the definitions of δ, δ (1.3), α, α (3.13) and R, R (3. 14-3.15). Using twice the resolvent identity yields:

u * (R -T )u = (α -δ)κ 1 + (α -δ)κ 2 , (6.2)
where

κ 1 = zu * RDT u κ 2 = u * RA(I + α D) -1 D(I + δ D) -1 A * T u .
The following bounds are straightforward:

|κ 1 | ≤ |z| dmax δ 2 z and |κ 2 | ≤ A 2 dmax δ 2 z × (I + α D) -1 × (I + δ D) -1 .
It remains to control the spectral norms of (I + α D) -1 and (I + δ D) -1 . Recall that α is the Stieltjes transform of a positive measure with support included in R + . This in particular implies that Im(zα) > 0 for z ∈ C + . One can check that

Υ j (z) = 1 -z(1 + α dj )
is analytic and satisfies Im(Υ j ) > 0 and Im(zΥ j ) > 0 on C + and that lim y→∞ (-iyΥ j (iy)) = 1. As a consequence, Υ j is the Stieltjes transform of a probability measure with support included in R + (see e.g. [15, Prop. 2.2(2)]). In particular,

|Υ j (z)| ≤ 1 δ z for 1 ≤ j ≤ n ,
which readily implies that (I + α D) -1 ≤ |z|δ -1 z . The same argument applies for (I + δ D) -1 . Finally,

|κ 2 | ≤ |z| 2 A 2 dmax δ 4 z .
In view of the estimates obtained for κ 1 and κ 2 , it is sufficient, in order to establish (6.1), to obtain estimates for α -δ and α -δ. Assume that the following estimate holds true:

∀z ∈ C -R + , max |α -δ|, |α -δ| ≤ 1 n Φ(|z|)Ψ 1 δ z , (6.3)
where Φ and Ψ are nice polynomials. Then, plugging (6.3) into (6.2) immediately yields the desired result (6.1).

The rest of the section is devoted to establish (6.3).

6.2. Auxiliary estimates over (α-δ) and (α-δ). Writing α = n -1 Tr DR+n -1 Tr D(EQ-R) and δ = n -1 Tr DT , the difference α -δ expresses as n -1 Tr D(R -T ) + n -1 Tr D(EQ -R). Now using the resolvent identity R -T = -R(R -1 -T -1 )T and performing the same computation for the tilded quantities yields the following system of equations:

α -δ α -δ = C 0 α -δ α -δ + ε ε where C 0 = u 0 zv 0 zṽ 0 ũ0 , (6.4)
the coefficients being defined as:

       u 0 = 1 n Tr D 1/2 RA(I + α D) -1 D(I + δ D) -1 A * T D 1/2 ũ0 = 1 n Tr D1/2 RA * (I + αD) -1 D(I + δD) -1 A T D1/2 v 0 = 1 n Tr DRDT ṽ0 = 1 n Tr D R D T , (6.5)
and the quantities ε and ε being given by:

ε = 1 n Tr D(EQ -R) and ε = 1 n Tr D(E Q -R) . (6.6)
The general idea, in order to transfer the estimates over ε and ε (as provided in Proposition 3.8-(ii) ), to α -δ and α -δ, is to obtain an estimate over 1/ det(I -C 0 ), and then to solve the system (6.4).

Lower bound for det(I -C 0 ). The mere definition of I -C 0 yields

| det(I -C 0 )| = (1 -u 0 )(1 -ũ0 ) -z 2 v 0 ṽ0 ≥ (1 -|u 0 |) × (1 -|ũ 0 |) -|z| 2 |v 0 | × |ṽ 0 |
In order to control the quantities u 0 , ũ0 , v 0 and ṽ0 , we shall use the following inequality: Using (6.7) together with identity (I + δ D) -1 A * T = T A * (I + δD) -1 (and similar ones for related quantities), we obtain:

|Tr AB * | ≤ (Tr AA * ) 1/2 × (Tr BB * ) 1/2 , (6.7
|u 0 | ≤ (ũ 1 u 2 ) 1/2 , |ũ 0 | ≤ (u 1 ũ2 ) 1/2 , |v 0 | ≤ (v 1 v 2 ) 1/2 , |ṽ 0 | ≤ (ṽ 1 ṽ2 ) 1/2 ,
hence the lower bound:

| det(I -C 0 )| ≥ (1 -(ũ 1 u 2 ) 1/2 )(1 -(u 1 ũ2 ) 1/2 ) -|z| 2 (v 1 v 2 ṽ1 ṽ2 ) 1/2 . (6.9)
Notice that it is not proved yet that the right hand side of the previous inequality is nonnegative.

In order to handle estimate (6.9), we shall rely on the following proposition.

Proposition 6.1. Consider the nonnegative real numbers x i , y i , s i , t i (i = 1, 2). Assume that:

x i ≤ 1, y i ≤ 1 and (1 -x i )(1 -y i ) -s i t i ≥ 0 for i = 1, 2. Then: (1 - √ x 1 x 2 ) (1 - √ y 1 y 2 ) - √ s 1 s 2 t 1 t 2 ≥ (1 -x 1 )(1 -y 1 ) -s 1 t 1 (1 -x 2 )(1 -y 2 ) -s 2 t 2 .
Proof. If a ≥ c ( ≥ 0) and b ≥ d ( ≥ 0), then:

√ ab - √ cd ≥ √ a -c √ b -d .
To prove this, simply take the difference of the squares. Applying once this inequality yields

1 - √ x 1 x 2 ≥ (1 -x 1 )(1 -x 2 ), hence: (1 - √ x 1 x 2 ) (1 - √ y 1 y 2 ) - √ s 1 s 2 t 1 t 2 ≥ (1 -x 1 )(1 -x 2 )(1 -y 1 )(1 -y 2 ) - √ s 1 s 2 t 1 t 2
Applying again the first inequality yields then the desired result.

Our goal is to apply Proposition 6.1 to (6.9). The main idea, in order to fulfill assumptions of Proposition 6.1 (at least on some portions of C -R + ), is to consider the quantities of interest, i.e. u i , ũi , v i , ṽi (i = 1, 2) as coefficients of linear systems whose determinants are the desired quantities (1

-u i )(1 -ũi ) -|z| 2 v i ṽi .
Consider the following matrices:

C i (z) = u i v i |z| 2 ṽi ũi , i = 1, 2 .
The following proposition holds true: Proposition 6.2. Assume that z ∈ C -R + . Then:

(i) The following holds true: 1 -u 1 (z) ≥ 0 and 1 -ũ1 (z) ≥ 0. Moreover, there exists positive constants K, η such that:

det(I -C 1 (z)) ≥ K δ 8 z (η 2 + |z| 2 ) 4 .
(ii) There exist nice polynomials Φ and Ψ and a set

E n = z ∈ C + , 1 n Φ(|z|)Ψ 1 δ z ≤ 1/2 , such that for every z ∈ E n , 1 -u 2 (z) ≥ 0, 1 -ũ2 (z) ≥ 0, and
det(I -C 2 ) ≥ K δ 8 z (η 2 + |z| 2 ) 4 ,
where K, η are positive constants.

Proof of Proposition 6.2 is postponed to Appendix B.

We are now in position to establish the following estimate:

∀z ∈ E n , max |α -δ|, |α -δ| ≤ 1 n Φ(|z|)Ψ 1 δ z . ( 6

.10)

Assume z ∈ E n . Thanks to Proposition 6.2, assumptions of Proposition 6.1 are fulfilled by u i , ũi , v i and ṽi , and (6.9) yields:

det(I -C 0 ) ≥ det(I -C 1 ) det(I -C 2 ) ≥ K δ 8 z (η 2 + |z| 2 ) 4 , (6.11)
where K, η are nice constants. Solving now the system (6.4), we obtain:

α -δ = (det(I -C 0 )) -1 ((1 -ũ0 )ε + zv 0 ε) α -δ = (det(I -C 0 )) -1 ((1 -u 0 )ε + zṽ 0 ε)
It remains to use (6.11), Proposition 3.8-(ii), and obvious bounds over u 0 , ũ0 , v 0 and ṽ0 to conclude and obtain (6.10).

We turn out to the case where z ∈ C -R + -E n , and rely on the same argument as in Haagerup and Thorbjornsen [START_REF] Haagerup | A new application of random matrices: Ext(C * red (F 2 )) is not a group[END_REF] (see also [START_REF] Capitaine | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations[END_REF]). In this case,

1 n Φ(|z|)Ψ(δ -1 z ) ≥ 1 2 . As |α -δ| = |n -1 Tr D(EQ -T )| ≤ 2ℓ + d max δ -1 z , we obtain: ∀z ∈ C -R + -E n , |α -δ| ≤ 2ℓ + d max δ z × 2Φ(|z|)Ψ 1 δz n ;
a similar estimate holds for α -δ for z / ∈ E n . Gathering the cases where z ∈ E n and z / ∈ E n yields (6.3).

Appendix A. Remaining proofs for Section 3 Proof of Lemma 3.5. Note that it is sufficient to establish the result for a vector u with norm one (which is assumed in the sequel). The general result follows by considering u/ u . We proceed by induction over p. Let p = 1 and consider:

0 ≤ E n j=1 E j-1 u * Qa j a * j Q * u = Eu * QAA * Q * u ≤ a max 2 E Q 2 .
As Q ≤ δ -1 z , we obtain the desired bound. Now, write

E n j=1 E j-1 (u * Qa j a * j Q * u) p = j1,••• ,jp E E j1-1 (u * Qa j1 a * j1 Q * u) • • • E jp-1 (u * Qa jp a * jp Q * u) ≤ p! j1≤•••≤jp E E j1-1 (u * Qa j1 a * j1 Q * u) • • • E jp-1 (u * Qa jp a * jp Q * u) = p! j1≤•••≤jp E E jp-1 (u * Qa jp a * jp Q * u) p-1 k=1 E j k -1 (u * Qa j k a * j k Q * u) Fj p -1 measurable = p! j1≤•••≤jp-1 E n jp=jp-1 (u * Qa jp a * jp Q * u) p-1 k=1 E j k -1 (u * Qa j k a * j k Q * u) (a) ≤ p! a max 2 δ 2 z E n j=1 E j-1 (u * Qa j a * j Q * u) p-1
, where (a) follows from the fact that n jp=jp-1

(u * Qa jp a * jp Q * u) ≤ n jp=1 (u * Qa jp a * jp Q * u) ≤ a max 2 δ 2 z .
It remains to plug the induction assumption to conclude. Hence (3.9) is established.

In order to establish (3.10), one may use the same arguments as previously together with the identity QΣΣ * = I + zQ, which yields the factor |z| p in estimate (3.10).

Proof of Lemma 3.6. We prove the lemma in the case where u = 1, the general result readily follows by considering u/ u . Write u * Q j a j a * j Q * j u = χ 1j + χ 2j + χ 3j + χ 4j with:

χ 1j = u * (Q j -Q)a j a * j (Q j -Q) * u χ 2j = u * Qa j a * j Q * u χ 3j = u * (Q j -Q)a j a * j Q * u χ 4j = u * Qa j a * j (Q j -Q) * u Hence, n j=1 E u * Q j a j a * j Q * j u 2 ≤ n j=1 Eχ 2 1j + n j=1 Eχ 2 2j + n j=1 E|χ 3j | 2 + n j=1 E|χ 4j | 2 .
Notice that:

E|χ 3j | 2 ≤ 1 2 Eχ 2 1j + Eχ 2 2j and E|χ 4j | 2 ≤ 1 2 Eχ 2 1j + Eχ 2 2j
.

Note that using the facts that a j a * j ≤ AA * and η j η * j ≤ ΣΣ * together with the identity QΣΣ * = I + zQ yield the rough but useful estimates:

u * Qa j a * j Q * u = O δ -2 z and u * Qη j η * j Q * u = O |z| δ 2 z . (A.1)
We first begin by the contribution of j Eχ 2 2j :

n j=1 χ 2 2j = n j=1 u * Qa j a * j Q * u × u * Qa j a * j Q * u , ≤ n j=1 u * Qa j a * j Q * u × u * QAA * Q * u , ≤ (u * QAA * Q * u) 2 = O δ -4 z ≤ Φ 2 (|z|)Ψ 2 1 δ z . (A.2) Similarly, n j=1 u * Qη j η * j Q * u 2 = O |z| 2 δ 4 z . (A.3)
We now turn to the contribution of j Eχ 2 1j . Using the decompositions (3.2) , (3.3) and (3.4), χ 1j writes:

χ 1j = 1 + η * j Q j η j 1 -η * j Qη j × u * Qη j η * j Qa j a * j Q * η j η * j Q * u = 1 + η * j Q j η j × u * Qη j η * j Q * u × a * j Q * η j η * j Qa j 1 -η * j Qη j . (A.4)
We first prove that

a * j Q * η j η * j Qa j 1 -η * j Qη j = O |z| δ 2 z . (A.5)
In fact: It remains to gather the contributions of χ 1j , χ 2j , χ 3j and χ 4j to get:

a * j Q * η j η * j Qa j 1 -η * j Qη j ≤ a * j Q * η j η * j Q * a j 1 -η * j Qη j + a * j Q * η j η * j (Q -Q * )a j 1 -η * j Qη j (a) ≤ a * j (Q j -Q) * a j + 2|Im(z)||a * j (Q j -Q)Qa j | = O 1 δ z + O |z|
n j=1 E u * Q j a j a * j Q * j u 2 ≤ 2Φ 1 (|z|)Ψ 1 1 δ z +2Φ 2 (|z|)Ψ 2 1 δ z (a) ≤ Φ(|z|) Ψ 1 δ z ,
where (a) follows from (3.7). Eq. (3.11) is proved.

In order to prove (3.12), first note that: Combining standard inequalities (Cauchy-Schwarz, | j a j b j | ≤ ( j a 2 j ) 1/2 ( j b 2 j ) 1/2 , and Cauchy-Schwarz again), we obtain: .

E n j=1 E j-1 u * Q j a j a * j Q * j u p ≤ K   E
E n j=1 E j-1 |∆ j | × u * Qη j η * j Q * u p ≤   E n j=1 E j-1 (u * Qη j η * j Q * u) 2 p × E n j=1 E j-1 |∆ j | 2
We can now find a lower bound to w 1 : e-mail: {philippe.loubaton, pascal.vallet}@univ-mlv.fr

3. 1 .

 1 Notations. The indicator function of the set A will be denoted by 1 A (x), its cardinality by #A. Denote by a∧b = inf(a, b) and by a∨b = sup(a, b).

  follows from the triangle and Jensen's inequality, (b) from (3.6) and (c) from Cauchy-Schwarz inequality, Lemma 3.1 and Corollary 3.2.

1 n 1 n 1 n 1 n

 1111 Tr DT A(I + δ * D) -1 D(I + δ D) -1 A * T * ũ1 = Tr D T A * (I + δD) -1 D(I + δ * D) -1 A T * v 1 = 1 n Tr DT DT * ṽ1 = Tr Tr DRA(I + α * D) -1 D(I + α D) -1 A * R * ũ2 = 1 n Tr D RA * (I + αD) -1 D(I + α * D) -1 A R * v 2 = 1 n Tr DRDR * ṽ2 = 1 n Tr D R D R * (6.8)

  the fact that Q -Q * = 2iIm(z)Q * Q to obtain (a). Now, 1 + η * j Q j η j ≤ 1 + |∆ j | + dj n Tr DQ j + a * j Q j a j . (A.6) Since |n -1 dj Tr DQ j + a * j Q j a j | = O(δ -1 z ), we obtain: follows from (A.3) and (A.1) and (b), from Corollary 3.2.

E j- 1 E j- 1

 11 remains to evaluate the contributions of each term. Using decomposition (A.4) together with the estimate (A.5), we obtain:|1 + η * j Q j η j | × u * Qη j η * j Q * u p .Using (A.6) together with (3.10) yields:|∆ j | × u * Qη j η * j Q * u p .

≤ Φ 1 1 Im 2 ) 3 ) 1 nD ≥ ℓ -d min 2 .

 112312 (|z|)Ψ 1 (δ -1 z ) . (A.7)Eq. (3.9) directly yields the estimate: exists for E| E j-1 χ 4j | p : obtain:E n j=1 E j-1 χ 4j p ≤ Φ 4 (|z|)Ψ 4 1 δ z . (A.10)Gathering (A.7), (A.8), (A.9) and (A.10), we end up with (3.12), and Lemma 3.6 is proved.By applying Cramer's rule ([16, Sec. 0.8.3]) where the first column of I -C 1 is replaced with the right hand member of (B.1), we obtaindet(I -C 1 ) = (1-ũ1 )wUsing the fact that the positive measure µ n is supported by R + and has a total mass n -1 Tr D, In order to find a lower bound on w 1 and w1 , we begin by finding a lower bound on |δ|.A computation similar to[START_REF] Hachem | Deterministic equivalents for certain functionals of large random matrices[END_REF] Lemma C.1] shows that the sequence of measures (µ n ) is tight. Hence there exists η > 0 such that:µ n [0, η] ≥ 1 2 TrWe have|δ| ≥ | Im(δ)| = | Im(z)| µ n (dt) |t -z| 2 ≥ | Im(z)| η 0 µ n (dt) 2(t 2 + |z| 2 ) ≥ | Im(z)| ℓ -d min 4(η 2 + |z| 2 ).(B.4) Furthermore, when Re(z) < 0, we have|δ| ≥ Re(δ) = t -Re(z) |t -z| 2 µ n (dt) ≥ -Re(z) µ n (dt) |t -z| 2 ≥ -Re(z) ℓ -d min 4(η 2 + |z| 2 ).which results in|δ| ≥ δ z ℓ -d min 4(η 2 + |z| 2 )

κ i T ii 2 = |δ| 2 1 n 2 ≥ K δ 8 z

 2128 Tr D ≥ (δ z ℓ -d min ) 2 16 ℓ + d max (η 2 + |z| 2 ) 2where (a) follows by convexity. A similar computation yields w1 ≥ (δ z dmin ) 2 /(16 dmax (η 2 + |z| 2 ) 2 ) where η is a positive constant. Grouping these estimates with those in (B.3) and plugging them into (B.2), we obtaindet(I -C 1 ) ≥ δ 8 z (ℓ - dmin dmin ) 2 256 (ℓ + d max dmax ) 2 (η 2 + |z| 2 ) 2 (η 2 + |z| 2 ) (max(η, η) 2 + |z| 2 ) 4where K is a nice constant. The same bound holds for z ∈ (-∞, 0) by continuity of det(I -C 1 (z)) at any point of the open real negative axis.

Developing the previous identities, we end up with the system:

where

.

By developing the first equation of this system, and by recalling that δ(z) is the Stieltjes transform of a positive measure µ n with support included in R + , we obtain

Replacing (Im(δ), Im(z δ)) with (Im( δ), Im(zδ)) and repeating the same argument, we obtain

By continuity of u 1 (z) and ũ1 (z) at any point of the open real negative axis, we have 1-u 1 ≥ 0 and 1 -ũ1 ≥ 0 for any z ∈ C -R + . The first two inequalities in the statement of Proposition 6.2-(i) are proven.

Proof of Proposition 6.2-(ii). Recall that

We first establish useful estimates.

Lemma B.1. There exists nice polynomials Φ and Ψ such that:

Proof. We prove the first inequality. By Proposition (3.8)-(ii), the sequence of functions

δ z where Φ and Ψ are nice polynomials. Let R be the region of the complex plane defined as

) and the result is proven. Assume now that z ∈ R. In this case, z belongs to the open disc D z centered at Re(z) with radius -Re(z)/2. For any u ∈ D z , we have

As Φ(x) is increasing and Ψ(1/x) is decreasing in x > 0, we obtain:

The function ε is holomorphic on D z . Consider the function: Applying Lemma 3.4 with

Let ζ = i2 Im(z)/ Re(z), apply Lemma 3.4, and use (B.5). This yields:

where Φ and Ψ are nice polynomials. As Im(ε(Re(z))) = 0, we obtain

This proves the first inequality. The second one can be proved similarly.

We now tackle the proof of Proposition 6.2-(ii), following closely the line of the proof of Proposition

We begin by establishing the lower bound on det(I -C 2 ). Assume that z ∈ C + ∪ C -. Writing α = 1 n Tr DR + ε and α = 1 n Tr D R + ε and developing Im(α) and Im(z α) with the help of the resolvent identity, we get the following system:

where w 2 (z) = 1 n Tr DRR * and x2 (z) > 0. Let w2 = n -1 Tr D R R * . Using the same arguments as in the proof of Proposition 6.2-(i), we obtain

We now find an upper bound on the perturbation term e(z). To this end, we have 0 ≤ w 2 ≤ ℓ + d max /δ 2 z and 0 ≤ v 2 ≤ ℓ + d 2 max /δ 2 z . Recalling (6.8), we also have

Using the same arguments as in the proof of Proposition 6.2-(i) (involving this time the tightness of the measures associated with the Stieltjes transforms 1 n Tr DR and 1 n Tr D R) yields:

for every z ∈ C + ∪ C -, where η, K are positive constants, and Φ and Ψ, nice polynomials.

Finally, we can state that there exist nice polynomials Φ and Ψ such that:

By continuity of det(I -C 2 (z)) at any point of the open real negative axis, this inequality is true for any z ∈ C -R + . Denote by E n the set:

If z ∈ E n , then det(I -C 2 ) is readily lower-bounded by the quantity stated in Proposition 6.2-(ii). By considering inequalities (B.6) and (B.7) and by possibly modifying the polynomials Φ and Ψ, we have 1 -u 2 ≥ 0 and 1 -ũ2 ≥ 0 for z ∈ E n . The proof of proposition 6.2-(ii) is completed.


Huynh-Thu Quan

Le Patrick

Marcus Callet

Barkowsky

VIDEO QUALITY ASSESSMENT: FROM 2D TO 3D -CHALLENGES AND FUTURE TRENDS

Keywords: video quality, 3D, objective metrics, subjective assessment, standards

Three-dimensional (3D) video is gaining a strong momentum both in the cinema and broadcasting industries as it is seen as a technology that will extensively enhance the user's visual experience. One of the major concerns for the wide adoption of such technology is the ability to provide sufficient visual quality, especially if 3D video is to be transmitted over a limited bandwidth for home viewing (i.e. 3DTV). Means to measure perceptual video quality in an accurate and practical way is therefore of highest importance for content providers, service providers, and display manufacturers. This paper discusses recent advances in video quality assessment and the challenges foreseen for 3D video. Both subjective and objective aspects are examined. An outline of ongoing efforts in standards-related bodies is also provided.

INTRODUCTION

The availability of multimedia services has greatly expanded in the recent years thanks to advances in video coding, convergence of networks and increase of transmission bandwidth. One fundamental aspect of the overall quality of experience (QoE) of a multimedia service is the video quality.

Whilst the access to high-definition video content is still to reach everyone in a home environment, three-dimensional (3D) video is gaining a strong momentum both in the cinema and broadcasting industries as it is expected to enhance extensively the viewer's visual experience through a higher level of immersion in the media content. Several 3D video formats and 3D video coding strategies currently co-exist and practical tools (i.e. objective quality metrics) to compare them in terms of QoE would be very useful for researchers and for the industry.

Video quality can be measured using either subjective assessment or objective measurement. Subjective testing requires human observers to view videos and provide their opinion of quality. Quality measurement using objective models (computational algorithms) can provide a more practical solution. However these objective models are only useful if their measurement closely correlates with subjective quality. The development of reliable objective models depends ultimately on the validation of those models using reliable subjective assessment.

From a discussion on recent advances in the field of video quality assessment and an outline of recent standardization efforts focusing mainly on VQEG and ITU, this paper intends to raise the challenges foreseen for 3D video and gives an overview of the ongoing effort towards that goal.

3D VIDEO TRANSMISSION CHAIN

Since 3D video is an extension of 2D, it can be affected by the same types of visual distortions than those encountered in 2D video. However, there are many additional aspects that can influence the 3D visual experience. Figure 1 shows the block diagram of a typical transmission chain. Several blocks are common to a 2D and 3D transmission chain but, in most cases, additional processing steps are required for 3D, and the delivery of 3D signals causes new types of artifacts.

Acquisition of 3D signals and format conversion

It can be considered that the most complete 3D representation is achieved by computer-generated imagery (CGI). The underlying 3D model can be stored and the scenario can be rendered from any position with as many (virtual) cameras as necessary. However, this might require an excessive processing power.

On the other hand, from a 2D still image only a very small number of cues are available about the 3D structure. Algorithms have been proposed to extract 3D information from a 2D image using monocular cues such as the focus information, the texture or shades. The result is a depth map, which measures the distance to the nearest visible object. This resulting representation is often referred to as 2D plus depth.

In the extraction of depth from video sequences, the motion parallax can be used to achieve a higher accuracy of the depth map. A disadvantage of the 2D plus depth representation is that only information about the first object in the line of sight for a monocular view is available. This causes problems when a second view is rendered and parts of objects that are further away must be disoccluded. Disocclusion designates the recovery of hidden parts of an object, usually by using inpainting algorithms. This can be avoided by adding another layer of texture and depth information which is often referred to as occlusion layer. The occlusion layer can be estimated in videos from camera or object movement.

In the acquisition of stereo content, often two separate cameras are used, thus resulting directly in a stereo pair. Depending on the precision of the alignment, several artifacts can be introduced such as vertical misalignment, color misalignment, different focus points or zoom levels, temporal offsets or geometry distortions resulting for example from toed-in configurations. The captured stereo pair is often stored and transmitted in a combined manner. Mostly, top/bottom, left/right or line interleaved formats are used.

A higher flexibility for the rendering is achieved by recording more than two views. The additional information can be used to adjust the depth range or to support free viewpoint navigation or to enable motion-parallax rendering for example by autostereoscopic multiview displays. The captured data is typically converted into Layered Depth Video (LDV), Multiple Video plus Depth (MVD) or Depth Enhanced Stereo (DES) format.

The wide variety of possible representations for 3D content often requires a format conversion. This conversion can only be considered as lossless if the output is a subset of the input, e.g. when converting from MVD to just a single view plus depth. In most cases, the artifacts introduced by the format conversion lead to noticeable degradations. For example, when estimating the depth from stereoscopic video, the resulting depth map contains many errors due to the ambiguity of features found in the two images. Sometimes background objects are mistakenly arranged in the foreground. When re-rendering the original stereoscopic view, the depth impression is severely distorted and in addition, visible artifacts around the borders of those objects occur.

Transmission of 3D signals

Numerous approaches exist to encode, transmit and decode 3D video signals, the easiest being a simulcast transmission of the different views or depth maps using standard 2D video codecs such as H.264. An extension to H.264, called Multi View Coding (MVC), was developed to allow the compression, transmission and storage of 3D video. MVC was adopted as a standard format on the Blu-Ray Disc. The independent or combined transmission of 3D video signals leads to new artifacts which most often lead to binocular rivalry. Moreover, each compression algorithm requires a specific input representation, thus conversions between formats frequently occur, leading to information loss.

Display of 3D signals

At the display side, another format conversion may occur when either 2D plus depth representation was used for transmission or a different viewpoint needs to be rendered. Depth Image Based Rendering (DIBR) approaches are frequently used.

These render the stereo pair before the display, producing a dedicated image for the left and the right eye. Because at least one viewpoint differs slightly from the transmitted view, inpainting algorithms need to fill the previously occluded image regions. The inaccuracy of the inpainting often produces artifacts around the edges.

VIDEO QUALITY ASSESSMENT

Subjective quality assessment

Subjective assessment of (2D) video quality can be considered to be a mature field. The International Telecommunication Union (ITU) has recommended several methodologies for standarddefinition [START_REF] Itu-R | Methodology for the subjective assessment of the quality of television pictures[END_REF], high-definition [START_REF] Itu-R | Subjective assessment methods for image quality in high-definition television[END_REF] and low-resolution video [3][4].

On the other hand, this is not the case for the subjective quality assessment of 3D or stereoscopic video. A first international recommendation was published in 2000 [START_REF] Itu-R | Subjective assessment of stereoscopic television pictures[END_REF]. However, it mostly discusses the way to measure the stereo acuity of subjects. It also mentions the vergence-accommodation conflict that occurs on most of today's displays due to the fact that flat screens are used. While the accommodation of the Human Visual System (HVS) focuses on the screen because the objects appear to be most sharp on the display plane, the disparity of the objects between the left and the right eye leads to a convergence of the eyes towards a point in front or behind the display plane. This is an unnatural condition.

In the subjective evaluation of 3D images and video sequences, the video quality is closer to the concept of a quality of experience and should be considered to be multi-dimensional: visual quality, depth quality/perception, and comfort. The first dimension may be considered to be the visual quality in the 2D sense because observers usually view a 3D video for the first time in a subjective test, whilst they have a lot of experience with 2D television quality. The added value of depth was often proposed as a second criterion, and the term "naturalness" was proposed to express the combination of the perceived depth and the overall quality [START_REF] Kaptein | Performance evaluation of 3D-TV systems[END_REF].

Comfort is crucial as it has also been reported that some observers experience visual fatigue with symptoms like eye strain, headache or nausea. This effect is often measured using questionnaires [START_REF] Pölönen | Comparison of near-to-eye displays: subjective experience and comfort[END_REF]. A recent excellent summary of the causes can be found in [START_REF] Lambooij | Visual discomfort in stereoscopic displays: a review[END_REF].

The 3D display itself has a large impact on the stability and reproducibility of the subjective experiment. As the 3D display technology is still advancing, different technologies exist and none can be recommended as a reference. The viewing angle, the field of view, the amount of crosstalk and the brightness are often limiting factors. The International Committee for Display Metrology (ICDM) will soon release a Display Measurement Standard (DMS) to unify the measurement of display properties [START_REF]Society for Information Display[END_REF]. As was mentioned earlier, the 3D content has to be prepared specifically to fit the 3D display, e.g. the depth range has to be adapted. This adjustment depends on the display characteristics and on the viewing distance [START_REF] Chen | New requirements of subjective video quality assessment methodologies for 3DTV[END_REF].

Special attention is required on the way the display itself processes the 3D content. Often, crosstalk reduction is applied by the playout program or a format conversion takes place, e.g. from 2D plus depth to nine distinct views, and the rendering artifacts may easily outweight the added value of depth [START_REF] Barkowsky | Influence of depth rendering on the quality of experience for an autostereoscopic display[END_REF].

ITU-R WP6C is working towards the identification of requirements for the broadcasting and subjective testing of 3DTV [START_REF] Itu-R | Digital three-dimensional (3D) TV broadcasting[END_REF], whilst ITU-T Study Group 9 added 3D video quality in its scope in 2009 [START_REF] Itu-T | Objective and subjective methods for evaluating perceptual audiovisual quality in multimedia services within the terms of Study Group 9[END_REF]. However, all the issues mentioned previously constitute major challenges in finding a standardized way to characterize and measure the perceived quality of 3D video.

Objective quality metrics: from 2D to 3D

Whilst quality assessment of video impaired by coding distortions has been widely covered in the literature, research on 2D video models that handle distortions due to transmission errors (e.g. packet loss) has only flourished recently. Since 1997, the Video Quality Experts Group (VQEG) is a good witness of this effort. This group has been investing a lot of effort to examine, test and validate objective models using subjective data collected around the world. Based on VQEG's results, several international recommendations for objective video quality metrics have been established. ITU-T Rec. J.144 and its counterpart ITU-R Rec. BT.1683 were published in 2004. Both provide four full-reference objective video quality assessment models for standard-definition television signals impaired by coding distortions only. ITU-T Rec. J.247 was published in 2008 and recommends four full-reference models for low-resolution video impaired by both coding and transmission errors, whilst reduced-reference models are included in ITU-T Rec. J.246. The results of the on-going validation phase for HDTV [START_REF]VQEG HDTV test plan[END_REF] are expected to produce new recommendations for objective models in 2010/2011. Pursuing their effort to align with the trends in the field, VQEG has recently extended their work to 3D video quality and is first investigating the issues related to subjective testing protocols.

Compared to 2D, the objective assessment of video quality in 3D is more complex:

there are additional steps in the transmission chain that need to be addressed, as depicted in Fig. 1; -the observer's opinion may be considered as multidimensional, including factors like visual fatigue and depth perception; -more aspects of the HVS need to be addressed, e.g. binocular rivalry, binocular suppression. In the 3D transmission chain, visible artifacts occur at several locations. The camera capture or the conversion and rendering steps may introduce geometric degradations [START_REF] Woods | Image distortions in stereoscopic video systems[END_REF] or distortions in 3D size leading to the puppet theater effect. For a recent definition of these artifacts, see [START_REF] Meesters | A survey of perceptual evaluations and requirements of threedimensional TV[END_REF].

As the 3D artifacts partially stem from the newly introduced steps in the transmission chain, it may be advantageous to perform the objective measurement with signals extracted at different stages as well. For example, a no-reference measure for geometric distortions may be used to indicate artifacts resulting from the capture process. Later, a full-reference approach may be applied to evaluate the quality of the conversion algorithms from a stereo pair to 2D plus depth representation by using a reference implementation of the inverse step and comparing the input stereo pair to the re-rendered views [START_REF] Shao | Objective quality of depth image based rendering in 3DTV system[END_REF]. The classical 2D quality assessment algorithms measure the lost information between the video encoder and decoder and may thus be used as basis for this part of the 3D transmission chain. Enhancements are necessary for binocular artifacts, e.g. occlusions, perspective distortions, depth distortions or the detection of binocular rivalry. In the optimal case, the screen itself should be considered as perfect by the objective measurement but it might also be worthwhile to model the influence of display artifacts such as crosstalk.

When the influence of each step in the transmission chain is known, an open question remains on how to combine the different degradations, as each artifact at a given point in the transmission may be emphasized or diminished by the following steps in the transmission. In this sense, a holistic video quality estimation algorithm that takes inputs from several stages in the 3D transmission chain might be advantageous. This model would also benefit from the data generated during the transmission, e.g. a depth map.

In 2D video quality assessment, the best performing algorithms use a full-reference approach comparing the displayed video with the captured sequence pixel by pixel. This is not universally applicable to 3D as the displayed video might be rendered from a different perspective than the one that was captured.

It should be mentioned that the video content itself has a larger impact on the perceived visual quality in 3D than in 2D. Typical issues are objects that are clipped by the frustum, a moving camera perspective destabilizing the human sense of orientation and fast moving objects in the foreground which result in visual discomfort [START_REF] Speranza | Effect of disparity and motion on visual comfort of stereoscopic images[END_REF]. While 2D proposals have been presented for the automated characterization of content, little work has been done for 3D.

Studies have indicated that viewers tend to focus their attention on specific areas of interest in the image and models of visual attention have been proposed [START_REF] Meur | What we see is most likely to be what matters: visual attention and applications[END_REF]. There is an increasing interest in using visual attention models (saliency maps) inside video quality assessment models in order to improve their accuracy [START_REF] Ninassi | Does where you gaze on an image affect your perception of quality? Applying visual attention to image quality metric[END_REF]. Visual attention is without any doubt also a crucial factor in the perception of 3D video.

Objective quality metrics: status on 3D

Besides the lack of reliable subjective QoE assessment methodologies for 3D, several approaches to objective 3D video quality assessment have been proposed so far. This might affect the validation value of the metrics themselves. We might suspect that those metrics have been able to capture one dimension of the 3D QoE, which represents nonetheless valuable first contributions towards an ideal QoE metric.

An objective assessment algorithm which uses the depth map as well as the stereoscopic views is proposed in [START_REF] Shao | Objective quality of depth image based rendering in 3DTV system[END_REF]. It includes parts of the Structural Similarity Index (SSIM), the detection of edge and color degradations.

The binocular suppression indicates that one view of the stereo pair might be transmitted at a worse visual quality than the other. This is investigated in [START_REF] Ozbek | Unequal inter-view rate allocation using scalable stereo video coding and an objective stereo video quality measure[END_REF] using a rate-distortion model based on the estimation of visual quality with an adapted Peak Signal to Noise (PSNR) and a jerkiness metric. The influence of a reduction in spatial, temporal and quality dimension is analyzed. A model based on the idea that the inferior view should not add high frequency components is proposed and analyzed in [START_REF] Lu | Quality assessment of 3D asymmetric view coding using spatial frequency dominance model[END_REF].

The applicability of PSNR and 2D video models (SSIM and VQM) to 3D was investigated on a small dataset both for the case of stereoscopic video and monoscopic video with depth information [START_REF] Yasakethu | Quality analysis for 3D video using 2D video quality models[END_REF]. Results show that 3D video quality might be estimated from separate assessment of each stereo-view, whilst models for 2D could also be used to estimate the quality of depth perception. A similar analysis is performed in [START_REF] Hewage | Quality evaluation of color plus depth mapbased stereoscopic video[END_REF]. Both subjective experiments used a Philips 42-inch autostereoscopic display for presenting the 2D plus depth content. However, a study has shown that subjects prefer to switch off the 3D effect on this display [START_REF] Barkowsky | Influence of depth rendering on the quality of experience for an autostereoscopic display[END_REF].

CONCLUSION AND FUTURE DIRECTIONS

Subjective quality assessment of 2D video is a very mature field. However, subjective assessment of 3D video quality is still facing many problems to solve before the performance of 3D video models can be properly evaluated in order to capture the essential QoE involved by such media. Standardized protocols for measuring display characteristics and for characterizing the different dimensions of perceived video quality in 3D are still needed.

The research literature has started to investigate the applicability of 2D objective video quality assessment models to 3D video, as quality issues in 2D and 3D video are related and present some similarities. However, the lack of reliable ground truth (subjective dataset) reflecting the essence of 3D QoE limits the value of this initial effort. Moreover, 3D video presents in addition significantly different quality issues that are not encountered or don't have their equivalent in 2D. As opposed to 2D video where a direct analysis of the transmitted signal can produce a quality measure that correlates with subjective opinion, in 3D it is not the signal itself but rather the rendered version that needs to be analyzed. For these reasons, it should be difficult to measure 3D video quality simply by using existing or straightforward extensions of 2D video quality heritage. Objective quality assessment of 2D video is somewhat a mature field where researchers are considering very complex degradations beyond compression artifacts, such as those caused by transmission errors. Although 3D video will face the same problems, the objective assessment of 3D video quality is today in its infancy, with many problems to solve already in the characterization of the concept of 3D video quality

Fig. 1 .

 1 Fig. 1. 3D video transmission chain.