Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries

Introduction

In this paper, we consider random matrices $A$ satisfying

We are concerned with the following question: how many translates of a Euclidean ball $\sqrt{n}B_{2}^{n}$ (or its constant multiple) are needed to cover the random ellipsoid $A(B_{2}^{n})$? Being geometrically natural, this problem, as we will see later, has an application to studying invertibility properties of the matrix $A$.

In particular, the above theorem implies the following more elegant

For any $\delta\in(0,1/4]$ and $n\geq\frac{1}{4\delta}$ there exists a non-random subset ${\mathcal{N}}\subset B_{2}^{n}$ of cardinality at most $\exp(13n\delta\ln\frac{2e}{\delta})$ such that for any $n\times n$ matrix $A$ satisfying (* ‣ 1), we have

for some universal constant $C^{\prime}>0$.

Both results have geometric interpretation in terms of covering numbers. Recall that for two subsets $S$ and $K$ of a vector space the covering number ${\bf N}(S,K)$ is defined as the smallest number of parallel translates of $K$ sufficient to cover $S$. By Theorem A, {\bf N}(A(B_{2}^{n}),\frac{C\sqrt{n}}{\delta}B_{2}^{n})\leq\exp\bigl{(}13\delta n\ln\frac{2e}{\delta}\bigr{)} with probability at least $1-4\exp(-\delta n/8)$.

A crucial feature of these results is that the set $\mathcal{C}$ in the theorem is non-random. Moreover, $\mathcal{C}$ (as well as the set ${\mathcal{N}}$ from Corollary A) provides a “universal” covering which is independent of the distribution of the entries of $A$.

Finally, compared to Corollary A, the statement of Theorem A is more flexible as it enables us to choose the “anchor” points within the parallelepipeds when constructing corresponding $\varepsilon$-net (this matter is covered in detail at the beginning of Section 5).

Let us briefly describe the main idea of the proof. The collection $\mathcal{C}$ of parallelepipeds is constructed using a special subset ${\mathcal{D}}$ of diagonal operators with diagonal elements in the interval $(0,1]$. Namely, we define ${\mathcal{D}}$ as the set of all diagonal operators with diagonal entries in $\{1\}\cup\{2^{-2^{k}}\}_{k=0}^{\infty}$ and with determinants bounded from below by $\exp(-\delta n)$. Then, for every operator $D$ from ${\mathcal{D}}$, we take a covering of the ball $B_{2}^{n}$ by appropriate translates of parallelepiped $D(L^{\prime\prime}n^{-1/2}B_{\infty}^{n})$ (for some $L^{\prime\prime}=L^{\prime\prime}(\delta)$), and let $\mathcal{C}$ be the union of such coverings over ${\mathcal{D}}$. It turns out that Theorem A follows almost immediately from the following relation:

In Section 3, we show that (1) holds true under condition (* ‣ 1); see Theorem 3.1. Geometrically, this property means that it is possible to construct a random parallelepiped $P\subset^{n}$ with sides parallel to the standard coordinate axes, such that ${\rm Vol}(P)\geq\exp(-\delta n)$ and $A$ maps $P$ inside the Euclidean ball $\frac{Cn}{\sqrt{\delta}}B_{2}^{n}$ with probability at least $1-4\exp(-\delta n/8)$. Note that parallelepiped $P$ will be “narrow” along directions $w\in S^{n-1}$ for which $\|Aw\|$ is large.

As we already mentioned above, Theorem A has a direct application to the problem of obtaining quantitative (non-asymptotic) estimates for the smallest singular value of $A$. Recall that, given an $m\times n$ ($m\geq n$) matrix $M$, its smallest singular value can be defined as $s_{n}(M)=\inf\limits_{y\in S^{n-1}}\|My\|$. An argument based on Theorem A and results of Rudelson and Vershynin from , yields:

Let us put Theorem B in the context of known results.

Convergence of (appropriately normalized) smallest singular values for a sequence of random rectangular matrices with i.i.d. entries and growing dimensions was established by Bai and Yin (see also , where the result is proved under optimal moment assumptions). For non-asymptotic results in this direction, we refer the reader to papers for the case of i.i.d. entries (see also where no moment conditions are assumed); for log-concave distributions of rows and for more general isotropic distributions. We refer to surveys (see also ) for more information.

where $L>0$ and $u\in(0,1)$ depend only on the subgaussian moment of $a_{ij}$’s. Note that Theorem B gives an estimate of exactly the same form, but for the matrices with heavy-tailed entries.

The idea of the proof of Theorem B can be described as follows. Denote by $A^{\prime}$ the transpose of the first $n-1$ columns of $A$. A principal component of the proof of is an analysis of the arithmetic structure of null vectors of $A^{\prime}$, which is described with the help of the notion of the least common denominator (LCD). To show that null vectors of $A^{\prime}$ typically have an exponentially large LCD, the authors of consider subsets $S$ of the unit sphere corresponding to vectors with small LCD, and show that $\inf\limits_{x\in S}\|A^{\prime}x\|>0$ with a large probability. For this, they use the standard $\varepsilon$-net argument, when the infimum is estimated by taking a Euclidean $\varepsilon$-net ${\mathcal{N}}$ on $S$ and applying relation $\inf\limits_{x\in S}\|A^{\prime}x\|\geq\inf\limits_{y\in{\mathcal{N}}}\|A^{\prime}y\|-\varepsilon\|A^{\prime}\|_{2\to 2}$ together with the estimate $\|A^{\prime}\|_{2\to 2}\leq C\sqrt{n}$ which holds with probability very close to one under the subgaussian moment assumptions on the entries. In our setting, the principal difficulty consists in the fact that the condition (* ‣ 1) does not guarantee a good upper bound for the operator norm $\|A^{\prime}\|_{2\to 2}$. To deal with this fundamental issue, we “refine” the nets constructed in by applying Theorem A. Indeed, it can be shown that Theorem A implies that, given an $\varepsilon$-net ${\mathcal{N}}$ on $S$, it is possible to construct a subset $\widetilde{\mathcal{N}}\subset S$ of cardinality at most \exp\bigl{(}13\delta n\ln\frac{2e}{\delta}\bigr{)}|{\mathcal{N}}| which is an $L^{\prime}\varepsilon\sqrt{n}$-net on $S$ (for some $L^{\prime}=L^{\prime}(\delta)$) with respect to the pseudometric $d(x,y)=\|A^{\prime}(x-y)\|$ with probability at least $1-4\exp(-\delta n/8)$. Then, $\inf\limits_{x\in S}\|A^{\prime}x\|\geq\inf\limits_{y\in\widetilde{\mathcal{N}}}\|A^{\prime}y\|-L^{\prime}\varepsilon\sqrt{n}$, so the argument does not depend any more on the value of $\|A^{\prime}\|_{2\to 2}$.

The paper is organized as follows: Sections 2 and 3 are devoted to proving the main novel element of the paper — Theorem A. Then, in Section 4, we collect some results from , and, in Section 5, prove Theorem B.

Throughout the paper, by $\mathcal{D}_{n}$ we denote the set of all $n\times n$ diagonal matrices with diagonal elements belonging to the interval $(0,1]$ (we will sometimes refer to such matrices as positive diagonal contractions). Further, denote by ${\mathcal{D}}^{2}_{n}$ the set of all $n\times n$ positive diagonal contractions whose diagonal entries belong to the set $\{1\}\cup\{2^{-2^{k}}\}_{k=0}^{\infty}$. The set ${\mathcal{D}}^{2}_{n}$ can be regarded as a discretization of $\mathcal{D}_{n}$.

Proposition 2.1 is a foundation block of our paper. In Section 3, we will amplify this result (the case $p=2$) by proving its “matrix version” (Theorem 3.1). The case $p\neq 2$ in this section is considered just for completeness.

Note that a trivial definition of the diagonal operator $D=(d_{ij})$ by setting

We will need the following standard fact:

$\widetilde{Y}$ and $\widetilde{Z}$ are equidistributed with $Y$ and $Z$, respectively;

Fix for a moment $i\leq n$ and consider the distributions of $y_{i}$ and $z_{i}$. Take any $t>0$. If $\tau_{k}(y_{i})\leq t$ for all $k\geq 0$ then, obviously,

Otherwise, let $k(t):=\max\{k\geq 0:\,\tau_{k}(y_{i})\leq t\}$. Then

The next lemma provides an actual construction of the required diagonal operator.

For any $\alpha\in(0,1)$ there is $L=L(\alpha)>0$ with the following property. Let $(\tau_{k})_{k=1}^{\infty}$ be an increasing non-negative sequence satisfying $\sum_{k=1}^{\infty}\tau_{k}2^{-k}<\infty$, and let

Let $L\geq 2e$ be a number which we will determine later. Now, for each $k\geq 0$, define random variables

As building blocks of the contraction $\widetilde{D}$, let us consider random diagonal matrices $D^{(k)}$ with

In particular, for all $k$ such that $L2^{-k}n/\delta\geq 1$, using the relation $L\geq 2e$, we obtain

and for all $k$ satisfying $L2^{-k}n/\delta<1$, we get

Now, let us choose $L=L(\alpha)$ sufficiently large so that both

(we set $W_{i}=0$ for $z_{i}=-\infty$). Further, for every $z$ we let

The above statement can be “tensorized”. In what follows, we are interested only in the case $p=2$ and $\alpha=1/2$.

There is a universal constant $C>0$ with the following property. Let $A=(a_{ij})$ be an $n\times n$ random matrix satisfying (* ‣ 1), and let $\delta\in(0,1]$. Then there is a random positive contraction $D$ taking values in $\mathcal{D}_{n}$ such that the Euclidean norms of the rows of $AD$ are uniformly bounded by $\frac{C}{\sqrt{\delta}}\sqrt{n}$ everywhere on the probability space, and

Indeed, for any $i=1,2,\dots,n$, let $D_{i}$ be the positive contraction defined with respect to the $i$-th row of $A$ using Proposition 2.1 (with parameters $\alpha=1/2$, $p=2$), so that $D_{1},D_{2},\dots,D_{n}$ are jointly independent. Then the product of these contractions $D:=\prod_{i=1}^{n}D_{i}$ satisfies the required conditions. ∎

Coverings of random ellipsoids

Let $\delta\in(0,1]$ and let $A=(a_{ij})$ be an $n\times n$ random matrix satisfying (* ‣ 1). Then

where $C_{\text{\tiny\ref{parallelepiped norm estimate}}}>0$ is a universal constant.

The above theorem can be seen as a way to “regularize” the random matrix $A$ by reducing its norm while preserving its “structure”. In this connection, let us mention work where a very general problem of regularizing random matrices was discussed (see [10, Section 5.4]).

As we have mentioned in the introduction, Theorem A follows almost immediately from the above statement; we give the proof of Theorem A at the very end of the section. The section is organized as follows. First, we use $\widetilde{D}$ constructed in Remark 2.8 to verify Theorem 3.1 under an additional assumption that the entries of $A$ are symmetrically distributed (see Proposition 3.6). Then, we will apply a symmetrization procedure to prove Theorem 3.1 in full generality.

A random variable $\xi$ is subgaussian if there exists a number $K>0$ such that

To put an emphasis on the value of $K$, we will sometimes call $\xi$ $K$-subgaussian. We note that the smallest value of $K$ satisfying (3) is equivalent to the subgaussian norm of $\xi$ (see, for example, [29, Lemma 5.5]); however, the latter notion is less convenient for us and will not be used in this paper.

The next lemma is equivalent to a standard Khintchine–type inequality (see, for example, ).

Let $r_{1},r_{2},\dots,r_{n}$ be independent Rademacher random variables. Then for any vector $y\in S^{n-1}$ the random variable $\sum_{i=1}^{n}y_{i}r_{i}$ is $C_{\text{\tiny\ref{Khintchine}}}$-subgaussian, where $C_{\text{\tiny\ref{Khintchine}}}>0$ is a universal constant.

The sum of squares of subgaussian variables has good concentration properties; the bound below follows from a standard “Laplace transform” argument (see, for example, [29, Corollary 5.17]):

For any $T>0$ there is $L_{\text{\tiny\ref{sum of subgaussians}}}>0$ depending on $T$ with the following property: Let $\xi_{1},\xi_{2},\dots,\xi_{n}$ be independent centered $1$-subgaussian random variables. Then

The next proposition implies that for a random matrix $A$ satisfying (* ‣ 1) with symmetrically distributed entries and the operator $\widetilde{D}$ from Remark 2.8, the norm $\|A\widetilde{D}\|_{\infty\to 2}$ can be efficiently bounded from above as long as $\widetilde{D}$ is a Borel function of $|A|$ (here and further in the text, given a matrix $B=(b_{ij})$, by $|B|$ we shall denote the matrix $(|b_{ij}|)$).

Let $K>0$ and let $A$ be an $n\times n$ random matrix satisfying (* ‣ 1), with symmetrically distributed entries. Further, let ${\mathcal{F}}\subset\mathcal{D}_{n}$ be any countable subset. Denote by ${\mathcal{E}}$ the event

Next, as the unit cube $^{n}$ is the convex hull of its vertices $V=\{-1,1\}^{n}$, we have

Note that, given event ${\mathcal{E}}_{D}$, the entries of $Af(|A|)=AD$ are symmetrically distributed, so the distribution of $ADv$ given ${\mathcal{E}}_{D}$ is the same for any vertex $v\in V$. Fix a vertex $v$.

Then the variables $\langle\widetilde{B}Dv,e_{i}\rangle$, $i=1,2,\dots,n$, are jointly independent and, in view of Lemma 3.3 and the choice of $B$, each variable $K^{-1}n^{-1/2}\langle\widetilde{B}Dv,e_{i}\rangle$ is $C_{\text{\tiny\ref{Khintchine}}}$-subgaussian. By Lemma 3.4, there is a universal constant $C>0$ such that

Then, taking a union bound over $2^{n}$ vertices of the unit cube and using (5) and (4), we get an estimate

Let $\delta\in(0,1]$ and let $A=(a_{ij})$ be an $n\times n$ random matrix satisfying (* ‣ 1), with symmetrically distributed entries. Then

In view of the conditions on $D$ and Markov’s inequality, we have

Hence, by Proposition 3.5, taking ${\mathcal{F}}$ to be the set of all contractions from ${\mathcal{D}}^{2}_{n}$ having determinant at least $\exp(-\delta n)$, we obtain

for a universal constant $C_{\text{\tiny\ref{parallelepiped norm estimate sym}}}>0$. ∎

$S_{k}$ is a refinement of $S_{k-1}$ for all $k=1,2,\dots,n$;

For each $k\in\{1,2,\dots,n\}$ and any $Q,Q^{\prime}\in S_{k}$ such that $Q\cup Q^{\prime}$ is a subset of an element of $S_{k-1}$, there is a one-to-one mapping $\phi:Q\to Q^{\prime}$ such that $d(s,\phi(s))\leq b_{k}$ for all $s\in Q$.

In particular, the above conditions on $S_{k}$ imply that all elements of $S_{k}$ have the same cardinality.

In , the above theorem is formulated for metric spaces. It is easy to see that passing to pseudometrics does not change the picture.

Denote by $\Pi_{n}$ the set of permutations of $[n]:=\{1,2,\dots,n\}$.

Without loss of generality, we can assume that $|y_{j}|\geq|y_{j+1}|$ ($j=1,2,\dots,n-1$). Define a pseudometric $d$ on $\Pi_{n}$: for any $p,q\in\Pi_{n}$ let

Further, we define a sequence of partitions $(\Pi_{n,k})_{k=0}^{n}$ of $\Pi_{n}$: let $\Pi_{n,0}:=\{\Pi_{n}\}$ and for each $k=1,2,\dots,n$, let $\Pi_{n,k}$ consist of all subsets of $\Pi_{n}$ of the form

for all $\{i_{1},i_{2},\dots,i_{k}\}\subset[n]$.

Now, let $k\in\{1,2,\dots,n\}$ and let $Q,Q^{\prime}\in\Pi_{n,k}$ be such that $Q\cup Q^{\prime}$ is a subset of an element of $\Pi_{n,k-1}$. Note that there are numbers $i_{1},i_{2},\dots,i_{k}$, $i_{k}^{\prime}$ such that $p(j)=i_{j}$ for all $j<k$ and $p\in Q\cup Q^{\prime}$; $p(k)=i_{k}$ for all $p\in Q$ and $p(k)=i_{k}^{\prime}$ for all $p\in Q^{\prime}$. Define a one-to-one mapping $\phi:Q\to Q^{\prime}$ by

with the last inequality due to the fact that $p^{-1}(i_{k}^{\prime})\geq k$. Thus, the space $(\Pi_{n},d)$ is of length at most $4\|y\|$. Applying Theorem 3.7, we get the result. ∎

The next statement shall be used in a symmetrization argument within the proof of Theorem 3.1; we think it may be of interest in itself.

Let $B=(b_{ij})$ be a non-random $n\times n$ matrix such that the Euclidean norm of every row is at most $\sqrt{n}$ and such that

Further, let $\pi_{i}$ ($i=1,2,\dots,n$) be independent random permutations uniformly distributed on $\Pi_{n}$, and denote by $\widetilde{B}=(\widetilde{b}_{ij})$ the random $n\times n$ matrix with entries defined by

for a universal constant $C_{\text{\tiny\ref{permutation model}}}>0$.

We will show that for any $v\in\{-1,1\}^{n}$ we have

for a sufficiently large universal constant $C_{\text{\tiny\ref{permutation model}}}$ and then take the union bound over the vertices of the cube.

Fix any $v=(v_{1},v_{2},\dots,v_{n})\in\{-1,1\}^{n}$ and let $m$ be the number of ones in $(v_{1},\dots,v_{n})$. Clearly, the random variables $\langle\widetilde{B}v,e_{i}\rangle$ ($i=1,2,\dots,n$) are independent. Next, for a fixed $i$, the distribution of $\langle\widetilde{B}v,e_{i}\rangle$ coincides with that of the variable $\xi_{i}:=\sum_{j=1}^{n}v_{\pi_{i}(j)}b_{ij}$. By Lemma 3.9 and in view of the condition on the rows of $B$, we have

for some constant $\widetilde{C}>0$. Finally, observe that

Let $\widetilde{A}$ be an independent copy of $A$. Obviously

for every $i=1,2,\dots,n$. Then, in view of Markov’s inequality, each row of $\widetilde{A}$ satisfies

with probability at least $1-\delta/16>\exp(-\delta/8)$. Denote by $\widetilde{\mathcal{E}}$ the event

But $\widetilde{B}$ is equidistributed with $\widetilde{A}$ given $\widetilde{\mathcal{E}}$, so that

Clearly, $\|\widetilde{A}D\|_{\infty\to 2}\leq\|\widetilde{A}\|_{\infty\to 2}$ for any contraction $D\in\mathcal{D}_{n}$ (deterministically), so we obtain for the event {\mathcal{E}}_{1}:=\big{\{}\|\widetilde{A}D\|_{\infty\to 2}\leq C_{\text{\tiny\ref{permutation model}}}\sqrt{32/\delta}\,n\;\;\mbox{for all }D\in\mathcal{D}_{n}\big{\}}:

Next, the matrix $2^{-1/2}(A-\widetilde{A})$ has symmetrically distributed entries, and satisfies conditions of Proposition 3.6. Hence,

Conditioning on ${\mathcal{E}}_{1}$, we get

Note that, given ${\mathcal{E}}_{1}$, we have $\|AD\|_{\infty\to 2}\leq\|(A-\widetilde{A})D\|_{\infty\to 2}+C_{\text{\tiny\ref{permutation model}}}\sqrt{32/\delta}\,n$ for all contractions $D\in\mathcal{D}_{n}$. Combining this with the last formula, we obtain

Finally, since $A$ is independent from ${\mathcal{E}}_{1}$, the conditioning in the last estimate can be dropped, and we obtain the statement. ∎

To complete the proof of Theorem A, we will need two more technical lemmas:

Denote {\mathcal{S}}:=\{D\in{\mathcal{D}}^{2}_{n}:\,\det D\geq\exp(-\delta n)\bigr{\}}. Note that for any matrix $D\in{\mathcal{S}}$ and for any $k\geq 0$, the number of diagonal elements of $D$ equal to $2^{-2^{k}}$ is less than $2^{-k+1}\delta n$. Hence, the cardinality of ${\mathcal{S}}$ can be estimated as

First, note that for any $y\in B_{2}^{n}$ we have

Let $\delta\in(0,1/4]$ and $n\geq\frac{1}{4\delta}$. First, applying Lemma 3.12 with $K=1/\sqrt{\delta}$, we see that $B^{n}_{2}$ can be covered by $(2e/\delta)^{8n\delta}$ translates of the dilated cube $\frac{1}{\sqrt{n\delta}}B^{n}_{\infty}$. Let

Then, in view of Lemma 3.11, we get that $B_{\infty}^{n}$ can be covered by at most $(2e/\delta)^{4\delta n}\exp(\delta n)$ parallelepipeds in such a way that for any $y\in B_{\infty}^{n}$ and $D\in{\mathcal{Q}}$, $y$ is covered by a translate of $D(B_{\infty}^{n})$. Combining the two coverings, we get a collection $\mathcal{C}$ of parallelepipeds covering $B_{2}^{n}$ such that

and for any $y\in B_{2}^{n}$ and $D\in{\mathcal{Q}}$, the set $\mathcal{C}$ contains a translate of $D(\frac{1}{\sqrt{n\delta}}B_{\infty}^{n})$ covering $y$. Finally, applying Theorem 3.1, we get that with probability at least $1-4\exp(-\delta n/8)$ for some $D\in{\mathcal{Q}}$ we have $AD(B^{n}_{\infty})\subset\frac{C_{\text{\tiny\ref{parallelepiped norm estimate}}}n}{\sqrt{\delta}}B^{n}_{2}$, implying

(the multiple “$2$” in the last formula appears because the translation $-Ax+A(P)$ is not origin-symmetric in general). ∎

Fix $n$ and $\delta$, and let $\mathcal{C}$ be the collection of parallelepipeds defined in Theorem A. For each $P\in\mathcal{C}$, choose a point $y_{p}\in P\cap B_{2}^{n}$, and let ${\mathcal{N}}:=\{y_{P}:\,P\in\mathcal{C}\}$. Then, clearly,

and with probability at least $1-4\exp(-\delta n/8)$ for every $x\in B_{2}^{n}$ there is $y=y(x)\in{\mathcal{N}}$ with $-Ax+Ay\in\frac{C\sqrt{n}}{\delta}B_{2}^{n}$. In short,

The smallest singular value — Preliminaries

As we already mentioned in the introduction, the proof of Theorem B heavily relies on results obtained by Rudelson and Vershynin in papers and . In this section, we will state several intermediate results from those papers that we will need in Section 5 to complete our proof.

A crucial step in the proof of [20, Theorem 1.2] is a decomposition of the unit sphere into sets of “compressible” and “incompressible” vectors.

A similar decomposition of the unit sphere was already introduced in an earlier paper for the purpose of bounding the smallest singular value of rectangular matrices.

Obviously, for any $\varepsilon>0$ we have

Treatment of the compressible vectors is simpler due to the fact the the set $\operatorname{Comp}$ is “small”; we will deal with this set in the first part of Section 5. Let us remark that, unlike in the subgaussian result of , where an estimate for compressible vectors follows almost directly from an analogue of Lemma 4.9 (see below) together with a standard covering argument, in our case we will still need to use additional results (proved in Section 3) as the norm $\|A\|_{2\to 2}$ may be “too large”. We will need the following simple lemma:

For any $\theta,\rho\in(0,1]$ the set $\operatorname{Comp}=\operatorname{Comp}_{n}(\theta,\rho)$ admits a Euclidean $3\rho$-net ${\mathcal{N}}\subset\operatorname{Comp}$ of cardinality |{\mathcal{N}}|\leq(e/\theta)^{\theta n}\bigl{(}\frac{5}{\rho}\bigr{)}^{\theta n}.

Note that the definition of $\operatorname{Comp}$ implies that for any $y\in\operatorname{Comp}$ there is $y^{\prime}\in S^{n-1}$ such that $|{\rm supp}(y^{\prime})|\leq\theta n$ and $\|y-y^{\prime}\|\leq 2\rho$. Hence, it is enough to show that one can find a Euclidean $\rho$-net ${\mathcal{N}}$ on the set of $\theta n$-sparse unit vectors, with the required estimate on $|{\mathcal{N}}|$. This follows from a standard estimate on the cardinality of an optimal $\rho$-net on $S^{\lfloor\theta n\rfloor-1}$, together with a bound for the binomial coefficient ${n\choose\lfloor\theta\rfloor}$. ∎

Incompressible vectors have the important property that a significant portion of their coordinates are of order $n^{-1/2}$. In paper , this property was referred to as “incompressible vectors are spread”. For reader’s convenience, we provide a proof of this fact below (let us note once again that analogous concepts were already considered in ).

For any $\theta,\rho\in(0,1)$ and for any vector $x\in\operatorname{Incomp}_{n}(\theta,\rho)$ there is a subset of indices $\sigma(x)\subset\{1,2,\dots,n\}$ of cardinality at least $\frac{1}{2}\rho^{2}\theta n$ such that for all $i\in\sigma(x)$ we have

For every subset $I\subset\{1,2,\dots,n\}$, let $P_{I}$ be the coordinate projection onto the span of $\{e_{i}:\,i\in I\}$. Let $\sigma=\sigma(x):=\sigma_{1}\cap\sigma_{2}$, where

Since $\|x\|=1$, we have $|\sigma_{1}^{c}|\leq\theta n$, and $P_{\sigma_{1}^{c}}(x)$ is a $\theta n$-sparse vector. Then the condition that $x$ is incompressible implies $\|P_{\sigma_{1}}(x)\|=\|x-P_{\sigma_{1}^{c}}(x)\|>\rho$. Hence,

On the other hand, in view of the inclusion $\sigma(x)\subset\sigma_{1}$, we get

Together (7) and (8) imply that $|\sigma|\geq\frac{1}{2}\rho^{2}\theta n$. ∎

For incompressible vectors we will need the following basic estimate from .

Let $M$ be a random $n\times n$ matrix with column vectors $X^{1}$, $X^{2},\dots,X^{n}$, and let $H_{j}$ ($j=1,2,\dots,n$) be the span of all column vectors except the $j$-th. Then for every $\varepsilon>0$ we have

In view of independence and equi-measurability of the columns of $A$ in our model, the above proposition yields for any $\varepsilon>0$:

where $X^{*}=(X_{1}^{*},X_{2}^{*},\dots,X_{n}^{*})$ denotes a random normal unit vector to the span of the first $n-1$ columns of $A$. Obtaining small ball probability estimates for \Bigl{|}\sum\limits_{i=1}^{n}X_{i}^{*}a_{in}\Bigr{|} was a crucial ingredient of .

Given a real-valued random variable $\xi$, define its Levy concentration function is

First, let us look at some well known estimates of ${\mathcal{L}}(\xi,v)$ and then state a stronger bound from .

where $C_{\ref{t: Rogozin}}>0$ is a universal constant.

Obviously, if $\xi$ is essentially non-constant, there are $v>0$ and $u\in(0,1)$ such that ${\mathcal{L}}(\xi,v)\leq u$. The following lemma is an elementary consequence of Theorem 4.6 (see [11, Lemma 3.6] and [20, Lemma 2.6] for similar statements proved under additional moment assumptions on the variable).

Let $\xi$ be a random variable with ${\mathcal{L}}(\xi,\widetilde{v})\leq\widetilde{u}$ for some $\widetilde{v}>0$ and $\widetilde{u}\in(0,1)$. Then there are $v^{\prime}>0$ and $u^{\prime}\in(0,1)$ depending only on $\widetilde{u},\widetilde{v}$ with the following property: Let $\xi_{1},\xi_{2},\dots,\xi_{n}$ be independent copies of $\xi$. Then for any vector $y\in S^{n-1}$ we have

By Theorem 4.6, for any $y\in S^{n-1}$ and any $h\geq\max\limits_{j}|y_{j}|\widetilde{v}$, we have

Define $v^{\prime}:=\frac{\widetilde{v}\sqrt{1-\widetilde{u}}}{2C_{\ref{t: Rogozin}}}$ and consider two cases.

1) For every $j=1,\ldots,n$ we have $|y_{j}|\leq\frac{\sqrt{1-\widetilde{u}}}{2C_{\ref{t: Rogozin}}}$. Then $v^{\prime}\geq\max\limits_{j}|y_{j}|\widetilde{v}$, and we obtain from the above relation

2) There is $j_{0}$ such that $|y_{j_{0}}|>\frac{\sqrt{1-\widetilde{u}}}{2C_{\ref{t: Rogozin}}}$. Then we get

Thus, we can take $u^{\prime}:=\max(1/2,\widetilde{u})$. ∎

Let $\alpha_{1},\alpha_{2},\dots,\alpha_{n}$ be i.i.d. random variables, and let $\varepsilon_{0}>0$.

Assume that ${\mathcal{L}}(\alpha_{1},v^{\prime})\leq u^{\prime}$ for some $v^{\prime}>0$ and $u^{\prime}\in(0,1)$. Then there are $v>0$ and $u\in(0,1)$ depending only on $u^{\prime},v^{\prime}$ such that

As a consequence of Lemmas 4.7 and 4.8, we get

Let $\alpha$ be a random variable with ${\mathcal{L}}(\alpha,\widetilde{v})\leq\widetilde{u}$ for some $\widetilde{v}>0$ and $\widetilde{u}\in(0,1)$. Then there are $v>0$ and $u\in(0,1)$ depending only on $\widetilde{u},\widetilde{v}$ with the following property: Let $A$ be an $n\times n$ random matrix with i.i.d. entries equidistributed with $\alpha$. Then for any $y\in S^{n-1}$ we have

Lemma 4.9 can be compared with [11, Proposition 3.4] and [20, Corollary 2.7]; however, those statements were proved with additional assumptions on the entries of $A$.

To get a stronger estimate than the one obtained in Lemma 4.7, the following notion was developed in and (see also preceding work by Tao and Vu).

We note that later we shall choose $r$ sufficiently small and $h$ to be a small multiple of $\sqrt{n}$. Thus, most of the coordinates of $\operatorname{LCD}_{h,r}(x)\cdot x$ are within a small distance to integers. For a detailed discussion of the above notion, we refer to .

Let $\xi_{1},\xi_{2},\dots,\xi_{n}$ be independent copies of a centered random variable such that ${\mathcal{L}}(\xi_{i},v)\leq u$ for some $v>0$ and $u\in(0,1)$. Further, let $x=(x_{1},x_{2},\dots,x_{n})\in S^{n-1}$ be a fixed vector. Then for every $h>0$, $r\in(0,1)$ and for every

where $C_{\text{\tiny\ref{small ball probability}}}$ is a universal constant.

Thus, in order to get a satisfactory small ball probability estimate for the infimum over incompressible vectors, it is sufficient to show that the random normal $X^{*}$ has exponentially large $\operatorname{LCD}$ with probability close to one. This will be done in the second part of Section 5. As for the set $\operatorname{Comp}$, our treatment of the random normal will be based on results of Section 3.

The smallest singular value — proof of Theorem B

In this section we give a proof of Theorem B stated in the introduction. Let us start with a version of Theorem A more convenient for us:

Let $\delta\in(0,1/4]$, $n\geq\frac{1}{4\delta}$, $\varepsilon\in(0,1/2]$, $S\subset S^{n-1}$, and let ${\mathcal{N}}\subset S$ be a Euclidean $\varepsilon$-net on $S$. Then there exists a (deterministic) subset $\widetilde{\mathcal{N}}\subset S$ with |\widetilde{\mathcal{N}}|~{}\leq~{}\exp\bigl{(}13\delta n\ln\frac{2e}{\delta}\bigr{)}|{\mathcal{N}}| such that for any $n\times n$ random matrix $A$ satisfying (* ‣ 1), with probability at least $1-4\exp(-\delta n/8)$ the set $\widetilde{\mathcal{N}}$ is a $(\frac{\varepsilon C_{\star}}{\delta}\sqrt{n})$–net on $S$ with respect to the pseudometric $d(x,y):=\|A(x-y)\|$ ($x,y\in S^{n-1}$), where $C_{\star}>0$ is a universal constant.

Fix parameters $n$ and $\delta$, and let $\mathcal{C}$ be the collection of parallelepipeds from Theorem A covering $B_{2}^{n}$. Define a set \widetilde{\mathcal{C}}:=\big{\{}\varepsilon P+y:\,P\in\mathcal{C},\;y\in{\mathcal{N}},\;S\cap(\varepsilon P+y)\neq\emptyset\big{\}} and for every $\widetilde{P}\in\mathcal{C}$ let $y_{\widetilde{P}}$ be a point in the intersection $S\cap\widetilde{P}$. Finally, set $\widetilde{\mathcal{N}}:=\{y_{\widetilde{P}}:\,\widetilde{P}\in\widetilde{\mathcal{C}}\}$. Informally speaking, $\widetilde{\mathcal{C}}$ is a “product” of the rescaled collection $\varepsilon\cdot\mathcal{C}$ and the net ${\mathcal{N}}$. For each parallelepiped in $\widetilde{\mathcal{C}}$ having a non-empty intersection with $S$, we take one (arbitrary) point from this intersection to construct the refined net $\widetilde{\mathcal{N}}$. What remains is to check that with high probability $\widetilde{\mathcal{N}}$ is indeed a $(\frac{\varepsilon C}{\delta}\sqrt{n})$–net on $S$ with respect to the pseudometric $d(x,y):=\|A(x-y)\|$.

Next, let $A$ be an $n\times n$ random matrix satisfying (* ‣ 1), and define event ${\mathcal{E}}$ as

Fix any point $x\in S$. By the definition of ${\mathcal{N}}$, there is a vector $y\in{\mathcal{N}}$ such that $\varepsilon^{-1}(x-y)\in B_{2}^{n}$. Hence, for any point $\omega\in{\mathcal{E}}$ on the probability space, there is a parallelepiped $P=P(\omega)\in\mathcal{C}$ such that $\varepsilon^{-1}(x-y)\in P$ and

Note that $S\cap(\varepsilon P+y)\supset\{x\}\neq\emptyset$, whence $\widetilde{P}:=\varepsilon P+y\in\widetilde{\mathcal{C}}$, and, from the above relation,

where $y_{\widetilde{P}}\in\widetilde{\mathcal{N}}$. We have shown that

Let us note that a weaker version of Theorem $A^{\star}$, with condition $\widetilde{\mathcal{N}}\subset S$ dropped, can be proved by applying Corollary A instead of Theorem A.

At this point, a significant part of our argument follows the same scheme as in . In the first part of this section, we are dealing with compressible vectors.

Without loss of generality, we can assume that $n$ is large. First, note that by Lemma 4.9 we have a strong probability estimate for any fixed unit vector: there are $v>0$ and $u\in(0,1)$ depending on $\widetilde{v},\widetilde{u}$ such that for any $y\in S^{n-1}$ we get

In order to obtain a uniform estimate over a set $S=\operatorname{Comp}_{n}(\theta,\theta)$ for some small parameter $\theta$, we will take a net ${\mathcal{N}}\subset S$ constructed in Lemma 4.3 and refine it with the help of Theorem $A^{\star}$ to get a net $\widetilde{\mathcal{N}}$ with respect to pseudometric $\|A(x-y)\|$. We will apply Theorem $A^{\star}$ with parameter $\delta$ defined as the largest number in $(0,1/4]$ so that \exp\bigl{(}13\delta n\ln\frac{2e}{\delta}\bigr{)}\leq u^{-n/3}. Let us describe the procedure in more detail.

First, define parameter $\theta\in(0,1/6]$ as the largest number satisfying the inequalities

Let $S$ be as above. By Lemma 4.3, there is a $3\theta$-net ${\mathcal{N}}\subset S$ on $S$ (with respect to the usual Euclidean metric) of cardinality $|{\mathcal{N}}|\leq(\frac{5e}{\theta^{2}})^{\theta n}$. Now, by Theorem $A^{\star}$, there is a deterministic subset $\widetilde{\mathcal{N}}\subset S$ having the following properties:

|\widetilde{\mathcal{N}}|\leq\exp\bigl{(}13\delta n\ln\frac{2e}{\delta}\bigr{)}\cdot|{\mathcal{N}}|\leq u^{-n/3}\cdot\big{(}\frac{5e}{\theta^{2}}\big{)}^{\theta n}\leq u^{-2n/3};

With probability at least $1-4\exp(-\delta n/8)$ for every $y\in S$ there exists $x(y)\in\widetilde{\mathcal{N}}$ such that

Applying the union bound over $\widetilde{\mathcal{N}}$ to relation (9), we get

On the other hand, the second property of $\widetilde{\mathcal{N}}$ implies that

and the result follows with $u_{\text{\tiny\ref{compressible prop}}}:=\max\{u^{1/3},\exp(-\delta/8)\}$. ∎

It is not difficult to see that Proposition 5.2 can be stated and proved in the same way for $A$ which is not square, but instead is an $n-1\times n$ matrix with i.i.d. entries equidistributed with $\alpha$. Indeed, for $n$ large enough we can assume that $\gamma\cdot n<(n-1)<n$ for $\gamma$ as close to one as we want (the values of $\theta_{\text{\tiny\ref{compressible prop}}}$, $u_{\text{\tiny\ref{compressible prop}}}$ and $v_{\text{\tiny{\ref{compressible prop}}}}$ may differ in that case). This will be important for us later.

Proposition 5.2 could be proved by a completely different argument based on [27, Proposition 13] and not using results of Section 3 at all. However, we prefer to have a “uniform” treatment of both compressible and incompressible vectors.

Let us turn to estimating the infimum over incompressible vectors. As we already discussed in Section 4, it suffices to show that the random unit normal vector to the span of the first $n-1$ columns of $A$ has exponentially large $\operatorname{LCD}$ with probability very close to one. This property is verified in Theorem 5.9 below. We start with some auxiliary statements. First, note that Theorem 4.12 together with Lemma 4.8 imply that anti-concentration probability for a single vector can be estimated in terms of the LCD of the vector. Namely, the bigger $\operatorname{LCD}(x)$ is, the less is the probability that the image $Ax$ concentrates in a small ball:

Let $h>0$, $r\in(0,1)$ and let $\alpha$ be a random variable satisfying ${\mathcal{L}}(\alpha,\widetilde{v})\leq\widetilde{u}$ for some $\widetilde{v}>0$ and $\widetilde{u}\in(0,1)$. Then there is $L_{\text{\tiny\ref{small ball single vector}}}\geq 1$ depending only on $\widetilde{v},\widetilde{u}$ with the following property: Let $A^{\prime}$ be an $n-1\times n$ random matrix with i.i.d. elements equidistributed with $\alpha$. Then for any vector $x\in S^{n-1}$ and any

Fix any vector $x\in S^{n-1}$ and denote $Y=(Y_{1},Y_{2},\dots,Y_{n-1}):=A^{\prime}x$. Note that, in view of Theorem 4.12, we have

for any $\varepsilon$ satisfying conditions of the lemma. Hence, by Lemma 4.8,

The above statement is useful for incompressible vectors: the following Lemma 5.6 shows that incompressible vectors have $\operatorname{LCD}$ at least of order $\sqrt{n}$. The lemma is taken from papers , and its proof is included for completeness.

For every $\theta,\rho\in(0,1)$ there are $q_{\text{\tiny\ref{incompressible lcd}}}=q_{\text{\tiny\ref{incompressible lcd}}}(\theta,\rho)>0$ and $r_{\text{\tiny\ref{incompressible lcd}}}=r_{\text{\tiny\ref{incompressible lcd}}}(\theta,\rho)>0$ such that for every $h>0$ any vector $x\in\operatorname{Incomp}_{n}(\theta,\rho)$ satisfies

Set $a:=\frac{1}{2}\rho^{2}\theta$ and $b:=\rho/\sqrt{2}$. We choose $r=r_{\text{\tiny\ref{incompressible lcd}}}:=b\sqrt{\frac{a}{2}}=\frac{1}{2}\rho^{2}\sqrt{\theta}$ and q=q_{\text{\tiny\ref{incompressible lcd}}}:=\big{(}1/\sqrt{\theta}+\frac{2r}{a}\big{)}^{-1}=\sqrt{\theta}/3.

It is easy to check that for a vector with such norm the set

has a cardinality at least $(1-\frac{a^{2}}{4})n$. Further, by Lemma 4.4, the set of “spread” coordinates $\sigma(x)$ has cardinality at least $an$. Hence, the set $I(x):=\sigma(x)\cap\widetilde{\sigma}(x)$ is non-empty, and $|I(x)|>\frac{a}{2}n$. For any $i\in I(x)$ we have

Finally, due to the definition of $I(x)$ and our choice of $r$, denoting by $P_{J}$ the coordinate projection on a span $\{i\in J:e_{i}\}$, we obtain

which contradicts (10) and, hence, the assumption that $\operatorname{LCD}_{h,r}(x)<q\sqrt{n}$. ∎

In the proof of the theorem below we will partition $\operatorname{Incomp}_{n}(\theta,\rho)$ into subsets of vectors having $\operatorname{LCD}$’s of the same order:

where, using Lemma 5.6, we introduce the lower bound $i_{0}:=\log_{2}(q_{\text{\tiny\ref{incompressible lcd}}}\sqrt{n}/2)$ (we have $S_{k}=\emptyset$ for all $k<q_{\text{\tiny\ref{incompressible lcd}}}\sqrt{n}/2$). Following , we are going to combine estimates for individual sets $S_{k}$.

A principal observation made in and is that the sets $S_{k}$ admit Euclidean $\varepsilon$-nets of relatively small cardinality. We give both the formal statement and its proof from below for the sake of completeness:

For any $\theta,\rho\in(0,1)$ there is $L=L(\theta,\rho)>0$ such that for every $h\geq 1$ and $k>0$ the set $S_{k}$ admits a Euclidean $(4h/k)$-net of cardinality at most \bigl{(}kL/\sqrt{n}\bigr{)}^{n}.

In view of Lemma 5.6, we can assume that $k\geq q_{\text{\tiny\ref{incompressible lcd}}}\sqrt{n}/2$. Further, without loss of generality $\frac{4h}{k}<2$; otherwise a one-point net works.

It is a simple planimetric observation that if we normalize the vector $p/\operatorname{LCD}_{h,r_{\text{\tiny\ref{incompressible lcd}}}}(x)$, the distance to the unit vector $x$ cannot increase more than twice:

for an appropriate number $L=L(\theta,\rho)>0$. The net ${\mathcal{N}}_{int}$ does not have to be contained in $S_{k}$. But, by a standard argument, we can “replace” ${\mathcal{N}}_{int}$ with a $4h/k$-net of the same cardinality, and with elements from the set $S_{k}$. ∎

Together with Theorem $A^{\star}$, the above lemma gives

For any $\theta,\rho\in(0,1)$ there is $L_{\text{\tiny\ref{net on level sets}}}=L_{\text{\tiny\ref{net on level sets}}}(\theta,\rho)\geq 1$ such that for every $h\geq 1$ and $k>0$ there is a finite subset ${\mathcal{N}}\subset S_{k}$ of cardinality at most \bigl{(}kL_{\text{\tiny\ref{net on level sets}}}/\sqrt{n}\bigr{)}^{n} with the following property. The event

has probability at least $1-4\exp(-n/32)$.

Let $\alpha$ be a centered random variable of unit variance such that ${\mathcal{L}}(\alpha,\widetilde{v})\leq\widetilde{u}$ for some $\widetilde{v}>0$ and $\widetilde{u}\in(0,1)$. Then there exist $q,s,w,r>0$ depending only on $\widetilde{v},\widetilde{u}$ with the following property: let $X^{1},X^{2}\dots,X^{n-1}$ be random $n$-dimensional vectors whose coordinates are jointly independent copies of $\alpha$. Consider any random unit vector $X^{*}$ orthogonal to $\{X^{1},X^{2},\dots,X^{n-1}\}$. Then

Without loss of generality, we can assume that $n$ is a large number and that $\widetilde{v}\leq 1$. Denote by $A^{\prime}$ the $n-1\times n$ matrix with rows $X^{1},X^{2},\dots,X^{n-1}$. Then, by the definition of $X^{*}$, we have $A^{\prime}X^{*}=0$ almost surely. Let $\theta_{\text{\tiny\ref{compressible prop}}}$ and $u_{\text{\tiny\ref{compressible prop}}}$ be defined as in Remark 5.3 (with $A^{\prime}$ replacing $A$). Then, by Proposition 5.2 and Remark 5.3, we have

for $w>0$ such that, say, $\exp(-2w)>u_{\text{\tiny\ref{compressible prop}}}$, and provided that $n$ is large. Thus, it is enough to prove that

for small enough $r,w,s,q$ depending only on $\widetilde{v},\widetilde{u}$. We start by defining $r:=r_{\text{\tiny\ref{incompressible lcd}}}(\theta_{\text{\tiny\ref{compressible prop}}},\theta_{\text{\tiny\ref{compressible prop}}})$. Note that, by Lemma 5.6, we have

for any $s>0$, and, in particular for $s$ defined by $s:=\frac{\widetilde{v}r}{4L^{2}_{\text{\tiny\ref{net on level sets}}}L_{\text{\tiny\ref{small ball single vector}}}}$, where $L_{\text{\tiny\ref{net on level sets}}}=L_{\text{\tiny\ref{net on level sets}}}(\theta_{\text{\tiny\ref{compressible prop}}},\theta_{\text{\tiny\ref{compressible prop}}})$ and $L_{\text{\tiny\ref{small ball single vector}}}$ are taken from Lemmas 5.8 and 5.5, respectively, and $q_{\text{\tiny\ref{incompressible lcd}}}=q_{\text{\tiny\ref{incompressible lcd}}}(\theta_{\text{\tiny\ref{compressible prop}}},\theta_{\text{\tiny\ref{compressible prop}}})$. Let us emphasize that no vicious cycle is created here in regard to interdependence between $s$ and $r$. Finally, we let $q:=2s^{2}(1-\widetilde{u})$ ($w$ will be defined at the very end of the proof).