On the interval of fluctuation of the singular values of random matrices

Introduction and main results

for a certain function $\phi$ and we assume that $X_{i}$ satisfies ${\bf H}(\phi)$ for all $i\leq N$. We will focus on two choices of the function $\phi$, namely $\phi(t)=t^{p}$, with $p>4$, which means heavy tail behavior for marginals, and $\phi(t)=(1/2)\exp(t^{\alpha})$, with $\alpha\in(0,2]$, which corresponds to an exponential power type tail behavior and extends the known subexponential case ($\alpha=1$, see ).

Until now the only known cases of random matrices satisfying a RIP were the cases of subgaussian and subexponential matrices. Our first main theorem says that matrices we consider have the RIP of order $m$, with “large” $m$ of the form $m=n\psi(n/N)$ with $\psi$ depending on $\phi$ and possibly on other parameters. In particular, when $N$ is proportional to $n$, then $m$ is proportional to $n$. We present a simplified version of our result, for the detailed version see Theorem 3.1 below.

Let $0<\theta<1$. Let $A$ be a random $n\times N$ matrix whose columns $X_{1},\ldots,X_{N}$ are independent random vectors satisfying hypothesis $\mbox{\bf H}(\phi)$ for some $\phi$. Assume that $n,N$ are large enough. Then there exists a function $\psi$ depending on $\phi$ and $\theta$ such that with high probability (depending on the concentration function $P(\theta)$) the matrix $A/\sqrt{n}$ has RIP of order $m=[n\psi(n/N)]$ with a parameter $\theta$ (that is, $\delta_{m}(A/\sqrt{n})\leq\theta$).

where $C$ is a positive absolute constant. In the same estimate was obtained for a large class of random matrices, which in particular did not require that entries of the columns are independent, or that $X_{i}$’s are identically distributed. In particular this solved the original KLS problem. More precisely, (4) holds with high probability under the assumptions that the $X_{i}$’s satisfy hypothesis $\mbox{\bf H}(\phi)$ with $\phi(t)=e^{t}/2$ and that $M\leq C(Nn)^{1/4}$ with high probability. Both conditions hold for log-concave random vectors.

Until recent time, quite strong conditions on the tail behavior of the one dimensional marginals of the $X_{i}$ were imposed, typically of subexponential type. Of course, in view of Bai-Yin theorem, it is a natural question whether one can replace the function $\phi(t)=e^{t}/2$ by the function $\phi(t)=e^{t^{\alpha}}/2$ with $\alpha\in(0,1)$ or $\phi(t)=t^{p}$, for $p\geq 4$. The first attempt in this direction was done in , where the bound $S\leq C(p,K)(n/N)^{1/2-2/p}(\ln\ln n)^{2}$ was obtained for every $p>4$ provided that $M\leq K\sqrt{n}$. Clearly, $\ln\ln n$ is a “parasitic” term, which, in particular, does not allow to solve the KLS problem with $N$ proportional to $n$. This problem was solved in under strong assumptions and in particular when $M\leq K\sqrt{n}$ and $X$ has i.i.d. coordinates with bounded $p$-th moment with $p>4$. Very recently, in , the “right” upper bound $S\leq C(n/N)^{1/2}$ was proved for $p>8$ provided that $M\leq C(Nn)^{1/4}$. The methods used in play an influential role in the present paper.

In this paper we solve the KLS problem for $4<p\leq 8$, in Theorem 1.2. Our argument works also in other cases and makes the bridge between the known cases $p>8$ and the exponential case.

with probability larger than $1-8e^{-n}-2\varepsilon^{-p/2}\max\{N^{-3/2},n^{-(p/4-1)}\}$.

In particular, if $N$ is proportional to $n$ and $M^{2}/n$ is bounded by a constant with high probability, which is the case for large classes of random vectors, then with high probability

Let $X$ have i.i.d. coordinates distributed as a centered random variable with finite $p$-th moment, $p>2$. Then by Rosenthal’s inequality (, see also and Lemma 6.3 below), $X$ satisfies hypothesis $\mbox{\bf H}(\phi)$ with $\phi(t)=t^{p}$. Let $X_{1}$, …, $X_{N}$ be independent random vectors distributed as $X$. It is known (, , see also for a quantitative version) that when $N$ is proportional to $n$ and in the absence of fourth moment, $M^{2}/n\to\infty$ as $n\to\infty$. Hence, bounds for $S$ involving the term $M^{2}/n$ like the bound (5) are of interest only for $p\geq 4$. We don’t know if it holds in the case $p=4$.

The main novelty of our proof is a delicate analysis of the behavior of norms of submatrices, namely quantities $A_{k}$ and $B_{k}$, $k\leq N$, defined in (6) below. This analysis is done in Theorem 2.1, which is in the heart of the technical part of the paper and it will be presented in the next section. The estimates for $B_{k}$ are responsible for RIP, Theorem 1.1, while the estimates for $A_{k}$ are responsible for KLS problem, Theorem 1.2.

As usual in this paper $C$, $C_{0}$, $C_{1}$, …, $c$, $c_{0}$, $c_{1}$, … always denote absolute positive constants whose values may vary from line to line.

The paper is organized as follows. In Section 2, we formulate the main technical result. For the reader convenience, we postpone its proof till Section 5. In Section 3, we discuss the results on RIP. The fully detailed formulation of the main result in this direction is Theorem 3.1, while Theorem 1.1 is its very simplified corollary. In Section 4, we prove Theorem 1.2 as a consequence of Theorem 4.5. The case $p>8$ and the exponential cases are proved in Theorem 4.7 using the same argument. Symmetrization and formulas for sums of the $k$ smallest order statistics of independent non-negative random variables with heavy tails allow to reduce the problem on hand to estimates for $A_{k}$. In the last Section 6, we discuss optimality of the results.

An earlier version of the main results of this paper was announced in .

Acknowledgment. A part of this research was performed while the authors were visiting at several universities. Namely, the first named author visited University of Alberta at Edmonton in April 2013 and the second and the fourth named author visited University Paris-Est in June 2013 and in June 2014. The authors would like to thank these universities for their support and hospitality.

Norms of submatrices

A standard volume argument implies that for every integer $n$ and for every $\varepsilon\in(0,1)$ there exists an $\varepsilon$-net $\Lambda\subset B_{2}^{n}$ of $B_{2}^{n}$ of cardinality not exceeding $(1+2/\varepsilon)^{n}$; that is, for every $x\in B_{2}^{n}$, $\min_{y\in\Lambda}|x-y|<\varepsilon$. In particular, if $\varepsilon\leq 1/2$ then the cardinality of $\Lambda$ is not larger than $(2.5/\varepsilon)^{n}$.

By $\cal{M}$ we denote the class of increasing functions $\phi:[0,\infty)\to[0,\infty)$ such that the function $\ln\phi\left(1/\sqrt{x}\right)$ is convex on $(0,\infty)$. The examples of such functions considered in this paper are $\phi(x)=x^{p}$ for some $p>0$ and $\phi(x)=(1/2)\exp(x^{\alpha})$ for some $\alpha>0$.

Recall that the hypothesis ${\bf H}(\phi)$ has been defined in the introduction by (1). Note that this hypothesis is satisfied if

We would like to note that $A_{k}$ is the supremum of norms of submatrices consisting of $k$ columns of $A$, while $B_{k}$ plays a crucial role for RIP estimates. We provide more details on the role of $A_{k}$ and $B_{k}$ in the next section.

Recall also a notation from the introduction

We formulate now the main technical result, Theorem 2.1, which is the key result for both bounds for $A_{k}$ and for $B_{k}$. The role of $A_{k}$ and $B_{k}$ in RIP estimates will be explained in the next section. We postpone the proof to Section 5.

Case 1. $\phi(x)=x^{p}$. We assume that $\lambda\leq p$ and we let $C_{\phi}=e^{4}$,

Case 2. $\phi(x)=(1/2)\exp(x^{\alpha})$. We assume that $\lambda\geq 2$ and we let $C_{\phi}=C^{1/\alpha}$, where $C$ is an absolute positive constant,

In both cases we also assume that $\beta<1/32$. Then with probability at least $1-\sqrt{\beta}$ one has

We would like to emphasize that $A_{k}$ and $B_{k}$ are of different nature. In particular, Theorem 2.1 in the case $\phi(x)=x^{p}$ has to be applied with different choices of the parameter $\sigma$. We summarize those choices in the following remark.

Remark. In the case $\phi(x)=x^{p}$ we will use the following two choices for $\sigma$: 1. Choosing $\sigma=p/4$ and assuming $p>8$ we get

2. Choosing $\sigma=2+\varepsilon$ with $\varepsilon\leq\min\{1,(p-4)/4\}$, we get

Remarks on optimality. 1. The case $\phi(x)=x^{p}$, $p>4$. Let $\tau\geq 1$, $N\geq(64C_{2}(\sigma,\lambda))^{1/\lambda}$ and $t=(64N^{2}C_{3}(\sigma,\lambda,p))^{1/p}$. Then $\beta\leq 1/32$ and $\sqrt{tM}\leq C_{4}(\sigma,\lambda,p)(M+M_{1})$. Hence with probability larger than 3/4 we have

In Proposition 6.5 below we show that there exist independent random vectors $X_{i}$’s satisfying the conditions of Theorem 2.1 with $\tau=1$ and such that

with probability at least 1/2. Note that $M=A_{1}\leq A_{k}$. Therefore

2. The case $\phi(x)=(1/2)\exp(x^{\alpha})$, $\alpha\in$. Let $\lambda=2$ and $t=(\ln N)^{1/\alpha}$. Then $\beta\leq 1/32$. Hence with probability larger than 3/4 we have

In Proposition 6.7 below we show that there exist independent random vectors $X_{i}$’s satisfying the conditions of Theorem 2.1 with $\tau$ bounded by an absolute constant and such that

with probability at least 1/2. Using again that $M=A_{1}\leq A_{k}$ we observe

Restricted Isometry Property

Let $T$ be an $n\times N$ matrix and let $1\leq m\leq N$. The $m$-th isometry constant of $T$ is defined as the smallest number $\delta_{m}=\delta_{m}(T)$ so that

Thus, in order to have a good bound on $\delta_{m}\left({A/\sqrt{n}}\right)$ we require a strong concentration of each $|X_{i}|$ around $\sqrt{n}$ and we need to estimate $B_{m}$.

To control the concentration of $|X_{i}|$ we consider the function $P(\theta)$, defined in the introduction by (2). Note that this function estimates the concentration of the maximum. Therefore, when it is small, we have much better concentration of each $|X_{i}|$ around $\sqrt{n}$.

We are now ready to state the main result about RIP. Theorem 1.1, announced in the introduction, is a very simplified form of it.

Case 1. $\phi(x)=x^{p}$. Let $\varepsilon\leq\min\{1,(p-4)/4\}$. Assume that

$c$ and $C$ are absolute positive constants.

Case 2. $\phi(x)=(1/2)\exp(x^{\alpha})$. Assume that

where $c$ and $C$ are absolute positive constants.

Remarks. 1. Note that for instance in case 1, the constraint $N\leq c(\theta,\varepsilon,\tau,p)n^{p/4}$ is not important because for $N\gg n^{p/4}$ one has

Moreover, Proposition 6.6 below shows that for $q>p>4$ there are independent random vectors $X_{i}$’s satisfying hypothesis $\mbox{\bf H}(\phi)$ with parameter $\tau=\tau(p,q)$ and such that for $\theta=1/2$, $N\leq C(p,q)n^{p/4}\left(\ln(2N/n)\right)^{-p/2}$ one can’t get better estimate than

Proof. We first pass to the subset $\Omega_{0}$ of our initial probability space where

Note that by (2) the probability of this event is at least $1-P(\theta/2)$ and if this event occurs then we also have

We will apply Theorem 2.1 with $k=m$, $t=\theta\sqrt{n}/(100C_{\phi})$, where $C_{\phi}$ is the constant from Theorem 2.1. Additionally we assume that $\beta\leq 2^{-9}\theta^{2}$ and $M_{1}\leq t$. Then with probability at least $1-\sqrt{\beta}-P(\theta/2)$ we have

Together with (10) this proves $\delta_{m}(A/\sqrt{n})\leq\theta$. Thus we only need to check when the estimates for $\beta$ and $M_{1}$ are satisfied.

Case 1. $\phi(x)=x^{p}$. We start by proving the estimate for $M_{1}$. We let $\sigma=2+\varepsilon$, $\varepsilon\leq\min\{1,(p-4)/4\}$ and $\lambda=2$. Then by Theorem 2.1 (see also the Remark following it), for some absolute constant $C$ we have

Therefore the estimate $M_{1}\leq c\,\theta\sqrt{n}$ with $c=1/(100e^{4})$ is satisfied provided that

with $C(\theta,\varepsilon,p)$ defined in (11) and the absolute constants properly adjusted.

Now we estimate the probability. From Theorem 2.1 (and the Remark following it), with our choice of $t$ and $\lambda$ we have

provided that $2^{8}/(\varepsilon\,\theta\tau)\leq N\leq 2^{-4}\theta\sqrt{\tau}\left(0.4c\,\varepsilon\,\theta\right)^{p/2}\,n^{p/4}$. This completes the proof of the first case.

Case 2. $\phi(x)=(1/2)\exp(x^{\alpha})$. As in the first case we start with the condition $M_{1}\leq t$. We choose $\lambda=4$. Note that $N\tau/m\geq 2^{1/\alpha}$ as $N\tau\geq 2^{1/\alpha}n$. Therefore for some absolute constant $C$,

Therefore the condition $M_{1}\leq t$ is satisfied provided that

for an absolute positive constant $C_{1}$. This justifies the choice of $m$.

Now we estimate the probability. From Theorem 2.1 with our choice of $t$ and $\lambda$ we have

provided that $4/(\theta\tau)\leq N\leq 2^{-5}\theta\sqrt{\tau}\exp\left(c\left(\theta\sqrt{n}\right)^{\alpha}\right)$. This completes the proof.

Approximating the covariance matrix

We start with the following $\varepsilon$-net argument for bilinear forms, which will be used below.

Let $m\geq 1$ be an integer and $T$ be an $m\times m$ matrix. Let $\varepsilon\in(0,1/2)$ and ${\cal{N}}\subset B_{2}^{m}$ be an $\varepsilon$-net of $B_{2}^{m}$ (in the Euclidean metric). Then

Therefore $|\langle Sx,x\rangle|\leq|\langle Sy,y\rangle|+2|x-y|\|S\|$. Since $S$ is symmetric, we have

Now we can prove the following technical lemma, which emphasizes the role of the parameter $A_{k}$ in estimates of the distance between the covariance matrix and the empirical one. This role was first recognized in and . Other versions of the lemma appeared in . Its proof uses the symmetrization method as in .

or $\phi(t)=(1/2)\exp(t^{\alpha})$ in which case we assume that $X_{i}$’s satisfy hypothesis $\mbox{\bf H}(\phi)$ with parameter $\tau$ and set $C_{\phi}=8\sqrt{C_{\alpha}N\tau}$, where $C_{\alpha}=(8/\alpha)\,\Gamma(4/\alpha)$, $\Gamma(\cdot)$ is the Gamma function. Then, for every $A,Z>0$,

The term involving $Z$ in the upper bound will be bounded later using general estimates in Lemma 4.4. Thus Lemma 4.2 clearly stresses the fact that in order to estimate the distance between the covariance matrix and the empirical one, it will remain to estimate $A_{k}$, to get $A$.

where $(s_{i}^{*})_{i}$ denotes a non-increasing rearrangement of $(|s_{i}|)_{i}$.

Also, it is easy to check using (6) that for any $a\in S^{n-1}$ and any $I\subset\{1,\ldots,N\}$ with $|I|\leq k$, $\sum_{i\in I}\langle X_{i},a\rangle^{2}\leq A_{k}^{2}$.

Note that $\sum_{i=1}^{N}\varepsilon_{i}\langle X_{i},a\rangle^{2}=\sum_{i\in E}\langle X_{i},a\rangle^{2}-\sum_{i\in E^{c}}^{N}\langle X_{i},a\rangle^{2}$ for some set $E\subset\{1,...,N\}$ and we can apply a union bound argument indexed by $\Lambda$ together with Lemma 4.1. We get that

Using again a union bound argument and the triangle inequality to estimate the probability that the $(X_{i})$ satisfy

and choosing $t=3\sqrt{n}$ (so that $2\cdot 9^{n}\exp(-t^{2}/2)\leq e^{-n}$) we get that

Now we transfer the result from Bernoulli random variables to centered random variables (see , Section 6.1). By the triangle inequality, for every $s,t>0$, one has

To conclude the proof it is enough to find $s$ so that $m(s)\geq 1/2$. To this end we will use a general Lemma 4.3 (below). First consider $\phi(t)=t^{p}$. For $a\in S^{n-1}$, set $Z_{i}=|\langle X_{i},a\rangle|^{2}/\tau^{2/p}$ and $q=p/2$. Then by Lemma 4.3 we have $m(s)\geq 1/2$ for $s=4\tau^{2/p}N^{1/r}$ and $r=\min(p/2,2)$. Now consider $\phi(t)=(1/2)\exp(t^{\alpha})$. Then for every $a\in S^{n-1}$ and every $i\leq N$ using hypothesis $\mbox{\bf H}(\phi)$ we have

It remains to prove the following general lemma. For convenience of the argument above, we formulate this lemma using two powers $q$ and $r$ rather than just one.

Let $q\geq 1$ and $Z_{1},\dots,Z_{N}$ be independent non-negative random variables satisfying

and since $z\geq 4N^{1/r}$, this implies the required estimate.

The following lemma is standard (cf. Lemma 5.8 in , which however contains a misprint).

Let $q>0$ and let $Z_{1},\dots,Z_{N}$ be independent non-negative random variables satisfying

Then, for every $s>1$, with probability larger than $1-s^{-k}$, one has

Proof: Assume first that $0<q\leq 1$. It is clear that

where we used the inequality $\binom{N}{i}\leq(Ne/i)^{i}$. Thus if $eNt^{-q}\leq 1$, then

with probability larger than $1-(2eN/t^{q})^{k}$. Choosing $t=(2esN)^{1/q}$, we obtain the estimate in the case $0<q<1$.

with probability larger than $1-(2eN/t)^{k}$. To obtain the desire estimate choose $t=2esN$.

with probability larger than $(Net^{-q})^{k}+(2Net^{-q})^{k}$. Thus, taking $t=(4esN)^{1/q}$, we obtain

We are now ready to tackle the problem of approximating the covariance matrix by the empirical covariance matrices, under hypothesis $H(\phi)$ with $\phi(t)=t^{p}$. As our proof works for all $p>4$, we also include the case $p>8$ originally solved in (under additional assumption on $\max_{i}|X_{i}|$). For clarity, we split the result into two theorems. The case $4<p\leq 8$ has been stated as Theorem 1.2 in the Introduction.

We also would like to mention that we don’t know how sharp the power $\gamma/p$ appearing in the bound below is. In particular, it is not clear if it can be improved to $1/2$.

An immediate consequence of this theorem is the following corollary.

Under assumptions of Theorem 4.7, assuming additionally that $\max_{i}|X_{i}|^{2}\leq Cn^{\gamma/p}N^{1-\gamma/p}$ with high probability, we have with high probability

where $C$ and $C_{1}$ are absolute positive constants.

and in the case $\phi(t)=(1/2)\exp(t^{\alpha})$, we assume $N\geq(4/\alpha)^{8/\alpha}$ and define

Then in both cases with probability larger than $1-p_{0}$ one has

As our argument works in all cases we prove both theorems together.

Proof of Theorems 4.5 and 4.7. We first consider the case $\phi=t^{p}$. Note that in this case

Thus, by Lemma 4.2 it is enough to estimate $A^{2}+\sqrt{n}\,Z+\sqrt{p/(p-4)}\,\sqrt{N}$ and the corresponding probabilities. We choose $k=n$.

In the case $\phi=t^{p}$ we apply Lemma 4.4 with $Z_{i}=|\left\langle X_{i},a\right\rangle|^{4}$, $i\leq N$, $q=p/4>1$ and $s=9e$. It gives

Now we estimate $A_{n}$, using Theorem 2.1.

Case 1: $4<p\leq 8$ (Theorem 4.5). We apply Theorem 2.1 (and the Remark following it), with $\sigma=2+\varepsilon$, where $\varepsilon<(p-4)/4$, $\lambda=3$ and $t=3N^{2/p}n^{\delta}$ for $\delta=1/2-2/p$. Then

provided that $n$ is large enough. Then, using $\delta=1/2-2/p$, we obtain

Combining all estimates and noticing that $(p-4)^{-\gamma}<2$, we obtain that the desired estimate holds with probability

Case 2: $p>8$ (Theorem 4.7). In this case we apply Theorem 2.1 (see also the Remark following it), with $\sigma=p/4$, $\lambda=(p-4)/2$, $t=3(nN)^{1/4}$. Then $M_{1}\leq C\sqrt{n}(N/n)^{1/4}$ and

provided that $N$ is large enough. Thus with probability at least $1-\sqrt{\beta}$ we have

Combining all estimates we obtain that the desired estimate holds with probability

Case 3: $\phi(t)=(1/2)\exp(t^{\alpha})$ (Theorem 4.7). As in Case 2 we apply Lemma 4.2. It implies that it is enough to estimate $A^{2}+\sqrt{n}\,Z+\sqrt{C(\alpha)N}$, with $C(\alpha)$ from Lemma 4.2, and the corresponding probabilities. A direct calculations show that in this case we have for $C_{\alpha}^{\prime}=(4/\alpha)^{1/\alpha}$ and $t>1$,

We apply Lemma 4.4 with $Z_{i}=|\left\langle X_{i},a\right\rangle|^{4}/\sqrt{C_{\alpha}^{\prime}}$, $i\leq N$, $q=2$ and $s=9e$. It gives

To estimate $A_{n}$ we use Theorem 2.1 with $t=(nN)^{1/4}$ and

Then for absolute positive constants $C$, $C^{\prime}$,

provided that $N\geq(4/\alpha)^{8/\alpha}$. Thus with probability at least $1-\sqrt{\beta}$ we have

where $C^{\prime\prime}$ and $C^{\prime\prime\prime}$ are absolute positive constants. This together with the estimate for $Z$ completes the proof (note that $C(\alpha)\leq C(2/\alpha)^{5/\alpha}$).

The proof of Theorem 2.1

In this section we prove the main technical result of this paper, Theorem 2.1, which establishes upper bounds for norms of submatrices of random matrices with independent columns. Recall that for $1\leq k\leq N$ the parameters $A_{k}$ and $B_{k}$ are defined by (6).

with the convention that $\sum_{i\in\emptyset}a_{i}X_{i}=0$.

The following two lemmas are in the spirit of Lemma 2.3 in . Recall that $(s_{i}^{*})_{i}$ denotes a non-increasing rearrangement of $(|s_{i}|)_{i}$.

If $|F_{1}|<k/2$ then $|F_{2}|\geq k/2$ and we proceed similarly interchanging the role of $F_{1}$ and $F_{2}$ and obtaining

where $\{U_{i}\}_{i}$ denotes either $\{V_{i}\}_{i}$ or $\{W_{i}\}_{i}$, and $\gamma_{0}=\gamma-1/2$.

Remarks. 1. Taking $\phi(t)=t^{p}$ for some $p>0$, we obtain that if

Note that the condition (13) is satisfied if

2. Taking $\phi=(1/2)\exp(x^{\alpha})$ for some $\alpha>0$, we obtain that if

Note that the condition (15) is satisfied if

Proof. Without loss of generality assume that $U_{i}=V_{i}$ for every $i$. Then

Let $F_{1}={\rm supp}(a)\cap I$ and $F_{2}={\rm supp}(a)\cap I^{c}$. Note that $V_{m}^{*}>s$ means that there exists a set $F\subset F_{1}$ of cardinality $m$ such that $V_{i}>s$ for every $i\in F$ (if cardinality of $F_{1}$ is smaller than $m$, the estimate for probability is trivial). Since $|F_{1}|\leq k$, we obtain

Denote $Z:=\sum_{j\in F_{2}}a_{j}X_{j}$. Since $|a|\leq 1$ then $|Z|\leq A_{k}$, and note that the $X_{i}$’s, $i\in F_{1}$ are independent of $Z$. Thus, conditioning on $Z$ we obtain

2 Estimates for off-diagonal of bilinear forms

For $1\leq k\leq N$ and $I\subset\{1,...,N\}$ we define $Q_{k}(I)$ by

Lemmas 5.1, 5.2 and 4.1 imply the following proposition.

Proof. For every $E\subset{1,...,N}$ with $|E|=k$ let ${\cal{N}}_{E}$ be an $\varepsilon$-net in $B_{2}^{E}$ of cardinality at most $\left(2.5/\varepsilon\right)^{k}$. Let $\cal{N}$ denote the union of ${\cal{N}}_{E}$’s. Lemma 4.1 yields

Therefore, applying Lemmas 5.1 and 5.2, we observe that the event

Finally, using the fact that $X_{i}$ is independent of $X_{j}$ for $i\neq j$, $|X_{j}|\leq M_{1}$ for every $j\in I^{c}$, and using the tail behavior of variables $\left\langle X_{i},z\right\rangle$, we obtain

Case 1. Let $p>4$ and $\phi(x)=x^{p}$. Let $\sigma\in(2,p/2)$. Then

Case 2. Assume that $\phi(x)=(1/2)\exp(x^{\alpha})$ for some $\alpha>0$. Then for every $t>0$,

Proof. Let $\gamma\in(1/2,1)$ to be chosen later. For integers $s\geq 0$ denote $k_{0}=k$, $k_{s+1}=[\gamma k_{s}]$. Clearly, the sequence is strictly decreasing whenever $k_{s}\geq 1$ and $k_{s}\leq\gamma^{s}k$. Assume that $k\geq 1/(1-\gamma)$. Define $m$ to be the largest integer $m\geq 1$ such that $k_{m-1}\geq 1/(1-\gamma).$ Note that $\gamma k_{m-1}\geq 1$. Therefore

By Proposition 5.3 we observe that for every positive $t_{s}$ and $\varepsilon_{s}\in(0,1/2)$, $0\leq s\leq m$, the event

Let $\varepsilon>0$ and a positive decreasing sequence $(\varepsilon_{s})_{s}$ be chosen later and set

where $\phi^{-1}(s)=\min\{t\geq 0\,:\,\phi(t)\geq s\}$.

We start estimating $Q_{k}(I)$. Since $\ln(1-x)\geq-2x$ on $(0,3/4]$, we observe that for $\varepsilon_{s}<3/8$,

Thus by (20) and by our choice of $t_{s}$,

Since $k_{m-1}\geq 1/(1-\gamma)$, this probability is larger than

Thus it is enough to choose appropriately $\varepsilon_{s}$ and to estimate $\sum_{s=0}^{m-1}t_{s}$, $Q_{k_{m}}(I)$ and $\sum_{s=0}^{m-1}\varepsilon_{s}^{k_{s}\varepsilon}$. We distinguish two cases for $\phi$.

Case 1: $\phi(x)=x^{p}$. In this case we choose $\varepsilon_{s}=(s+2)^{-2}$ so that

Choose $\varepsilon=\lambda(1-\gamma)$. Since $\lambda\geq 1$ and $k_{m-1}\geq 1/(1-\gamma)$, we have $2k_{m-1}\varepsilon\geq 2\varepsilon/(1-\gamma)=2\lambda$ and

Using again $k_{m-1}\geq(1-\gamma)^{-1}$, we conclude that the probability in (22) is larger than

Now we estimate $\sum_{s=0}^{m-1}t_{s}$. We have

Recall that $\gamma>1/2$, $k_{m-1}\geq 1/(1-\gamma)$, so that $(1-\gamma)k_{s}+1\leq 2(1-\gamma)k_{s}$ for $s\leq m-1$. Thus

Let $b=(1+\varepsilon)/\gamma_{0}p$. Assume that $b<1/2$. Since $k_{s}\leq\gamma^{s}k$, we have

As $2b\leq 1$, $\Gamma(1+2b)\leq 1$. Using also that $\ln(1/\gamma)\geq 1-\gamma$, we observe that the previous quantity does not exceed

To conclude this computation, we choose the parameter

Note that $\gamma\in(1/2,1)$ as required, since $\lambda\geq 1$ and $2<\sigma$. With such a choice of $\gamma$, we have $b=\sigma/p<1/2$, since $\sigma<p/2$. Thus from (25) and (23)

Finally, to estimate $Q_{k_{m}}$, we note that

Case 2: $\phi(x)=(1/2)\exp(x^{\alpha})$. In this case we choose $\gamma=2/3$, so that $\gamma_{0}=1/6$. As before we assume that $k\geq 1/(1-\gamma)=3$ (otherwise $Q_{k}(I)\leq Q_{2}(I)$). By (19) we have $k_{m}<3$, hence, by (21)

Observe that since $k_{s}\leq\gamma^{s}k$ and $\gamma=2/3$, one has

By (19) we have $k_{m}<3\leq k_{m-1}$, hence,

By the choice of $\varepsilon_{s}$ we obtain

Since $3^{-s}k\leq k_{s}\leq(2/3)^{s}k$, we observe

where $C_{1}$ is an absolute positive constant and $\Gamma$ is the Gamma function. This together with (27) implies that

where $C_{2}$ is an absolute positive constant.

Now we estimate the probability. By the choice of $k_{s}$ we have

Since $k_{s}\geq k_{m-1}\geq 1/(1-\gamma)$ and $s+2\leq m+1$ for every $s\leq m-1$, we get that

Since $m$ is chosen such that $1/(1-\gamma)\leq k_{m-1}\leq(2/3)^{m-1}k$, we observe that

which shows that probability in (22) is at least

We are now ready to pass to the proof of Theorem 2.1. To prove the theorem we need two simple lemmas.

Then there exists $W\subset\Omega_{2}$ such that

Proof of Theorem 2.1. From Lemma 5.6 we have

Let $I\subset\{1,\dots,N\}$ be fixed. Proposition 5.4 implies

Since $A_{k}^{2}\leq\max_{i\leq N}|X_{i}|^{2}+B_{k}^{2},$ we have

Using $\sqrt{u^{2}+v^{2}}\leq u+v$, and denoting $\gamma=(1-4\sqrt{\beta})^{-1}$ (recall $M=\max_{i\leq N}|X_{i}|$) we obtain

which proves the estimate for $A_{k}$. Plugging this into (30), we also observe

Optimality

In this section we discuss optimality of estimates in Theorems 2.1 and 3.1. In Propositions 6.5, 6.6 and 6.7 we will prove results justifying remarks on optimality following these theorems.

To obtain the lower estimates on $A_{m}$ we use the following observation.

Let $A=(X_{ij})_{{i\leq n},{j\leq N}}$ be an $n\times N$ matrix with i.i.d. entries. Then

To evaluate RIP, we will use the following simple observation.

Let $n\leq N$ and $m\leq N$. Let $A$ be an $n\times N$ random matrix satisfying

Assume also that $A$ satisfies RIP${}_{m}(\delta)$ for some $\delta<1$ with probability greater than $1/2$. Then

Proof. As $A$ satisfies RIP${}_{m}(\delta)$ for some $\delta<1$ with probability greater than $1/2$, then clearly

with probability greater than $1/2$. Therefore, with positive probability one has

Note that originally the Rosenthal inequality was proved for symmetric random variables, but using standard symmetrization argument (i.e., passing from random variables $\xi_{i}$’s to $(\xi_{i}-\xi_{i}^{\prime})$’s, where $(\xi_{i}^{\prime})$’s have the same distribution and are independent), one can pass to centered random variables.

where $M_{q}:=\max\left\{\|a\|_{2}\|\xi_{1}\|_{2},\|a\|_{q}\|\xi_{1}\|_{q}\right\}$.

The following is an almost immediate corollary of Rosenthal’s inequality. It should be compared with Proposition 1.3 of .

Let $p>4$. Let $\xi$ be a random variable of variance one and with a finite $p$-th moment. Let $\xi_{ij}$, $i\leq n$, $j\leq N$ be i.i.d. random variables distributed as $\xi$. Then for every $t>0$,

where $C$ is a positive absolute constant.

Proof. Let $\xi_{1}$, …, $\xi_{n}$ be i.i.d. random variables distributed as $\xi$. We apply Rosenthal’s inequality to random variables $(\xi_{i}^{2}-1)$ with $q=p/2$ and $a=(1,1,...,1)$. Then

where $C_{p}=Cp/\ln p$ for an absolute positive constant $C$. Using Chebyshev’s inequality we observe

As is mentioned in remarks on optimality following Theorem 2.1 the next proposition gives a lower bound for $A_{m}$ to be compared with Case 1 of Theorem 2.1.

where $C$ is an absolute positive constant.

Proof. Let $\lambda\geq 1$ to be set later and let us put

Finally, to satisfy condition (33), we pass from matrix $A$ to $A^{\prime}=A/c_{p}=(X_{ij}/c_{p})_{ij}$, where $c_{p}\leq Cp/\ln p$ is a constant in Rosenthal’s inequality (32). By Rosenthal’s inequality, the sequence of columns of $A^{\prime}$ satisfies the condition (33).

The next proposition gives an upper bound on the size of sparsity $m$ in order to satisfy RIP under condition of Case 1 of Theorem 3.1 (see Remark 3 following this theorem).

Let $q>p>2$, $n\leq N$ and $m\leq N$. There exist an absolute positive constant $C$, an $n\times N$ matrix $A$, whose columns $X_{1},...,X_{N}$ are independent random vectors satisfying

Assume that $A$ satisfies RIP${}_{m}(\delta)$ for some $\delta<1$ with probability greater than $1/2$. Then

Consider the random variable $\xi(\omega)=\omega$ with respect to the density $f$ and let $(X_{ij})_{ij}$ be i.i.d. copies of $\xi/a_{2}$. Clearly,

Then Rosenthal’s inequality (32) implies the condition (34) and Corollary 6.4 implies (35).

and we complete the proof applying Lemma 6.2.

The next proposition shows the optimality (up to absolute constants) of the sparsity parameter in Case 2 of Theorem 3.1 (see Remark 4 following this theorem) as well as optimality of bounds for $A_{m}$ in Case 2 of Theorem 2.1 (see remarks on optimality following this theorem).

There exist absolute positive constants $c$, $C$ such that the following holds. Let $\alpha\in$, $1\leq m\leq N/2$ and $n$ satisfies $N\leq\exp(cn^{\alpha/2})$. There exists an $n\times N$ matrix $A$, whose columns $X_{1},...,X_{N}$ are independent random vectors satisfying

Additionally, if $n\leq N$ and if $A$ satisfies RIP${}_{m}(\delta)$ for some $\delta<1$ with probability greater than $1/2$, then

Finally, the “additionally” part follows by Lemma 6.2.

References