A remark on the diameter of random sections of convex bodies

Introduction

In this note we revisit the following problem.

Given a random vector $X$ distributed according to $\mu$ and for $X_{1},...,X_{k}$ that are independent copies of $X$, let $\Gamma$ be the random matrix $k^{-1/2}\sum_{i=1}^{k}\bigl<X_{i},\cdot\bigr>e_{i}$.

The origin of this problem was the study of the geometry of convex bodies, and in particular, Milman’s low-$M^{*}$ estimate and subsequent estimates on the Gelfand widths of convex bodies, due to Pajor and Tomczak-Jaegermann .

In recent years, more emphasis has been put on other choices of measures on the Grassmann manifold, for example, using the distribution generated by kernels of matrices selected from some random ensemble – like $\Gamma=k^{-1/2}\sum_{i=1}^{k}\bigl<X_{i},\cdot\bigr>e_{i}$ defined above.

It is straightforward to show (see, for example, the discussion in ) that given $r>0$, if

Setting $r_{0}(k,\delta)$ to be the smallest for which

it follows that with probability at least $1-\delta$,

A version of Theorem 1.2 has been established in when $T\subset S^{n-1}$ and with a weaker probability estimate.

One other case in which the global complexity may be upper bounded using a mean-width of $T$, is when $X$ is isotropic, unconditional and log-concave. Using the Bobkov-Nazarov Theorem , $X$ is dominated by $Y=(y_{1},...,y_{n})$, a vector with independent, standard, exponential coordinates. One may show that with high probability,

Additional bounds on the quadratic process are known for more general measures, but only for very specific choices of sets $T$. The most important example is when $T$ is the Euclidean ball, and the quadratic empirical process may be used to obtain a Bai-Yin type estimate on the largest and smallest singular values of $\Gamma$ .

At this point, it should be noted that (1.1) is a much stronger statement than what is actually needed to bound the diameter of $T\cap{\rm ker}(\Gamma)$. Clearly, any sort of a positive lower bound on

would suffice – rather than the ‘almost isometric’, two-sided bound that follows from bounds on the quadratic process.

Here, we will show that (1.3) holds for rather general matrix ensembles.

Then, there exist a constant $c$ that depends only on $\lambda$, for which, with probability at least $3/4$,

Theorem 1.3 can be improved and extended in various ways.

First of all, the ‘correct’ upper estimate on the diameter should be based on a fixed point condition defined using the norms $\|\ \|_{(T\cap rB_{2}^{n})^{\circ}}$ rather than the norm $\|\ \|_{T^{\circ}}$. Also, the constant probability estimate of $3/4$ may be improved significantly to $1-2\exp(-ck)$ with a slightly more involved proof (see for a similar argument). We will formulate, without proof, a more general version of Theorem 1.3 at the end of the note.

1. If $X$ is an isotropic $L$-subgaussian vector, it is standard to verify that $k^{-1/2}\sum_{i=1}^{k}X_{i}$ is isotropic and $cL$-subgaussian for a suitable absolute constant $c$. Therefore,

and by Theorem 1.3, with probability at least $3/4$,

This coincides with the estimate from (up to the ‘localization’ mentioned above) and with the classical result of when $X$ is the standard gaussian vector.

2. If $X$ is an isotropic, unconditional, log-concave measure then so is $Z=k^{-1/2}\sum_{i=1}^{k}X_{i}$. By the Bobkov-Nazarov Theorem , both $Z$ and $G$ are strongly dominated by $Y$, the random vector with independent, standard exponential coordinates. Therefore, by Theorem 1.3, with probability at least $3/4$,

3. Theorem 1.3 leads to a ‘heavy tails’ result in some cases. Since $X$ is symmetric, $\sum_{i=1}^{k}X_{i}$ has the same distribution as $\sum_{i=1}^{k}\varepsilon_{i}X_{i}$, where $(\varepsilon_{i})_{i=1}^{k}$ are independent, symmetric $\{-1,1\}$-valued random variables that are independent of $(X_{i})_{i=1}^{k}$. If $T^{\circ}$ has a Rademacher type 2 constant $R_{2}(T^{\circ})$, then

Proof of Theorem 1.3

Let $\zeta$ be a random variable that satisfies

for constants $0<\varepsilon<1/12$ and $\lambda>0$.

If $\zeta_{1},...,\zeta_{k}$ are independent copies of $\zeta$, then with probability at least $1-2^{-6\varepsilon k}$ there is a subset $J\subset\{1,...,k\}$ of cardinality at least $(1-6\varepsilon)k$, and for every $j\in J$,

Proof. It suffices to show that no more than $6\varepsilon k$ of the $|\zeta_{i}|$’s are smaller than $\lambda\|\zeta\|_{L_{2}}$. By a binomial estimate, if $6\varepsilon k\leq k/2$,

If each $\zeta^{i}$ satisfies the small-ball condition (2.1) and $N\leq 2^{3\varepsilon k}$, then with probability at least $1-2^{-3\varepsilon k}$, for every $1\leq i\leq N$ there is a subset $J_{i}\subset\{1,...,k\}$, of cardinality at least $(1-6\varepsilon)k$, and

Proof of Theorem 1.3. Let $\varepsilon=1/600$ and observe that by the small ball assumption and since $X$ is isotropic,

Fix $r>0$ to be named later and set $T_{r}=T\cap rS^{n-1}$. Let

and set $Z_{i}=(\zeta_{j}^{i})_{j=1}^{k}$, a vector whose coordinates are independent copies of $\zeta^{i}$.

Applying Corollary 2.2 to the set $\{Z_{i}:1\leq i\leq 2^{3\varepsilon k}\}$, it follows that with probability at least $1-2^{-3\varepsilon k}$, for every $v\in V_{r}$ there is a subset $J_{v}\subset\{1,...,k\}$, $|J_{v}|\geq(1-6\varepsilon)k=99k/100$, and for every $j\in J_{v}$,

and the last equality holds because $V_{r}\subset rS^{n-1}$.

By the Giné-Zinn symmetrization inequality , the contraction inequality for Bernoulli processes (see, e.g., ), and since $x-\pi(x)\in 2T\cap\rho B_{2}^{n}$ for every $x\in T_{r}$,

Hence, by the choice of $\rho$ and the trivial inclusion $T\cap\rho B_{2}^{n}\subset T$,

Note that for $0<\delta<1$, with probability at least $1-\delta$,

On that event, if $(w_{i})_{i=1}^{k}\in W_{r}$ and $(w_{i}^{*})_{i=1}^{k}$ is a non-increasing rearrangement of $(|w_{i}|)_{i=1}^{k}$,

Thus, for every $x\in T_{r}$ there is a subset $J^{\prime}_{x}\subset\{1,...,k\}$ of cardinality at least $99k/100$, and for every $j\in J^{\prime}_{x}$,

Fix $X_{1},...,X_{k}$ in the intersection of the two events defined in (2.2) and (2.4). For every $x\in T_{r}$ set $I_{x}=J^{\prime}_{x}\cap J_{\pi(x)}$. Observe that $|I_{x}|\geq 98k/100$ and that for every $i\in I_{x}$,

concluding comments

The proof of Theorem 1.3 has two components. The first is based on a small-ball estimate for linear functionals and does not require additional information on their tails. Thus, this part holds even for heavy-tailed ensembles.

The more restrictive condition is on the random vector $k^{-1/2}\sum_{i=1}^{k}X_{i}$. Still, it is far easier to handle the norm $\|\sum_{i=1}^{k}X_{i}\|_{T^{\circ}}$ than the supremum of the quadratic empirical process indexed by $T$.

The estimate in Theorem 1.3 can be improved using what is, by now, a standard argument. First, observe that all the inequalities leading to (2.3) hold in probability and not just in expectation (see, for example, ). Keeping the ‘localization’ level $r$, one can define two fixed points:

It is straightforward to verify that there are constants $Q_{1}$ and $Q_{2}$ that depend only on $\lambda$, for which, with probability at least $1-\delta-2^{-k/200}$, if

Finally, it is possible to use a slightly more involved, empirical processes based method, that leads to an exponential probability estimate of $1-2\exp(-ck)$ in Theorem 1.3. A result of a similar flavour, concerning the smallest singular value of a random matrix with iid rows may by found in .

Since the goal in this note was to present the idea of using a simple small-ball argument, rather than pursuing an optimal result, we have opted to present this proof.

References