Arup Bose

Walid Hachem
email: walid.hachem@u-pem.fr

Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application

Keywords: Large non-Hermitian matrix theory, Limit spectral distribution, Smallest singular value, Whiteness test in multivariate time series. 2020 MSC: Primary 60B20, 62H15, Secondary 15A18, 15B52

Suppose X is an N × n complex matrix whose entries are centered, independent, and identically distributed random variables with variance 1/n and whose fourth moment is of order O(n -2 ). Suppose A is a deterministic matrix whose smallest and largest singular values are bounded below and above respectively, and z 0 is a complex number. First we consider the matrix XAX *z, and obtain asymptotic probability bounds for its smallest singular value when N and n diverge to infinity and N/n → γ, 0 < γ < ∞. Then we consider the special case where A = J = [1 i-j=1 mod n ] is a circulant matrix. Using the above result, we show that the limit spectral distribution of XJX * exists when N/n → γ, 0 < γ < ∞ and describe the limit explicitly. Assuming that X represents a C N -valued time series which is observed over a time window of length n, the matrix XJX * represents the one-step sample autocovariance matrix of this time series. A whiteness test against an MA correlation model for this time series is introduced based on the above limit result. Numerical simulations show the excellent performance of this test.

Introduction and the main results

Let (N (n) ) n≥1 be a sequence of positive integers, such that lim n→∞ N (n) /n = γ, 0 < γ < ∞. Let (X (n) = [x (n) i j ] N (n) -1,n-1 i, j=0

) n≥1 be a sequence of complex random matrices and (A (n) ) be a sequence of n × n deterministic matrices with complex entries. Suppose that Assumption 1. For each n ≥ 1, the complex random variables {x (n) i j } N (n) -1,n-1 i, j=0 are i.i.d. with Ex (n) 00 = 0, E|x (n) 00 | 2 = 1/n. Moreover, there exists a constant m 4 such that sup n n 2 E|x (n) 00

| 4 ≤ m 4 < ∞. Assumption 2. 0 < inf n s n-1 (A (n) ) ≤ sup n s 0 (A (n) ) < ∞ ,
where s 0 (M) ≥ • • • ≥ s n-1 (M) will refer hereinafter to the singular values of the matrix M ∈ C n×n .

We shall first study the probabilistic behavior of the smallest singular value of the matrix X (n) A (n) X (n) * -zI N , where M * is the Hermitian adjoint of the matrix M, and where z is any non-zero complex number. We shall then use this result to obtain the limiting spectral behavior of the matrix X (n) J (n) X (n) * where J (n) is as in Equation (1) below. Finally, we shall discuss a statistical application of this last result.

The behavior of the smallest singular value of large random matrices has recently aroused an intense research effort in the field of random matrix theory. One of the main motivations for this interest is its close connections with the spectral behavior of large square non-Hermitian random matrices. It is well-known that probabilistic control of the smallest singular value of the matrix Yz is a key step towards understanding the behavior of the spectral measure of Y [START_REF] Bordenave | Around the circular law[END_REF]. Starting with the fundamental model where Y has i.i.d. elements, most of the contributions dealing with the smallest singular value assume the independence between the entries of Y, as seen in [START_REF] Bai | Circular law[END_REF][START_REF] Cook | Lower bounds for the smallest singular value of structured random matrices[END_REF][START_REF] Götze | The circular law for random matrices[END_REF][START_REF] Litvak | Smallest singular value of random matrices and geometry of random polytopes[END_REF][START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF][START_REF] Tao | Random matrices: the circular law[END_REF][START_REF] Tao | Random matrices: universality of ESDs and the circular law[END_REF] among many others. An increasing degree of generality on the probability law on the independent entries of Y has been considered in these contributions. On the other side, more structured models, such as the one dealt with in this paper, have received comparatively much less attention. We can however cite in this respect the works of Girko (see, e.g., his treatise [START_REF] Girko | Theory of stochastic canonical equations[END_REF]) or [START_REF] Bordenave | Circular law theorem for random Markov matrices[END_REF][START_REF] O'rourke | Products of independent elliptic random matrices[END_REF], which all deal with quite different models than ours.

Our results will be proved under the following additional assumption on the elements of X (n) .

Assumption 3. The random variables x (n) 00 satisfy sup n |nE(x (n) 00 ) 2 | < 1.

Assumption 3 essentially amounts to demanding that x i j R. Indeed, suppose that for some n, |nE(x (n) 00 ) 2 | = 1. Drop the superscript (n) , and write x 00 = x 00 + ı x 00 . Then, 1/n = |Ex 2 00 | = E|x 00 | 2 . This implies (E x 00 x 00 ) 2 = E( x 00 ) 2 E( x 00 ) 2 . Suppose x 00 0. Then clearly x 00 = α x 00 with probability one (w.p.1) for some constant α. Thus, denoting as L = the equality in law, x 00 L = exp(ıθ)Z, where Z is a real random variable and θ is a constant. This amounts to x 00 being real since the factor exp(ıθ) has no influence on XJX * .

We can now state our first result. We denote as • the spectral norm of a matrix. Events are expressed in the forms [. . .] or {. . .}.

Theorem 1. Let Assumptions 1, 2, and 3 hold true. Then, there exist α, β > 0 such that for each C > 0, t > 0, and z ∈ C \ {0},

P s N-1 (X (n) A (n) X (n) * -z) ≤ t, X ≤ C ≤ c n α t 1/2 + n -β ,
where the constant c > 0 depends on C, z, and m 4 only.

The first step to prove this theorem is to "linearize" (similar linearizations have been used elsewehere, see, e.g., [START_REF] Haagerup | A new application of random matrices: Ext(C * red (F 2 )) is not a group[END_REF]), and consider the matrix N+n) .

H (n) = A (n) -1 X (n) * X (n) z ∈ C (N+n)×(
The inversion formula for partitioned matrices implies that (X (n) A (n) X (n) *z) -1 ≤ H (n) -1 . Thus, it is enough to deal with s N+n-1 (H (n) ). A similar problem was tackled in [START_REF] Nguyen | On the least singular value of random symmetric matrices[END_REF][START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF]. We follow closely the approach of [START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF] but there, the author had a real symmetric matrix with i.i.d. elements above the diagonal. Our matrix H (n) is more structured, and so we need appropriate modification in the arguments.

Motivated by the statistical application described in Section 2, we consider the following choice of A (n) . Since it is an orthogonal circulant matrix, it automatically satisfies Assumption 2.

A (n) = J (n) =                     0 1 1 . . . . . . . . . 1 0                     ∈ R n×n , (1)
Theorem 1 can be used to study the limit eigenvalue distribution of the matrix X (n) J (n) X (n) * (see [START_REF] Bordenave | Around the circular law[END_REF] or Section 4 for more information). Let {λ (n) 0 , . . . , λ (n) N (n) -1 } be its (complex) eigenvalues. The spectral distribution or measure of X (n) J (n) X (n) * is the random probability measure:

µ n = 1 N (n) N (n) -1 i=0 δ λ (n) i .
When N (n) /n → γ, 0 < γ < ∞, we shall identify a deterministic probability measure µ such that µ n ⇒ µ in probability, where ⇒ refers to weak convergence. The limit µ is called the limiting spectral distribution or measure (LSD) of the sequence of matrices. To describe µ, we need the following function. For any 0 < γ < ∞, let g(y) = y y + 1

(1 -γ + 2y) 2 , (0 ∨ (γ -1)) ≤ y ≤ γ.

(2)

Then g -1 exists on the interval [0 ∨ ((γ -1) 3 /γ), γ(γ + 1)] and maps it to [0 ∨ (γ -1), γ]. It is an analytic increasing function on the interior of the interval.

Theorem 2. Suppose Assumptions 1 and 3 hold. Then, there exists a deterministic rotationally invariant probability measure µ on C such that µ n ⇒ µ in probability. Let the distribution function of its radial component be

F(r) = µ({z ∈ C : |z| ≤ r}), 0 ≤ r < ∞. If γ ≤ 1, then F(r) =            γ -1 g -1 (r 2 ) if 0 ≤ r ≤ γ(γ + 1), 1 if r > γ(γ + 1).
If γ > 1, then

F(r) =                      1 -γ -1 if 0 ≤ r ≤ (γ -1) 3/2 / √ γ, γ -1 g -1 (r 2 ) if (γ -1) 3/2 / √ γ < r ≤ γ(γ + 1), 1 if r > γ(γ + 1).
The support of µ is the disc {z : |z| ≤ γ(γ + 1)} when γ ≤ 1, and when γ > 1, it is the ring {z : (γ -1) 3/2 / √ γ ≤ |z| ≤ γ(γ + 1)} together with the point {0} which has mass 1 -γ -1 . Moreover, F(r) has a positive and analytical density on the open interval (0 ∨ sign(γ -1)|γ -1| 3/2 / √ γ, γ(γ + 1)). A closer inspection of g shows that this density is bounded if γ 1. If γ = 1, then the density is bounded everywhere except when r ↓ 0.

In the next section, we consider a statistical application of this result, belonging to the domain of hypothesis testing. We then turn to the proofs of our results. Theorem 1 is proven in Section 3, while Sections 4-6 are devoted to the proof of Theorem 2. Specifically, the main steps of this proof are provided in Section 4. One of these steps is to analyze the singular value spectrum of X (n) J (n) X (n) *z for z ∈ C. This will be done in Section 5. Finally, Section 6 is devoted to the identification of the measure µ.

Application to statistical hypothesis testing

Consider the high dimensional linear moving average time series model

y (n) t = p i=0 B (n) i w (n) t-i , (3)
where {B (n) i } p i=0 are C N×N deterministic parameter matrices, and {w (n) i } i are random vectors such that the random matrix n) . Such models have found increasing attention in, e.g., the fields of signal processing, wireless communications, Radar, Sonar, and wideband antenna array processing [START_REF] Haykin | Adaptive radar detection and estimation[END_REF][START_REF] Van Trees | Optimum array processing: Part IV of detection, estimation, and modulation theory[END_REF]. The sample autocovariance matrices {n -1 n t=k+1 y (n) t (y (n) t-k ) * }, k ≥ 0, (k is called the lag or the step) carry useful information about the model (3), specially through their spectral distributions. Some of the works that deal with limit spectral distributions, mostly for high-dimensional real-valued time series, and their use in statistical inference are, [2-5, 8, 25, 26, 28, 39].

W (n) = (w (n) 0 • • • w (n) n-1 ) is equal in distribution to n 1/2 X (
The k-step sample autocovariance matrices (k 0), are non-Hermitian. To the best of our knowledge LSD results are known only for certain symmetrized versions of these matrices. All references cited above rely on symmetrization. The result of Theorem 2 is a beginning towards deriving the LSD of the sample autocovariance matrices in the general model (3) by considering the simplest case where B (n) 0 = I N and p = 0. This will be called the white noise model.

Consider the problem of testing the white noise model against an MA correlated model. To this end, we explore the idea of designing a test which is based on the eigenvalue distribution of the one-step sample autocovariance matrix, in contrast to more classical tests that are based on its singular value distribution. A non-rigorous justification of this idea is that when performing an eigenvalue-based test, we take advantage of the higher sensitivity of the eigenvalues of a matrix with respect to perturbations as compared to its singular values.

Assuming for simplicity that p = 1, our purpose is to test the null (white noise) hypothesis H0:

B (n) 0 = I, B (n) 1 = 0 against the alternative H1: B (n) 0 = I, B (n) 1
0. Consider the one-step sample autocovariance matrix

R (n) 1 = 1 n n-1 t=0 y (n) t y (n) t-1 * ,
where the sum is taken modulo n, and observe that under H0, this matrix coincides with X (n) J (n) X (n) * . We shall consider the asymptotic regime where n → ∞ and N/n → γ > 0. By Theorem 2, the spectral measure of R (n) 1 converges weakly in probability to the measure µ. This suggests the use of a white noise test based on a distance between the spectral measure of R (n) 1 and µ. We consider herein a test based on the 2-Wasserstein distance between these two distributions, which is known to produce the same topology as the weak convergence topology. For the sake of comparison, we also considered the more classical singular value based test which consists in comparing

N -1 tr R (n) 1 ( R (n) 1 )
* to a threshold. We denote these two tests as T 1 and T 2 respectively. To get a more complete picture of the problem, we also considered a third test which is based on the eigenvalue distribution of the Hermitian sample covariance matrix

R (n) 0,1 = 1 n n-1 t=0 y (n) t y (n) t-1 y (n) t * y (n) t-1 * .
Its spectral distribution is known to converge weakly almost surely under H0 to the Marchenko-Pastur distribution MP 2γ with parameter 2γ (see [START_REF] Loubaton | On the almost sure location of the singular values of certain Gaussian block-Hankel large random matrices[END_REF], which deals with the Gaussian case). This suggests the use of the 2-Wasserstein distance between the spectral measure of R 0,1 and MP 2γ . We denote the resulting test as T 3 .

Figures 1a and1b give the ROC curves for these tests. Tests T 1 and T 3 were implemented by sampling µ and MP 2γ from the spectra of two large random matrices and by using the transport library of the R software. These figures clearly show that T 1 outperforms T 2 and T 3 . This tends to corroborate the intuition that the eigenvalue sensitivity alluded to earlier, can be beneficial when it comes to designing white noise tests.

To better understand the behavior of the eigenvalue-based tests, the next step would be to study the large dimensional behavior of the spectral distribution of R (n) 1 under H1. It would be also useful to evaluate the test performance for Wasserstein distances of orders higher than two. These tasks appear to be quite non-trivial and are left for future research.

Before entering our proofs, let us present some notations. The dimension of a subspace V of some vector space will be denoted dim(V). The orthogonal subspace to V will be V ⊥ . The column span of a matrix M will be denoted as span(M). Similarly, span(V, d) is the span of the vector space V and the vector d.

The indices of the elements of a vector or a matrix start from zero. Given a positive integer m, we write [m] = {0, . . . , m -1}. For i ∈ [m], we denote as e m,i the i th canonical vector of C m , with 1 at the mth place and 0 elsewhere. Given a matrix M ∈ C m×n and two sets I ⊂ [m] and J ⊂ [n], M I,J denotes the |I| × |J| supmatrix of M that is obtained by retaining the rows and columns of M whose indices belong to I and J respectively. We also write

M •,k = M [m],{k} and M k,• = M {k},[n]
. We define as Π I : C m → C m the projection operator such that Π I u is the vector obtained by setting to zero the elements of u whose indices are in I c . We also denote as u I the vector of C |I| obtained by removing the elements of u whose indices are in I c . When M is a matrix, Π M refers to the orthogonal projector on span(M).

As mentioned above, • denotes the spectral norm. It will also denote the Euclidean norm of a vector. The Hilbert-Schmidt norm of a matrix will be denoted as • HS . The unit-sphere of C n will be denoted as S n-1 .

The notations P x and E x will refer respectively to the probability and the expectation with respect to the law of the vector x.

B (n) 1 = (b (n) i j ) Toeplitz with b (n) i j ∝ exp(-8|i -j|/N) and tr B (n) 1 (B (n) 1 ) * /N = 10 -2 .
Fig. 1: ROC curves for the tests T 1 , T 2 and T 3 described in Section 2. Setting: (N, n) = (50, 100)

Proof of Theorem 1: Smallest singular value

To simplify the notations, from now on, we omit the superscript (n) . Writing s inf = inf n s n-1 (A -1 ) and s sup = sup n s 0 (A -1 ), Assumption 2 is rewritten as 0 < s inf ≤ s sup < ∞. We also assume that z 0 without further mention.

General context and outline of proof

It is enough to establish Theorem 1 under the assumption that the entries have densities. This is because we can replace the matrix X with, the independent sum (1n -20 ) -1/2 (X + n -10 X ) where X is a properly chosen matrix whose elements have densities, and use a standard perturbation argument. Hence, we assume throughout this section that the elements of X have densities.

Suppose E ∈ C N×n is such that E 2 A < |z|. Then det(z -EAE * ) 0. This implies that the multivariate polynomial det(z -XAX * ) in the variables ( x i j , x i j ) i, j is not identically zero. Since X has a density, we conclude that z -XAX * is invertible w.p. 1. Define the matrix N+n) .

H = A -1 X * X z ∈ C (N+n)×(
By the inversion formula for partitioned matrices, the N × N lower-right block of H -1 coincides with (z -XAX * ) -1 . Thus, (XAX *z) -1 ≤ H -1 . Therefore, it is enough to prove that

P s N+n-1 (H) ≤ t, X ≤ C ≤ c n α t 1/2 + n -β , (4)
where c > 0 depends on C, z, and m 4 only.

As mentioned earlier, we shall follow here the argument of [START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF] but we shall need substantial modifications. Here is a description of the general approach. First recall that s N+n-1 (H) = min u∈S N+n-1 Hu .

Invoking an idea that has been frequently used in the literature since [START_REF] Litvak | Smallest singular value of random matrices and geometry of random polytopes[END_REF][START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF], we partition S N+n-1 into two sets of so-called compressible and incompressible vectors as follows.

Let θ, ρ ∈ (0, 1) be fixed. A vector in S N+n-1 is said to be θ-sparse if it does not have more than θ(N + n) nonzero elements. Let S N+n-1 I be the set of vectors of S N+n-1 that are supported by the (index) set I ⊂ [N + n]. Given S ⊂ C N+n , let N δ (S ) denote the δ-neighborhood of S in C N+n in the Euclidean metric. Given θ, ρ ∈ (0, 1), the set of (θ, ρ)-compressible vectors is comp(θ, ρ)

= S N+n-1 ∩ I⊂[N+n] |I|= θ(N+n) N ρ (S N+n-1 I ).
This is the set of all unit vectors at a distance at most ρ from the set of the θ-sparse unit vectors. The complementary set incomp(θ, ρ) = S N+n-1 \ comp(θ, ρ) is the set of incompressible vectors.

With these notations, for judiciously chosen θ, ρ ∈ (0, 1), we write

s N+n-1 (H) = inf u∈comp(θ,ρ) Hu ∧ inf u∈incomp(θ,ρ)
Hu .

(

) 5
The infimum over comp(θ, ρ) is relatively easier to handle. Given a fixed vector u ∈ S N+n-1 , we first show that P [ Hu ≤ c] for some c > 0 is exponentially small in n. Recall that an ε-net is a set of points that are separated from each other by a distance of at most ε. Now, since the vectors of comp(θ, ρ) are close to being sparse, it has an ε-net of controlled cardinality for a well-chosen ε > 0. Using this, along with a simple union bound, we will be able to infer the smallness of the probability that inf u∈comp(θ,ρ) Hu is small.

The infimum over the set of incompressible vectors poses a much bigger challenge since the ε-net argument fails. In this case the argument is more geometric. Observe that when u is incompressible, Hu is close to a sum of O(n) columns of H with comparable weights. This helps to reduce the problem of controlling inf u∈incomp(θ,ρ) Hu to the problem of controlling the distance between an arbitrary column of H and the subspace generated by the other columns.

Let h 0 be the first column of H, and let H -0 ∈ C (N+n)×(N+n-1) be the supmatrix left after extracting this column. Partition H accordingly as

H = b g 01 g 10 G ,
with b ∈ C and G ∈ C (N+n-1)×(N+n-1) . In Lemma 11 below, we show that G -1 exists w.p. 1. Noting that the distance dist(h 0 , H -0 ) between h 0 and the column span of H -0 satisfies dist(h 0 , H -0 ) 2 = h * 0 (I -H -0 (H * -0 H -0 ) -1 H * -0 )h 0 , and making use of the Sherman-Morrison-Woodbury formula [16, Chap. 2], we get after a small derivation that dist(h 0 ,

H -0 ) = b -g 01 G -1 g 10 1 + g 01 G -1 2 . ( 6
)
Our purpose is to bound the probability that this distance is small. If we write

A -1 = b b 01 b 10 B , X = x W ,
where B ∈ C (n-1)×(n-1) , and x ∈ C N is the first column of X, then

g 01 = b 01 x * , g 10 = b 10 x , and
G = B W * W zI N . (7)
Assuming that the inverse exists, partition G -1 as

G -1 = E F P R , E ∈ C (n-1)×(n-1) , R ∈ C N×N . (8)
Then using Equation ( 6), we have dist(h 0 , H -0 ) = Num Den w.p. 1, where,

Num = |bb 01 Eb 10x * Pb 10b 01 F xx * Rx| , and

Den = 1 + b 01 E + x * P 2 + b 01 F + x * R 2 1/2 . ( 10
)
To control the behavior of Num, we need an anti-concentration result. Loosely speaking, we show that conditionally on the matrix W and for most of these matrices, the probability that a properly normalized version of the random variable x * Pb 10 + b 01 F x + x * Rx lives in an arbitrary ball of C of small radius is itself small.

Small ball probabilities are captured by the so-called Lévy's concentration function. Given a constant vector a ∈ C n and a random vector Z ∈ C n , Lévy's concentration function of the inner product a, Z at ε > 0 is

L Z ( a, Z , ε) = sup w∈C P Z [| a, Z -w| ≤ ε] .
When the elements of Z are i.i.d. random variables with finite third moment, the behavior of L Z can be controlled by the Berry-Esséen theorem, whose use in random matrix theory dates back to [START_REF] Litvak | Smallest singular value of random matrices and geometry of random polytopes[END_REF]. Berry-Esséen theorem is a refinement of the Central Limit Theorem and implies that when a ∈ S n-1 has O(n) elements with magnitudes of order

1/ √ n, it holds that L Z ( a, Z , ε) ε + 1/ √ n.
Our plan now is to apply this theorem after replacing Z with the random vector x. Unfortunately, this theorem cannot be used as is on the random variable x * Pb 10 + b 01 F x + x * Rx because of the presence of the quadratic form x * Rx. To circumvent this problem, we use a decoupling argument that replaces x * Pb 10 + b 01 F x + x * Rx with an inner product that can be processed by the Berry-Esséen theorem. This decoupling idea that dates back to [START_REF] Götze | Asymptotic expansions for bivariate von Mises functionals[END_REF] has also been used in [START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF].

Technical results

The following proposition is an easy variation of [35, Proposition 5.1], see also [7, Lemma A2] and [START_REF] Götze | On the asymptotic spectrum of products of independent random matrices[END_REF].

Proposition 3 (Distance of a random vector to a constant subspace). Let Z = (Z 0 , . . . , Z n-1 ) ∈ C n be a vector of i.i.d. centered unit-variance random variables such that for some κ > 0, E|Z 0 | 2+κ ≤ C κ < ∞. Then, there exist c, c > 0 and δ ∈ (0, 1) that depend only on κ and C κ and that satisfy the following property. For all n 1, and for any deterministic subspace V of C n such that 0 ≤ dim(V) ≤ δn,

P[dist(Z, V) ≤ c √ n] ≤ exp(-c n).
This result leads to the following lemma:

Lemma 4. Let the matrix X satisfy Assumption 1. Then, there exist constants c, c > 0 and a constant δ ∈ (0, 1) that depend on m 4 only and that satisfy the following property. For each deterministic vector u ∈ S n-1 and each deterministic subspace

V ⊂ C N with 0 ≤ dim(V) ≤ δN, P [dist(Xu, V) ≤ c] ≤ exp(-c n). (11)
In particular, for each deterministic vector a ∈ C N , it holds that

P [ Xu -a ≤ c] ≤ exp(-c n). Similar conclusions hold if X is replaced with X * .
Proof. Let x0 , . . . , xN-1 ∈ C 1×n be the rows of X, and define the random variables

Z k = √ n xk u for k ∈ [n]
. These random variables are i.i.d., centered, and have unit-variance. Furthermore, writing u = (u 0 , . . . , u n-1 ) T , we get by Rosenthal's inequality that for some universal constant C,

E|Z 1 | 4 ≤ C (n 2 E|X 11 | 4 |u i | 4 ) ∨ 1 ≤ Cm 4 .
Writing Z = (Z 0 , . . . , Z N-1 ) T , we note that dist(Xu, V) = dist(Z, V)/ √ n. Applying Proposition 3 with κ = 2, we obtain [START_REF] Cook | Non-Hermitian random matrices with a variance profile (I): deterministic equivalents and limiting ESDs[END_REF]. The rest of the claims follow immediately.

The two following results regarding Lévy's concentration functions will be needed.

Lemma 5 ( Lemma 2.1 of [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF]). Let Z ∈ C n be a vector of independent random variables. Then, for each non-empty

I ⊂ [n], we have L Z ( a, Z , ε) ≤ L Z I ( a I , Z I , ε).
Proposition 6. There exists a constant c > 0 such that for any vector Z = (Z 0 , . . . , Z n-1 ) of complex centered independent random variables with finite third moments,

L Z Z i , t ≤ ct E|Z i | 2 + c E|Z i | 3 ( E|Z i | 2 ) 3/2 .
For a proof, see [START_REF] Bordenave | Around the circular law[END_REF]Lemma A6]. In particular, if there exist two positive constants c 2 and c 3 such that

E|Z i | 2 ≥ c 2 and E|Z i | 3 ≤ c 3 for each i ∈ [n], then L Z Z i , t √ n ≤ c t + c √ n , (12)
where c = c/ √ c 2 and c = cc 3 /c 3/2 2 . We now enter the proof of Theorem 1 via proving Inequality [START_REF] Bhattacharjee | Polynomial generalizations of the sample variance-covariance matrix when pn -1 → 0[END_REF]. Recall that we have written X = x W where x is the first column of X. Given C > 0, we denote as E op (C) the probability event

E op (C) = [ W ≤ C] .
In the remainder of this section, the constants that do not depend on n will be referred to by the letter c, possibly with primes or numerical indices referring to the propositions or lemmas where these constants appear for the first time. In all statements of the type

P [[• • • ≤ c] ∩ E] ≤ exp(-c n) + c 1 n -γ , where E = [ X ≤ C] or E op (C)
, the constants such as c, c , or c 1 depend on C, z, and m 4 at most.

Compressible vectors

Recalling ( 5), we start with the compressible vectors.

Proposition 7. Let Assumption 1 hold true. Then, there exists θ 7 ∈ (0, 1), ρ 7 > 0, c > 0 and c > 0 such that

P inf u∈comp(θ 7 ,ρ 7 ) Hu ≤ c ∩ [ X ≤ C] ≤ exp(-c n) for large enough n.
Proof. We first show that there exist c 0 , c 1 > 0 such that for each deterministic vector u ∈ S N+n-1 ,

P [ Hu ≤ c 0 ] ≤ exp(-c 1 n). ( 13
) Write u = (v T , w T ) T , where v ∈ C n and w ∈ C N . Since u = 1, either v ≥ 1/ √ 2 or w ≥ 1/ √ 2. Assume that w ≥ 1/ √ 2, and note that [ Hu ≤ c 0 ] ⊂ [ A -1 v + X * w ≤ c 0 ]
. Writing w = w/ w , we have

P X * w + A -1 v ≤ c 0 = P X * w + A -1 v/ w ≤ c 0 / w ≤ P X * w + A -1 v/ w ≤ c 0 √ 2 ≤ exp(-c 1 n)
by applying Lemma 4 and choosing c 0 and c 1 judiciously. When v ≥ 1/ √ 2, we can use a similar argument (with possibly different c 0 and c 1 ) after observing that [

Hu ≤ c 0 ] ⊂ [ Xv + zw ≤ c 0 ]
. This establishes [START_REF] Feinberg | Non-Hermitian random matrix theory: method of Hermitian reduction[END_REF]. Now, on the event [ X ≤ C], we have

H ≤ X * X + A -1 z ≤ C H C + |z| ∨ s sup .
On this event, assume that there exists y ∈ N c 0 /(2C H ) ({u}) such that Hy ≤ c 0 /2. Then Hu ≤ H(uy) + Hy ≤ c 0 .

In other words,

∃y ∈ N c 0 /(2C H ) ({u}) : Hy ≤ c 0 /2 ∩ [ X ≤ C] ⊂ [ Hu ≤ c 0 ] .
We now use a ε-net argument. Let θ 7 ∈ (0, 1) to be fixed in a moment, and choose I ⊂ [N + n] so that that |I| = θ 7 (n + N) . The unit-sphere S N+n-1

I

of the subspace of the vectors of C N+n that are supported by I has a (c 0 /(2C H ))-net of cardinality bounded by (6C H /c 0 ) 2|I| (see, e.g., [10, Lemma 2.2]). Applying the previous results and making use of the union bound, we get that

P ∃y ∈ N c 0 /(2C H ) (S N+n-1 I ) : Hy ≤ c 0 /2 ∩ [ X ≤ C] ≤ (6C H /c 0 ) 2θ 7 (N+n) exp(-c 1 n).
Finally, considering all the sets I ⊂ [N +n] such that |I| = θ 7 (N +n) , recalling the elementary bound on the binomial coefficients m k ≤ (em/k) k , and using the union bound, we get that

P ∃y ∈ comp(θ 7 , c 0 /(2C H )) : Hy ≤ c 0 /2 ∩ [ X ≤ C] ≤       36eC 2 H θ 7 c 2 0       θ 7 (N+n) exp(-c 1 n).
A small calculation shows that the right hand side is of the form exp(-c n) for large enough n when θ 7 is chosen small enough. By taking ρ 7 = c 0 /(2C H ), the proposition is proven.

Incompressible vectors

One main feature of incompressible vectors of C n is that they contain O(n) elements of absolute values of order O(n -1/2 ), as shown in [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF]Lemma 3.4]. We shall need the following slightly stronger version of this lemma with a similar proof. Lemma 8. Let u = (u 0 , . . . , u n-1 ) T ∈ incomp(θ, ρ), and let ũ = (ũ 0 , . . . , ũn-1 ) T ∈ S n-1 . Then, |J| ≥ θn/2 where,

J = {i ∈ [n] : ρ √ n ≤ |u i | ≤ 2 √ θn and |ũ i | ≤ 2 √ θn }.
One consequence of [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF]Lemma 3.4] is the following lemma, which implies that the infimum of Hu over a set of incompressible vectors can be handled by controlling the distance between an arbitrary column of H and the subspace generated by the other columns: Lemma 9 (Invertibility via mean distance, Lemma 3.5 of [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF]). Let M ∈ C n×n be a random matrix. Let m k be the kth column of M and let M -k ∈ C n×(n-1) be the supmatrix left after removing this column. Then,

P inf u∈incomp(θ,ρ) Mu ≤ ρt √ n ≤ 2 θn n-1 k=0 P [dist(m k , M -k ) ≤ t] .
Using Lemma 9, we need to control the distance between a column of H and the subspace generated by the other columns. Denote as x k the k th column of X (thus, x 0 = x). Let b k and x denote the k th column of A -1 and the th row of X respectively. Then the columns of H are one of the two types:

b k x k , or x * ze N,
. Due to the fact that A is not necessarily a diagonal matrix, it will be more difficult to control the distances involving columns of the first type.

Recall the partition H = h 0 H -0 , where h 0 is the first column of H. We have Proposition 10. Let Assumptions 1, 2, and 3 hold true. Then

P[[dist(h 0 , H -0 ) ≤ t] ∩ [ X ≤ C]] ≤ c 1 (n 59/88 t 1/2 + n -1/22 ) + exp(-c 2 n).
Since [ X ≤ C] is obviously included in E op (C), it will be enough to establish the inequality

P[[dist(h 0 , H -0 ) ≤ t] ∩ E op (C)] ≤ c 1 (n 59/88 t 1/2 + n -1/22 ) + exp(-c 2 n)
to obtain Proposition 10. Replacing [ X ≤ C] with E op (C) will be more convenient due to the independence of x and E op (C). The remainder of this section is devoted towards proving this inequality. Our starting point will be Equation [START_REF] Bordenave | Circular law theorem for random Markov matrices[END_REF]. To be able to use it, we need to check that G defined in ( 7) is invertible. Recall that X is assumed to have a density.

Lemma 11. The matrix G is invertible with probability one.

Since

A -1 = b b 01 b 10 B , it follows that rank(B) ≥ n -2. Thus, either B is invertible or rank(B) = n -2.
Assume it is invertible. Then on the set {W ∈ C N×(n-1) :

z -1 W * W ≤ s n-2 (B)/2}, it holds that s n-2 (∆) ≥ s n-2 (B) -z -1 W * W ≥ s n-2 (B)/2 > 0.
Thus, det(∆) is a non-zero multivariate polynomial in the real and imaginary parts of the elements of W. Since W has a density, det(∆) 0 w.p. 1.

Assume now that rank(B) = n -2. Then we can write B = UV * where U, V ∈ C (n-1)×(n-2) are full column-rank matrices. Writing W * = w Y where w ∈ C n-1 , we get that

B -z -1 W * W = U z -1 w V -w * -z -1 YY * = D -z -1 YY * .
Given a vector u ⊥ span(U) where ⊥ denotes the orthogonality, the inner product u * w is a continuous random variable, thus u * w 0 w.p. 1. Consequently, w span(U) w.p. 1., which implies that U z -1 w is invertible w.p. 1. The same argument holds for V -w , and thus the matrix D is invertible w.p. 1. To obtain that ∆ is invertible, it remains to apply the previous argument after replacing B with D and W * with Y, and making use of the independence of w and Y along with the Fubini-Tonelli theorem.

From Equation ( 6), dist(h 0 , H -0 ) = Num/Den w.p. 1, where Num and Den are as given in [START_REF] Cook | Lower bounds for the smallest singular value of structured random matrices[END_REF]. To study the behavior of these random variables, we first need to show that the image of each deterministic vector by the matrix R at the right hand side of ( 8) is incompressible with high probability. This will be stated in the corollary of Proposition 13 below. Proof. Let θ 13 ∈ (0, 1) and t ∈ (0, 1) to be fixed later. Let I ∈ [N]such that |I| = θ 13 N . Fix an element w of the unit-sphere S N-1 I . In this first part of the proof, we shall control the probability of the event inf

v∈C n-1 dist G v w , span 0 d ≤ t ∩ E op (C). ( 14
)
Given two elements a and b of some vector space on C, it holds that dist(a, span b) = inf α∈C a -αb . Thus, the event between [ ] brackets in ( 14) is included in the event

E w (t) = ∃v ∈ C n-1 , ∃α ∈ C : Bv + W * w ≤ t, Wv + zw + αd ≤ t . (15)
Let

B = P p Σ 0 0 s n-2 (B) Q * q * (16)
be a singular value decomposition of B, where p and q are respectively the last columns of the unitary matrices P p and Q q . Given any vector y ∈ C n-1 , we shall use in the remainder of the proof the notations y Q = Π Q y and y q = Π q y, making y = y Q + y q an orthogonal sum. As is well-known [16, Chap. 5], the vector u = -B † W * w where B † is the Moore-Penrose pseudo-inverse of B, minimizes By+W * w with respect to y. Assume that there is a solution v ∈ C n-1 of the inequality By+W * w ≤ t in y. Then, since u is also a solution, we get that

B(u Q -v Q )+B(u q -v q )+Bv+W * w ≤ t,
and hence, B(u

Q -v Q ) + B(u q -v q ) ≤ Bv + W * w + t ≤ 2t. Noting that B(u Q -v Q ) and B(u q -v q ) are orthogonal, we get that B(u Q -v Q ) ≤ 2t
. By Lemma 12, the smallest singular value of the operator B restricted to the subspace span(Q) is bounded below by s inf . Hence

v Q -u Q ≤ 2t s inf .
The vector v also satisfies the inequality Wv+zw+αd ≤ t for some α ∈ C. Thus, W(v Q -u Q )+Wv q +Wu Q +zw+αd ≤ t, which implies that on the event E op (C),

Wv q + Wu Q + zw + αd ≤ W(v Q -u Q ) + t ≤ 1 + 2C s inf t.
Observing that v q is collinear with q, we get at this stage of the proof that

E w (t) ∩ E op (C) ⊂ ∃α, β ∈ C, : βWq + Wu Q + zw + αd ≤ 1 + 2C s inf t ∩ E op (C). ( 17
)
To proceed, we need to control the Euclidean norm of u Q . For m, M > 0, consider the event

E u Q (m, M) = m ≤ u Q ≤ M . Since u Q = -Π Q B † W * w, we get from Lemma 12 that s -1 sup W * w ≤ u Q ≤ s -1 inf W * w . By Lemma 4, there exist c 0 > 0 and c 1 > 0 such that P[ W * w ≤ c 0 ] ≤ exp(-c 1 n). We thus obtain P E u Q (s -1 sup c 0 , s -1 inf C) c ∩ E op (C) ≤ exp(-c 1 n). (18)
To bound the probability of the event at the right hand side of the inclusion (17), we consider separately the situations where |β| is large and where |β|is bounded above. Consider the event

E |β|> (m, M) = ∃α, β ∈ C : βWq + Wu Q + zw + αd ≤ m, |β| ≥ M . On E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C), it holds that βWq + Wu Q + zw + αd ≥ βWq + zw + αd -s -1 inf C 2 ≥ |β| dist(Wq, span[w, d]) -s -1 inf C 2 From Lemma 4, there exist c 2 , c 3 > 0 such that P[dist(Wq, span[w, d]) ≤ c 2 ] ≤ exp(-c 3 n). Writing s = (1 + 2C/s inf )t,
we have

E |β|> (s, M) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C) ⊂ ∃β ∈ C : |β| dist(Wq, span[w, d]) -s -1 inf C 2 ≤ s, |β| ≥ M ⊂       dist(Wq, span[w, d]) ≤ s + s -1 inf C 2 M       .
Thus, setting C = (s + s -1 inf C 2 )/c 2 , we get that

P E |β|> (s, C ) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C) ≤ exp(-c 3 n). (19)
Now consider the case |β| < C . We discretize this ball as follows. Consider the event

E |β|< (s, C ) = ∃α, β ∈ C : βWq + Wu Q + zw + αd ≤ s, |β| < C .
Given k, ∈ Z, define the event

E q (k, , s, C) = ∃α ∈ C : s C √ 2 (k + ı )Wq + Wu Q + zw + αd ≤ s . For β ∈ C, let k β = C √ 2 β/s and β = C √ 2 β/s . Then β -(k β + ı β )s/(C √ 2) ≤ s/C. Therefore, E |β|< (s, C ) ∩ E op (C) ⊂ k, ∈Z, |k+ı |≤CC √ 2/s E q (k, , 2s, C).
Let us bound the probability of the event E q (k, , 2s,

C) ∩ E u Q (s -1 sup c 0 , s -1 inf C). Recalling that u Q = -Π Q B † W * w
and that w is supported by I, we observe that u Q and W I c ,• are independent. Writing r = s(k+ı ) C √ 2 q + u Q and r = r/ r , we have

E q (k, , 2s, C) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ⊂ [∃α ∈ C, : Wr + zw + αd ≤ 2s] ∩ u Q ≥ s -1 sup c 0 ⊂ ∃α ∈ C, : W I c ,• r + αd I c ≤ 2s ∩ u Q ≥ s -1 sup c 0 ⊂ r dist W I c ,• r, span d I c ≤ 2s ∩ u Q ≥ s -1 sup c 0 ⊂ dist W I c ,• r, span d I c ≤ 2ss sup /c 0 . By Lemma 4 once again, P[dist W I c ,• r, span d I c ≤ c 2 ] ≤ exp(-c 3 |I c |). Thus, if we choose t small enough so that 2 + 4 C s inf s sup c 0 t ≤ c 2 , we get that P E q (k, , 2s, C) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ≤ exp(-(1 -θ 13 )c 3 n). (20)
Putting things together, we get

P inf v∈C n-1 dist G v w , span 0 d ≤ t ∩ E op (C) ≤ P E w (t) ∩ E op (C) (using (15)
)

≤ P E w (t) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C) + P E u Q (s -1 sup c 0 , s -1 inf C) c ∩ E op (C) ≤ P E |β|> (s, C ) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C) + P E |β|< (s, C ) ∩ E u Q (s -1 sup c 0 , s -1 inf C) ∩ E op (C) + exp(-c 1 n) (using (18)) ≤ exp(-c 3 n) + |k+ı |≤CC √ 2/s P E q (k, , 2s, C) ∩ E u Q (s -1 sup c 0 , s -1 inf C) + exp(-c 1 n) (using (19)) ≤ exp(-c 1 n) + C exp(-(1 -θ 13 )c 3 n) (using (20)),
where C = C (m 4 , C) > 0. Now, let Σ t be a t-net of (S N-1 I ). Given an element y of N t (S N-1 I )∩S N-1 , there exists y ∈ S N-1 I such that y-y ≤ t, and there exists w ∈ Σ t such that wy ≤ t. Thus, yw ≤ 2t by the triangle inequality. Assume that there exist α ∈ C and v ∈ C n-1 such that the inequality

G v y + α 0 d ≤ t
holds true. Then on the set E op (C), we have

G v w + α 0 d = G v w - v y + G v y + α 0 d ≤ 2(C + |z|)t + t.
Observe that |Σ t | ≤ (3/t) 2|I| . Adjusting t again in such a way that 2C

+ 2|z| + 1)(2 + 4 C s inf s sup c 0 t ≤ c 2 , we obtain that P inf v∈C n-1 , y∈N t (S N-1 I )∩S N-1 dist G v y , span 0 d ≤ t ∩ E op (C) ≤ (3/t) 2θ 13 n exp(-c 1 n) + C exp(-(1 -θ 13 )c 3 n) .
Finally, considering all the sets I ⊂ [N] such that |I| = θ 13 N , and using the bound m k ≤ (em/k) k along with the union bound, we get that

P inf v∈C n-1 , w∈comp(θ 13 ,t) dist G v w , span 0 d ≤ t ∩ E op (C) ≤ (e/θ 13 ) θ 13 N (3/t) 2θ 13 n exp(-c 1 n) + C exp(-(1 -θ 13 )c 3 n) .
Choosing θ 13 small enough, we get the result with ρ 13 = t and c 13 small enough.

Corollary 14. For each deterministic vector d ∈ C N \ {0},

P Rd/ Rd ∈ comp(θ 13 , ρ 13 ) ∩ E op (C) ≤ exp(-c 13 n). Proof. Write u y = G -1 0 d = Fd
Rd with y ∈ C N , and let ỹ = y/ y , which can be shown to be defined w.p. 1 as in the proof of Lemma 11. Considering the event E ỹ = [ỹ defined, ỹ ∈ comp(θ 13 , ρ 13 )], our purpose is to show that

P[E ỹ ∩ E op (C)] ≤ exp(-c 13 n). Since G u/ y ỹ = y -1 0 d , it holds that E ỹ ⊂ inf v∈C n-1 , w∈comp(θ 13 ,ρ 13 ) dist G v w , span 0 d ≤ ρ 13 ,
and the result follows from Proposition 13.

We now get back to the expression (9) of dist(h 0 , H -0 ), handling the denominator Den given by [START_REF] Cook | Lower bounds for the smallest singular value of structured random matrices[END_REF].

Lemma 15. For M = F, P, or E, there exist positive constants c 15 and C 15 such that

P [ M ≥ C 15 R ] ∩ E op (C) ≤ exp(-c 15 n).
Proof. We reuse the notations of the singular value decomposition (16) of B. For any matrix M with n -1 rows, we also write M Q = Π Q M and M q = Π q M. We first consider M = F.

From Lemma 4, we know that there exist c 0 , c > 0 such that P[ Wq ≤ c 0 ] ≤ exp(-cn). We shall show that on the event [ Wq ≥ c 0 ] ∩ E op (C), there exists some C 1 > 0, such that ∀u ∈ S N-1 , Fu ≤ C 1 (1 + Ru ). This will establish that

P [ F ≥ C 1 (1 + R )] ∩ E op (C) ≤ exp(-cn). (21)
Recall that G -1 0 u = Fu Ru = v w say, or equivalently,

Bv + W * w = 0, ( 22a
)
Wv + zw = u. (22b)
Since Bv q ⊥ Bv Q , Lemma 12 and (22a) imply that

s inf v Q ≤ Bv Q ≤ W * w . Thus, v Q ≤ (C/s inf ) w on E op (C).
Writing v q = βq, Equation (22b) can be rewritten as βWq = uzw -Wv Q , which gives that |β| ≤ (1

+ (|z| + C 2 /s inf ) w )/c 0 on [ Wq ≥ c 0 ] ∩ E op (C). Since v 2 = |β| 2 + v Q 2 , there exists C 1 > 0 such that v ≤ C 1 (1 + w )
, and the inequality (21) follows.

Our next step is to show that there exists a constant

C 2 such that E op (C) ⊂ [ R ≥ C 2 ]
. It is then easy to deduce from (21

) that P [ F ≥ C R ] ∩ E op (C) ≤ exp(-cn) with C = C 1 (C -1
2 + 1). We shall assume that R < C 2 on E op (C) and obtain a contradiction if C 2 is chosen small enough. From the equation GG -1 = I N+n-1 , we have

BF + W * R = 0, ( 23a
)
WF + zR = I. (23b)
By Equation (23a), BF ≤ CC 2 on E op (C). Writing BF = BF Q + BF q and observing from ( 16) that span(BF Q ) and span(BF q ) are orthogonal, we obtain that BF Q ≤ BF Q + BF q ≤ CC 2 . Turning to (16) again and using Lemma 12, we also have

BF Q 2 = F * QΣ 2 Q * F ≥ s 2 inf F * QQ * F = s 2 inf F Q 2 ,
thus, F Q ≤ CC 2 /s inf . Now, rewriting Equation (23b) as WF q -I = -zR -WF Q and using the triangle inequality, we get that WF q -

I ≤ |z| R + WF Q ≤ (|z| + C 2 /s inf )C 2 .
Since WF q is a rank-one matrix, the set of vectors u ∈ S N-1 such that WF q u = 0 is not empty. For any such vectors, we have

(|z| + C 2 /s inf )C 2 ≥ WF q -I ≥ (WF q -I)u = 1,
which raises a contradiction if we choose C 2 < (|z| + C 2 /s inf ) -1 . The lemma is proven for M = F.

The case M = P can be shown similarly. To handle the case M = E, we first show an analogue of ( 21) where (F, R) is replaced with (E, F), and then we combine the obtained inequality with [START_REF] Haagerup | A new application of random matrices: Ext(C * red (F 2 )) is not a group[END_REF] to get that

P [ E ≥ C 1 (1 + R )] ∩ E op (C) ≤ exp(-cn)
with possibly different constants. The rest of the proof is unchanged.

The following lemma is very close to [38, Proposition 8.2], with the difference that the bound on the probability in Statement (iii) is a Berry-Esséen type bound.

Lemma 16. The following hold true:

(i) There exist c 16 , C 16 > 0 such that

P[[ g 01 G -1 ≤ C 16 ] ∩ E op (C)] ≤ exp(-c 16 n).
(ii) Let y = (y 0 , . . . , y N-1 ) T ∈ C N be a random vector with independent elements such that Ey i = 0 and E|y i | 2 = 1/n for all i ∈ [N], and let M ∈ C N×N be deterministic. Then for each η > 0,

P y * M ≤ 1 √ η M HS √ n ≥ 1 -η.
(iii) There exists c > 0 such that for each ε ≥ 0,

P x * R ≤ ε R HS √ n ∩ E op (C) ≤ cε + c √ n .
The following result is needed to prove this lemma:

Lemma 17 (Lemma 8.3 of [START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF]). Let Z 0 , . . . , Z N-1 be arbitrary non-negative random variables, and let p 0 , . . . , p N-1 be non-negative numbers such that p k = 1. Then,

P[ p k Z k ≤ t] ≤ 2 p k P[Z k ≤ 2t] for each t ≥ 0.
Proof of Lemma 16. To prove the first statement, we write g 01 = g 01 G -1 G ≤ g 01 G -1 G . By Lemma 4, there exist two constants c, c 16 > 0 such that g 01 ≥ x ≥ c with a probability larger than 1exp(-c 16 n). Moreover, G ≤ (C + |z| ∨ s sup ) on E op (C), hence the result.

We have E y * M 2 = Ey * MM * y = M 2 HS /n, thus, P[ y * M ≥ M HS / √ ηn] ≤ η by Markov's inequality. This proves Statement (ii). Turning to the third statement, we start by writing

x * R 2 = k∈[N] | R * x, e N,k | 2 = k∈[N] | x, Re N,k | 2 = k∈[N] Re N,k 2 | x, Re N,k Re N,k | 2 . ( 24
)
Define u k = Re N,k / Re N,k = (u 0,k , . . . , u N-1,k ) T . The idea of the proof is the following. By Corollary 14, u k is incompressible with high probability. Moreover, x and u k are independent. Therefore, we can use the Berry-Esséen theorem (Proposition 6) to control the behavior of the inner products x, u k . We now apply Lemma 17. Specifically, define for each k ∈ [N] the set of indices

I k = i ∈ [N] : ρ 13 √ N ≤ |u i,k | ≤ 2 √ θ 13 N .
After a small calculation using the independence of x and u k , Lemma 5 and Proposition 6,

P x | x, u k | ≤ ε 2/n ≤ L x i∈I k xi,0 u i,k , ε 2/n ≤ V k ∧ 1,
where

V k = cε √ 2 ρ 13 |I k |N -1 + 8cm 3/4 4 θ 3/2 13 ρ 3 13 1 √ |I k | ,
and c > 0 is the constant that appears in the statement of Proposition 6. Observing that k∈[N] Re N,k 2 = R 2 HS and using Lemma 17, we get that

P x k∈[N] Re N,k 2 R 2 HS | x, u k | 2 ≤ ε 2 n ≤ 2 k∈[N] Re N,k 2 R 2 HS (V k ∧ 1).
Defining the event E incomp = ∩ k∈[N] [u k ∈ incomp(θ 13 , ρ 13 )], we know from Corollary 14 that P[E c incomp ∩ E op (C)] ≤ N exp(-c 13 n). Moreover, |I k | ≥ θ 13 N/2 on E incomp for each k ∈ [N] by Lemma 8. Thus, by changing the value of the constant c above we get that

V k ≤ cε + c/ √ n on E incomp for each k ∈ [N].
Putting things together, we conclude that

P x * R ≤ ε R HS √ n ∩E op (C) = E W P x k∈[N] Re N,k 2 R 2 HS | x, u k | 2 ≤ ε 2 n 1 E op (C) ≤ 2E W k∈[N] Re N,k 2 R 2 HS (V k ∧ 1)1 E incomp + 2E W [1 E c incomp 1 E op (C) ] ≤ 2cε + 2c/ √ n + 2N exp(-c 13 n),
which leads to the required result after changing once again the value of c. Lemmas 15 and 16 lead to the following control on the denominator:

Lemma 18. There exist positive constants c 18 and C 18 such that for each η > 0,

P Den 2 ≥ C 18 (1 + η -1 ) R 2 HS ∩ E op (C) ≤ 2η + exp(-c 18 n).
Proof. Starting with the expression Den 2 = 1 + g 01 G -1 2 , and using Lemma 16-(i), we get that

P Den 2 ≥ (C -2 16 + 1) g 01 G -1 2 ∩ E op (C) ≤ exp(-c 16 n). (25)
Since

g 01 G -1 2 ≤ 2( b 01 E 2 + b 01 F 2 + x * P 2 + x * R 2 ), the event E = g 01 G -1 2 ≥ 2( b 01 E 2 + b 01 F 2 + P 2 HS /(ηn) + R 2 HS /(ηn))
is included in the event E = x * P 2 ≥ P 2 HS /(ηn) ∪ x * R 2 ≥ R 2 HS /(ηn) . . Furthermore, the event

Thus, P[E] ≤ P[E ] = P W ⊗ P x [E ] ≤ 2η by
E = g 01 G -1 2 ≥ 4s 2 sup C 2 15 R 2 + 2C 2 15 R 2 /η + 2 R 2 HS /(ηn)) is included in the event E ∪ [ E ≥ C 15 R ] ∪ [ F ≥ C 15 R ] ∪ [ P ≥ C 15 R ] ,
since P 2 HS /n ≤ P 2 . Thus, P E ∩ E op (C) ≤ 2η + 3 exp(-c 15 n) by Lemma 15. The proof is completed by combining this inequality with (25) and using the inequality R ≤ R HS .

We now turn to the numerator Num in [START_REF] Cook | Lower bounds for the smallest singular value of structured random matrices[END_REF]. We shall use the idea of decoupling that will allow us to replace the term -x * Pb 10b 01 F xx * Rx in Num with an inner product whose concentration function is manageable by means of the Berry-Esséen theorem. This decoupling idea that dates back to [START_REF] Götze | Asymptotic expansions for bivariate von Mises functionals[END_REF] has been used many times in the literature.

Lemma 19 (See in [START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF]). Let Y and Z be independent random vectors, and let Z be an independent copy of Z. Let E(Y, Z) be an event that depends on Y and Z.

Then P[E(Y, Z)] 2 ≤ P[E(Y, Z) ∩ E(Y, Z )]. Lemma 20. Let a ∈ C, u, v ∈ C N and M ∈ C N×N be deterministic. Let I ⊂ [N]. Then for each t > 0, P |x * Mx + u * x + x * v + a| ≤ t 2 ≤ E x I c ,x I c L x I (x I c -x I c ) * M I c ,I x I + x * I M I,I c (x I c -x I c ), 2t ,
where x is an independent copy of x (here we assume that the right hand side is equal to one if

I = ∅ or [N]).
P |x * Mx + u * x + x * v + a| ≤ t 2 ≤ P x I ,x I c ,x I c |x * Mx + u * x + x * v + a| ≤ t, | x * M x + u * x + x * v + a| ≤ t ≤ P x I ,x I c ,x I c |x * Mx -x * M x + u * (x -x) + (x -x) * v| ≤ 2t ,
where the second inequality is due to the triangle inequality. Developing, we get that

P x I ,x I c ,x I c |x * Mx -x * M x + u * (x -x) + (x -x) * v| ≤ 2t = P x I ,x I c ,x I c (x I c -x I c ) * M I c ,I x I + x * I M I,I c (x I c -x I c ) +u * I c (x I c -x I c ) + (x I c -x I c ) * v I c + x * I c M I c ,I c x I c -(x I c ) * M I c ,I c x I c ≤ 2t ≤ E x I c ,x I c L x I (x I c -x I c ) * M I c ,I x I + x * I M I,I c (x I c -x I c ), 2t .
We now have all the ingredients to prove Proposition 10.

Proof of Proposition 10. In the remainder, we write

E Den (η) = Den ≤ C η R HS ,
where

C η = C 1/2 18 (1 + η -1 ) 1/2 .
Given t > 0, we have

P [dist(h 0 , H -0 ) ≤ t] ∩ E op (C) 2 = P[[Num ≤ tDen] ∩ E op (C)] 2 ≤ 2P [Num ≤ tDen] ∩ E Den (η) ∩ E op (C) 2 + 2P[E Den (η) c ∩ E op (C)] 2 ,
and [START_REF] Cook | Lower bounds for the smallest singular value of structured random matrices[END_REF] and using Lemma 20, we get that for each s > 0,

P [Num ≤ tDen] ∩ E Den (η) ∩ E op (C) 2 ≤ P [Num/ R HS ≤ tC η ] ∩ E op (C) 2 = E W E x [1 [Num/ R HS ≤tC η ] ]1 E op (C) 2 ≤ E W (E x 1 [Num/ R HS ≤tC η ] ) 2 1 E op (C) .

Given an arbitrary

P x [Num ≤ s] 2 ≤ E v,w L u (v -w) * R I c ,I u + u * R I,I c (v -w), 2s = E v,w L u (v -w) * P * I c RP I u + u * P * I RP I c (v -w), 2s , ( 26
) where P I the C |I| → C N linear mapping such that if I = {i 1 < • • • < i |I| }, then P I u = (0, . . . , 0, u 1 , 0, . . . , 0, u |I| , 0, . . .),
where u j is at the position i j .

Let ξ = (ξ 0 , . . . , ξ N-1 ) be a vector of N i.i.d. Bernoulli random variables valued in {0, 1} such that P[ξ 0 = 1] = p, where the probability pwill be fixed below. This vector is assumed to be independent of everything else. Since ( 26) is true for each I ⊂ [N], we can randomize I by setting

I = {i ∈ [n] : ξ i = 1}. Setting s = R HS C η t, we obtain (E x 1 [Num/ R HS ≤tC η ] ) 2 ≤ E ξ E v,w L u (v -w) * P * I c R R HS P I u + u * P * I RP I c (v -w) R HS , 2C η t = E ξ,x,x L u (x -x ) * Π I c R R HS P I u + u * P * I RΠ I c (x -x ) R HS , 2C η t . ( 27
)
where x is a vector that has the same law as x and is independent of all other random variables. Write

y = RΠ I c (x -x ) RΠ I c (x -x ) =             y 0 . . . y N-1             , ỹ * = (x -x ) * Π I c R (x -x ) * Π I c R = ỹ0 , . . . , ỹN-1 ,
and let

α = √ n RΠ I c (x -x ) 2(1 -p) R HS , α = √ n (x -x ) * Π I c R 2(1 -p) R HS . For i ∈ I, let Z i = αỹ i [P I u] i + α[P I u] i y i .
Then the concentration function L u at the right hand side of ( 27) can be rewritten as

L u αỹ * P I u + αu * P * I y, 2/(1 -p)C η t √ n = L u i∈I Z i , 2/(1 -p)C η t √ n .
We wish to control this by using the Berry-Esséen theorem (Proposition 6). Recalling Proposition 13, define the set

J = i ∈ [N] : ρ 13 √ N ≤ |y i | ≤ 2 √ θ 13 N , |ỹ i | ≤ 2 √ θ 13 N .
By the restriction lemma 5, we have

L u i∈I Z i , 2/(1 -p)C η t √ n ≤ L u i∈I∩J Z i , 2/(1 -p)C η t √ n .
Informally, we expect that |I ∩ J| = O(n) with high probability, the E u |Z i | 2 to be lower bounded with high probability, and the E u |Z i | 3 to be upper bounded with high probability for i ∈ I ∩ J, in order to benefit from the effect of the Berry-Esséen theorem in a manner similar to Inequality [START_REF] Erdös | On a lemma of Littlewood and Offord[END_REF]. More rigorously, for each i ∈ I, we have

E u |Z i | 2 = E x 00 | αỹ i x 00 + αy i x 00 | 2 = E|x 00 | 2 α2 |ỹ i | 2 + α 2 |y i | 2 + 2α α Ex 2 00 ỹi y i ≥ n -1 ϑ( α2 |ỹ i | 2 + α 2 |y i | 2 )
for all large enough n, where ϑ = 1lim sup n |nEx 2 00 | is positive by Assumption 3. Focusing on the set I ∩ J, we get that

i∈I∩J E u |Z i | 2 ≥ n -1 ϑ i∈I∩J α 2 |y i | 2 ≥ α 2 ϑρ 2 13 |I ∩ J| nN . ( 28
) Moreover, i∈I∩J E u |Z i | 3 ≤ 32E|x 00 | 3 (α 3 + α3 ) |I ∩ J| θ 3/2 13 N 3/2 .
Then, by the Berry-Esséen theorem,

L u         i∈ c I Z i , 2/(1 -p)C η t √ n         ≤ L u i∈I∩J Z i , 2/(1 -p)C η t √ n ≤ 2/(1 -p)c √ N αρ 13 √ ϑ|I ∩ J| C η nt + 32cm 3/4 4 (α 3 + α3 ) ρ 3 13 ϑ 3/2 θ 3/2 13 α 3 1 √ |I ∩ J| ∧ 1 V ∧ 1 (here, we assume that L u ( I∩J • • • ) = V = 1 if I ∩ J = ∅).
The constant c > 0 in the term after the second inequality is the one that appears in the statement of Proposition 6. In the remainder of the proof, the value of this constant may change without mention.

At this stage of the calculation, we have

P[[dist(h 0 , H -0 ) ≤ t] ∩ E op (C)] 2 ≤ 2E W,ξ,x,x [(V ∧ 1)1 E op (C) ] + 2P[E Den (η) c ∩ E op (C)] 2 . (29)
Now, take p = 1 -θ 13 /8, and consider the event

E ξ = [|I| > N(1 -θ 13 /4)] = ξ i > N(1 -θ 13 /4) . Since E ξ = [|I| > N(p -θ 13 /8)],
we get by Hoeffding's concentration inequality [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] that

P[E c ξ ] ≤ exp(-Nθ 2 13 /32
). Consider also the event

E incomp = [y ∈ incomp(θ 13 , ρ 13 )].
By Corollary 14, there exists a constant c > 0 such that

P[E c incomp ∩ E op (C)] ≤ exp(-cn)
. On E incomp , we have that |J| ≥ θ 13 N/2 by Lemma 8. Therefore, on E ξ ∩ E incomp , it holds that

|I ∩ J| = N -|I c ∪ J c | ≥ N -|I c | -|J c | ≥ Nθ 13 /4.
It remains to control the terms α and α in the expression of V. Given a small β > 0, consider the event

E α (β) = β R HS / √ n ≤ RΠ I c (x -x ) 2(1 -p) ≤ β -1/2 R HS / √ n ∩ (x -x ) * Π I c R 2(1 -p) ≤ β -1/2 R HS / √ n . Note that α ∈ [β, β -1/2 ] and α ≤ β -1/2 , thus (α 3 + α3 )/α 3 ≤ 2β -9/2 on E α (β).
Applying Lemma 16 after setting the vector y in its statement to ((1

-ξ 0 )(x 00 -x 0 ), . . . , (1 -ξ N-1 )(x N-1,0 -x N-1 )) T / 2(1 -p)
, we get that there exists a constant c > 0 for which

P[E α (β) c ∩ E op (C)] ≤ cβ + c √ n .
Turning back to [START_REF] Loubaton | On the almost sure location of the singular values of certain Gaussian block-Hankel large random matrices[END_REF], we can now conclude by writing

P[[dist(h 0 , H -0 ) ≤ t] ∩ E op (C)] 2 ≤ 2E W,ξ,x,x [V1 E ξ 1 E incomp 1 E α (β) 1 E op (C) ]] + 2P[E c ξ ] + 2P[E c incomp ∩ E op (C)] + 2P[E α (β) c ∩ E op (C)] + 2P[E Den (η) c ∩ E op (C)] 2 ≤ c n β √ η t + β -9/2 √ n + β + η + 1 √ n + exp(-c n).
If we take η ∝ n -1/2 and β ∝ n -1/11 (without further optimization of these exponents), then we get that

P[[dist(h 0 , H -0 ) ≤ t] ∩ E op (C)] 2 ≤ c(n 59/44 t + n -1/11 ) + exp(-c n),
which proves Proposition 10. Theorem 1: end of proof. First note that for any k ∈ [n], Proposition 10 continues to hold when dist(h 0 , H -0 ) is replaced by dist(h k , H -k ), by the same proof. When n ≤ k < N + n, too, the proof continues to be valid once the roles of A and z are interchanged. Indeed, one can check that the argument is simpler and hence is omitted. Applying Lemma 9, we obtain that

P inf u∈incomp(θ 7 ,ρ 7 ) Hu ≤ t ∩ E op (C) ≤ c(n 81/88 t 1/2 + n -1/22 ) + exp(-c n).
Using Proposition 7 along with the characterization (5) of the smallest singular value, we obtain Theorem 1 with α = 81/88 and β = 1/22.

Remark 1. The proof of Proposition 10 shows that the origin of the slow decreasing term n -β = n -1/22 at the right hand side of the last inequality is the O(1/ √ n) decay that is optimal while using the Berry-Esséen theorem, as shown by Inequality [START_REF] Erdös | On a lemma of Littlewood and Offord[END_REF]. To obtain a better decay rate of the concentration functions, one can use the so-called Littlewood-Offord theory [START_REF] Erdös | On a lemma of Littlewood and Offord[END_REF] instead. This was the approach of [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF][START_REF] Tao | Random matrices: universality of ESDs and the circular law[END_REF][START_REF] Tao | Inverse Littlewood-Offord theorems and the condition number of random discrete matrices[END_REF][START_REF] Vershynin | Invertibility of symmetric random matrices[END_REF] to solve small singular value problems. Remark 2. Assumption 3 was needed in the proof of Proposition 10 to ensure that the variance at the left hand side of ( 28) is bounded away from zero.

Proof of Theorem 2

A well established technique for studying the spectral behavior of large random non-Hermitian matrices is Girko's so-called hermitization technique [START_REF] Girko | The circular law[END_REF]. This is intimately tied to the logarithmic potential of their spectral measures. In all the remainder, we shall write Y = XJX * , and recall that {λ 0 , . . . , λ N-1 } are the eigenvalues of this matrix. The logarithmic potential U µ n : C → (-∞, ∞] of the spectral measure µ n can then be written as

U µ n (z) = - C log |λ -z| µ n (dλ) = - 1 N N-1 i=0 log |λ i -z| = - 1 N log | det(Y -z)| = - 1 2N log det(Y -z)(Y -z) * = -log λ ν n,z (dλ),
where the probability measure ν n,z is the singular value distribution of Yz, given as

ν n,z = 1 N N-1 i=0 δ s i (Y-z) .
The above observation is at the heart of the hermitization technique. It transforms the eigenvalue problem into a problem of singular values. To study the asymptotic behavior of µ n , we need to study the asymptotic behavior of U µ n (z) for Lebesgue almost all z ∈ C. To that end, we need to perform the two following steps, see, e.g., [7, Lemma 4.3]:

Step 1: Show that for almost all z ∈ C, ν n,z ⇒ ν z (a deterministic probability measure) in probability.

Step 2: Show that the function log is uniformly integrable with respect to the measure ν n,z for almost all z ∈ C in probability. That is,

∀ε > 0, lim T →∞ lim sup n≥1 P ∞ 0 | log λ| 1 | log λ|≥T ν n,z d(λ) > ε = 0. (30)
By achieving these two steps, we conclude that there exists a probability measure µ such that µ n ⇒ µ in probability, and such that U µ (z) =log |λ| νz (dλ) C-almost everywhere.

Step 3: Identify µ. This can be done by relying on the generic relation µ = -(2π) -1 ∆U µ , where ∆ is the Laplace operator defined on D (C), the space of Schwarz distributions on C.

Step 1: Weak convergence of ν n,z . Going a bit further than what is required for this step, we shall show that for each z ∈ C, there exists a probability measure ν z such that ν n,z ⇒ ν z almost surely. As is usual in random matrix theory, this convergence will be established through the convergence of the associated Stieltjes transforms. For this, it will be convenient to consider the Hermitian matrix

Σ(z) = 0 Y -z Y * -z 0 whose spectral measure νn,z = 1 2N N-1 i=0 δ s i (Y-z) + δ -s i (Y-z)
is the symmetrized version of ν n,z (ν n,z is symmetric in the sense that νn,z (S ) = νn,z (-S ) for each Borel set S ⊂ R). It is enough to show that νn,z converges weakly a.s. to a probability measure νz . Given η ∈ C + = {w ∈ C, w > 0}, let us write

Q(z, η) = (Σ(z) -η) -1 = η[(Y -z)(Y -z) * -η 2 ] -1 (Y -z)[(Y -z) * (Y -z) -η 2 ] -1 [(Y -z) * (Y -z) -η 2 ] -1 (Y -z) * η[(Y -z) * (Y -z) -η 2 ] -1 = Q 00 (z, η) Q 01 (z, η) Q 10 (z, η) Q 11 (z, η) , (31)
which is the resolvent of Σ(z) in the complex variable η. The a.s. convergence ν n,z ⇒ ν z is a consequence of the following theorem, whose proof is provided in Section 5. Note that the Stieltjes transform of a symmetric probability measure is purely imaginary with a positive imaginary part on the positive imaginary axis. ----

→ n→∞ γ -1 p(z, η), 1 N tr Q 01 (z, η) a.s. ----→ n→∞ γ -1 d(z, η), η ∈ C + , (32)
where for each z ∈ C, (p(z, •), d(z, •)) is a pair of holomorphic functions on C + such that γ -1 p(z, •) is the Stieltjes transform of a symmetric probability measure, |d(z, η)| ≤ γ/ η, and writing p(z, ıt) = ıh(z, t) for t > 0, the pair (h(z, t), d(z, ıt)) ∈ (0, ∞) × C uniquely solves the equations

-th(z, t) + zd(z, ıt) = u(h(z, t), d(z, ıt), t) -γ, (33a)
zh(z, t) + td(z, ıt) = v(h(z, t), d(z, ıt), t), (33b)
where

u(h, d) = 1 2π 2π 0 h 2 + |d| 2 + d exp(ıθ) h 2 + |1 + d exp(ıθ)| 2 dθ, v(h, d) = 1 2π 2π 0 h exp(-ıθ) h 2 + |1 + d exp(ıθ)| 2 dθ. ( 34
)
It is well known that the convergence of (2N) -1 tr Q(z, η) in [START_REF] Pastur | A simple approach to the global regime of Gaussian ensembles of random matrices[END_REF] implies that νn,z ⇒ νz (symmetric) a.s., with Stieltjes transform γ -1 p(z, •). The system of equations [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF] which provides the values of p(z, •) on the positive imaginary axis completely determines the measure νz . The function d(z, ıt) will be used below to identify the limit measure µ.

Step 2: uniform integrability. Noting that log is unbounded near both 0 and ∞, we start with the uniform integrability near zero. Proposition 22. Let Assumption 1 hold true, and assume that z 0. Then, there exist two constants α, C > 0 such that -ı

N E tr Q(z, ıt) ≤ C(1 + t -α n -1/2 ).
The proof is sketched at the end of Section 5. We just point out that by using this proposition and by making some elementary Stieltjes transform calculations (see [START_REF] Guionnet | The single ring theorem[END_REF]Proposition 14]), one can show that there exist constants K, ρ > 0 such that E σn ([-x, x]) ≤ K(x ∨ n -ρ ). This is a so-called local Wegner estimate on the number of intermediate singular values [START_REF] Bordenave | Around the circular law[END_REF].

The smallest singular value of Yz is controlled by Theorem 1 with A = J. Thanks to the boundedness of the fourth moment specified by Assumption 1, we know from [START_REF] Yin | On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix[END_REF] that X a.s.

----→ n→∞ 1 + √ γ. Thus, the probability of the event [ X ≤ C] in the statement of Theorem 1 converges to 1 by setting C = 2 + √ γ.

Thanks to these controls, we get that for all z ∈ C \ {0}, ∀ε > 0, lim

δ→0 lim sup n≥1 P δ 0 log λ ν n,z (dλ) > ε = 0, (35)
see [START_REF] Guionnet | The single ring theorem[END_REF]Proposition 14] for a proof that results of the type of Proposition 22 and Theorem 1 lead together to [START_REF] Tao | Random matrices: universality of ESDs and the circular law[END_REF].

Remark 3. The uniform integrability only in probability and the convergence only in probability in Theorem 2 are due to the slow rate β = 1/22 in the statement of Theorem 1.

To complete

Step 2, it only remains to establish the uniform integrability of log near infinity. But this result follows immediately from the identity λ≥T log λ ν n,z (dλ) = 0 a.s. for all large n, which is valid for T > (1

+ √ γ) 2 + |z| + 1.
Step 3: Identification of µ. We use an idea that dates back to [START_REF] Feinberg | Non-Hermitian random matrix theory: method of Hermitian reduction[END_REF] and that has been frequently used in the literature devoted to large non-Hermitian matrices. Define on C × (0, ∞) the regularized versions of U µ n (z) and U µ (z) respectively:

U n (z, t) = - 1 2N log det((Y -z) * (Y -z) + t 2 ), and
U(z, t) = - 1 2 log(λ 2 + t 2 ) νz (dλ) .
In parallel, let us get back to the resolvent Q(z, η) defined in [START_REF] O'rourke | Products of independent elliptic random matrices[END_REF]. By Jacobi's formula,

∂ zU n (z, t) = 1 2N tr(Y -z)((Y -z) * (Y -z) + t 2 ) -1 = 1 2N tr Q 01 (z, ıt).
Letting n → ∞ we know from Theorem 21 that ∂ zU n (z, t) → (2γ) -1 d(z, ıt) a.s. At the same time, U n (z, t) → U(z, t) a.s. since ν n,z ⇒ ν z . We can therefore assert that ∂ zU(z, t) = (2γ) -1 d(z, ıt) in D (C), and then extract the properties of µ from the equation

µ = - 1 2π ∆U µ = - 2 π lim t→0 ∂ z ∂ zU(z, t) = - 1 γπ lim t→0 ∂ z d(z, ıt) in D (C).
This line of thought leads to the following proposition, which proof can be done along the lines of [START_REF] Cook | Non-Hermitian random matrices with a variance profile (I): deterministic equivalents and limiting ESDs[END_REF]Section 7], and is omitted.

Proposition 23. As t → 0, the function (2γ) -1 d(•, ıt) converges to ∂ zU µ (•) in D (C).
The following lemma specifies the properties of the function g defined in [START_REF] Bhattacharjee | Estimation of autocovariance matrices for infinite dimensional vector linear process[END_REF], that we shall need. Its proof is straight-forward.

Lemma 24. Consider the function g on the interval [0 ∨ (γ -1), γ]. It is analytical and increasing on (0 ∨ (γ -1), γ). Moreover, g(0 ∨ (γ -1)) = 0 ∨ (γ -1) 3 /γ, and g(γ) = γ(γ + 1).

By this lemma, g has an inverse g -1 on [0 ∨ (γ -1) 3 /γ, γ(γ + 1)] that takes this interval to [0 ∨ (γ -1), γ]. On (0 ∨ (γ -1) 3 /γ, γ(γ + 1)), the function g -1 is analytical and increasing.

By showing that d(z, ıt) converges as t → 0 point-wise for each z 0 and by identifying the limit function b(z), we get the following proposition whose proof is given in Section 6.

(z) =            -g -1 (|z| 2 )/z if 0 < |z| ≤ γ(γ + 1), -γ/z if |z| ≥ γ(γ + 1). If γ > 1, then b(z) =                      -(γ -1)/z if 0 < |z| ≤ (γ -1) 3/2 / √ γ, -g -1 (|z| 2 )/z if (γ -1) 3/2 / √ γ ≤ |z| ≤ γ(γ + 1), -γ/z if |z| ≥ γ(γ + 1). Then ∂ zU µ (z) = (2γ) -1 b(z) in D (C).
C ϕ dµ = - 1 2π C ϕ(z)∆U µ (z) dz = - 1 γπ C ϕ(z)∂ z b(z) dz = C ϕ(z) f (z) dz,
where, by Proposition 25, the density f (z) of µ on S is given by

f (z) =                1 γπ ∂ z g -1 (|z| 2 ) z = 1 γπ ∂ |z| 2 g -1 (|z| 2 ) if 0 ∨ ((γ -1) 3 /γ) < |z| 2 < γ(γ + 1), 0 elsewhere (36)
Hence the density f depends on z through |z| only, and thus µ is rotationally invariant on S . Now we consider µ on the boundary ∂S . We deal separately with the cases γ ≤ 1 and γ > 1. First suppose γ ≤ 1. Let 0 < s < r < γ(γ + 1). Changing to polar co-ordinates, we get

µ({z : |z| ∈ [s, r]}) = 1 γπ {z:|z|∈[s,r]} ∂ |z| 2 g -1 (|z| 2 ) dz = γ -1 g -1 (r 2 ) -γ -1 g -1 (s 2 ).
But since γ -1 g -1 (0) = 0 and γ -1 g -1 (γ(γ + 1)) = 1, we get that µ({0}) = µ({z : |z| = γ(γ + 1)}) = 0, establishing the formula in Theorem 2 for γ ≤ 1. Now suppose γ > 1. Put a = (γ-1) 3/2 / √ γ. If we set 0 < s < r < a, we obtain from (36) that µ({z

: |z| ∈ [s, r]}) = 0. If a < s < r < γ(γ + 1), then µ({z : |z| ∈ [s, r]}) = γ -1 g -1 (r 2 ) -γ -1 g -1 (s 2
) by the same derivation as for γ ≤ 1. Now we claim that µ({z : |z| = a}) = 0. To show this, let φ : [-1, 1] → [0, 1] be a smooth function such that φ(0) = 1 and φ(-1) = φ(1) = 0. Given ε > 0, define the C → [0, 1] function ψ ε (z) = φ((|z|a)/ε), which is supported on the ring {z : a -ε ≤ |z| ≤ a + ε}. It is then enough to show that ψ ε dµ → 0 as ε → 0. Indeed, by an integration by parts, we get that

ψ ε dµ = - 1 γπ ψ ε (z) ∂ z b(z) dz = 1 γπ ∂ z ψ ε (z) b(z) dz = 1 2εγπ 1 |z| φ |z| -a ε c(|z|) dz,
where the function c(ρ) = zb(z) for ρ = |z| is a real bounded function near ρ = a that satisfies c(a) = 1 -γ by Proposition 25. Making a Cartesian to polar variable change and using the dominated convergence theorem, we get that ψ ε dµ → ε→0

1-γ γ (φ(1) -φ(-1)) = 0. Since γ -1 g -1 (a 2 ) = 1 -γ -1
, we can infer now that µ({z : s ≤ |z| ≤ r}) = γ -1 g -1 (r 2 ) -(1 -γ -1 ) for each s ∈ (0, a) and each r ∈ [a, γ(γ + 1)). Letting s ↓ 0 and r ↑ γ(γ + 1), and recalling that g -1 (γ(γ + 1)) = γ, we get that µ({z : |z| < γ(γ + 1)}) = 1 -(1 -γ -1 ) + µ({0}). Similarly to µ({z : |z| = a}) = 0, we can show that µ({z : |z| = γ(γ + 1)}) = 0. We therefore get that µ({0}) = 1 -γ -1 , and hence the formula in Theorem 2 is verified also for γ > 1.

Limit singular value distribution

Given (z, η) ∈ C × C + , α ∈ R, and a sequence (a n (z, η)) n of complex numbers, the notation a n = O η (n α ) (or a n = O t (n α ) when η = ıt) will refer in this section to the existence of a constant C > 0 and two non-negative integers k and such that |a n (z, η)| ≤ C|η| k ( η) n α . The constants C, k, and may depend on z but not on η or n. If a n (z, η) is a matrix, then the notations a n = O η (n α ) and a n = O t (n α ), are to be understood in a uniform entry-wise sense.

Proof of Theorem 21. We first state that the n -1 tr Q i j (z, η), i, j = 0, 1 concentrate around their means, and that the elements of X can be replaced by complex Gaussian random variables. The proof of the following proposition is standard and is omitted.

Proposition 26. Under Assumption 1, for each (z, η) ∈ C × C + , if n → ∞, 1 n tr Q 00 (z, η) tr Q 01 (z, η) tr Q 10 (z, η) tr Q 11 (z, η) - 1 n
tr EQ 00 (z, η) tr EQ 01 (z, η) tr EQ 10 (z, η) tr EQ 11 (z, η) a.s.

--→ 0.

Let x N = (U + ıV)/ √ 2n, where U and V are real independent standard Gaussian random variables. Define

X N = x N i j N-1,n-1 i, j=0
, where the x N i j are independent copies of x N . Let Q N i j (z, η) be the analogues of the Q i j (z, η), obtained by replacing the matrix X with X N . Then, 1 n tr EQ 00 (z, η) tr EQ 01 (z, η) tr EQ 10 (z, η) tr EQ 11 (z, η) -1 n tr EQ N 00 (z, η) tr EQ N 01 (z, η) tr EQ N 10 (z, η) tr EQ N 11 (z, η)

= O η (n -1/2 ).
Thanks to Proposition 26, we reduce our problem to the study of n -1 tr EQ i j (z, η) in the complex Gaussian case. We now invoke the so-called Integration by Parts (IP) formula for Gaussian variables [START_REF] Pastur | A simple approach to the global regime of Gaussian ensembles of random matrices[END_REF]. Let w = (w 0 , . . . , w n-1 ) T be a complex Gaussian random vector with Ew = 0, Eww T = 0, and E[ww * ] = Ξ. Let ϕ = ϕ(w 0 , . . . , w n-1 , w0 , . . . , wn-1 ) be a C 1 complex function which is polynomially bounded together with its derivatives. Then, the IP formula reads as

Ew k ϕ(w) = n-1 =0 [Ξ] k E ∂ϕ(w) ∂ w . (37)
We shall apply this formula to the case w ≡ X and ϕ ≡ u * Qv where Q = Q(z, η) is the resolvent given by Eq. ( 31) (seen as a function of X), and u and v are deterministic vectors in C 2N . By a standard derivation, we have

∂u * Qv ∂ xi j = -u * Q 0 XJe n, j e * N,i XJ -1 e n, j e * N,i 0
Qv.

In particular, by taking u = e 2N,k and v = e 2N, for k, ∈ [N], we obtain that

∂[Q 00 ] k, ∂ xi j = -[Q 01 XJ -1 ] k j [Q 00 ] i -[Q 00 XJ] k j [Q 10 ] i , (38)
and by taking u = e 2N,k and v = e 2N,N+ for k, ∈ [N], we get

∂[Q 01 ] k, ∂ xi j = -[Q 00 XJ] k j [Q 11 ] i -[Q 01 XJ -1 ] k j [Q 01 ] i . (39)
Given M ∈ C n×n , we shall also use the trivial relations

[MJ k ] •, j = [M] •, j+k and [J k M] i,• = [M] i-k,•
, where both the sum j + k and the difference ik are taken modulo-n.

We can now start our calculations. Recalling that x j refers to the j th column of X for j ∈ [n], our first task is to study quadratic forms of the type x * k Q 00 x and x * k Q 01 x . Define the matrices

A 00 = E x * k Q 00 x n-1 k, =0
and

A 01 = E x * k Q 01 x n-1 k, =0
.

It is obvious that X L = XJ m for each m ∈ Z. Thus, given a measurable function f : C N×N → C N×N and the integers k, , m ∈ [n], it holds that

x * k+m f (XJX * )x +m = e * n,k+m X * f (XJX * )Xe n, +m = e * n,k J -m X * f (XJ m JJ -m X * )XJ m e n, L = x * k f (XJX * )
x , where the index summations are taken modulo-n. As a consequence, the matrices A 00 and A 01 are circulant matrices, a fact very useful to us.

Starting with A 00 , we have by the IP formula [START_REF] Van Trees | Optimum array processing: Part IV of detection, estimation, and modulation theory[END_REF],

Ex * k Q 00 x = N-1 i, j=0 E[( xik [Q 00 ] i j )x j ] = 1 n i, j E ∂( xik [Q 00 ] i j ) ∂ x j = 1 n i, j 1 i= j 1 k= E[Q 00 ] i j - 1 n i, j E[Q 01 XJ -1 ] i xik [Q 00 ] j j - 1 n i, j E[Q 00 XJ] i xik [Q 10 ] j j (using 38) = 1 k= E tr Q 00 /n -E [X * Q 01 XJ -1 ] k tr Q 00 /n -E [X * Q 00 XJ] k tr Q 10 /n .
We also have

Ex * k Q 01 x = N-1 i, j=0 E[( xik [Q 01 ] i j )x j ] = 1 n i, j E ∂( xik [Q 01 ] i j ) ∂ x j (using 39) = 1 k= E[tr Q 01 /n] -E [X * Q 00 XJ] k tr Q 11 /n -E [X * Q 01 XJ -1 ] k tr Q 01 /n .
In the right side of the above two expressions we have terms of the type E [• • • ] k tr Q i j /n . We now need to decouple [• • • ] k from tr Q i j /n. Specifically, we have the following lemma.

We now prove that th(z, t) = t p(z, ıt) → γ as t → ∞. The functions h(z, t) and d(t) satisfy (33a), and furthermore, 0 ≤ h(z, t), |d(t)| ≤ γ/t. From the expressions (51), it is clear that (h 2 +d 2 )I(h(z, t), d(t)) and d(t)J(h(z, t), d(t)) converge to zero as t → ∞. The result is then obtained from Equation (50a).

We also need to prove that (h(z, t), d(z, ıt)) satisfy the system (33) for each t > 0. By the convergence q 00 (z, •) → p(z, •), we get that Eν n,z ⇒ νz . In particular, Eν n,z is tight. Let a > 0 be such that inf n Eν n,z ([-a, a]) ≥ 1/2. By an easy derivation involving the expression of a Stieltjes transform, we then get that s(z, ıt) ≥ γ n t/(2(a 2 + t 2 )). Therefore, for each t > 0, the matrix P defined in (46) satisfies P ≥ γt/(4(a 2 + t 2 ))I in the semidefinite ordering for all large enough n. By repeating the argument that follows Equation (46), we obtain that (p(z, ıt), d(z, ıt)) solve the system [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF].

The proof of Theorem 21 is completed by combining Proposition 26 with the convergence of q 00 (z, •) to p(z, •).

Proposition 22: Sketch of proof. Assume first that X L = X N , where X N was defined in the statement of Proposition 26. Fixing z 0, and writing q 00 (z, ıt) = ıs, we obtain from Equations ( 44), ( 45), (47), and (48) that (s, q 01 ) satisfy a system which is a finite-n analogue to Equations (49) with a O t (n -1 ) error. This system can be used to show that there exist constants α, C > 0 such that s ∈ (0, C(1 + n -1 t -α )] for t ∈ (0, 1]. The Gaussian assumption is then removed with the help of Proposition 26.

Identification of µ. Proof of Proposition 25

The following preliminary lemma can be proven by inspecting Equations (49) and by using that p(z, •)/γ is the Stieltjes transform of νz .

Lemma 29. For each z 0, the function h(z, t) is bounded for t ∈ (0, ∞), and h(z, t)/t is lower-bounded by a positive constant for t ∈ (0, 1]. Moreover, |d(z, ıt)| ≤ C/|z| for C > 0.

In the proof of Proposition 25, we shall use the fact that (h(z, t), d(z, ıt)) satisfies the system of equations (50). We rewrite Equation (50a) as γ = (h 2 + |d| 2 )I(h, d) + d J(h, d)zd + th, and Equation (50b) as zh + t d = hJ(h, d), or equivalently, as zd = d J(h, d) -t|d| 2 /h. Since h(z, t) > 0 for t > 0, we can use the expressions (51) of the integrals I(h, d) and J(h, d) to obtain Reducing to the same denominator, we get after some simple manipulations that |z| 2 = g(y), where g is the function given in the statement of Theorem 2. Let us delineate the domain of variation of y. Equation |z| 2 = g(y) = (1 -γ + 2y) 2 y/(y+1) shows that y(y+1) > 0, thus y < -1 or y > 0. By Equation (55), γ 1-γ+2y ≥ y 2 |z| 2 = y(y+1) (1-γ+2y) 2 . We therefore get that 2y + 1 -γ > 0 and furthermore, by rearranging the terms of the inequality above, that y 2 + (1 -2γ)y + γ(γ -1) ≤ 0. The last inequality implies that γ -1 ≤ y ≤ γ. In conclusion, we get that y ∈ [0 ∨ (γ -1), γ] \ {0}.

γ = h 2 +
The case t k /h(z, t k ) → α > 0. Here we get of course that h(z, t k ) → 0. Taking a subsequence if necessary, we shall assume that d(t k ) → b. Getting back to the system (52) and taking t k to zero, we get that These statements show that given z 0, the accumulation points b reduce to a genuine limit. Moreover, the behavior of this limit b(z) is as described in the statement of Proposition 25.

From

1 =

 1 αI N with α 2 = 10 -2.5 .

Lemma 12 .

 12 s n-3 (B) ≥ s inf . Proof. The matrix b 10 b * 10 + BB * is a principal supmatrix of the Hermitian matrix A -1 (A -1 ) * . Using the variational representation of the eigenvalues of A -1 (A -1 ) * , we get that s n-2 (b 10 b * 10 +BB * ) ≥ s 2 inf . By Weyl's interlacing inequalities [23, Chap. 4], s n-3 (BB * ) ≥ s n-2 (b 10 b * 10 + BB * ), hence the result. Proposition 13. There exist θ 13 ∈ (0, 1), ρ 13 > 0, and c 13 > 0 such that for each d ∈ C N , P inf v∈C n-1 , w∈comp(θ 13 ,ρ 13 ) dist G v w , span 0 d ≤ ρ 13 ∩ E op (C) ≤ exp(-c 13 n).

Proof.

  Assume without loss of generality that I = [|I|]. Write x = x I x I c , and x = x I x I c . Using Lemma 19 with Y = x I , Z = x I c , and Z = x I c , we get

  I ⊂ [n], we denote as u ∈ C |I| , v ∈ C |I c | , and w ∈ C |I c | three independent vectors, independent of everything else, such that u L = x I and v, w L = x I c . Recalling the expression of Num in

Theorem 21 .

 21 Let Assumption 1 hold true. Then 1 2N tr Q(z, η) a.s.

Proposition 25 .

 25 Let b(z) be the function defined on C \ {0} as follows: If γ ≤ 1, then b

By Lemma 24 ,

 24 b(z) = b(u + ıv) is continuously differentiable as a function of u, v on the open set S = {z ∈ C : z 0, |z| 2 (γ -1) 3 /γ, |z| 2 γ(γ + 1)}. Therefore, ∆U µ = 4∂ z ∂ zU µ coincides with 2γ -1 ∂ z b in D (S ), where ∂ z b is the pointwise derivative of b w.r.t. z. Specifically, for each test function ϕ ∈ C ∞ c (S ), the set of compactly supported real smooth functions on C, we have

2 + |b| 2 = r 2 + y 2 |z| 2 = γ 1 - 2 -4 y 2 |z| 2 = 1 ( 1

 221211 ) → b ∈ C and h(z, t k ) → r ≥ 0. The pair (r, b) satisfies the equationsγ 2 ∆(r, b) = (r 2 + |b| 2 ) 2 , and(53)2zb = 1 -γγ r 2 + |b| 2 . (54)By Equation (54), the number y = -zb is real and satisfiesr γ + 2y . (55) Moreover, we have ∆(r, b) = ((γ/(1 -γ + 2y) + 1) 2 -4y 2 /|z| 2 . Replacing in (53), we get γ 1 -γ + 2y + 1 -γ + 2y) 2 .

γ 1 - 1 ( 1 •

 111 |b| 2 = |b| 2 + α|b| 2 1 -|b| 2 , 2zb|b| 2 = (1 -γ)|b| 2 -γ + α|b| 2 (1 -|b| 2 ).The first equation implies that |b| {0, 1}, and that α = γ |b| 2 -1 |1-|b| 2 | . Replacing α by its value in the second equation, we get after a simple calculation that 2zb = 1 -2γ -1-|b| 2 |1-|b| 2 | . Here we need to consider two cases: either |b| < 1 or |b| > 1. If |b| < 1, we get from the last equation that b = -γ/z (thus, |z| ≥ γ). Plugging in the expression of α, we get thatα = |z| 2 1 γ -1 |z| 2 -γ 2 . Since α > 0, this implies that |z| > γ(γ + 1). If |b| > 1, we obtain that b = (1 -γ)/z, thus, |z| < |1 -γ| and α = |z| 2 γ (1-γ) 2 --γ) 2 -|z| 2 .Using again that α > 0, we get after a small calculation that γ > 1 and |z| 2 ≤ (γ -1) 3 /γ. Let us summarize our conclusions for clarity.• If t k /h(z, t k ) → 0,let b be an arbitrary accumulation point of d(z, t k ), and let y = -zb. If γ ≤ 1, then y ∈ (0, γ], and |z| 2 = g(y) ∈ (0, γ(γ + 1)]. If γ > 1, then y ∈ [γ -1, γ], and |z| 2 = g(y) ∈ [(γ -1) 3 /γ, γ(γ + 1)]. If t k /h(z, t k ) converges to a positive constant, let b be an arbitrary accumulation point of d(z, t k ). If γ ≤ 1, then |z| 2 > γ(γ + 1), and b = -γ/z. If γ > 1, thein either |z| 2 > γ(γ + 1) in which case b = -γ/z, or |z| 2 < (γ -1) 3 /γ, in which case b = (1 -γ)/z.

  the point-wise convergence d(z, ıt) → t→0 b(z) for z 0 and Lemma 29, we get that d(•, ıt) → t→0 b(•) in D (C). Thus, (2γ) -1 b(z) = ∂ zU µ (z) in D (C) by Proposition 23.

  = (h 2 + |d| 2 + 1) 2 -4|d|2 . We now let t → 0. Here, each sequence t k → 0 satisfies one of two cases : either t k /h(z, t k ) → 0, or t k /h(z, t k ) → α where α is a positive number. Indeed, Lemma 29 shows that t k /h(z, t k ) → ∞ is excluded.The case t k /h(z, t k ) → 0. Using Lemma 29, and taking a further subsequence, still denoted as (k), we can assume that d(t k

	|d| 2 ∆(h, d) 2zd = 1 -√ h 2 + |d| 2 + 1 + t h 2 + |d| 2 , h √ ∆(h, d) -2|d| 2 t h	= 1 -γ -	γ h 2 + |d| 2 +	h t	h 2 + 1 -|d| 2 ,	(52)
	where ∆(h, d)

Acknowledgments

The visit of AB to France has been funded by the Indo-French Center for Applicable Mathematics project High Dimensional Random Matrix Models with Applications. This work has been partially supported by the French ANR grant HIDITSA (ANR-17-CE40-0003). The authors would like to thank Monika Bhattacharjee, Nicholas Cook, and David Renfrew for fruitful discussions.

 Lemma 27.For each i, j ∈ {0, 1} and each k, ∈ [n],

Var tr Q i j /n = O η (n -2 ) and Var x * k Q i j x = O η (n -1 ).

This lemma can be proven with the help of, e.g., the so-called Poincaré-Nash inequality [START_REF] Chatterjee | A new method for bounding rates of convergence of empirical spectral distributions[END_REF], [START_REF] Pastur | A simple approach to the global regime of Gaussian ensembles of random matrices[END_REF], which is a particular case of the Brascamp-Lieb inequality [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]. A result of this sort is standard in random matrix theory. We omit its proof for lack of space.

Let us write q i j = q i j (z, η) = n -1 E tr Q i j (z, η) for i, j ∈ {0, 1}. Using Lemma 27, and applying the Cauchy-Schwartz inequality, it is easy to see that

Since Y is a square matrix, we see from [START_REF] O'rourke | Products of independent elliptic random matrices[END_REF] that q 00 = q 11 . Thus, the equations above can be written in a matrix form as A 00 (I n + q 10 J) + q 00 A 01 J -1 = q 00 I n + O η (n -3/2 ), and ( 40)

Let us give these equations a more symmetric form. Developing (41) × q 00 J -1 -(40) × (I + q 01 J -1 ), we get that

Similarly, taking (40) × q 00 J -(41) × (I + q 10 J),

A 01 q 2 00 -(I n + q 10 J)(I n + q 01 J -1 ) = q 2 00 Jq 01 (I n + q 10 J)

Now, by using the obvious identity Q(Σ -η) = I 2N we obtain

-zQ 00 -ηQ 01 + Q 00 XJX * = 0, (the similar equations involving the terms Q 10 and Q 11 will not be used). Taking the traces of the expectations, we get

-zq 00 -ηq 01 + n -1 tr A 00 J = 0, (

where

Using the normal family theorem, let us extract from the sequence (n) a subsequence (still denoted as (n)) such that q (n) 00 (z, •), q (n) 01 (z, •), and q (n) 10 (z, •) converge to holomorphic functions in the sense of uniform convergence on the compact subsets of C + . Denote these functions respectively as p(z, •), d(z, •) and d(z, •). We shall show that they uniquely solve a system of equations on the line segment ı[C, ∞) of the positive imaginary axis, where C is some positive constant. This will show that p(z, •) is uniquely defined on C + , and that q 00 (z, •) → n p(z, •) and q 01 (z, •) → n d(z, •) on C + . We then show that t p(z, ıt) → γ as t → ∞. This will lead to the fact that γ -1 p(z, •) is the Stieltjes transform of a symmetric probability measure νz .

Assume that η = ıt where t > 0. Then, since the measure Eν n,z is symmetric, q 00 (z, ıt) = ıs(z, t) with s(z, t) > 0. Moreover, we notice from the expressions of Q 01 and Q 10 in (31) that q 10 (z, ıt) = q01 (z, ıt).

Recall that A 00 and A 01 are circulant matrices. Writing F n = n -1/2 exp(2ıπk /n) n-1 k, =0 , the circulant matrix J can be written as J = F n diag(exp(-2ıπk/n)) n-1 k=0 F * n . Notice that the matrices A 00 , A 01 and J commute, since they are circulant. Now, (42) can be rewritten as A 00 P = ıs + E where E = O t (n -3/2 ) is a circulant matrix, and

If t ≥ 2 sup n γ n , then |q 01 | ≤ 1/2, and thus, the positive definite matrix P satisfies P ≥ (1/4)I n in the semi-definite positive ordering. In view of Equation ( 45), we need an expression for n -1 tr A 00 J. We can write tr A 00 J n = ıs tr P -1 J n

Given two square matrices M 1 and M 2 of the same size, it is well known that

), we get that

By a similar derivation, and in view of Equation ( 44), we also get from Equation (43) that

Now, taking n to infinity along the subsequence (n) in Equations ( 44), ( 45), (47), and (48), writing p(ıt) = ıh(z, t) where h(z, t) ≥ 0, and noting that d(z, ıt) = d(z, ıt), the pair (h(z, t), d(z, ıt)) satisfies the system of Equations ( 33) of the statement of Theorem 21 for t ≥ 2 sup n γ n .

Let us consider the system of equations in (h, d) ∈ (0, ∞) × C

zh

where u(h, d) and v(h, d) are given by Equations [START_REF] Tao | Random matrices: the circular law[END_REF]. Writing

the system (49) can be rewritten as

By the residue theorem (derivations omitted), the integrals are given by the expressions

, and J(a, u) = 1 2u

for each a ∈ R and u ∈ C such that a 0 or |u| 1.

Lemma 28. There exists C > 0 (depending on z and γ) such that for each t ∈ [C, ∞), the system (49) has a unique solution (h, d) such that h ∈ (0, γ/t) and |d| < γ/t. Sketch of proof. Using (50b), we show that we can assume without generality loss that z and d are real. Rewriting the system (49) as (h, d) T = f ((h, d) T ), we show by computing the Jacobian matrix of f that if C is large enough, f is a Banach contraction on [0, 2γ/t] × [-γ/t, γ/t].