Random points in the unit ball of ℓ_{p}^{n}

Guillaume Aubrun

Abstract. We show that two limit results from random matrix theory, due to Marčenko–Pastur and Bai–Yin, are also valid for matrices with independent rows (as opposed to independent entries in the classical theory), when rows are uniformly distributed on the unit ball of ℓ_{p}^{n}, under proper normalization.

Mathematics Subject Classification (2000). Primary 15A52, 52A21.

Keywords. ℓ_{p}^{n} spaces, random matrices, random vectors.

Let us start with the following classical results from Random Matrix Theory. Let Z be a random variable such that

EZ = 0 and EZ^{2} = 1.  (1)

Consider an infinite array (Z_{ij}) of i.i.d. copies of Z. For each couple (n, N) of integers, let G_{n,N} be the N × n random matrix

G_{n,N} = (\frac{1}{\sqrt{N}} Z_{ij})_{1⩽i⩽N,1⩽j⩽n} .  (2)

We consider also the matrix

A_{n,N} = G_{n,N}^{†}G_{n,N}.

We may drop subscripts and write simply G and A. The matrix A is sometimes called a sample covariance matrix. Let (λ_{i}(A)) be the eigenvalues of A, arranged in decreasing order. We write λ_{max}(A) for λ_{1}(A) and λ_{min}(A) for λ_{n}(A). The spectral measure of A is the probability measure on R defined as

μ_{A} = \frac{1}{n} ∑_{i} δ_{λ_{i}(A)}.

In other words, μ_{A}(B) is the proportion of eigenvalues of A that fall in a Borel set B ⊂ R. The following theorems describe the limit behaviour of the spectrum of such large-dimensional matrices, in both global and local regime.

Research was supported in part by the European Network PHD, FP6 Marie Curie Actions, MCRN-511953 and was done in part while the author was visiting the University of Athens.

Theorem (Marčenko–Pastur [6]). Let (n, N) be a sequence of sizes tending to infinity in such a way that the ratio n/N has a limit β ∈]0, 1[. Then, almost surely, the sequence of (empirical) spectral measures (μ_{A_{n,N}}) converges weakly to the deterministic measure μ_{(β)} supported on the segment

[λ_{−}(β), λ_{+}(β)] := [(1 − \sqrt{β})^{2}, (1 + \sqrt{β})^{2}]

and with density

\frac{dμ_{(β)}}{dx} = \frac{1}{2πβx}\sqrt{(x − λ_{−}(β))(λ_{+}(β) − x)}.

Theorem (Bai–Yin [2]). Assume moreover that EZ^{4} < ∞. Let (n, N) be a sequence of sizes tending to infinity in such a way that the ratio n/N has a limit β ∈]0, 1[. Let A_{n,N} = G_{n,N}^{†}G_{n,N} with G_{n,N} defined as (2). Then almost surely, we have

lim_{n,N→∞} λ_{max}(A_{n,N}) = λ_{+}(β) = (1 + \sqrt{β})^{2},

lim_{n,N→∞} λ_{min}(A_{n,N}) = λ_{−}(β) = (1 − \sqrt{β})^{2}.

In some cases it is natural to consider a more general model of random matrices, and to weaken the hypothesis “independence of entries” to “independence of rows”. A random vector X in R^{n} is said to be isotropic if for every direction θ ∈ S^{n−1},

E⟨X, θ⟩ = 0 and E⟨X, θ⟩^{2} = 1.  (3)

It is actually enough to check (3) for θ being a vector of the canonical basis. Condition (3) is the analogue of condition (1). Note also that any random vector (unless it belongs almost surely to an affine hyplerplane) has an affine image which is isotropic. Also, (3) can be rephrased as EX ⊗ X = Id: the inertia matrix of X equals the identity matrix. Here x ⊗ x is the rank one positive operator on R^{n} defined by (x ⊗ x)(y) = ⟨x, y⟩x. Let (X_{i}) be i.i.d. copies of X, and consider the random matrices

Γ_{n,N} = \frac{1}{\sqrt{N}} ( X_{1} ; X_{2} ; ⋮ ; X_{N} )  (4)

and, as before

A_{n,N} = Γ_{n,N}^{†}Γ_{n,N} = \frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i}.

The matrix A_{n,N} is the empirical approximation of the inertia matrix of X, with N sample points. A well-studied class of random vectors is the class of vectors uniformly distributed on a convex body (see the survey [5]). If K is a convex body in R^{n} (i.e. a compact full-dimensional convex subset), the random vector X_{K} is defined as

P(X_{K} ∈ B) = \frac{vol(K ∩ B)}{vol(K)}

for any Borel set B ⊂ R^{n}. If X_{K} is isotropic, we say that K is isotropic. It is natural to wonder whether the theorems mentioned before can be extended to large classes of random vectors, especially uniformly distributed on convex bodies. We show that this holds for the simplest examples of convex bodies, the unit balls of the ℓ_{p}^{n} spaces, defined as for 1 ⩽ p < +∞ by

B_{p}^{n} = {(x_{1}, …, x_{n}) ∈ R^{n} s.t. ∑_{i=1}^{n} |x_{i}|^{p} ⩽ 1}

and B_{∞}^{n} = [−1, 1]^{n}. We simply write X_{p}^{n} instead of X_{B_{p}^{n}}. The random vector X_{p}^{n} can be obtained by simple operations from one-dimensional random variables, as shown by the following theorem due to Ball–Guédon–Mendelson–Naor [3]:

Theorem (Representation of the uniform measure on B_{p}^{n}). Let 1 ⩽ p < +∞ and (Y_{i}) be a n-tuple of i.i.d. random variables distributed according to the probability measure ν_{p} with density 1/(2Γ(1+1/p))e^{−|t|^{p}} (t ∈ R). Let also Z be an exponential random variable independent from Y (i.e. the density of Z is e^{−t}, t ⩾ 0). Then the random vector

\frac{(Y_{1}, …, Y_{n})}{(∑_{i=1}^{n} |Y_{i}|^{p} + Z)^{1/p}}

is uniformly distributed on B_{p}^{n}.

We write c_{n,p} for the unique positive number such that c_{n,p}B_{p}^{n} is isotropic, and write B̃_{p}^{n} = c_{n,p}B_{p}^{n}:

c_{n,p} = (\frac{1}{vol(B_{p}^{n})} ∫_{B_{p}^{n}} x_{1}^{2}dx_{1} … dx_{n})^{−1/2} .

We prove the following results

Theorem 1. Let (n, N) be a sequence of sizes tending to infinity in such a way that the ratio n/N has a limit β ∈]0, 1[. Let A_{n,N} = Γ_{n,N}^{†}Γ_{n,N} with Γ_{n,N} defined as (4), where (X_{i}) are independent and uniformly distributed on B̃_{p}^{n}. Then, almost surely, the sequence of empirical spectral measures (μ_{A_{n,N}}) converges weakly to the Marčenko–Pastur limit μ_{(β)}.

Remark. Theorem 1 has been obtained independently by Pajor and Pastur [7] using the Stieltjes transform method.

Theorem 2. Let (n, N) be a sequence of sizes tending to infinity in such a way that the ratio n/N has a limit β ∈]0, 1[. Let A_{n,N} = Γ_{n,N}^{†}Γ_{n,N} with Γ_{n,N} defined as (4), where (X_{i}) are independent and uniformly distributed on B̃_{p}^{n}. Then, almost surely,

lim_{n,N→∞} λ_{max}(A_{n,N}) = λ_{+}(β),

lim_{n,N→∞} λ_{min}(A_{n,N}) = λ_{−}(β).

Remark. The author was able in [1] to adapt the techniques used by Bai–Yin to the setting of random vectors uniformly distributed on unconditional convex bodies, leading to a weaker conclusion (with estimates 1 ± C\sqrt{β} instead of 1 ± \sqrt{β}, for some absolute constant C).

The proof uses the following lemma, which is an immediate consequence of the Barthe–Guédon–Mendelson–Naor representation theorem.

Lemma 1. Let Γ be defined as (4), where (X_{i}) are i.i.d. copies of X_{p}^{n}. Let B = (b_{ij}) be a N ×n random matrix whose entries are independent and distributed according to ν_{p}. Let Δ be a N ×N diagonal matrix with entries δ_{jj} = (∑_{i=1}^{n} |b_{ij}|^{p} +Z_{j})^{−1/p}, where Z_{j} are i.i.d. exponential random variables independent from B. Then the random matrices Γ and \frac{c_{n,p}}{\sqrt{N}} Δ · B have the same distribution (here · is the usual matrix product).

Proof of theorems 1 and 2. With notations from lemma 1, the matrices Γ_{n,N} and \frac{c_{n,p}}{\sqrt{N}} Δ · B have the same distribution. We set

B′ = \frac{1}{γ_{p}} B,

Δ′ = c_{n,p}γ_{p}Δ,

where γ_{p} = (Eb_{11}^{2})^{1/2}. We claim that

∥Δ′ − Id∥_{op} ⟶_{n→∞} 0 almost surely.  (5)

Using strong versions of the law of large numbers (see [2], Lemma 2) — note that E|b_{ij}|^{q} < ∞ for all q — we get that, almost surely

lim_{n,N→∞} sup_{1⩽j⩽N} |\frac{1}{n} ∑_{i=1}^{n} b_{ij}^{p} − Eb_{ij}^{p}| = 0.

Since lim_{n,N→∞} sup_{j} |\frac{1}{n}Z_{j}| = 0 almost surely, we deduce that

lim_{n,N→∞} sup_{1⩽j⩽N} |(nE|b_{11}|^{p})^{\frac{1}{p}} δ_{jj} − 1| = 0.

Now (5) follows from the fact that

c_{n,p} ∼_{n→∞} \frac{n^{1/p}(E|b_{11}|^{p})^{1/p}}{(Eb_{11}^{2})^{1/2}} .

Consider now A_{n,N} = Γ_{n,N}^{†}Γ_{n,N} and A′_{n,N} = (\frac{1}{\sqrt{N}} B′)^{†}(\frac{1}{\sqrt{N}} B′). The normalization was chosen so that the matrix B′ has independent entries with variance 1, so it enters the setting of the Marčenko–Pastur and the Bai–Yin theorems. We now use the following inequalities, which are proved using the min-max characterization of eigenvalues

\frac{1}{∥Δ^{′−1}∥^{2}} λ_{i}(A′_{n,N}) ⩽ λ_{i}(A_{n,N}) ⩽ ∥Δ′∥^{2}λ_{i}(A′_{n,N}).  (6)

Theorem 2 is now a direct consequence of (5), (6) and the Bai–Yin theorem applied to the matrices (A′_{n,N}). Similarly, the use of Marčenko–Pastur theorem on the matrices (A′_{n,N}) gives that for every interval I ⊂ R, the sequence (μ_{A_{n,N}} (I)) converges almost surely to μ_{(β)}(I). We conclude by arguing that it is enough to test the weak convergence on intervals with rational endpoints (see [4], Theorem 2.2). □

References

[1] G. Aubrun. Sampling convex bodies: a random matrix approach (preprint). http:

   //www.institut.math.jussieu.fr/~aubrun/sampling.dvi.

[2] Z. D. Bai and Y. Q. Yin. Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix. Ann. Probab., 21(3):1275–1294, 1993.

[3] F. Barthe, O. Guédon, S. Mendelson, and A. Naor. A probabilistic approach to the geometry of the l_{p}^{n}-ball. Ann. Probab., 33(2):480–513, 2005.

[4] P. Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York, second edition, 1999. A Wiley-Interscience Publication.

[5] A. Giannopoulos. Notes on isotropic convex bodies (preprint). http://eudoxos.math.

   uoa.gr/~apgiannop/isotropic-bodies.ps, 2003.

[6] V. A. Marčenko and L. A. Pastur. Distribution of eigenvalues in certain sets of random matrices. Mat. Sb. (N.S.), 72 (114):507–536, 1967.

[7] A. Pajor and L. A. Pastur. Private communication.

Guillaume Aubrun Institut de Mathématiques de Jussieu, Projet Analyse Fonctionnelle, Université de Paris 6, 175 rue du Chevaleret, 75013 PARIS, France

e-mail: aubrun@math.jussieu.fr