SAMPLING CONVEX BODIES: A RANDOM MATRIX APPROACH

GUILLAUME AUBRUN

Abstract. We prove the following result: for any ε > 0, only C(ε)n sample points are enough to obtain (1+ε)-approximation of the inertia ellipsoid of an unconditional convex body in R^{n}. Moreover, for any ρ > 1, already ρn sample points give isomorphic approximation of the inertia ellipsoid. The proofs rely on an adaptation of the moments method from the Random Matrix Theory.

Warning: this version differs from the (to be) published one (the proof of the main theorem is actually slightly simpler here).

1. Introduction and the main results

Notation kept throughout the paper: The letters C, c, C′... denote absolute positive constants, notably independent of the dimension. The value of such constants may change from line to line. Similarly, C(ε) denotes a constant depending only on the parameter ε. The canonical basis of R^{n} is (e_{1}, …, e_{n}), and the Euclidean norm and scalar product are denoted by | · | and ⟨·, ·⟩. The operator norm of a matrix is denoted by ∥ · ∥. For a real symmetric matrix A, we write λ_{max}(A) (respectively λ_{min}(A)) for the largest (respectively smallest) eigenvalue of A. A convex body is a convex compact subset of R^{n} with non-empty interior. A convex body K is said to be unconditional if it is invariant under sign flips of the coordinates: for any η = (η_{1}, …, η_{n}) ∈ {−1, 1}^{n},

(x_{1}, …, x_{n}) ∈ K ⟺ (η_{1}x_{1}, …, η_{n}x_{n}) ∈ K.

We reserve the letters X, Y to denote an R^{n}-valued random vector; X_{1}, …, X_{N} are i.i.d. copies of X. If EX = 0, X is said to be centered. The random vector X is said to be isotropic if it is centered and for all y ∈ R^{n}

E⟨X, y⟩^{2} = |y|^{2}.

This is equivalent to the inertia matrix EX ⊗ X being is the identity matrix. We will consider the special case when X is uniformly distributed on a convex body K. We will then say “inertia matrix of K”, “K is isotropic^{1}”... for “inertia matrix of X”, “X is isotropic”... . The inertia ellipsoid of K is the unique ellipsoid with the same inertia matrix as K. For recent results on isotropic convex bodies, a good reference is the survey [9]. Any random vector has an affine image which is isotropic, and this image is unique up to orthogonal transformation. Thus, for affinely invariant problems we can restrict ourselves to isotropic random vectors. If we do not know the law but only N samples of the random vector X, we can only consider the empirical inertia matrix

A^{N}(X) := \frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i}.

1991 Mathematics Subject Classification. Primary 15A52,52A20.

Key words and phrases. Isotropic, random matrix, convex body, moments method.

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.

1This terminology slightly differs from [16, 9] where isotropic convex bodies are normalized to have volume 1.

The matrices A^{N}(X) tend almost surely to the identity matrix when N tends to infinity; a natural question is to quantify this convergence. This problem was considered with algorithmic motivations by Kannan, Lovász and Simonovits [12] in the case when X is uniformly distributed on a convex body. It was proved in [12] that ∥A^{N}(X)−Id∥ ⩽ ε with probability larger than 1−ε provided N ⩾ C(ε)n^{2}. This was improved by Bourgain [6] to N ⩾ C(ε)n log^{3} n and later by Rudelson [20] to N ⩾ C(ε)n log^{2} n. Rudelson proved actually the following inequality, valid for a general random vector.

Theorem (Rudelson’s inequality). For any isotropic random vector X we have

(1)  E ∥A^{N}(X) − Id∥ ⩽ C\sqrt{\frac{log n}{N}}(E|X|^{log N})^{1/ log N}

provided the right-hand side is smaller than 1.

If X is uniformly distributed on an isotropic convex body, then it satisfies

(2)  (E|X|^{p})^{1/p} ⩽ C\sqrt{n} for 2 ⩽ p ⩽ c\sqrt{n}.

This estimate was proved by Bobkov and Nazarov [4] for unconditional convex bodies and recently extended by Paouris [18] to general isotropic bodies. When plugged in Rudelson’s inequality, it yields that if N ⩾ C(ε)n log n, we have ∥A^{N}(X) − Id∥ ⩽ ε with probability larger than 1 − ε (see [10, 18]). On the other hand, when X is isotropic we have E|X|^{2} = n and consequently we must take N larger than cn log n to use Rudelson’s inequality. Note that this value N ∼ n log n is sharp for some discrete examples. The simplest is given by the isotropic random vector Y uniformly distributed on the (properly normalized) vertices of the cross-polytope

\{±\sqrt{n}e_{1}, …, ±\sqrt{n}e_{n}\}.

The matrix A^{N}(Y) is then diagonal and its diagonal coefficients are distributed as

\frac{n}{N} (p_{1}, …, p_{n}) ,

where p_{i} denote the number of balls falling in the ith urn when we put randomly, uniformly and independently N balls in n urns. This problem, known as the random allocation problem, is wellstudied and it is known (see [13], chapter 2.6) than we must take N ⩾ c(ε)n log n in order to get max(p_{i}) ⩽ (1 + ε) min(p_{i}) with probability larger than \frac{1}{2}.

We prove that for the class of unconditional convex bodies, it is possible to go below this bound of n log n and to take N proportional to n

Theorem 1. There are absolute constants C, c such that the following holds. Let 0 < ε ⩽ 1. Let X be uniformly distributed on an unconditional isotropic convex body in R^{n}. Then for N ⩾ Cn/ε^{2}, we have with probability larger than 1 − exp(−cn^{1/5})

∥A^{N}(X) − Id∥ ⩽ ε.

In other words, for every y in R^{n}

(3)  (1 − ε)|y|^{2} ⩽ \frac{1}{N} ∑_{i=1}^{N}⟨X_{i}, y⟩^{2} ⩽ (1 + ε)|y|^{2}.

We can also obtain the isomorphic analogue of theorem 1, using as few sample points as possible Theorem 2. Let ρ > 1 and N ⩾ ρn. Let X be uniformly distributed on an unconditional isotropic convex body in R^{n}. Then, with probability larger than 1 − 2 exp(−c(ρ)n^{1/5}) we have for every y in R^{n}

\frac{1}{C(ρ)}|y|^{2} ⩽ \frac{1}{N} ∑_{i=1}^{N}⟨X_{i}, y⟩^{2} ⩽ C(ρ)|y|^{2}.

Question 1. Do both results extend to all isotropic convex bodies ?

Remark. With slight modifications of the proofs, one can prove the same results for all isotropic random vectors with a law being log-concave and unconditional.

2. The random matrix approach: auxiliary results and the structure of the proof

Our proof uses standard techniques from Random Matrix Theory (RMT). A part of the classical random matrix theory deals with random vectors X with i.i.d. coordinates. Here is a reformulation of a result of Bai and Yin [2]

Theorem (Bai–Yin). Let Z be a random variable with mean 0, variance 1 and finite fourth moment. Let X^{(n)} be a random vector on R^{n} whose coordinates are i.i.d. copies of Z. We consider a sequence of integers (N_{n}) tending to infinity in such a way that the ratio n/N_{n} tends to a limit β ∈ (0, 1). Then, almost surely,

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

lim_{n→∞} λ_{min} (A^{N_{n}}(X^{(n)})) = (1 − \sqrt{β})^{2}.

This theorem is restricted to random vectors with independent coordinates. Moreover, as often in RMT, this is a limit-result. Therefore it may be hard to use to get a result in a fixed dimension. In a few cases, quantified analogues (sometimes called localized) of limit-theorems from RMT have been proved; see [14]. For Bai–Yin theorem, this has been done by S. Sodin in the special case of random signs [21], but we still lack a quantified version for general entries. Bai and Yin proved their theorem as a consequence of the following result

(4)  lim sup_{n→∞} ∥A^{N_{n}}(X^{(n)}) − (1 + β)Id∥ ⩽ 2\sqrt{β} a.s.

We follow an similar approach, except that we will rather estimate

(5)  ∥A^{N_{n}}(X^{(n)}) − Id∥ .

When β ≪ 1, the quantities involved in (4) and (5) are comparable. This is no longer true when β becomes large (i.e. when matrices involved become close to being square matrices). Because of λ_{max}, it is even impossible to obtain from (5) any non-trivial information on λ_{min} when β is larger than 3 − 2\sqrt{2} ≈ 0.172.

In this framework, the expected norm of a self-adjoint random matrix A is usually bounded from above by (EtrA^{k})^{1/k}, for even integer k (usually large, but not very large). We are led to some combinatorial problems to estimate EtrA^{k}. This is the so-called moments method initiated by Wigner. The main advantage of considering (5) rather than (4) is that the combinatorics involved are simpler. We prove the following proposition.

Proposition 1. Let X be a random vector uniformly distributed on an unconditional convex body in R^{n}, and (X_{i}) be i.i.d. copies of X. We write A for A^{N}(X), the empirical inertia matrix of X with N ⩾ n sample points. For k = n^{1/5}, we have

(6)  (E∥A − Id∥^{k})^{1/k} ⩽ C\sqrt{\frac{n}{N}} ,

where C is a universal constant.

We postpone the proof of proposition 1 to section 3. Then, the lower estimate in theorem 2 is proved using the Laplace transform technique from [15] (see section 4).

Remark. A natural question is whether the Bai–Yin theorem can be extended to random vectors uniformly distributed on convex bodies. This question needs sharper tools than the problem which is treated here. The author obtained an affirmative answer for the case of the unit ball of ℓ_{p}^{n} [1].

We now show how proposition 1 implies the theorems

Proof of theorem 1. We write A = A^{N}(X). Let N ⩾ 4C^{2}n/ε^{2}, where C is the constant appearing in proposition 1. By proposition 1, for k = n^{1/5} we have (E∥A − Id∥^{k})^{1/k} ⩽ ε/2. Markov’s inequality now implies that P(∥A − Id∥ ⩾ ε) ⩽ 2^{−k} = exp(−cn^{1/5}). □

Proof of theorem 2. We get as a consequence of proposition 1 a good estimate for the largest eigenvalue of A using the inequality ∥A∥ ⩽ ∥A − Id∥ + 1 (or alternatively, using the moments method directly on A instead of A − Id): for any N ⩾ n

P(∥A∥ ⩾ C) ⩽ C exp(−cn^{1/5}).

The smallest eigenvalue is automatically controlled by the following general proposition, proved in section 4. □

Proposition 2. For every M > 0 and ρ > 1 there are constants c = c(M, ρ) and κ = κ(M, ρ) such that, for every random vector X uniformly distributed on an isotropic convex body and any N ⩾ ρn, the empirical inertia matrix A = A^{N}(X) automatically satisfies

P (λ_{min}(A) ⩽ c) ⩽ P (λ_{max}(A) ⩾ M) + exp(−κn).

Remark. Usually in random matrix theory, it is substantially harder to deal with the smallest eigenvalue than with the largest, hence the above proposition may surprise. We emphasize that it this is only an isomorphic result.

3. Proof of proposition 1: the moments method

Proof of proposition 1. We start with the following standard symmetrization lemma

Lemma 1. Let (X_{i}) be i.i.d. copies of an isotropic random vector X. Let (ε_{i}) be i.i.d. copies of a Bernoulli random variable (P(ε = 1) = P(ε = −1) = 1/2), independent from (X_{i}). Then for any k ⩾ 1,

E ∥\frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i} − Id∥^{k} ⩽ 2^{k}E ∥\frac{1}{N} ∑_{i=1}^{N} ε_{i}X_{i} ⊗ X_{i}∥^{k} .

Proof of lemma 1. Let (X′_{i}) be an independent copy of the sequence (X_{i}), also independent from (ε_{i}). We write respectively E, E′ and E_{ε} for expectations relative to (X_{i}), (X′_{i}) and (ε_{i}).

E ∥\frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i} − Id∥^{k} = E ∥\frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i} − E′ \frac{1}{N} ∑_{i=1}^{N} X′_{i} ⊗ X′_{i}∥^{k}

⩽ EE′ ∥\frac{1}{N} ∑_{i=1}^{N} X_{i} ⊗ X_{i} − X′_{i} ⊗ X′_{i}∥^{k}

= EE′E_{ε} ∥\frac{1}{N} ∑_{i=1}^{N} ε_{i}(X_{i} ⊗ X_{i} − X′_{i} ⊗ X′_{i})∥^{k}

⩽ 2^{k}EE_{ε} ∥\frac{1}{N} ∑_{i=1}^{N} ε_{i}X_{i} ⊗ X_{i}∥^{k} .

We used Jensen’s inequality to obtain the first inequality. □

Let k be an even integer (we will choose later k ≈ n^{1/5}). We write A for A^{N}(X). Using lemma 1 and the moments method, we get

E∥A − Id∥^{k} ⩽ 2^{k}Etr (\frac{1}{N} ∑_{i=1}^{N} ε_{i}X_{i} ⊗ X_{i})^{k}

= \frac{2^{k}}{N^{k}} E ∑_{r_{1},...,r_{k}} ε_{r_{1}} … ε_{r_{k}}⟨X_{r_{1}}, X_{r_{2}}⟩ … ⟨X_{r_{k−1}}, X_{r_{k}}⟩⟨X_{r_{k}}, X_{r_{1}}⟩

= \frac{2^{k}}{N^{k}} ∑_{r_{1},...,r_{k}}(Eε_{r_{1}} … ε_{r_{k}})(E⟨X_{r_{1}}, X_{r_{2}}⟩ … ⟨X_{r_{k−1}}, X_{r_{k}}⟩⟨X_{r_{k}}, X_{r_{1}}⟩).

The summation runs a priori on multi-indices (r_{1}, …, r_{k}) ∈ {1, …, N}^{k}. However, note that the quantity Eε_{r_{1}} … ε_{r_{k}} equals 0 or 1, and that it equals 1 if and only if every i ∈ {1, …, N} appears an even (possibly 0) number of times among (r_{1}, …, r_{k}). Call such a multi-index paired; we actually sum over paired multi-indices. We write X_{i} = (x_{i1}, …, x_{in}) for the coordinates of X_{i} in the canonical basis, and expand the k scalar products as follows

⟨X_{r_{p}}, X_{r_{p+1}}⟩ = ∑_{s_{p}=1}^{n} x_{r_{p}s_{p}}x_{r_{p+1}s_{p}}.

This yields

E∥A − Id∥^{k} ⩽ \frac{2^{k}}{N^{k}} ∑_{{r_{1},...,r_{k} paired \atop s_{1},...,s_{k}}} Ex_{r_{1}s_{1}}x_{r_{2}s_{1}}x_{r_{2}s_{2}}x_{r_{3}s_{2}} … x_{r_{k}s_{k}}x_{r_{1}s_{k}},

where the sum is taken over all indices r_{1}, …, r_{k} in {1, …, N} and s_{1}, …, s_{k} in {1, …, n}. We now use unconditionality to show that most of these terms are actually 0. Since the random vectors (X_{1}, …, X_{N}) are independent, each expectation appearing in the sum can be factorized as the product of N factors of the form

(7)  Ex_{1}^{α_{1}}x_{2}^{α_{2}} … x_{n}^{α_{n}}

for some integers α_{1}, …, α_{n}, where X = (x_{1}, …, x_{n}). Since the vector X is unconditional, it is invariant under sign flips of coordinates, and this shows that the expectation (7) is zero if one of the α_{i} is odd. We are led to the following inequality (note that we changed the indexation)

E∥A − Id∥^{k} ⩽ \frac{2^{k}}{N^{k}} ∑_{[(r_{1},s_{1}),...,(r_{2k},s_{2k})]V-graph} Ex_{r_{1}s_{1}}x_{r_{2}s_{2}} … x_{r_{2k−1}s_{2k−1}}x_{r_{2k}s_{2k}},

where a V-graph is a 2k-tuple of pairs (r_{i}, s_{i}) ∈ {1, …, N} × {1, …, n} such that (V1) r_{2i+1} = r_{2i} (and r_{1} = r_{2k}), (V2) s_{2i} = s_{2i−1}, (V3) Each couple (r, s) ∈ {1, …, N} × {1, …, n} appears an even (possibly 0) number of times

among [(r_{i}, s_{i})], (V4) The number of occurences of each r ∈ {1, …, N} among (r_{i}) is a multiple of 4 (possibly 0). Condition (V4) has to be satisfied since we restricted ourself to paired multi-indices. We associate

several parameters to a V-graph G = [(r_{1}, s_{1}), …, (r_{2k}, s_{2k})], following the standard combinatorial techniques of [8, 22]. Let r(G) = #{r_{i}}, c(G) = #{s_{i}} and ℓ(G) = r(G) + c(G); ℓ(G) is the number of distinct indices appearing in G. Let also d(G) = #{(r_{i}, s_{i})} be the number of distinct couples of indices that appear in G. Let n_{2}(G) be the number of indices i such that the couple (r_{i}, s_{i}) appears exactly 2 times in G and n_{+}(G) be the number of indices i such that the couple (r_{i}, s_{i}) appears 4 times or more in G. We clearly have n_{2}(G) + n_{+}(G) = 2k.

Lemma 2. If G = [(r_{1}, s_{1}), …, (r_{2k}, s_{2k})] is a V-graph then

Ex_{r_{1}s_{1}} … x_{r_{2k}s_{2k}} ⩽ C^{k}k^{n_{+}(G)}.

Proof. First, we use the fact that the vectors (X_{i}) are independent to write the whole expectation as a product of N factors of the form (7). Note that the sum of all exponents α_{i} appearing in factors (7) is exactly 2k, while the sum restricted to the exponents satisfying α_{i} ⩾ 4 is exactly n_{+}(G). We use the following comparison theorem by Bobkov and Nazarov. Let B_{1}^{n} = {x ∈ R^{n} s.t. ∑ |x_{j}| ⩽ 1} denote the unit ball of ℓ_{1}^{n}; the convex body α_{n}B_{1}^{n} is isotropic for α_{n} = \sqrt{(n + 1)(n + 2)/2}. It has been proved in [4] that for some absolute constant C, if X = (x_{1}, …, x_{n}) is uniformly distributed on an isotropic unconditional convex body, and if Y = (y_{1}, …, y_{n}) is uniformly distributed on CnB_{1}^{n}, then for any increasing functions f_{i} : R^{+} → R

E ∏_{i=1}^{n} f_{i}(|x_{i}|) ⩽ E ∏_{i=1}^{n} f_{i}(|y_{i}|).

On each factor (7), we use this result with f_{i}(x) = x^{α_{i}} (recall that α_{i} is necessarily even). The resulting expectation for Y can then be estimated using sub-independence [3], a special property of ℓ_{p}^{n}-balls asserting that for any increasing functions f_{i} : R^{+} → R

E ∏_{i=1}^{n} f_{i}(|y_{i}|) ⩽ ∏_{i=1}^{n} Ef_{i}(|y_{i}|).

Now, by Borell’s lemma (see [5], or [17] p.135), there is an absolute constant C such that Ψ_{1}(y_{i}) ⩽ C, which means that E|y_{i}|^{p} ⩽ (Cp)^{p}. If α_{i} ⩾ 4, we use the following bound

Ey_{i}^{α_{i}} ⩽ (Ey_{i}^{n_{+}(G)})^{α_{i}/n_{+}(G)} ⩽ (Cn_{+}(G))^{α_{i}} ⩽ (2Ck)^{α_{i}}.

Using this method to bound separately all the factors of the form (7), we are led to

Ex_{r_{1}s_{1}} … x_{r_{2k}s_{2k}} ⩽ (Ey_{1}^{2})^{n_{2}(G)/2}(2Ck)^{n_{+}(G)},

and the lemma is proved. □

Applying lemma 2, we obtain the inequality

(8)  E∥A − Id∥^{k} ⩽ (\frac{C}{N} )^{k} ∑_{G V-graph} k^{n_{+}(G)}.

We now state some bounds on the parameters associated to a V-graph.

Lemma 3. Let G = [(r_{1}, s_{1}), …, (r_{2k}, s_{2k})] be a V-graph. Then (a) d(G) ⩽ k.

(b) ℓ(G) ⩽ d(G) + 1 ⩽ k + 1.
(c) r(G) ⩽ k/2.
(d) n_{+}(G) ⩽ 4(k − ℓ(G) + 1).

Proof. Assertion (a) is an immediate consequence of property (V3). To prove (b), read the V-graph from (r_{1}, s_{1}) to (r_{2k}, s_{2k}). Each of the d(G) first occurences (r_{i}, s_{i}) of some couple of indices may bring a new row index or a new column index, but not both (except for i = 1) because of properties (V1-V2). This shows ℓ(G) ⩽ d(G) + 1, and (b) follows from (a). Assertion (c) is an immediate consequence of property (V3). For (d), note that d(G) ⩽ \frac{1}{2}n_{2}(G) + \frac{1}{4}n_{+}(G) (with equality iff no couple (r, s) appears 6 times or more). The result then follows from (b) and the equality n_{2}(G) + n_{+}(G) = 2k. □

We now need a bound on the number of V-graphs with given r and c. This can be done using standard combinatorial techniques developed in [8, 22]. We present here a different approach, suggested to us by S. Szarek, based on the facts that the combinatorics of V -graphs do not depend on the specific entries of the random matrix, and that for Gaussian random matrices very precise information is available.

Lemma 4. Let I ⊂ {1, …, N} and J ⊂ {1, …, n}, such that r + c ⩽ k + 1, with r = #I and c = #J. Then the number of V-graphs G = [(r_{1}, s_{1}), …, (r_{2k}, s_{2k})] such that {r_{i}} ⊂ I and {s_{i}} ⊂ J is bounded from above by (Ck)^{k}, for some absolute constant C.

Proof. We can assume that I = {1, …, r} and J = {1, …, c}. Let G_{r,c} = (g_{ij}) a random r × c matrix with entries being independent N(0, 1) random variables. It is well-known (as a consequence of Slepian’s lemma, see [7] chapter 2.3, or using a net argument) that for some absolute constant C, E∥G_{r,c}∥ ⩽ C(\sqrt{r} + \sqrt{c}) ⩽ C′\sqrt{k}. Moreover, the operator norm is a 1-Lipschitz function with respect to the entries of the matrix (in the Hilbert–Schmidt metric), and standard concentration property of the Gaussian measure ([7], chapter 2.2) implies that for any t ⩾ 0

P(∥G_{r,c}∥ ⩾ E∥G_{r,c}∥ + t) ⩽ exp(−t^{2}/2).

This in turn implies that

E∥G_{r,c}∥^{2k} = ∫_{0}^{∞} 2kt^{2k−1}P(∥G_{r,c}∥ ⩾ t)dt ⩽ (C\sqrt{k})^{2k}.

Also, since tr(G_{r,c}^{t}G_{r,c})^{k} is the sum of 2kth powers of singular values of G_{r,c}, we have

Etr(G_{r,c}^{t}G_{r,c})^{k} ⩽ min(r, c)E∥G_{r,c}∥^{2k} ⩽ (C′k)^{k}.

On the other hand, the quantity Etr(G_{r,c}^{t}G_{r,c})^{k} itself can also be expanded as

Etr(G_{r,c}^{t}G_{r,c})^{k} = ∑ Eg_{r_{1}s_{1}} … g_{r_{2k}s_{2k}},

where the sum is taken over 2k-tuples of pairs (r_{i}, s_{i}) ⊂ I × J satisfying conditions (V1), (V2), (V3). Notably, all V-graphs considered in the statement of the lemma enter this setting. Moreover, all terms in the sum are positive, and even larger than 1 since Eg_{ij}^{p} ⩾ 1 for p even integer. This shows that the number of V-graphs with indices contained in I × J is bounded from above by Etr(G_{r,c}^{t}G_{r,c})^{k}, which proves the lemma. □

Lemma 4 implies that the number of V-graphs G such that r(G) = r and c(G) = c is bounded by

\binom{N}{r}\binom{n}{c}(Ck)^{k} ⩽ C_{1}^{k}N^{r}n^{c} \frac{k^{k}}{ℓ(G)^{ℓ(G)}} ⩽ C_{2}^{k}N^{r}n^{c}k^{k−ℓ(G)},

where we used the inequalities \binom{B}{b} ⩽ (Be/b)^{b}, r^{r}c^{c} ⩾ (ℓ/2)^{ℓ} and k^{k}/ℓ^{ℓ} ⩽ (ke)^{k−ℓ}. By lemma 3c, for any V-graph G we have

N^{r(G)}n^{c(G)} ⩽ \begin{cases}N^{ℓ(G)} & if ℓ(G) ⩽ k/2, \\ N^{k/2}n^{ℓ(G)−k/2} & if ℓ(G) ⩾ k/2, \end{cases}

⩽ N^{k} (\frac{n}{N} )^{k/2} \frac{1}{n^{k−ℓ(G)}} .

Gathering the V-graphs with the same ℓ, we get as a consequence of inequality (8) and lemma 3d that (setting m = l − 1)

E∥A − Id∥^{k} ⩽ (\frac{C}{N} )^{k} ∑_{l=2}^{k+1} k^{4(k−l+1)}kC_{2}^{k}k^{k−l}N^{k} (\frac{n}{N} )^{k/2} \frac{1}{n^{k−l}} ,

⩽ (C\sqrt{\frac{n}{N}} )^{k} n ∑_{m=1}^{k} (\frac{k^{5}}{n} )^{k−m} .

We now choose k to be the smallest even integer such that k ⩾ n^{1/5}. We then use the inequality n ∑(k^{5}/n)^{k−m} ⩽ C^{k} to finish the proof (note that the l.h.s. in (6) is an increasing function of k). □

4. Proof of proposition 2: the role of log-concavity

Proof. The proof is similar to the proof of the main theorem in [15], but here the log-concavity makes things much easier. We introduce the matrix Γ defined by

(9)  Γ = \frac{1}{\sqrt{N}} ( X_{1} ; X_{2} ; ⋮ ; X_{N} ) .

We have the equality A = Γ^{t}Γ ; we think of Γ as an operator from ℓ_{2}^{n} to ℓ_{2}^{N}. We write s_{min}(Γ) for the smallest singular value of Γ, which equals \sqrt{λ_{min}(A)}. For ε > 0 to be determined later, let N be a ε-net in S^{n−1} with cardinality smaller that (3/ε)^{n} (existence of such a net is proved using volumetric arguments, see Lemma 4.10 in [19]). Set also t = ε\sqrt{M}. Let \overline{Ω} be the event “∥Γ∥ < \sqrt{M}”. By the standard approximation argument, the event

\overline{Ω} ∩ \{∃x ∈ S^{n−1} s.t. |Γx| ⩽ t\}

is contained in the event

\overline{Ω} ∩ \{∃x ∈ N s.t. |Γx| ⩽ 2t\}.

Consequently,

P(s_{min}(Γ) ⩽ t) ⩽ P(\overline{Ω}^{c}) + #N max_{x∈S^{n−1}} P(|Γx| ⩽ 2t).

For fixed x in the sphere S^{n−1} and j between 1 and N, let f_{j} be the random variable ⟨X_{j}, x⟩. It is well-known [11, 9] that when K is an isotropic convex body in R^{n}, the (n − 1)-dimensional volume of hyperplane sections is controlled: for any affine hyperplane H, we have vol_{n−1}(K ∩ H) ⩽ C for a universal constant C. Consequently, for any s ⩾ 0 we have P(|f_{j}| ⩽ s) ⩽ Cs. Calculations are now straightforward:

P(|Γx| ⩽ 2t) = P (∑_{i=1}^{N} f_{i}^{2} ⩽ 4t^{2}N)

= P (N − ∑_{i=1}^{N} f_{j}^{2}/4t^{2} ⩾ 0)

⩽ E exp (N − ∑_{i=1}^{N} f_{j}^{2}/4t^{2})

= (eE exp(−f_{1}^{2}/4t^{2}))^{N}

= e^{N} (∫_{0}^{1} P(exp(−f_{1}^{2}/4t^{2}) > s)ds)^{N}

= e^{N} (∫_{0}^{1} P(f_{1} ⩽ 2t\sqrt{log(1/s)})ds)^{N}

⩽ e^{N} (2Ct ∫_{0}^{1} \sqrt{log(1/s)}ds)^{N}
= (Ce\sqrt{π}t)^{N}.

And consequently

P(s_{min}(Γ) ⩽ t) ⩽ P(∥A∥ ⩾ M) + (\frac{3\sqrt{M}}{t} )^{n} (Ce\sqrt{π}t)^{N}.

thus for any ρ > 1, we can choose t (and thus ε) such that the conclusion of the proposition holds. □

Acknowledgement: I want to thank Alain Pajor, Olivier Guédon and Sasha Sodin for many fruitful discussions, and Staszek Szarek for useful remarks on a preliminary version of this paper.

References

[1] G. Aubrun. Random points in the unit ball of ℓ_{p}^{n}. http://www.institut.math.jussieu.fr/~aubrun/ellp.ps, 2005.

[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] K. Ball and I. Perissinaki. The subindependence of coordinate slabs in ℓ_{p}^{n} balls. Israel J. Math., 107:289–299, 1998.

[4] S. G. Bobkov and F. L. Nazarov. Large deviations of typical linear functionals on a convex body with unconditional basis. In Stochastic inequalities and applications, volume 56 of Progr. Probab., pages 3–13. Birkhäuser, Basel, 2003.

[5] C. Borell. The Brunn-Minkowski inequality in Gauss space. Invent. Math., 30(2):207–216, 1975.

[6] J. Bourgain. Random points in isotropic convex sets. In Convex geometric analysis (Berkeley, CA, 1996), volume 34 of Math. Sci. Res. Inst. Publ., pages 53–58. Cambridge Univ. Press, Cambridge, 1999.

[7] K. R. Davidson and S. J. Szarek. Local operator theory, random matrices and Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 317–366. North-Holland, Amsterdam, 2001.

[8] S. Geman. A limit theorem for the norm of random matrices. Ann. Probab., 8(2):252–261, 1980.

[9] A. Giannopoulos. Notes on isotropic convex bodies (preprint). http://eudoxos.math.uoa.gr/~apgiannop/

    isotropic-bodies.ps, 2003.

[10] A. Giannopoulos, M. Hartzoulaki, and A. Tsolomitis. Random points in isotropic unconditional convex bodies. Journal of the London Mathematical Society, to appear.

[11] D. Hensley. Slicing convex bodies—bounds for slice area in terms of the body’s covariance. Proc. Amer. Math. Soc., 79(4):619–625, 1980.

[12] R. Kannan, L. Lovász, and M. Simonovits. Random walks and an O^{∗}(n^{5}) volume algorithm for convex bodies. Random Structures Algorithms, 11(1):1–50, 1997.

[13] V. F. Kolchin, B. A. Sevast′yanov, and V. P. Chistyakov. Random allocations. V. H. Winston & Sons, Washington, D.C., 1978. Translated from Russian, translation edited by A. V. Balakrishnan, Scripta Series in Mathematics.

[14] M. Ledoux. Deviations inequalities on largest eigenvalues. http://www.lsp.ups-tlse.fr/Ledoux/Jerusalem.pdf, 2005.

[15] A. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann. Smallest singular value of random matrices and geometry of random polytopes. Advances in mathematics, to appear.

[16] V. D. Milman and A. Pajor. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed ndimensional space. In Geometric aspects of functional analysis (1987–88), volume 1376 of Lecture Notes in Math., pages 64–104. Springer, Berlin, 1989.

[17] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[18] G. Paouris. Concentration of mass on isotropic convex bodies. C. R. Math. Acad. Sci. Paris, 2005. To appear.

[19] G. Pisier. The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.

[20] M. Rudelson. Random vectors in the isotropic position. J. Funct. Anal., 164(1):60–72, 1999.

[21] S. Sodin. On the smallest singular value of a Bernoulli random matrix (following Bai and Yin). Appendix to a preprint by Artstein–Friedland–Milman “More geometric applications of Chernoff inequalities”.

[22] Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah. On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix. Probab. Theory Related Fields, 78(4):509–521, 1988.

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