ALMOST ORTHOGONAL SUBMATRICES

OF AN ORTHOGONAL MATRIX

M. Rudelson

Abstract. Let t ≥ 1 and let n, M be natural numbers, n < M. Let A = (a_{i,j}) be an n × M matrix whose rows are orthonormal. Suppose that for all j

\sqrt{\frac{M}{n}} · (∑_{i=1}^{n} a_{i,j}^{2})^{1/2} ≤ t.

Using majorizing measure estimates we prove that for every ε > 0 there exists a set I ⊂ {1, …, M} of cardinality at most

C · \frac{t^{2}}{ε^{2}} · n · log n

so that for all x ∈ ℓ_{2}^{n}

(1 − ε) · ∥x∥ ≤ \sqrt{\frac{M}{|I|}} · ∥R_{I}A^{T} x∥ ≤ (1 + ε) · ∥x∥ .

Here R_{I} : ℝ^{M} → ℝ^{M} is the orthogonal projection onto the space span{e_{i} | i ∈ I}, where {e_{i}}_{i=1}^{M} is the standard basis of ℓ_{2}^{M}.

1. Introduction

We consider the following problem, posed by B. Kashin and L. Tzafriri [K-T]: Let ε > 0 and let n, M be natural numbers, n < M. Given an n × M matrix A whose rows are orthonormal, what is the smallest cardinality L(A, ε) of a subset I ⊂ {1, …, M} so that for all x ∈ ℓ_{2}^{n}

(1.1)  (1 − ε) · ∥x∥ ≤ \sqrt{\frac{M}{|I|}} · ∥R_{I}A^{T} x∥ ≤ (1 + ε) · ∥x∥ .

Here R_{I} : ℝ^{M} → ℝ^{M} is the orthogonal projection onto the space span{e_{i} | i ∈ I}, where {e_{i}}_{i=1}^{M} is the standard basis of ℝ^{M}. Throughout this paper we denote by ∥·∥ the standard ℓ_{2}-norm and by |I| the cardinality of a set I.

Research supported in part by a grant of the US–Israel BSF. Research at MSRI is supported in part by NSF grant DMS-9022140.

Typeset by AMS-TEX

Under an additional assumption that all the entries of A have the same absolute value 1/\sqrt{M} Kashin and Tzafriri proved that

(1.2)  L(A, ε) ≤ \frac{c}{ε^{4}} · n^{2} log n.

Moreover, their proof shows that a random subset I of this cardinality satisfies (1.1) with probability close to 1. Clearly, the estimate (1.2) is not optimal. The example of random selection of columns of a rectangular Walsh matrix, considered by Kashin and Tzafriri suggests that the possible upper bound could be

(1.3)  L(A, ε) ≤ C(ε) · n log n.

From the other side, simple examples ([K-T], [R]) show that the estimate (1.3) is the best one can obtain by the random selection method.

As it was mentioned in [R], the Kashin and Tzafriri problem is dual to that of finding an approximate John’s decomposition. Entropy estimates used in [R] for the last problem enabled to improve (1.2). More precisely, let t ≥ 1 and suppose that the matrix A satisfies

\sqrt{\frac{M}{n}} · (∑_{i=1}^{n} a_{i,j}^{2})^{1/2} ≤ t.

for all j = 1, …, M. Then

L(A, ε) ≤ C(ε) · t^{2} · n log^{3} n.

In order to improve this estimate one can use majorizing measures instead of entropy estimates. The method of majorizing measures, developed by Talagrand ([L-T], [T1]), is extremely useful in obtaining estimates of stochastic processes, related to random selection. A random process, similar to that arising in the Kashin and Tzafriri problem was considered by Talagrand [T2] for the problem of embedding of a finite dimensional subspace of L_{p} into ℓ_{p}^{N}. For this kind of processes Talagrand introduced a special method of constructing majorizing measures. This method (s-separated trees) can be used to prove an estimate

L(A, ε) ≤ C(ε) · t^{2} · n log n · (log log n)^{2}

for the Kashin and Tzafriri problem. It is unlikely that the (log log n)^{2} factor can be removed by a modification of the s-separated trees method. However, using a different approach based on the explicit construction of a partition tree, we obtained a sharper estimate. More precisely, we prove the following Theorem. Let t ≥ 1 and let A = (a_{i,j}) be an n × M matrix, whose rows are orthonormal. Suppose that for all j

(1.4)  \sqrt{\frac{M}{n}} · (∑_{i=1}^{n} a_{i,j}^{2})^{1/2} ≤ t.

Then for every ε > 0 there exists a set I ⊂ {1, …, M} so that

(1.5)  |I| ≤ C · \frac{t^{2}}{ε^{2}} · n · log n

and for all x ∈ ℝ^{n}

(1.6)  (1 − ε) · ∥x∥ ≤ \sqrt{\frac{M}{|I|}} · ∥R_{I}A^{T} x∥ ≤ (1 + ε) · ∥x∥ .

Throughout this paper C, c etc. denote absolute constants whose value may change from line to line.

The main part of the proof is the proof of Lemma 1 below. Our original proof of this lemma used the direct construction of the majorizing measure. It included an explicit construction of a sequence of partitions and putting weights on the elements of each partition. This scheme is based on the Talagrand and Zinn’s proof of the majorizing measure theorem of Fernique (Proposition 2.3 and Theorem 2.5 [T4]). The proof was rather involved, since we had to approximate the natural metric of a random process by a family of metrics depending on the elements of the partition. After we had shown our proof to M. Talagrand, he pointed out that the explicit construction of the partition tree may be substituted by applying his general majorizing measure construction (Theorems 4.2, 4.3 and Proposition 4.4 [T4]). This resulted in a considerable simplification of the proof. We present here the argument suggested by Talagrand.

By the duality between the Kashin and Tzafriri problem and approximate John’s decompositions, we have the following

Corollary. 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 its John ellipsoid is less than

m(n, ε) = C(ε) · n · log n.

2. The random selection method

Clearly, we may assume that M ≥ C · \frac{t^{2}}{ε^{2}} · n · log n for some absolute constant C.

The proof of the Theorem is based on the following iteration procedure. Let A = (a_{i,j}) be an n × M matrix , satisfying (1.4), We define a sequence {ε_{i}}_{i=1}^{M} of independent Bernoulli variables taking values ±1 with probability 1/2 and put

I_{1} = {i | ε_{i} = 1}.

Then

(2.1)  \frac{M}{2} · (1 − \frac{1}{\sqrt{M}} ) ≤ |I_{1}| ≤ \frac{M}{2}

with probability at least 1/4. Define

W = Aℝ^{n}

and denote by w(1), …, w(M) the coordinates of a vector w. We have to estimate

sup_{x∈B_{2}^{n}} |2 ∥R_{I}Ax∥^{2} − ∥x∥^{2}| = sup_{w∈W ∩B_{2}^{M}} |2 · ∑_{i∈I} w^{2}(i) − ∑_{i=1}^{M} w^{2}(i)|

= sup_{w∈W ∩B_{2}^{M}} |∑_{i=1}^{M} ε_{i}w^{2}(i)| .

Denote by 𝔼X the expectation of a random variable X. The key step of the proof is the following

Lemma 1. Let W be an n-dimensional subspace of ℝ^{M} . Let ε_{1}, …, ε_{M} be independent Bernoulli variables taking values ±1 with probability 1/2. Then

𝔼 sup_{w∈W ∩B_{2}^{M}} |∑_{i=1}^{M} ε_{i}w^{2}(i)| ≤ C\sqrt{log M} · ∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ .

Here P_{W} : ℝ^{M} → ℝ^{M} is the orthogonal projection onto W.

From (1.4) it follows that

∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ ≤ t · \sqrt{\frac{n}{M}} ,

so by Lemma 1 and Chebychev’s inequality we have

(2.2)  sup_{x∈B_{2}^{n}} |2 ∥R_{I_{1}}Ax∥^{2} − ∥x∥^{2}| ≤ C · t · \sqrt{\frac{n}{M}} · \sqrt{log M}

with probability more than 3/4. Thus, there exists a set I_{1} ⊂ {1, …, M} satisfying (2.1) and (2.2).

Repeating this procedure, we obtain a sequence of sets {1, …, M} = I_{0} ⊃ I_{1} ⊃ … ⊃ I_{s} so that

(2.3)  \frac{|I_{k}|}{2} · (1 − \frac{1}{\sqrt{|I_{k}|}}) ≤ |I_{k+1}| ≤ \frac{|I_{k}|}{2}

and

(2.4) sup_{x∈B_{2}^{n}} (2^{k} ∥R_{I_{k}}Ax∥^{2} − 2^{k−1} ∥R_{I_{k−1}}Ax∥^{2}) ≤ C · t · \sqrt{\frac{n}{M/2^{k}}} · \sqrt{log |I_{k−1}|}.

Indeed, at each step of induction we have

(2.5)  \frac{1}{2} ∥x∥ ≤ 2^{\frac{k−1}{2}} ∥R_{I_{k−1}}Ax∥ ≤ \frac{3}{2} ∥x∥ .

Assume for simplicity that I_{k−1} = {1, …, m} for some m < M. Let W_{k} = R_{I_{k−1}}Aℝ^{M} ⊂ ℝ^{m} and let P_{W_{k}} : ℝ^{m} → ℝ^{m} be the orthogonal projection onto W_{k}. Then

2^{\frac{k−1}{2}} R_{I_{k−1}}AB_{2}^{n} ⊂ \frac{3}{2}B_{2}^{m} ∩ W_{k},

so for a random set I_{k} ⊂ {1, …, m} we have

𝔼 sup_{x∈B_{2}^{n}} (2^{k} ∥R_{I_{k}}Ax∥^{2} − 2^{k−1} ∥R_{I_{k−1}}Ax∥^{2}) ≤𝔼 sup_{w∈ \frac{3}{2} B_{2}^{m}∩W_{k}} ∑_{i=1}^{m} ε_{i}w^{2}(i) ≤

\frac{9}{4}𝔼 sup_{w∈B_{2}^{m}∩W_{k}} ∑_{i=1}^{m} ε_{i}w^{2}(i).

To apply Lemma 1 we need to compute ∥P_{W_{k}} : ℓ_{1}^{m} → ℓ_{2}^{m}∥. By (2.5) we have

∥P_{W_{k}} : ℓ_{1}^{m} → ℓ_{2}^{m}∥ ≤ 2 · ∥(2^{\frac{k−1}{2}} R_{I_{k−1}}A)^{∗} : ℓ_{1}^{M} → ℓ_{2}^{n}∥ ≤ 2^{\frac{k+1}{2}} · t · \sqrt{\frac{n}{M}} .

Now (2.4) follows from Lemma 1 and Chebychev’s inequality.

Summing up inequalities (2.4) we get

(2.6)

sup_{x∈B_{2}^{n}} |2^{s} ∥R_{I_{s}}Ax∥^{2} − ∥x∥^{2}| ≤ C · t · \sqrt{\frac{n}{M/2^{s}}} · \sqrt{log |I_{s}|} ≤

C · t · \sqrt{\frac{n}{M/2^{s}}} · \sqrt{log \frac{M}{2^{s}}} .

We proceed until the last expression is greater than ε/2. In this case

c · \frac{t^{2}}{ε^{2}} · n · log n ≤ \frac{M}{2^{s}} ≤ C · \frac{t^{2}}{ε^{2}} · n · log n.

From (2.3) it follows that

\frac{M}{2^{s}} · (1 − \frac{4}{\sqrt{|I_{s}|}}) ≤ |I_{s}| ≤ \frac{M}{2^{s}} ,

so we obtain (1.5) and

\frac{M}{|I_{s}|} · (1 − (c · \frac{t^{2}}{ε^{2}} · n · log n)^{−1/2}) ≤ 2^{s} ≤ \frac{M}{|I_{s}|}.

Then, (2.6) implies that

sup_{x∈B_{2}^{n}} |\frac{M}{|I_{s}|} · ∥R_{I_{s}}Ax∥^{2} − ∥x∥^{2}| ≤ ε

and this completes the proof of the Theorem. □

Remark. The random selection method was used first by Talagrand [T3] to simplify the construction of embedding of a finite dimensional subspace of L_{1} into ℓ_{1}^{N}. The original construction of Bourgain, Lindenstrauss and Milman used the empirical distribution method instead of it. The advantage of the random selection is that it enables to deal with random processes having a subgaussian tail estimate, rather than with general Bernoulli processes.

3. Construction of the majorizing measure.

The proof of Lemma 1 uses the majorizing measure theorem of Talagrand [T1], [T4]. This theorem provides a bound to

𝔼 sup_{t∈T} X_{t}

for a subgaussian process X_{t} indexed by points of a metic space T with a metric d through the geometry of this space. However it turns out that the space T does not have to be assumed metric. The same proof works in the case when d is a quasimetric, i.e. if there exists a constant A such that for any t, t̄, s ∈ T

d(t, t̄) ≤ A · (d(t, s) + d(s, t̄)).

We use the following version of

Majorizing measure 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.1)  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 version may be obtained as 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 [T4]).

To prove Lemma 1 we need some estimates of covering numbers. Denote by N(B, d, ε) the ε-entropy of B, i.e. the number of ε-balls in the (quasi–) metric d needed to cover the body B. We use the following

Lemma 2. Let W be an n-dimensional subspace of ℝ^{M} and let P_{W} be the orthogonal projection onto W.

(1) ε\sqrt{log N(B_{2}^{M} ∩ W, ∥·∥_{∞} , ε)} ≤ C · ∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ · \sqrt{log M};

(2) Let ∥·∥_{E} be a norm defined by

∥x∥_{E} = (∑_{i=1}^{M} x^{2}(i) · a_{i}^{2})^{1/2} .

Then

ε\sqrt{log N(B_{2}^{M} ∩ W, ∥·∥_{E} , ε)} ≤ C · ∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ · (∑_{i=1}^{M} a_{i}^{2})^{1/2} .

Proof. Both statements follow from the dual Sudakov minoration [L-T].

(1) Let g be the standard Gaussian vector in ℝ^{M} . Then P_{W} g is the standard Gaussian vector in the space W. So,

ε\sqrt{log N(B_{2}^{M} ∩ W, ∥·∥_{∞} , ε)} ≤ C · 𝔼 ∥P_{W} g∥_{∞} = C · 𝔼 max_{j=1,...,M} |⟨P_{W} g, e_{j}⟩| ≤

C · \sqrt{log M} · max_{j=1,...,M} ∥P_{W} e_{j}∥ = C · \sqrt{log M} · ∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ . □

8 M. RUDELSON

(2) Again dual Sudakov minoration gives ε\sqrt{log N(B_{2}^{M} ∩ W, ∥·∥_{E} , ε)} ≤ C · 𝔼 ∥P_{W} g∥_{E} ≤ C · (𝔼 ∥P_{W} g∥_{E}^{2})^{1/2} =

C · (𝔼 ∑_{i=1}^{M}⟨P_{W} g, e_{i}⟩^{2}a_{i}^{2})^{1/2} ≤ C · max_{i=1,...,M} ∥P_{W} e_{i}∥ · (∑_{i=1}^{M} a_{i}^{2})^{1/2} . □

Proof of Lemma 1. Denote

W_{1} = B_{2}^{M} ∩ W.

We have to estimate the expectation of the supremum over all w ∈ W_{1} of a random process

V_{w} = ∑_{i=1}^{M} ε_{i}w^{2}(i).

The process V_{w} has a subgaussian tail estimate

P \{V_{w} − Vw̄ > a\} ≤ exp (−c\frac{a^{2}}{d̃^{2}(w, w̄)}) ,

where

d̃(w, w̄) = (∑_{i=1}^{M} (w^{2}(i) − w̄^{2}(i))^{2})^{1/2} .

We shall estimate the metric d̃ by a quasimetric, which is simpler to control.

\frac{1}{\sqrt{2}}d̃(w, w̄) ≤ d(w, w̄) = (∑_{i=1}^{M} (w(i) − w̄(i))^{2} · (w^{2}(i) + w̄^{2}(i)))^{1/2} .

Since

d(w, w̄) = (∑_{i=1}^{M} \frac{1}{2}(w(i) − w̄(i))^{2} · ((w(i) + w̄(i))^{2} + (w(i) − w̄(i))^{2}))^{1/2} ≤

\frac{1}{\sqrt{2}} · (d̃(w, w̄) + ∥w − w̄∥_{ℓ_{4}^{M}}^{2} ) ≤ \sqrt{2} · d(w, w̄),

we have a generalized triangle inequality for d. Namely for all u, w, w̄ ∈ W

(3.2)  d(w, w̄) ≤ 4 · (d(w, u) + d(u, w̄)).

The balls in the quasimetric d are not convex. However, we have the following Lemma 3. For all w ∈ W and ρ > 0

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

Here we denote by B_{ρ}(w) a ρ-ball in the quasimetric d.

Proof. Note that since for all u ∈ B_{ρ}(w)

(∑_{i=1}^{M} (u(i) − w(i))^{2}w^{2}(i))^{1/2} ≤ ρ

and

(∑_{i=1}^{M} (u(i) − w(i))^{4})^{1/4} ≤ (\sqrt{2}ρ)^{1/2},

the same inequalities hold also for all u ∈ convB_{ρ}(w). Since for all a, b ∈ ℝ, a^{2}+b^{2} ≤ 4a^{2} + 2(a − b)^{2}, for any u ∈ convB_{ρ}(w) we have

d(u, w) ≤ (∑_{i=1}^{M} (u(i) − w(i))^{2} · (4w^{2}(i) + 2(u(i) − w(i))^{2}))^{1/2} ≤

2· (∑_{i=1}^{M} (u(i) − w(i))^{2} · w^{2}(i))^{1/2} + \sqrt{2} · (∑_{i=1}^{M} (u(i) − w(i))^{4})^{1/2} ≤ 4ρ.

□ Denote

Q = ∥P_{W} : ℓ_{1}^{M} → ℓ_{2}^{M} ∥ .

Let now r be a natural number to be chosen later. Let k_{0} and k_{1} be the largest natural numbers so that

r^{−k_{0}} ≥ diam (W_{1}, ∥·∥_{∞}) = Q

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

Then k_{1} − k_{0} ≤ (2 log r)^{−1} log n.

Define functions φ_{k} : W_{1} → ℝ by

φ_{k}(w) = min\{∥u∥^{2} | u ∈ convB_{2r^{−k}}(w)\} + \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 + 2\sqrt{2}r^{l})}}{Q · \sqrt{log M}},  if k > k_{1}.

For any w ∈ W_{1} the sequence {φ_{k}(w)}_{k=k_{0}}^{∞} is nonnegative nondecreasing and bounded by an absolute constant depending only on r. Indeed, if k ≤ k_{1} then

φ_{k}(w) ≤ 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 + 2\sqrt{2}r^{l})}}{Q · \sqrt{log M}} ≤

1 + \frac{1}{2 log r} + c(r) · r^{−k_{1}} · \frac{\sqrt{n}}{Q} · \begin{matrix}√ & \overline{log(1 + 2\sqrt{2}r^{k_{1}})} \\ √ & \overline{log M} \end{matrix} ≤ C(r).

To prove Lemma 1 we have to show that condition (3.1) holds for {φ_{k}(w)}_{k=k_{0}}^{∞} with σ = (c · Q · \sqrt{log M})^{−1}. Let x ∈ W_{1} and suppose that the points x_{1}, …, x_{N} ∈ B_{r^{−k}}(x) satisfy

d(x_{j}, x_{l}) ≥ r^{−k−1} for all j ≠ l.

For k ≥ k_{1} − 1 condition (3.1) follows from the simple volume estimate

N ≤N(W_{1}, d, r^{−k−1}) ≤ N(W_{1}, ∥·∥_{∞} , \frac{r^{−k−1}}{\sqrt{2}} ) ≤ N(W_{1}, ∥·∥ , \frac{r^{−k−1}}{\sqrt{2}} ) ≤

(1 + \frac{2\sqrt{2}}{r^{−k−1}} )^{n} .

Suppose now that k_{0} ≤ k < k_{1} − 1. For j = 1, …, N denote by z_{j} the point of convB_{2r^{−k−2}}(x_{j}) for which the minimum of ∥z∥ is attained and denote by u the similar point of convB_{2r^{−k}}(x). By (3.2) and Lemma 3 we have for all j ≠ l

d(x_{j}, x_{l}) ≤ 16 · (d(x_{j}, z_{j}) + d(z_{j}, z_{l}) + d(z_{l}, x_{l})) ≤ 16 · (16 · r^{−k−2} + d(z_{j}, z_{l})),

so, d(z_{j}, z_{l}) ≥ \frac{1}{2}r^{−k−1} if r ≥ 512. Under the same assumption on r we have

d(z_{j}, x) ≤ 4(d(z_{j}, x_{j}) + d(x_{j}, x)) ≤ 2r^{−k}.

Denote

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

We have to prove that

(3.3) 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 \frac{z_{j}+u}{2} ∈ convB_{2r^{−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.4)  ∥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}^{M} ∩ W 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 ℓ_{∞} metric. By part (1) of Lemma 2 we may assume that

(3.5)  \frac{1}{16}r^{−k−1} · θ^{−1/2}\sqrt{log S} ≤ c · Q · \sqrt{θ}\sqrt{log M}.

If S ≥ \sqrt{N}, we are done, because in this case (3.5) implies (3.3). 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.6)  ∥z_{j} − z_{l}∥_{∞} ≤ \frac{1}{16}r^{−k−1} · θ^{−1/2}

for all j, l ∈ J, j ≠ l. Since d(z_{j}, z_{l}) ≥ \frac{1}{2}r^{−k−1}, we have

(3.7)  \begin{matrix}(\frac{1}{2}r^{−k−1})^{2} ≤ & ∑_{i=1}^{M} (z_{j}(i) − z_{l}(i))^{2} · (z_{j}^{2}(i) + z_{l}^{2}(i)) ≤ \\ ∑_{i=1}^{M} (z_{j}(i) − z_{l}(i))^{2}· \\ [4u^{2}(i) + z_{j}^{2}(i)· & 1_{\{i||z_{j}|≥2|u(i)|\}}(i) + z_{l}^{2}(i) · 1_{\{i||z_{l}|≥2|u(i)|\}}(i) ]. \end{matrix}

Then (3.4) implies

(3.8)  ∑_{i=1}^{M} z_{j}^{2}(i) · 1_{{i||z_{j}|≥2|u(i)|}}(i) ≤ 16θ

Combining (3.6) and (3.8) we get that (3.7) is bounded by

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

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

(∑_{i=1}^{M} (z_{j}(i) − z_{l}(i))^{2} · u^{2}(i))^{1/2} ≥ \frac{1}{8}r^{−k−1}.

Then part (2) of Lemma 2 implies

\frac{1}{8}r^{−k−1}\sqrt{log |J|} ≤ C\sqrt{θ} · Q · (∑_{i=1}^{M} u^{2}(i))^{1/2} ≤ C\sqrt{θ} · Q.

Since for all θ > 0

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

we get

\frac{1}{16}r^{−k−1}\sqrt{log N} ≤ \frac{1}{8}r^{−k−1}\sqrt{log |J|} ≤ C · Q · \sqrt{log M} · (θ + \frac{1}{log M} ) . □

Acknowledgment. I would like to thank Joram Lindenstrauss for helpful discussions and Michel Talagrand for the permission to present his approach to the proof of Lemma 1.

References

[K-T] Kashin, B., Tzafriri, L., Some remarks on the restrictions of operators to coordinate

subspaces, Preprint.

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

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

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

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

[T2] Talagrand, M., Embedding subspaces of L_{p} in ℓ_{p}^{N}, Operator Theory Advances and Applications, vol. 77, 1995, pp. 311–326.

[T3] Talagrand, M., Embedding subspaces of L_{1} in ℓ_{1}^{N}, Proc. Amer. math. Soc. 108 (1990), 363–369.

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

Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, 91904 Jerusalem, Israel and Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720, USA

E-mail address: mark@math.huji.ac.il, mark@msri.org