RANDOM VECTORS IN THE ISOTROPIC POSITION

M. Rudelson

MSRI Texas A & M University

Abstract. Let y be a random vector in ℝ^{n}, satisfying

𝔼 y ⊗ y = id.

Let M be a natural number and let y_{1}, …, y_{M} be independent copies of y. We prove that for some absolute constant C

𝔼 ∥ \frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · (𝔼 ∥y∥^{log M} )^{1/ log M} ,

provided that the last expression is smaller than 1.

We apply this estimate to obtain a new proof of a result of Bourgain concerning the number of random points needed to bring a convex body into a nearly isotropic position.

1. Introduction

The problem we consider has arisen from a question studied by R. Kannan, L. Lovász and M. Simonovits [K-L-S]. To construct a fast algorithm for calculating the volume of a convex body, they needed to bring it into some symmetric position. More precisely, let K be a convex body in ℝ^{n}. We shall say that it is in the isotropic position if for any x ∈ ℝ^{n}

\frac{1}{vol (K)} ∫_{K}⟨x, y⟩^{2} dy = ∥x∥^{2}

By ∥·∥ we denote the standard Euclidean norm.

The notion of isotropic position was extensively studied by V. Milman and A. Pajor [M-P]. Note that our definition is consistent with [K-L-S]. The normalization in [M-P] is slightly different.

If the information about the body K is uncomplete it is impossible to bring it exactly to the isotropic position. So, the definition of the isotropic position has to be modified to allow a small error. We shall say that the body K is in ε-isotropic position if for any x ∈ ℝ^{n}

(1 − ε) · ∥x∥^{2} ≤ \frac{1}{vol (K)} ∫_{K}⟨x, y⟩^{2} dy ≤ (1 + ε) · ∥x∥^{2} .

Typeset by AMS-TEX

Research at MSRI is supported in part by NSF grant DMS-9022140.

Let ε > 0 be given. Consider M random points y_{1}, …, y_{M} independently uniformly distributed in K and put

T = \frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i}.

If M is sufficiently large, than with high probability

∥T − \frac{1}{vol(K)} ∫_{K} y ⊗ y∥

will be small, so the body T^{−1/2}K will be in ε-isotropic position. R. Kannan, L. Lovász and M. Simonovits ([K-L-S]) proved that it is enough to take

M = c\frac{n^{2}}{ε}

for some absolute constant c. This estimate was significantly improved by J. Bourgain [B]. Using rather delicate geometric considerations he has shown that one can take

M = C(ε)n log^{3} n.

Since the situation is invariant under a linear transformation, we may assume that the body K is in the isotropic position. Then the result of Bourgain may be reformulated as follows:

Theorem 0. [B] Let K be a convex body in ℝ^{n} in the isotropic position. Fix ε > 0 and choose independently M random points x_{1}, …, x_{M} ∈ K,

M ≥ C(ε)n log^{3} n.

Then with probability at least 1 − ε for any x ∈ ℝ^{n} one has

(1 − ε) ∥x∥^{2} ≤ \frac{1}{M} ∑_{i=1}^{M}⟨x, y⟩^{2} ≤ (1 + ε) ∥x∥^{2} .

We shall show that this theorem follows from a general result about random vectors in ℝ^{n}. Let y be a random vector. Denote by 𝔼 X the expectation of a random variable X. We say that y is in the isotropic position if

(1.1)  𝔼 y ⊗ y = id.

If y is uniformly distributed in a convex body K, then this is equivalent to the fact that K is in the isotropic position.

We prove the following Theorem 1. Let y ∈ ℝ^{n} be a random vector in the isotropic position. Let M be a natural number and let y_{1}, …, y_{M} be independent copies of y. Then

(1.2)  𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · (𝔼 ∥y∥^{log M})^{1/ log M} ,

provided that the last expression is smaller than 1.

Here and later C, c, etc. denote absolute constants whose values may vary from line to line.

Remark. Taking the trace of (1.1) we obtain that 𝔼 ∥y∥^{2} = n, so to make the right hand side of (1.2) smaller than 1, we have to assume that M ≥ cn log n.

Using Theorem 1 we prove a better estimate of the length of approximate John’s decompositions [R1] and thus improve the results about approximating a convex body by another one having a small number of contact points, obtained in [R2]. Estimating the moment of the norm of random vector in a convex body, we obtain a different proof of Theorem 0 which gives also a better estimate.

2. Main results.

The proof of Theorem 1 consists of two steps. First we introduce a Bernoulli random process and estimate the expectation of the norm in (1.2) by the expectation of its supremum. Then we construct a majorizing measure to obtain a bound for the latest.

The first step is relatively standard. Let ε_{1}, …, ε_{M} be independent Bernoulli variables taking values 1, −1 with probability 1/2 and let y_{1}, …, y_{M}, ȳ_{1}, …, ȳ_{M} be independent copies of y. Denote 𝔼_{y}, 𝔼_{ε} the expectation according to y and ε respectively. Since y_{i} ⊗ y_{i} − ȳ_{i} ⊗ ȳ_{i} is a symmetric random variable, we have

𝔼_{y} ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ 𝔼_{y} 𝔼ȳ ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − \frac{1}{M} ∑_{i=1}^{M} ȳ_{i} ⊗ ȳ_{i}∥ =

𝔼_{ε} 𝔼_{y} 𝔼ȳ ∥\frac{1}{M} ∑_{i=1}^{M} ε_{i}(y_{i} ⊗ y_{i} − ȳ_{i} ⊗ ȳ_{i})∥ ≤ 2 𝔼_{y} 𝔼_{ε} ∥\frac{1}{M} ∑_{i=1}^{M} ε_{i}y_{i} ⊗ y_{i}∥ .

To estimate the last expectation, we need the following Lemma, which generalizes Lemma 1 [R3].

Lemma. Let y_{1}, …, y_{M} be vectors in ℝ^{n} and let ε_{1}, …, ε_{M} be independent Bernoulli variables taking values 1, −1 with probability 1/2. Then

𝔼 ∥∑_{i=1}^{M} ε_{i}y_{i} ⊗ y_{i}∥ ≤ C\sqrt{log M} · max_{i=1,...,M} ∥y_{i}∥ · ∥∑_{i=1}^{M} y_{i} ⊗ y_{i}∥^{1/2} .

We postpone the proof of the Lemma to the next section.

Applying the Lemma, we get

(2.1)  \begin{matrix}𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ \\ C · \frac{\sqrt{log M}}{M} · & (𝔼 max_{i=1,...,M} ∥y_{i}∥^{2})^{1/2} · (𝔼 ∥∑_{i=1}^{M} y_{i} ⊗ y_{i}∥)^{1/2} . \end{matrix}

We have

(𝔼 max_{i=1,...,M} ∥y_{i}∥^{2})^{1/2} ≤ (𝔼 (∑_{i=1}^{M} ∥y_{i}∥^{log M})^{2/ log M} )^{1/2} ≤
M^{1/ log M} · (𝔼 ∥y∥^{log M})^{1/ log M} .

Thus, denoting

D = 𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ,

we obtain by (2.1)

D ≤ C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · (𝔼 ∥y∥^{log M})^{1/ log M} · (D + 1)^{1/2}.

If

C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · (𝔼 ∥y∥^{log M})^{1/ log M} ≤ 1,

we get

D ≤ 2C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · (𝔼 ∥y∥^{log M})^{1/ log M} ,

which completes the proof of Theorem 1.

We turn now to the applications of Theorem 1. Applying Theorem 1 to the question of Kannan, Lovász and Simonovits, we obtain the following Corollary 2.1. Let ε > 0 and let K be an n-dimensional convex body in the isotropic position. Let

M ≥ C · \frac{n}{ε^{2}} · log^{2} \frac{n}{ε^{2}}

and let y_{1}, …, y_{M} be independent random vectors uniformly distributed in K. Then

𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ ε.

Proof. It follows from a result of S. Alesker [A], that

𝔼 exp (\frac{∥y∥^{2}}{c · n} ) ≤ 2

for some absolute constant c. Then

𝔼 ∥y∥^{log M} ≤ (𝔼 e^{\frac{∥y∥^{2}}{c·n}} )^{1/2} · (𝔼 (∥y∥^{2 log M} · e^{− \frac{∥y∥^{2}}{c·n}} ))^{1/2} ≤

\sqrt{2} · (max_{t≥0} t^{log M} · e^{− \frac{t}{c·n}} )^{1/2} ≤ (C · n · log M)^{\frac{log M}{2}} .

Corollary 2.1 follows from this estimate and Theorem 1. □

By a Lemma of Borell [M-S, Appendix III], most of the volume of a convex body in the isotropic position is concentrated within the Euclidean ball of radius c\sqrt{n}. So, it might be of interest to consider a random vector uniformly distributed in the intersection of a convex body and such a ball. In this case the previous estimate may be improved as follows.

Corollary 2.2. Let ε, R > 0 and let K be an n-dimensional convex body in the isotropic position. Suppose that R ≥ c\sqrt{log 1/ε} and let

(2.2)  M ≥ C_{0} · \frac{R^{2} · n}{ε^{2}} · log \frac{R^{2} · n}{ε^{2}}

and let y_{1}, …, y_{M} be independent random vectors uniformly distributed in K ∩ R\sqrt{n}) · B_{2}^{n}. Then

𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ ε.

Proof. Denote a = R · \sqrt{n} and let z be a random vector uniformly distributed in K ∩ aB_{2}^{n}. Then for x ∈ B_{2}^{n}

𝔼 ⟨z, x⟩^{2} = \frac{vol (K)}{vol (K ∩ aB_{2}^{n})} · (\frac{1}{vol (K)} ∫_{K}⟨y, x⟩^{2} dy −
\frac{1}{vol (K)} ∫_{K}⟨y, x⟩^{2} · 1_{\{u|∥u∥≥a\}}(y) dy).

By a result of S. Alesker [A] and Khinchine type inequality [M-P], we have

\frac{vol (K)}{vol (K ∩ aB_{2}^{n})} ≤ 1 + e^{−ca^{2}/n} ≤ 1 + \frac{ε}{4}

and

\frac{1}{vol (K)} ∫_{K}⟨y, x⟩^{2} · 1_{\{u|∥u∥≥a\}}(y) dy ≤

(\frac{1}{vol (K)} ∫_{K}⟨y, x⟩^{4} dy)^{1/2} · (\frac{1}{vol (K)} ∫_{K} 1_{\{u|∥u∥≥a\}}(y) dy)^{1/2} ≤

Ce^{−ca^{2}/2n} ≤ \frac{ε}{4}.

Thus for any x ∈ B_{2}^{n}

|𝔼 ⟨z, x⟩^{2} − 1| ≤ \frac{ε}{2}.

Define a random vector

y = (𝔼 z ⊗ z)^{−1/2}z.

Then y is in the isotropic position and

(𝔼 ∥y∥^{log M})^{1/ log M} ≤ ∥(𝔼 z ⊗ z)^{−1/2}∥ · (𝔼 ∥z∥^{log M})^{1/ log M} ≤ 2a,

so

𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ C · \begin{matrix}√ & \overline{log M} \\ √ & \overline{M} \end{matrix} · 2a ≤ \frac{ε}{2}

provided the constant C_{0} in (2.2) is large enough. Thus,

𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} z_{i} ⊗ z_{i} − id∥ ≤ 𝔼 ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ · ∥𝔼 z ⊗ z∥ + ∥𝔼 z ⊗ z − id∥ ≤ ε.

□

The next application is connected to the approximation of a convex body by another one having a small number of contact points [R2]. Let K be a convex body in ℝ^{n} such that the ellipsoid of minimal volume containing it is the standard Euclidean ball B_{2}^{n}. Then by the theorem of John, there exist N ≤ (n + 3)n/2 points z_{1}, …, z_{N} ∈ K, ∥x_{i}∥ = 1 and N positive numbers c_{1}, …, c_{N} satisfying the following system of equations

(2.3)  id = ∑_{i=1}^{N} c_{i} z_{i} ⊗ z_{i}

(2.4)  0 = ∑_{i=1}^{N} c_{i} z_{i}.

It was shown in [R1] for convex symmetric bodies and in [R2] in the general case, that the identity operator can be approximated by a sum of a smaller number of terms x_{i} ⊗ x_{i}. We derive from Theorem 1 the following corollary, which improves Lemma 3.1 [R2].

Corollary 2.3. Let ε > 0 and let K be a convex body in ℝ^{n}, so that the ellipsoid of minimal volume containing it is B_{2}^{n}. Then there exist

(2.5)  M ≤ \frac{C}{ε^{2}} · n · log \frac{n}{ε}

contact points x_{1}, …, x_{M} and a vector u, ∥u∥ ≤ \frac{C}{\sqrt{M}}, so that the identity operator in ℝ^{n} has the following representation

id = \frac{n}{M} ∑_{i=1}^{M}(x_{i} + u) ⊗ (x_{i} + u) + S,

where

∑_{i=1}^{M}(x_{i} + u) = 0 (2.6)

and

∥S : ℓ_{2}^{n} → ℓ_{2}^{n}∥ < ε.

Proof. Let (2.3) be a decomposition of the identity operator. Let y be a random vector in ℝ^{n}, taking values \sqrt{n}z_{i} with probability c_{i}/\sqrt{n}. Then, by (2.3), y is in the isotropic position. Obviously, for all 1 ≤ p < ∞

(𝔼 ∥y∥^{p})^{1/p} = \sqrt{n}.

So, taking M as in (2.5), we obtain that for sufficiently large C

(2.7)  ∥\frac{1}{M} ∑_{i=1}^{M} y_{i} ⊗ y_{i} − id∥ ≤ \frac{ε}{2}

with probability greater than 3/4. Since by (2.4), 𝔼 y = 0 and ∥y∥ = \sqrt{n}, we have

(2.8)  ∥∑_{i=1}^{M} y_{i}∥ ≤ 2\sqrt{M}

with probability greater than 3/4. Take y_{1}, …, y_{M} for which (2.7) and (2.8) hold and put

x_{i} = \frac{1}{\sqrt{n}} · y_{i}, u = −\frac{1}{M} ∑_{i=1}^{M} x_{i}.

Then (2.6) is satisfied and

∥\frac{n}{M} ∑_{i=1}^{M}(x_{i} + u) ⊗ (x_{i} + u) − id∥ ≤

∥\frac{n}{M} ∑_{i=1}^{M} x_{i} ⊗ x_{i} − id∥ + n · ∥u ⊗ u∥ ≤ \frac{ε}{2} + \frac{4 n}{M} ≤ ε. □

Substituting Lemma 3.1 [R2] by Corollary 2.3 in the proof of Theorem 1.1 [R2] we obtain the following

Corollary 2.3. Let B be a convex body in ℝ^{n} and let ε > 0. There exists a convex body K ⊂ ℝ^{n}, so that d(K, B) ≤ 1 + ε and the number of contact points of K with the ellipsoid of minimal volume containing it is less than

M(n, ε) = \frac{C}{ε^{2}} · n · log \frac{n}{ε}.

3. Proof of the Lemma

The proof of the Lemma is similar to that of Lemma 1 [R3]. For the reader’s convenience we present here a complete proof.

Without loss of generality, we may assume that

∥∑_{i=1}^{M} y_{i} ⊗ y_{i}∥ = 1.

Define a random process

V_{x} = ∑_{i=1}^{M} ε_{i}⟨x, y⟩^{2}

for x ∈ B_{2}^{n}. We have to estimate

(3.1)  𝔼 sup_{x∈B_{2}^{n}} V_{x}.

Note that the process V_{x} has a subgaussian tail estimate

P\{V_{x} − Vx̄ > a\} ≤ exp (−C \frac{a^{2}}{d̃^{2}(x, x̄)}) ,

where C is an absolute constant and

d̃(x, x̄) = (∑_{i=1}^{M} (⟨x, y_{i}⟩^{2} − ⟨x̄, y_{i}⟩^{2})^{2})^{1/2} .

The function d̃ is not a metric on B_{2}^{n}, since d̃(x, x̄) = 0 does not imply x = x̄. To avoid this obstacle, we shall estimate d̃ by a quasimetric d defined by

d(x, x̄) = (∑_{i=1}^{M}⟨x − x̄, y_{i}⟩^{2}(⟨x, y_{i}⟩^{2} + ⟨x̄, y_{i}⟩^{2}))^{1/2} .

Then for all , x̄ ∈ B_{2}^{n}

d̃(x, x̄) ≤ \sqrt{2} · d(x, x̄),

so we may treat V_{x} as a subgaussian process with the quasimetric d. It can be easily shown that d satisfies a generalized triangle inequality

(3.2)  d(x, x̄) ≤ 4 · (d(x, z) + d(z, x̄))

for all x, x̄, z ∈ B_{2}^{n}.

Denote by B_{ρ}(x) a ball in the quasimetric d with center x and radius ρ. Then for any x ∈ B_{2}^{n} and ρ > 0 we have

conv B_{ρ}(x) ⊂ B_{4ρ}(x).

The proof of this fact is the same as that of Lemma 3 [R3], so we shall omit it. To estimate the expression (3.1), we apply the following version of the Majorizing measure theorem.

Theorem. Let (T, d) be a quasimetric space. Let (X_{t})_{t∈T} be a collection of mean 0 random variables with the subgaussian tail estimate

P \{|X_{t} − Xt̄| > a\} ≤ exp (−c\frac{a^{2}}{d^{2}(t, t̄)}) ,

for all a > 0. Let r > 1 and let k_{0} be a natural number so that the diameter of T is less than r^{−k_{0}}. Let {φ_{k}}_{k=k_{0}}^{∞} be a sequence of functions from T to ℝ^{+}, uniformly bounded by a constant depending only on r. Assume that there exists σ > 0 so that for any k the functions φ_{k} satisfy the following condition:

for any s ∈ T and for any points t_{1}, …, t_{N} ∈ B_{r^{−k}}(s) with mutual distances at least r^{−k−1} one has

(3.3)  max_{j=1,...,N} φ_{k+2}(t_{j}) ≥ φ_{k}(s) + σ · r^{−k} · \sqrt{log N}.

Then

𝔼 sup_{t∈T} X_{t} ≤ C(r) · σ^{−1}.

This Theorem is a combination of the majorizing measure theorem of Fernique [L-T] and the general majorizing measure construction of Talagrand (Theorems 2.1 and 2.2 [T1] or Theorems 4.2, 4.3 and Proposition 4.4 [T2]).

Let

Q = max_{i=1,...,M} ∥y_{i}∥ .

Let r be a natural number and let k_{0} and k_{1} be the largest numbers so that

r^{−k_{0}} ≥ Q

r^{−k_{1}} ≥ \frac{Q}{\sqrt{n}}.

Then k_{1} − k_{0} ≤ (2 log r)^{−1} log n. Define now the functions φ_{k} : B_{2}^{n} → ℝ by

φ_{k}(x) = min\{∥u∥^{2} | u ∈ convB_{8r^{−k}}(x)\} + \frac{k − k_{0}}{log M} ,  if k = k_{0}, …, k_{1},

φ_{k}(w) =1 + \frac{1}{2 log r} + ∑_{l=k_{1}}^{k} r^{−l} · \frac{\sqrt{n · log(1 + 4Qr^{l})}}{Q · \sqrt{log M}},  if k > k_{1}.

The functions φ_{k} form a nonnegative nondecreasing sequence bounded by a constant depending only on r. Indeed, for k ≤ k_{1},

φ_{k}(x) ≤ 1 + \frac{1}{2 log r} · \frac{log n}{log M} .

For k > k_{1} we have

φ_{k}(w) ≤1 + \frac{1}{2 log r} + ∑_{l=k_{1}}^{∞} r^{−l} · \frac{\sqrt{n · log(1 + 4Qr^{l})}}{Q\sqrt{log M}} ≤

1 + \frac{1}{2 log r} + c(r) · r^{−k_{1}} · \sqrt{n} · \frac{\sqrt{log(1 + 4Qr^{k_{1}})}}{Q\sqrt{log M}} ≤ C(r).

10 M. RUDELSON

Now let x_{1}, …, x_{N} ∈ B_{r^{−}k}(x) and suppose that

d(x_{i}, x_{j}) > r^{−k−1}

for any i ≠ j. We have to prove that

(3.4) max_{j=1,...,N} φ_{k+2}(x_{i}) ≥ φ_{k}(x) + \frac{C}{Q\sqrt{log M}} · \sqrt{log N}.

Note that for x, x̄ ∈ B_{2}^{n}

d(x, x̄) ≤\sqrt{2} · max_{i=1,...,M} |⟨x − x̄, y_{i}⟩| · (∑_{i=1}^{M}⟨x, y_{i}⟩^{2} + ⟨x̄, y_{i}⟩^{2})^{1/2} ≤

\sqrt{2} · max_{i=1,...,M} |⟨x − x̄, y_{i}⟩| · ∥∑_{i=1}^{M} y_{i} ⊗ y_{i}∥ · (∥x∥^{2} + \left∥{ \atop x̄}\right∥^{2})^{1/2} ≤

2 · max_{i=1,...,M} |⟨x − x̄, y_{i}⟩|.

Define a norm in ℝ^{n} by

∥x∥_{Y} = max_{i=1,...,M} |⟨x, y_{i}⟩|.

If k ≥ k_{1} − 2 then (3.4) follows from a simple entropy estimate. Indeed, we have

N ≤N(B_{2}^{n}, d, r^{−k−1}) ≤ N(B_{2}^{n}, ∥·∥_{Y} , \frac{1}{2}r^{−k−1}) ≤

N(B_{2}^{n}, ∥·∥ , \frac{1}{2Q}r^{−k−1}) ≤ (1 + 4Q · r^{k+1})^{n},

since ∥·∥_{Y} ≤ Q ∥·∥. Suppose now that k < k_{1} − 2. For j = 1, …, N denote z_{j} the point of convB_{8r^{−k−2}}(x_{j}) for which the minimum of ∥z∥^{2} is attained and denote u the similar point of B_{8r^{−k}}(x). Put

θ = max_{j=1,...,N} ∥z_{j}∥^{2} − ∥u∥^{2} .

We have to show that

(3.5) r^{−k} · (c · Q · \sqrt{log M})^{−1} · \sqrt{log N} ≤ max_{j=1,...,N} φ_{k+2}(x_{j}) − φ_{k}(x) = θ + \frac{2}{log M} .

Since d(x_{i}, x_{j}) ≥ r^{−k−1}, it follows from (3.2) that

d(z_{i}, z_{j}) ≥ \frac{1}{2}r^{−k−1},

provided r is sufficiently large. From the other side, d(x, z_{j}) ≤ 4(d(x, x_{j}) + d(x_{j}, z_{j})) ≤ 8r^{−k}.

Since \frac{z_{j} + u}{2} ∈ convB_{8r^{−k}}(x), and ∥u∥ ≤ ∥z_{j}∥, we have

∥\frac{z_{j} − u}{2}∥^{2} = \frac{1}{2} ∥z_{j}∥^{2} + \frac{1}{2} ∥u∥^{2} − ∥\frac{z_{j} + u}{2}∥^{2} ≤ ∥z_{j}∥^{2} − ∥\frac{z_{j} + u}{2}∥^{2} ≤ ∥z_{j}∥^{2} − ∥u∥^{2} ,

so,

(3.6)  ∥z_{j} − u∥ ≤ 2\sqrt{θ}.

Thus, N is bounded by the \frac{1}{2}r^{−k−1}-entropy of the set K = u + 2\sqrt{θ}B_{2}^{n} in the quasimetric d. To estimate this entropy we partition the set K into S disjoint subsets having diameter less than δ = \frac{1}{16}r^{−k−1}θ^{−1/2} in the ∥·∥_{Y} metric.

Let g be a Gaussian vector in ℝ^{n}, normalized by 𝔼 ∥g∥^{2} = n. Denote by N(B, Δ, ε) ε-entropy of the set B in the metric Δ. By dual Sudakov minoration [L-T] we have

\sqrt{log S} ≤\sqrt{log N(2\sqrt{θ}B_{2}^{n}, ∥·∥_{Y} , δ)} ≤

\frac{c}{δ} · 2\sqrt{θ} · 𝔼 ∥g∥_{Y} ≤ C · r^{k}θ · 𝔼 max_{i=1,...,M} |⟨g, y_{i}⟩| ≤ C · r^{k}θ · Q · \sqrt{log M}. (3.7)

If S ≥ \sqrt{N}, we are done, because in this case (3.7) implies (3.5). Suppose that S ≤ \sqrt{N}. Then there exists an element of the partition containing at least \sqrt{N} points z_{j}. Let J ⊂ {1, …, N} be the set of the indices of these points. We have

(3.8)  ∥z_{j} − z_{l}∥_{Y} ≤ \frac{1}{16}r^{−k−1} · θ^{−1/2}

for all j, l ∈ J.

For j = 1, …, M denote

I_{j} = {i ∈ {1, …, M} | |⟨z_{j}, y_{i}⟩ ≥ 2 |⟨u, y_{i}⟩|}.

Then (3.6) imlies that

∑_{i∈I_{j}}⟨z_{j}, y_{i}⟩^{2} ≤ 2 ∑_{i∈I_{j}}⟨z_{j} − u, y_{i}⟩^{2} + 2 ∑_{i∈I_{j}}⟨u, y_{i}⟩^{2} ≤ 8θ + \frac{1}{2} ∑_{i∈I_{j}}⟨z_{j}, y_{i}⟩^{2},

so,

(3.9)  ∑_{i∈I_{j}}⟨z_{j}, y_{i}⟩^{2} ≤ 16θ.

Since d(z_{j}, z_{l}) ≥ \frac{1}{2}r^{−k−1}, we have

(\frac{1}{2}r^{−k−1})^{2} ≤ ∑_{i=1}^{M}⟨z_{j} − z_{l}, y_{i}⟩^{2} · (⟨z_{j}, y_{i}⟩^{2} + ⟨z_{l}, y_{i}⟩^{2}) ≤

∑_{i=1}^{M}⟨z_{j} − z_{l}, y_{i}⟩^{2} · 4⟨u, y_{i}⟩^{2} +

max_{i∈I_{j}}⟨z_{j} − z_{l}, y_{i}⟩^{2} · ∑_{i∈I_{j}}⟨z_{j}, y_{i}⟩^{2} + max_{i∈I_{l}}⟨z_{j} − z_{l}, y_{i}⟩^{2} · ∑_{i∈I_{l}}⟨z_{l}, y_{i}⟩^{2}.

Combining (3.8) and (3.9) we get that the last expression is bounded by

2 · 16θ · (\frac{θ^{−1/2}}{8} r^{−k−1})^{2} + 4 ∑_{i=1}^{M}⟨z_{j} − z_{l}, y_{i}⟩^{2} · ⟨u, y_{i}⟩^{2}.

Define a norm ∥·∥_{E} by

∥x∥_{E} = (∑_{i=1}^{M}⟨x, y_{i}⟩^{2} · ⟨u, y_{i}⟩^{2})^{1/2} .

Then, for all j, l ∈ J, j ≠ l we have

∥z_{j} − z_{l}∥_{E} ≥ \frac{1}{8}r^{−k−1}.

Applying again dual Sudakov minoration, we obtain

\sqrt{log |J|} ≤\sqrt{log N(2\sqrt{θ}B_{2}^{n}, ∥·∥_{E} , \frac{1}{8}r^{−k−1})} ≤ cr^{k} · 2\sqrt{θ} · 𝔼 ∥g∥_{E} ≤

cr^{k} · 2\sqrt{θ} · (𝔼 ∑_{i=1}^{M}⟨g, y_{i}⟩^{2} · ⟨u, y_{i}⟩^{2})^{1/2} ≤

Cr^{k} · 2\sqrt{θ} · max_{i=1,...,M} ∥y_{i}∥ · ∥∑_{i=1}^{M} y_{i} ⊗ y_{i}∥ · ∥u∥ ≤ Cr^{k} · 2\sqrt{θ} · Q.

Since for all θ > 0

2\sqrt{θ} ≤ \sqrt{log M} · θ + \frac{1}{\sqrt{log M}} ,

we get

\sqrt{log N} ≤ 2\sqrt{log |J|} ≤ C · Q · r^{k} · \sqrt{log M} · (θ + \frac{1}{log M} ) ,

so (3.5) is satisfied.

References

[A] Alesker, S., ψ_{2}-esimate for the Euclidean norm on a convex body in isotropic position, Operator Theory Advances and Applications, vol. 77, 1995, pp. 1–4.

[B] Bourgain, J., Random points in isotropic convex sets, Preprint. [K-L-S] Kannan, R., Lovász, L., Simonovits, M., Random walks and O^{∗}(n^{5}) volume algorithm

for convex bodies, Preprint.

[L-T] Ledoux M., Talagrand M., Probability in Banach spaces, Ergeb. Math. Grenzgeb., 3

Folge, vol. 23, Springer, Berlin, 1991.

[M-P] Milman V. D., Pajor A., Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, Lecture Notes in Mathematics, Vol. 1376, Springer, Berlin, 1989, pp. 64–104.

[M-S] Milman V. D., Schechtman G., Asymptotic theory of finite–dimensional normed spaces, Lecture Notes in Mathematics, Vol. 1200, Springer, Berlin, 1986.

[R1] Rudelson, M., Approximate John’s decompositions, Operator Theory Advances and Applications, vol. 77, 1995, pp. 245–249.

[R2] Rudelson, M., Contact points of convex bodies, Israel Journal of Math. (to appear).

[R3] Rudelson, M., Almost orthogonal submatrices of an orthogonal matrix, MSRI Preprint.

[T1] Talagrand, M., Construction of majorizing measures, Bernoulli processes and cotype, Geometric and Functional Analysis 4, No. 6 (1994), 660–717.

[T2] Talagrand, M., Majorizing measures: the generic chaining, Ann. of Probability (to appear).

Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720, USA

E-mail address: mark@msri.org