On generic chaining and the smallest singular value of random matrices with heavy tails

Introduction

The main goal of this article is to obtain a non-asymptotic version of the Bai-Yin Theorem on the largest and smallest singular values of certain random matrices. The Bai-Yin theorem asserts the following:

Let $A=A_{N,n}$ be an $N\times n$ random matrix with independent entries, distributed according to a random variable $\xi$, for which

If $N,n\to\infty$ and the aspect ratio $n/N$ converges to $\beta\in(0,1]$, then

almost surely, where $s_{\max}$ and $s_{\min}$ denote the largest and smallest singular value of $A$.

Also, without the fourth moment assumption, $s_{\max}(A)/\sqrt{N}$ is almost surely unbounded.

The main result of this article is a quantitative version of the Bai-Yin Theorem.

We will focus on the following questions:

Observe that the two questions are very similar. For example, it is straightforward to verify that if $\mu$ is isotropic, then both parts can be resolved by estimating the supremum of the empirical process

And, in view of the second part of Question 1.2, we will be especially interested in the case $N\sim n$, that is, while keeping the aspect ratio $n/N$ constant.

To formulate the moment assumption we will use here, recall that for $\alpha\geq 1$, the $\psi_{\alpha}$ Orlicz norm of random variable $Z$ is defined by

and there are obvious extensions for $0<\alpha<1$. It is standard to verify that for every $\alpha>0$, $\|Z\|_{\psi_{\alpha}}$ is equivalent to $\sup_{q\geq 1}\|Z\|_{L_{q}}/q^{1/\alpha}$.

For $p,q\geq 2$, a symmetric measure $\mu$ satisfies a $p$-small diameter, $L_{q}$ moment assumption with constants $\kappa_{1}$ and $\kappa_{2}$, if a random vector $X$ distributed according to $\mu$ satisfies that

$\mu$ satisfies a small diameter $\psi_{\alpha}$ moment assumption if the $\psi_{\alpha}$ norm replaces the $L_{q}$ one in (1.2).

One should note that with very few exceptions, both parts of Assumption 1.3 are needed if one wishes to address Question 1.2.

and $c_{1},c_{2}$ are constants that depend only on $\kappa_{1}$.

It is straightforward to verify that this bound is optimal by considering the uniform measure on the set of coordinate vectors $\{\sqrt{n}e_{1},...,\sqrt{n}e_{n}\}$, which results in the coupon-collector problem. Thus, given $\varepsilon>0$, one requires at least $c(\varepsilon)n\log n$ random points to ensure that the sample covariance matrix $\varepsilon$-approximates the true covariance. Of course, does not lead to a nontrivial estimate in the second part of Question 1.2, i.e. if the aspect ratio $n/N\to\beta\in(0,1]$ and $n\to\infty$, and in particular, (1.3) can not yield a Bai-Yin type of bound. Any hope of getting the desired bounds in Question (1.2) requires additional assumptions on $X$.

Unfortunately, when one has a weaker moment estimate than a $\psi_{2}$ one, the situation becomes considerably more difficult. The complexity of the set one has to control remains the same, but the individual concentration deteriorates, because N^{-1}\sum\bigl{<}X_{i},x\bigr{>}^{2} does not exhibit a strong enough concentration around its mean to balance the concentration-complexity tradeoff at the level of $\sqrt{n/N}$. Therefore, with a weaker moment assumption than a $\psi_{2}$ one, a combination of individual tail bounds and a “global” assumption, like the small diameter information, is required in both parts of Question 1.2.

Partial results in the isotropic, log-concave case have been obtain by Bourgain , yielding an estimate on the covariance operator for $N=c(\varepsilon)n\log^{3}n$, which was improved by Rudelson to $N=c(\varepsilon)n\log^{2}n$. Subsequent improvements were $N=c(\varepsilon)n\log n$ for unconditional convex bodies in and for general log-concave measures in . Finally, the optimal estimate of $N=c(\varepsilon)n$ was obtained for an unconditional, log-concave measures by Aubrun , and for an arbitrary log-concave measure in Adamczak et al. , where the following result was proved:

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. If $\mu$ is an isotropic, log-concave measure, then with probability at least $1-\exp(-c_{1}\sqrt{n})$,

Naturally, Question 1.2 becomes even harder when one assumes that linear functionals have heavy tails, because sums of independent random variable exhibit very limited concentration – far below the level required for the proof of Theorem 1.4. Recently, Vershynin proved the following remarkable fact:

For every $q>4$, $\delta>0$ and constants $\kappa_{1}$ and $\kappa_{2}$, there exist constants $c_{1}$ and $c_{2}$ that depend on $q$, $\delta$ and $\kappa_{1},\kappa_{2}$ for which the following holds.

If $\mu$ satisfies a $2$-small diameter, $L_{q}$ moment assumption with constants $\kappa_{1}$ and $\kappa_{2}$, then for every $\delta>0$, with probability at least $1-\delta$,

In particular, if $\mu$ is isotropic then

Moreover, very recently Strivastava and Vershynin , obtained the following result:

If $(X_{i})_{i=1}^{N}$ are independent random vectors distributed according to $\mu$ then for every $N\geqslant c_{1}n$,

Moreover, only under a $q$-moment assumption,

It should be noted that the boundedness assumption in Theorem 1.6 is satisfied by a vector with independent components $X=(\xi_{i})_{i=1}^{n}$, if $\xi\in L_{q}$ for $q>4$, and thus both parts may be used in the i.i.d situation. However, for any $\eta>0$, $c_{3}<\frac{1}{2}$ ($1/2$ being the power in the Bai-Yin Theorem).

Our main result gives a version of Theorem 1.5 for an unconditional measure with “heavy tails”.

Theorem A. Let $\mu$ be an unconditional measure that satisfies the $p$-small diameter, $L_{q}$ moment assumption with constants $\kappa_{1}$ and $\kappa_{2}$ for some $p>2$.

1. For every $q>4$ and $\delta<1/2-1/2(p-1)$, there exist constants $c_{0}$, $c_{1}$ and $c_{2}$ that depend on $q$, $p$, $\kappa_{1}$, $\kappa_{2}$ and $\delta$, such that, for every $n\leq N\leq\exp(c_{0}n^{\delta})$, with probability at least $1-\exp(-c_{1}n^{\delta})$,

2. For every $2<q\leq 4$, if $p>(1-2/q)^{-1}$ and $\delta<1/2-1/2(p-1)$, there exist constants $c_{3}$ and $c_{4}$ that depend on $q$, $p$, $\delta$, $\kappa_{1}$ and $\kappa_{2}$, such that, for every $n\leq N\leq\exp(c_{0}n^{\delta})$, with probability at least $1-\exp(-c_{3}n^{\delta})$,

In both cases, for every $\varepsilon>0$, with probability at least $1-2\exp(-cn^{\delta})$, $\|\Sigma_{N}-\Sigma\|_{2\to 2}\leq\varepsilon$ provided that $N\gtrsim_{q,p,\delta,\kappa_{1},\kappa_{2}}n$. Moreover, if $\mu$ is isotropic and $q>4$, then

for an arbitrary class of functions $H$ – not even for H_{T}=\{\bigl{<}t,\cdot\bigr{>}:t\in T\} when $T$ is not the sphere or close to the sphere in some sense.

The proof of Theorem A does just that, since it is based on a bound on (1.4) in terms of a certain notion of “complexity” of the class $H$. It is not tailored to the case $H_{B_{2}^{n}}$, nor does it relay on the fact that the indexing class consists of linear functionals. Rather, the proof is based on a chaining scheme which is much more general than the applications that will be presented here.

The second application we chose to present as an illustration of the potential this empirical processes based method has, is the following.

and thus $\mu$ is weakly dominated by $G$.

Moreover, the results of show that if $T$ is centrally symmetric and $\mu$ is isotropic and $L$-subgaussian, then

Theorem B has many standard applications, leading to embedding results of a similar nature to the Johnson-Lindenstrauss Lemma and to “low $M^{*}$” estimates that hold for unconditional, log-concave ensembles. Deriving these and other outcomes from Theorem B is standard and will not be presented here. One should also note that a log-concave Chevet type inequality, i.e., upper estimates on the operator norm $\|\Gamma\|_{X\to Y}$ for finite dimensional normed spaces $X$ and $Y$ has recently been established in .

Preliminaries

Throughout, all absolute constants are positive numbers, denoted by $c,c_{0},c_{1},...$ and their value may change from line to line. $\kappa_{0},\kappa_{1},...$ denote constants whose value will remain unchanged. By $A\sim B$ we mean that there are absolute constants $c$ and $C$ such that $cB\leq A\leq CB$, and by $A\lesssim B$ that $A\leq CB$. $A\sim_{\gamma}B$ (resp. $A\lesssim_{\gamma}B$) denotes that the constants depend only on $\gamma$.

Next, let us turn to the complexity parameters that motivated our method of analysis – Talagrand’s $\gamma$-functionals.

For a metric space $(T,d)$, an admissible sequence of $T$ is a collection of subsets of $T$, $\{T_{s}:s\geq 0\}$, such that for every $s\geq 1$, $|T_{s}|\leq 2^{2^{s}}$ and $|T_{0}|=1$. For $\beta\geq 1$, define the $\gamma_{\beta}$ functional by

where the infimum is taken with respect to all admissible sequences of $T$. For an admissible sequence $(T_{s})_{s\geq 0}$ we denote by $\pi_{s}t$ a nearest point to $t$ in $T_{s}$ with respect to the metric $d$.

One should note that our chaining approach is based on a slightly less restrictive definition, giving one more freedom; for example, the cardinality of the sets will not necessarily be $2^{2^{s}}$, the metric may change with $s$, etc. (see Section 3).

When considered for a set $T\subset L_{2}$, $\gamma_{2}$ has close connections with properties of the canonical gaussian process indexed by $T$, and we refer the reader to for detailed expositions on these connections. One can show that under mild measurability assumptions, if $\{G_{t}:t\in T\}$ is a centered gaussian process indexed by a set $T$, then

Decomposition of sets

Let $\phi$ be an increasing function which will be chosen according to additional information one will have on the given class. Examples that one should have in mind are $\phi_{\beta}(x)\sim_{\beta}\sqrt{x}\log^{1/\beta}(eN/x)$, resulting from a bound on the $\psi_{\beta}$ diameter of $H$, or $\phi_{q,\varepsilon}\sim_{q,\varepsilon}N^{(1+\varepsilon)/q}x^{1/2-(1+\varepsilon)/q}$ for $q>2$ and $\varepsilon$ in the right range, arising from an $L_{q}$ moment assumption.

1. $\sup_{v\in V}\left(\theta_{0}(\pi_{0}v)+\sum_{s>0}\theta_{s}(\Delta_{s}v)\right)\leq\gamma$.

2. For every $v\in V$ and every $I\subset\{1,...,N\}$,

3. If $\eta_{s}\leq N$ then for every $v\in V$ and every $I\subset\{1,...,N\}$

and if $\eta_{s}\geq N$ then for every $v\in V$ and every $I\subset\{1,...,N\}$,

Although this definition seems artificial at first glance, we will show that it captures the geometry of a typical coordinate projection $P_{\sigma}H=\{(h(X_{i}))_{i=1}^{N}:h\in H\}$.

To formulate the estimate on the Bernoulli process, set

For $2<q\leq 4$ and $0\leq\varepsilon<(q/2)-1$, let

As will become clearer, the most important of the $B_{q,\varepsilon}$ parameters is

which, under the standard choice of $\eta_{0}=0$ and $\eta_{s}=2^{s}$ for $s\geq 1$, corresponds to $\gamma_{2}(V,\|\ \|)$.

Before presenting the proof, let us consider the two main examples which will interest us, namely, the families $\phi_{\beta}=\sqrt{x}\log^{1/\beta}(eN/x)$ for any $\beta>0$ and $\phi_{q,\varepsilon}=\sqrt{x}(N/x)^{(1+\varepsilon)/q}$ for any $q>2$ (and for $\varepsilon$ selected appropriately).

In both cases $\phi(N)\sim\sqrt{N}$ and for any $\beta>0$, $\Phi\sim_{\beta}\sqrt{N}$. If $q>4$ and $0\leq\varepsilon\leq q/4-1$, $\Phi\leq(1-4(1+\varepsilon)/q)^{-1/2}\sqrt{N}$, and since $\Phi_{s}\leq\Phi$, then for $\beta>0$ or $q>4$,

with the constant depending either on $\beta$ or on $q$ and $\varepsilon$ as above.

On the other hand, if $2<q\leq 4$ and $0<\varepsilon<q/2-1$ then

Next, since $(\eta_{s})_{s\geq 0}$ increases exponentially, then for $q>2$

and the constant in (3.1) depends on $\beta$ or on $q$ and $\varepsilon$ respectively. In particular, if $2<q\leq 4$ and $0<\varepsilon<q/2-1$, then

Finally, one has to control $\sum_{\{s:\eta_{s}\leq N\}}\phi^{2}(\eta_{s})\|\Delta_{s}v\|$. Note that if $\beta>0$ or $q>4$, then

and if $2<q\leq 4$ and $0<\varepsilon<q/2-1$ then

We thus arrive to a more compact formulation of Theorem 3.2 in the cases we will be interested in.

For any $\beta>0$ or $q>4$, with probability at least $1-2\exp(-c_{1}r^{2}\eta_{0})$,

with a constant that depends on $\beta$ or on $q$ and $\varepsilon$ respectively.

Also, if $2<q\leq 4$ and $0<\varepsilon<q/2-1$, then with probability at least $1-2\exp(-c_{1}r^{2}\eta_{0})$,

Let $w\cdot v=\sum_{i=1}^{N}w_{i}v_{i}e_{i}$, and since

one has to control increments of the form $\sum_{i=1}^{N}\varepsilon_{i}(\Delta_{s}v)_{i}(\pi_{s}v+\pi_{s-1}v)_{i}$.

Observe that if $\eta_{s}\geq N$ then with probability $1$,

Next, if $\eta_{s}\leq N$ we will decompose the vectors one has to control according to the size of their coordinates, because, with probability $1-2\exp(-r^{2}/2)$,

Consider the following two cases. If $i_{s,v}=\eta_{s}$ then

Therefore, summing the three terms over $\{s>0:\eta_{s}\leq N\}$,

then splitting each $w\in V$ to $w^{+}+w^{-}$ as above,

Recall that $|\Delta_{s}V|,|V_{s}|\leq 10\cdot 2^{\eta_{s+1}}$ and that $\eta_{s+1}\leq 10\eta_{s}$. Given $r\geq c_{0}$, then applying (3) for $t_{s}=10r\eta_{s}^{1/2}$ and summing over $\{s:\eta_{s}\leq N\}$, it follows that $\sup_{v\in V}\left|\sum_{i=1}^{N}\varepsilon_{i}(v^{2}-(\pi_{0}v)^{2})_{i}\right|$ is bounded by the desired quantity with probability at least $1-2\exp(-c_{1}r^{2}\eta_{0})$.

Coordinate projections of Function classes

The aim of this section is to show that under very mild assumptions, empirical processes have well behaved coordinate projections in the sense of Definition 3.1. A first result in this direction was established in , in which the main observation, formulated in the language of Section 3, was that if $\eta_{0}=0$ and $\eta_{s}=2^{s}$ for $s\geq 1$, then for the choice of $\theta_{s}((h(X_{i}))_{i=1}^{N})=2^{s/2}\|h\|_{\psi_{2}}$, $\alpha=\sqrt{u}$, $\|(h(X_{i}))_{i=1}^{N}\|=\|h\|_{\psi_{1}}$ and $\phi(x)\sim\sqrt{x}\log(eN/x)$, the set $V=\{(h(X_{i}))_{i=1}^{N}:h\in H\}$ has a good decomposition with high probability. Hence, the Bernoulli process indexed by $V^{2}$ satisfies the following:

There exist absolute constants $c_{1}$, $c_{2}$ and $c_{3}$ for which the following holds. If $H$ is a class of functions, then for every $r,u\geq c_{1}$, with $\mu^{N}$-probability at least $1-2\exp(-c_{2}u)$, $V=P_{\sigma}H$ satisfies that

with probability at least $1-2\exp(-c_{3}r^{2})$ with respect to the Bernoulli random variables.

Theorem 4.1 is rather restricted because the $\psi_{2}$-based complexity parameter seems too strong in many situations, as does the assumption that $H$ is a bounded subset of $L_{\psi_{1}}$. Here, we will try to impose as few assumptions as possible on $H$.

Let $H$ be a class of functions on $(\Omega,\mu)$. For every $u>0$ we will define three events in the product space $\Omega^{N}$, which will be denoted by $\Omega_{1,u}$, $\Omega_{2,u}$ and $\Omega_{3,u}$. On the event $\Omega_{1,u}\cap\Omega_{2,u}\cap\Omega_{3,u}$, the random set $P_{\sigma}H=\{(h(X_{i}))_{i=1}^{N}:h\in H\}$ will be well behaved for the right choice of functionals $\theta_{s}$ and $\phi$. We will then study cases in which the event $\Omega_{1,u}\cap\Omega_{2,u}\cap\Omega_{3,u}$ has high probability.

For $(\eta_{s})_{s\geq 0}$ as above, set $s_{0}\geq 0$ to be the first integer for which $\eta_{s}\geq\log(eN)$.

For an admissible sequence $(H_{s})_{s\geq 0}$ and a sequence of functionals $(\theta_{u,s})_{s\geq s_{0}}$, let $\Omega_{1,u}$ be the event for which, for every $h\in H$, the following holds:

2. for every $\eta_{s}>N$, $\left(\sum_{i=1}^{N}((\Delta_{s}h)^{2}(X_{i}))^{*}\right)^{1/2}\leq\theta_{u,s}(\Delta_{s}h)$.

Formally, to define the set $\Omega_{2,u}$, first fix a random variable $Y$, an integer $N$ and $\varepsilon>0$. For every $j\leq N$ let $\delta_{j}=(j/eN)^{(1+\varepsilon)}$, set

and without loss of generality, we will assume that the infimum is attained.

where $\kappa_{3}$ is a suitable chosen absolute constant.

The motivation for this definition is the following observation, showing that with high probability, the “tail” of a sum of i.i.d random variables can be controlled using $f$.

Proof. Since $Pr(|Y|\geq y_{j})\leq\delta_{j}=(j/eN)^{1+\varepsilon}$ then for $u\geq 1$,

where the last inequality is evident by a change of variables.

We will also need the following “global” counterpart of the functional $f$.

Given a class of functions $H$, an integer $N$ and $\varepsilon>0$, set

Clearly, for every $h\in H$ and every $k$, $f_{u}(h,k)\leq F_{u}(k)$.

The final set, $\Omega_{3,u}$ is very close in nature to $\Omega_{2,u}$. It is needed to control the coordinates of “very small” increments – when $s<s_{0}$, if such an integer exists.

If $\eta_{0}<\log(eN)$, let $\Omega_{3,u}$ be the event on which for every $h\in H$, every $0\leq s<s_{0}$ and $1\leq j\leq N$,

If $\eta_{0}\geq\log(eN)$ set $\Omega_{3,u}=\Omega^{N}$.

It turns out that on the event $\Omega_{1,u}\cap\Omega_{2,u}\cap\Omega_{3,u}$, the set $P_{\sigma}H$ is indeed well behaved. Let

with the infimum is taken with respect to all $(\eta_{s})$-admissible sequences. From here on we will assume that $(H_{s})_{s\geq 0}$ is an almost optimal $(\eta_{s})_{s\geq 0}$-admissible sequence.

There exists absolute constants $c_{1}$ and $c_{2}$ for which the following holds. Let $(\theta_{u,s})_{s\geq s_{0}}$ be functionals, and for $s<s_{0}$ set $\theta_{u,s}=0$. For every $u\geq c_{1}$, on the event $\Omega_{1,u}\cap\Omega_{2,u}\cap\Omega_{3,u}$, for every $h\in H$ and $I\subset\{1,...,N\}$,

where $R_{s_{0},I}(h)=\theta_{u,0}(\pi_{0}h)$ if $s_{0}=0$ and $R_{s_{0}}(h,I)=\min\{\theta_{u,s_{0}}(\pi_{s_{0}}h),F_{u}(|I|)\}$ otherwise.

and the claim is evident from the definition of the function $f_{u}$ and the set $\Omega_{2,u}$.

If, on the other hand, $\eta_{s}<\log(eN)$ then $s_{0}>0$ and the assertion follows from the definition of $\Omega_{3,u}$.

The second part of (1) follows from the definition of $\Omega_{1,u}$.

and thus, for every $h\in H$ and every $I\subset\{1,...,N\}$,

For Lemma 4.8 to have any meaning, one has to identify the functionals $f_{u}$, $F_{u}$ and $\theta_{u,s}$ in the cases one is interested in. Our next goal is to study the functions $f_{u}$ and $F_{u}$ under various tail assumptions on functions in $H$, and naturally, the two families of tail estimates we will be interested in are when $H$ has a bounded diameter in $L_{\psi_{\beta}}$ or in $L_{q}$ for $q>2$.

If $H\subset L_{\psi_{\beta}}$, then for every $h\in H$, $Pr(|h|\geq y)\leq\exp(-(y/\|h\|_{\psi_{\beta}})^{\beta})$. Thus, for $\varepsilon\geq 1$ and every $j$,

Hence, if $d_{\psi_{\beta}}=\sup_{h\in H}\|h\|_{\psi_{\beta}}$, then

Using the same argument, if $h\in L_{q}$ then $Pr(|h|\geq\|h\|_{L_{q}}y)\leq 1/y^{q}$ and for any $0<\varepsilon<q/2-1$, $y_{j}=\|h\|_{L_{q}}(N/j)^{(1+\varepsilon)/q}$. If $\sup_{h\in H}\|h\|_{L_{q}}=d_{L_{q}}$, $q>2$ and $c_{q,\varepsilon}=1-2(1+\varepsilon)/q$ then

Combining these observations with the estimates of Lemma 4.8 and noting that if $s_{0}>0$ then $R_{s_{0},I}(h)\lesssim\sqrt{u}d_{L_{q}}\phi_{q,\varepsilon}(|I|)$, one reaches the following corollary.

Let $(\theta_{u,s})_{s\geq s_{0}}$ be a sequence of functionals and for $s<s_{0}$ let $\theta_{u,s}=0$. If $H$ is bounded in $L_{q}$ for $q>2$, then on $\Omega_{1,u}\cap\Omega_{2,u}\cap\Omega_{3,u}$, for every $h\in H$ and every $I\subset\{1,...,N\}$

A similar bound holds when $H$ is bounded in $L_{\psi_{\beta}}$.

We will begin by showing that $\Omega_{2,u}$ is a large set, almost regardless of any assumptions on $\phi$, an observation that is based on the same idea as Lemma 4.4.

There exist absolute constants $c_{1}$ and $c_{2}$ such that, for every $\varepsilon>0$ and $u\geq c_{1}/\varepsilon$, $Pr(\Omega_{2,u})\geq 1-2\exp(-c_{2}\varepsilon u\eta_{s_{0}})$.

Since $\Omega_{2,u}$ is always large, and since $\Omega_{3,u}$ will behave in a very similar way when $s_{0}>0$, the crucial point in the construction of a good decomposition of $P_{\sigma}H$ is a correct choice of $\theta_{u,s}$ and estimates on $\Omega_{1,u}$.

The functionals $\theta_{u,s}$ capture the geometry of $H$, and thus have to be selected according to the information one has on the class. We will present two examples of such choices, each leading to one of our two main results. The first one will be based on “global” structure like metric entropy, while the second uses accurate estimates on each “chain”.

Let $\kappa_{4}\geq 10$ be an absolute constant to be fixed later, set $2^{s_{1}}\sim n^{\delta}$ for $\delta<1/2-1/2(p-1)$, and put

Note that $s_{0}=0$ as long as $\eta_{0}\sim 2^{s_{1}}\log(en/2^{s_{1}})\geq\log(eN)$, i.e., if $n^{\delta}\log(n)\gtrsim\log(eN)$ - which we will assume is the case, since our main interest in when $N\sim n$.

For every $\kappa_{1}$, $p>2$ and $\delta<1/2-1/2(p-1)$ there exist constants $c_{1},c_{2}$ and $c_{3}$ that depend only on $\kappa_{1}$, $p$ and $\delta$ for which the following holds. There is an $(\eta_{s})_{s\geq 0}$-admissible sequence of $B_{2}^{n}$, for which, if $u\geq c_{1}$, then $Pr(\Omega_{1,u})\geq 1-\exp(-c_{2}n^{\delta})$ and

Indeed, by the unconditionality of $\mu$, $(x_{1},...,x_{n})$ has the same distribution as $(\varepsilon_{1}x_{1},...,\varepsilon_{n}x_{n})$. Hence, for every $r\geq 1$

If $I\subset\{1,...,n\}$ then for every $\varepsilon>0$, $\log N(B_{2}^{I},\varepsilon B_{\psi_{2}})\lesssim M_{|I|}^{2}/\varepsilon^{2}$. Moreover, for $\varepsilon\leq 1$, $\log N(B_{2}^{n},\varepsilon B_{\psi_{2}})\lesssim n\log(2/\varepsilon)$.

for a suitable absolute constant $c$, proving the first part.

For the second part, note that $N(B_{2}^{n},\varepsilon B_{\psi_{2}})\leq N(B_{2}^{n},B_{\psi_{2}})\cdot N(B_{\psi_{2}},\varepsilon B_{\psi_{2}})$. By the first part, $\log N(B_{2}^{n},B_{\psi_{2}})\lesssim n$, while a standard volumetric estimate shows that $N(B_{\psi_{2}},\varepsilon B_{\psi_{2}})\leq(5/\varepsilon)^{n}$.

Next, let us define the sets $T_{s}$. If $2^{s+s_{1}}>n$, let $T_{s}$ be a maximal $\varepsilon_{s}$ separated subset of $B_{2}^{n}$ relative to the $\psi_{2}$ norm and of cardinality $2^{\eta_{s}}$. If $2^{s+s_{1}}\leq n$, let $T_{s}$ be a maximal $\varepsilon_{s}$ separated subset of $U_{2^{s+s_{1}}}=\{x\in B_{2}^{n}:|{\rm supp}(x)|\leq 2^{s+s_{1}}\}$ with respect to the $\psi_{2}$ norm, and of cardinality $2^{\eta_{s}}$. Given a vector $t\in B_{2}^{n}$, we will define the functions $\pi_{s}$ as follows. If $2^{s+s_{1}}>n$, $\pi_{s}t$ is a best $\psi_{2}$ approximation of $t$ in $T_{s}$. For $2^{s+s_{1}}\leq n$ one combines approximation and dimension reduction. Set $s_{*}$ to satisfy that $2^{s_{*}+s_{1}}=n$ (and without loss of generality we will assume that such an integer exists). If $v=\pi_{s_{*}}t$, let $I_{n/2}$ be the set of the largest $n/2$ coordinates of $v$, and put $\pi_{s_{*}-1}t$ to be the best approximation of the coordinate projection $P_{I_{n/2}}v$ in $T_{s_{*}-1}$, and so on.

There exists an absolute constant $c$ such that for every $t\in B_{2}^{n}$, if $s>s_{*}$ (i.e., if $\eta_{s}>\kappa_{3}n$), then \|\bigl{<}\Delta_{s}t,\cdot\bigr{>}\|_{\psi_{2}}\leq c2^{-2^{s+s_{1}}/n}, and if $0<s\leq s_{*}$ then \|\bigl{<}\Delta_{s}t,\cdot\bigr{>}\|_{\psi_{2}}\leq c2^{-(s+s_{1})/2}M_{2^{s+s_{1}}}.

Proof. First consider $s>s_{*}$. Note that \|\bigl{<}\Delta_{s}t,\cdot\bigr{>}\|_{\psi_{2}}\leq\|\bigl{<}t-\pi_{s}t,\cdot\bigr{>}\|_{\psi_{2}}+\|\bigl{<}t-\pi_{s-1}t,\cdot\bigr{>}\|_{\psi_{2}}\leq\varepsilon_{s}+\varepsilon_{s-1}, and by the covering numbers estimate from Lemma 5.3, in that range $\varepsilon_{s}\lesssim 2^{-2^{s+s_{1}}/n}$.

In the range $s\leq s_{*}$, $\Delta_{s}t=u+w$, where $w$ consists of the smallest $2^{s+s_{1}-1}$ coordinates of $\pi_{s}t\in B_{2}^{I}$ for some $|I|=2^{s+s_{1}}$, and $u$ is an $\varepsilon_{s-1}$-approximation of the largest $2^{s+s_{1}-1}$ coordinates of $\pi_{s}t$. Therefore, \|\bigl{<}\Delta_{s}t,\cdot\bigr{>}\|_{\psi_{2}}\leq\|\bigl{<}w,\cdot\bigr{>}\|_{\psi_{2}}+\varepsilon_{s-1}. Recall that for every such $s$, $U_{2^{s+s_{1}}}$ is a union of $\binom{n}{2^{s+s_{1}}}$ balls of dimension $2^{s+s_{1}}$, then

Proof of Theorem 5.2. Observe that $\|Y\|_{\psi_{2}}^{2}=\|Y^{2}\|_{\psi_{1}}$, and thus, by a standard application of Bernstein’s inequality, for every integer $m$,

Also, with probability at least $1-2\exp(-c_{2}w^{2}\eta_{s})$, if $\eta_{s}\geq N$ then

Using Lemma 5.4 and summing the probability estimates, it is evident that with probability at least $1-2\exp(-c_{3}w^{2}\eta_{0})$, the following holds: if $\eta_{s}\geq N$ then

and if $s>0$ and $\eta_{s}\leq\kappa_{4}n$ then

Note that if $2^{s_{1}}\sim n^{\delta}$ for $\delta<1/2-1/2(p-1)$, then

There exist absolute constants $c_{1}$, $c_{2}$ and $c_{3}$ and $c_{4}$ that depend on $\kappa_{1},\kappa_{2},p,\delta$, for which the following holds. If $\mu$ is as above and $\varepsilon>0$, then $B_{2}^{n}$ has an $(\eta_{s})_{s\geq 0}$-admissible sequence $(T_{s})_{s\geq 0}$ for which, for $u\geq c_{1}/\varepsilon$, with probability at least $1-2\exp(-c_{2}\varepsilon un)-2\exp(-c_{3}n^{\delta})$, for every $t\in B_{2}^{n}$ and every $I\subset\{1,...,N\}$,

For every $\kappa_{1}$, $\kappa_{2}$, $q>4$, $p>2$ and $\delta<1/2-1/2(p-1)$, there exist constants $c_{0}$, $c_{1}$, $c_{2}$ and $c_{3}$ which depend on $\kappa_{1}$, $\kappa_{2}$, $p$, $q$ and $\delta$, and an absolute constant $c_{4}$ for which the following holds. If $\mu$ is as above, and $N\leq\exp(c_{0}n^{\delta})$, then for every $u\geq c_{1}$, with $\mu^{N}$-probability at least $1-2\exp(-c_{2}n^{\delta})$, $P_{\sigma}(B_{2}^{n})$ satisfies that

with probability at least $1-2\exp(-c_{4}nr^{2})$ relative to the Bernoulli random variables.

Turning to the case $2<q\leq 4$, recall that for $0<\varepsilon<q/2-1$, $B_{q,\varepsilon}=\sum_{\{s:\eta_{s}\leq N\}}\eta_{s}^{1-2(1+\varepsilon)/q}\|\Delta_{s}v\|_{L_{q}}$. Assume that $\mu$ is as above and satisfies the $p$-small diameter assumption for $p>q/(q/2-1)$. Then, for $0<\varepsilon<q/2-1-q/p$ (i.e. if $1-(2(1+\varepsilon)/q)-1/p>0$),

Let $2<q\leq 4$, $p>(1-2/q)^{-1}$ and $0<\varepsilon<2/q-1-q/p$. If $\mu$ and $\delta$ are as above, $u\gtrsim 1/\varepsilon$, and $N\lesssim\exp(c_{0}n^{\delta})$, then with $\mu^{N}$ probability at least $1-2\exp(-c_{1}\varepsilon un)-2\exp(-c_{2}n^{\delta})$, $P_{\sigma}(B_{2}^{n})$ satisfies that

with probability at least $1-2\exp(-c_{3}nr^{2})$ relative to the Bernoulli random variables.

In particular, taking $\varepsilon\sim 1/\log(eN/n)$, then for every such $N$ satisfying that $N\gtrsim_{\kappa_{1},\kappa_{2},q,p}n$, and any $u\geq_{\kappa_{1},\kappa_{2},q,p}\log(eN/n)$,

2 Unconditional log-concave measures

We will now present a different way of bounding $\Omega_{1,u}$ (and $\Omega_{3,u}$ if needed) by estimating the moments of the increments $\Delta_{s}h$, and selecting the functionals $\theta_{u,s}$ accordingly.

In light of Theorem B, we will assume that $H$ is a bounded subset of $L_{\psi_{1}}$ (although what we do here can be extended to other moment assumptions), and thus one may control $\Omega_{2,u}$ using $\phi_{\beta}$ for $\beta=1$ and $\varepsilon$ which will be selected later.

There exist absolute constants $c_{1}$, $c_{2}$ and $c_{3}$ for which the following holds. For $u\geq c_{1}$, with probability at least $1-2\exp(-c_{1}u\eta_{s_{0}})$, for every $s\geq s_{0}$ and every $h\in H$, $Z_{s}(h)\leq e\|Z_{s}(h)\|_{L_{2u\eta_{s+1}}}$.

Next, one has to control the moments appearing in Lemma 5.8, which is based on the following result, due to Latała .

Let $X_{1},...,X_{m}$ be independent, distributed according to a nonnegative random variable $X$. Then for every $p\geq 1$,

If $X$ is a random variable, for every $p\geq 1$ set

The $(p)$-norms are a local version of the $\psi_{2}$ norm, and clearly $\|X\|_{(p)}\lesssim\|X\|_{\psi_{2}}$. Using those norms one may obtain a more compact expression for the required moments.

There exist an absolute constant $c$ such that for every $h\in H$, every $s>s_{0}$ and every $u>0$,

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. If, for $s>s_{0}$,

then $Pr(\Omega_{1,u})\geq 1-2\exp(-c_{2}u\eta_{s_{0}})$.

Next, assume that $s_{0}>0$, and thus one has to bound $Pr(\Omega_{3,u})$.

There exists absolute constants $c_{1}$, $c_{2}$ and $c_{3}$ such that, for every $u\geq c_{1}$, with probability at least $1-2\exp(-c_{2}u\log N)$, for every $0\leq s<s_{0}$ and every $h\in H$,

and a similar bound holds for $\pi_{s_{0}}h$.

Proof. Recall that for a fixed $\varepsilon>0$ and every $i$, $Pr(Y_{i}^{*}\geq y_{i})\leq\exp(-\varepsilon i\log(eN/i))$. Let $\varepsilon\sim u\geq 1$ and observe that if $Y\in L_{\psi_{1}}$, then $y_{i}\lesssim u\|Y\|_{\psi_{1}}\log(eN/i)$ and

Since the cardinality of the set $\cup_{s<s_{0}}\Delta_{s}H$ is at most $\sum_{s<s_{0}}2^{\eta_{s+1}}\lesssim N^{c_{2}}$, (5.6) holds uniformly with probability at least $1-\exp(-c_{3}u\log N)$ for $u\geq c_{4}$. Therefore, on that event, for every $0\leq s<s_{0}$ and every $j$,