Introduction to the non-asymptotic analysis of random matrices

1 Introduction

Random matrix theory studies properties of $N\times n$ matrices $A$ chosen from some distribution on the set of all matrices. As dimensions $N$ and $n$ grow to infinity, one observes that the spectrum of $A$ tends to stabilize. This is manifested in several limit laws, which may be regarded as random matrix versions of the central limit theorem. Among them is Wigner’s semicircle law for the eigenvalues of symmetric Gaussian matrices, the circular law for Gaussian matrices, the Marchenko-Pastur law for Wishart matrices $W=A^{*}A$ where $A$ is a Gaussian matrix, the Bai-Yin and Tracy-Widom laws for the extreme eigenvalues of Wishart matrices $W$. The books offer thorough introduction to the classical problems of random matrix theory and its fascinating connections.

The asymptotic regime where the dimensions $N,n\to\infty$ is well suited for the purposes of statistical physics, e.g. when random matrices serve as finite-dimensional models of infinite-dimensional operators. But in some other areas including statistics, geometric functional analysis, and compressed sensing, the limiting regime may not be very useful . Suppose, for example, that we ask about the largest singular value $s_{\max}(A)$ (i.e. the largest eigenvalue of $(A^{*}A)^{1/2}$); to be specific assume that $A$ is an $n\times n$ matrix whose entries are independent standard normal random variables. The asymptotic random matrix theory answers this question as follows: the Bai-Yin law (see Theorem 5.31) states that

as the dimension $n\to\infty$. Moreover, the limiting distribution of $s_{\max}(A)$ is known to be the Tracy-Widom law (see ). In contrast to this, a non-asymptotic answer to the same question is the following: in every dimension $n$, one has

here $C$ is an absolute constant (see Theorems 5.32 and 5.39). The latter answer is less precise (because of an absolute constant $C$) but more quantitative because for fixed dimensions $n$ it gives an exponential probability of success.For this specific model (Gaussian matrices),Theorems 5.32 and 5.35 even give a sharp absolute constant $C\approx 2$ here. But the result mentioned here is much more general as we will see later; it only requires independence of rows or columns of $A$. This is the kind of answer we will seek in this text – guarantees up to absolute constants in all dimensions, and with large probability.

Tall matrices are approximate isometries

where $K$ is an appropriate normalization factor and $\delta\ll 1$. Equivalently, this says that all the singular values of $A$ are close to each other:

where $s_{\min}(A)$ and $s_{\max}(A)$ denote the smallest and the largest singular values of $A$. Yet equivalently, this means that tall matrices are well conditioned: the condition number of $A$ is $\kappa(A)=s_{\max}(A)/s_{\min}(A)\leq(1+\delta)/(1-\delta)\approx 1$.

In the asymptotic regime and for random matrices with independent entries, our heuristic is justified by Bai-Yin’s law, which is Theorem 5.31 below. Loosely speaking, it states that as the dimensions $N,n$ increase to infinity while the aspect ratio $N/n$ is fixed, we have

In these notes, we study $N\times n$ random matrices $A$ with independent rows or independent columns, but not necessarily independent entries. We develop non-asymptotic versions of (5.1) for such matrices, which should hold for all dimensions $N$ and $n$. The desired results should have the form

with large probability, e.g. $1-e^{-N}$, where $C$ is an absolute constant.More accurately, we should expect $C=O(1)$ to depend on easily computable quantities of the distribution, such as its moments. This will be clear from the context. For tall matrices, where $N\gg n$, both sides of this inequality would be close to each other, which would guarantee that $A$ is an approximate isometry.

Models and methods

We shall study quite general models of random matrices – those with independent rows or independent columns that are sampled from high-dimensional distributions. We will place either strong moment assumptions on the distribution (sub-gaussian growth of moments), or no moment assumptions at all (except finite variance). This leads us to four types of main results:

Matrices with independent sub-gaussian rows: Theorem 5.39

Matrices with independent heavy-tailed rows: Theorem 5.41

Matrices with independent sub-gaussian columns: Theorem 5.58

Matrices with independent heavy-tailed columns: Theorem 5.62

These four models cover many natural classes of random matrices that occur in applications, including random matrices with independent entries (Gaussian and Bernoulli in particular) and random sub-matrices of orthogonal matrices (random Fourier matrices in particular).

The analysis of these four models is based on a variety of tools of probability theory and geometric functional analysis, most of which have not been covered in the texts on the “classical” random matrix theory. The reader will learn basics on sub-gaussian and sub-exponential random variables, isotropic random vectors, large deviation inequalities for sums of independent random variables, extensions of these inequalities to random matrices, and several basic methods of high dimensional probability such as symmetrization, decoupling, and covering ($\varepsilon$-net) arguments.

Applications

In compressed sensing, the best known measurement matrices are random. A sufficient condition for a matrix to succeed for the purposes of compressed sensing is given by the restricted isometry property. Loosely speaking, this property demands that all sub-matrices of given size be well-conditioned. This fits well in the circle of problems of the non-asymptotic random matrix theory. Indeed, we will see in Section 5.6 that all basic models of random matrices are nice restricted isometries. These include Gaussian and Bernoulli matrices, more generally all matrices with sub-gaussian independent entries, and even more generally all matrices with sub-gaussian independent rows or columns. Also, the class of restricted isometries includes random Fourier matrices, more generally random sub-matrices of bounded orthogonal matrices, and even more generally matrices whose rows are independent samples from an isotropic distribution with uniformly bounded coordinates.

Related sources

This text is a tutorial rather than a survey, so we focus on explaining methods rather than results. This forces us to make some concessions in our choice of the subjects. Concentration of measure and its applications to random matrix theory are only briefly mentioned. For an introduction into concentration of measure suitable for a beginner, see and [49, Chapter 14]; for a thorough exposition see ; for connections with random matrices see . The monograph also offers an introduction into concentration of measure and related probabilistic methods in analysis and geometry, some of which we shall use in these notes.

We completely avoid the important (but more difficult) model of symmetric random matrices with independent entries on and above the diagonal. Starting from the work of Füredi and Komlos , the largest singular value (the spectral norm) of symmetric random matrices has been a subject of study in many works; see e.g. and the references therein.

We also did not even attempt to discuss sharp small deviation inequalities (of Tracy-Widom type) for the extreme eigenvalues. Both these topics and much more are discussed in the surveys , which serve as bridges between asymptotic and non-asymptotic problems in random matrix theory.

Because of the absolute constant $C$ in (5.2), our analysis of the smallest singular value (the “hard edge”) will only be useful for sufficiently tall matrices, where $N\geq C^{2}n$. For square and almost square matrices, the hard edge problem will be only briefly mentioned in Section 5.3. The surveys discuss this problem at length, and they offer a glimpse of connections to other problems of random matrix theory and additive combinatorics.

Many of the results and methods presented in these notes are known in one form or another. Some of them are published while some others belong to the folklore of probability in Banach spaces, geometric functional analysis, and related areas. When available, historic references are given in Section 5.7.

Acknowledgements

The author is grateful to the colleagues who made a number of improving suggestions for the earlier versions of the manuscript, in particular to Richard Chen, Subhroshekhar Ghosh, Alexander Litvak, Deanna Needell, Holger Rauhut, S V N Vishwanathan and the anonymous referees. Special thanks are due to Ulas Ayaz and Felix Krahmer who thoroughly read the entire text, and whose numerous comments led to significant improvements of this tutorial.

2 Preliminaries

The main object of our study will be an $N\times n$ matrix $A$ with real or complex entries. We shall state all results in the real case; the reader will be able to adjust them to the complex case as well. Usually but not always one should think of tall matrices $A$, those for which $N\geq n>1$. By passing to the adjoint matrix $A^{*}$, many results can be carried over to “flat” matrices, those for which $N\leq n$.

It is often convenient to study $A$ through the $n\times n$ symmetric positive-semidefinite matrix the matrix $A^{*}A$. The eigenvalues of $|A|:=\sqrt{A^{*}A}$ are therefore non-negative real numbers. Arranged in a non-decreasing order, they are called the singular valuesIn the literature, singular values are also called s-numbers. of $A$ and denoted $s_{1}(A)\geq\cdots\geq s_{n}(A)\geq 0$. Many applications require estimates on the extreme singular values

The smallest singular value is only of interest for tall matrices, since for $N<n$ one automatically has $s_{\min}(A)=0$.

Equivalently, $s_{\max}(A)$ and $s_{\min}(A)$ are respectively the smallest number $M$ and the largest number $m$ such that

The extreme singular values can also be described in terms of the spectral norm of $A$, which is by definition

(5.3) gives a link between the extreme singular values and the spectral norm:

where $A^{\dagger}$ denotes the pseudoinverse of $A$; if $A$ is invertible then $A^{\dagger}=A^{-1}$.

2.2 Nets

Nets are convenient means to discretize compact sets. In our study we will mostly need to discretize the unit Euclidean sphere $S^{n-1}$ in the definition of the spectral norm (5.4). Let us first recall a general definition of an $\varepsilon$-net.

Let $(X,d)$ be a metric space and let $\varepsilon>0$. A subset $\mathcal{N}_{\varepsilon}$ of $X$ is called an $\varepsilon$-net of $X$ if every point $x\in X$ can be approximated to within $\varepsilon$ by some point $y\in\mathcal{N}_{\varepsilon}$, i.e. so that $d(x,y)\leq\varepsilon$. The minimal cardinality of an $\varepsilon$-net of $X$, if finite, is denoted $\mathcal{N}(X,\varepsilon)$ and is called the covering numberEquivalently, $\mathcal{N}(X,\varepsilon)$ is the minimal number of balls with radii $\varepsilon$ and with centers in $X$ needed to cover $X$. of $X$ (at scale $\varepsilon$).

From a characterization of compactness we remember that $X$ is compact if and only if $\mathcal{N}(X,\varepsilon)<\infty$ for each $\varepsilon>0$. A quantitative estimate on $\mathcal{N}(X,\varepsilon)$ would give us a quantitative version of compactness of $X$.In statistical learning theory and geometric functional analysis, $\log\mathcal{N}(X,\varepsilon)$ is called the metric entropy of $X$. In some sense it measures the “complexity” of metric space $X$. Let us therefore take a simple example of a metric space, the unit Euclidean sphere $S^{n-1}$ equipped with the Euclidean metricA similar result holds for the geodesic metric on the sphere, since for small $\varepsilon$ these two distances are equivalent. $d(x,y)=\|x-y\|_{2}$, and estimate its covering numbers.

The unit Euclidean sphere $S^{n-1}$ equipped with the Euclidean metric satisfies for every $\varepsilon>0$ that

This is a simple volume argument. Let us fix $\varepsilon>0$ and choose $\mathcal{N}_{\varepsilon}$ to be a maximal $\varepsilon$-separated subset of $S^{n-1}$. In other words, $\mathcal{N}_{\varepsilon}$ is such that $d(x,y)\geq\varepsilon$ for all $x,y\in\mathcal{N}_{\varepsilon}$, $x\neq y$, and no subset of $S^{n-1}$ containing $\mathcal{N}_{\varepsilon}$ has this property.One can in fact construct $\mathcal{N}_{\varepsilon}$ inductively by first selecting an arbitrary point on the sphere, and at each next step selecting a point that is at distance at least $\varepsilon$ from those already selected. By compactness, this algorithm will terminate after finitely many steps and it will yield a set $\mathcal{N}_{\varepsilon}$ as we required.

The maximality property implies that $\mathcal{N}_{\varepsilon}$ is an $\varepsilon$-net of $S^{n-1}$. Indeed, otherwise there would exist $x\in S^{n-1}$ that is at least $\varepsilon$-far from all points in $\mathcal{N}_{\varepsilon}$. So $\mathcal{N}_{\varepsilon}\cup\{x\}$ would still be an $\varepsilon$-separated set, contradicting the minimality property.

Moreover, the separation property implies via the triangle inequality that the balls of radii $\varepsilon/2$ centered at the points in $\mathcal{N}_{\varepsilon}$ are disjoint. On the other hand, all such balls lie in $(1+\varepsilon/2)B_{2}^{n}$ where $B_{2}^{n}$ denotes the unit Euclidean ball centered at the origin. Comparing the volume gives \operatorname{vol}\big{(}\frac{\varepsilon}{2}B_{2}^{n}\big{)}\cdot|\mathcal{N}_{\varepsilon}|\leq\operatorname{vol}\big{(}(1+\frac{\varepsilon}{2})B_{2}^{n}\big{)}. Since \operatorname{vol}\big{(}rB_{2}^{n}\big{)}=r^{n}\operatorname{vol}(B_{2}^{n}) for all $r\geq 0$, we conclude that $|\mathcal{N}_{\varepsilon}|\leq(1+\frac{\varepsilon}{2})^{n}/(\frac{\varepsilon}{2})^{n}=(1+\frac{2}{\varepsilon})^{n}$ as required. ∎

Nets allow us to reduce the complexity of computations with linear operators. One such example is the computation of the spectral norm. To evaluate the spectral norm by definition (5.4) one needs to take the supremum over the whole sphere $S^{n-1}$. However, one can essentially replace the sphere by its $\varepsilon$-net:

Let $A$ be an $N\times n$ matrix, and let $\mathcal{N}_{\varepsilon}$ be an $\varepsilon$-net of $S^{n-1}$ for some $\varepsilon\in[0,1)$. Then

The lower bound in the conclusion follows from the definition. To prove the upper bound let us fix $x\in S^{n-1}$ for which $\|A\|=\|Ax\|_{2}$, and choose $y\in\mathcal{N}_{\varepsilon}$ which approximates $x$ as $\|x-y\|_{2}\leq\varepsilon$. By the triangle inequality we have $\|Ax-Ay\|_{2}\leq\|A\|\|x-y\|_{2}\leq\varepsilon\|A\|$. It follows that

Taking maximum over all $y\in\mathcal{N}_{\varepsilon}$ in this inequality, we complete the proof. ∎

A similar result holds for symmetric $n\times n$ matrices $A$, whose spectral norm can be computed via the associated quadratic form: $\|A\|=\sup_{x\in S^{n-1}}|\langle Ax,x\rangle|$. Again, one can essentially replace the sphere by its $\varepsilon$-net:

Let $A$ be a symmetric $n\times n$ matrix, and let $\mathcal{N}_{\varepsilon}$ be an $\varepsilon$-net of $S^{n-1}$ for some $\varepsilon\in[0,1)$. Then

Let us choose $x\in S^{n-1}$ for which $\|A\|=|\langle Ax,x\rangle|$, and choose $y\in\mathcal{N}_{\varepsilon}$ which approximates $x$ as $\|x-y\|_{2}\leq\varepsilon$. By the triangle inequality we have

It follows that $|\langle Ay,y\rangle|\geq|\langle Ax,x\rangle|-2\varepsilon\|A\|=(1-2\varepsilon)\|A\|$. Taking the maximum over all $y\in\mathcal{N}_{\varepsilon}$ in this inequality completes the proof. ∎

2.3 Sub-gaussian random variables

In this section we introduce the class of sub-gaussian random variables,It would be more rigorous to say that we study sub-gaussian probability distributions. The same concerns some other properties of random variables and random vectors we study later in this text. However, it is convenient for us to focus on random variables and vectors because we will form random matrices out of them. those whose distributions are dominated by the distribution of a centered gaussian random variable. This is a convenient and quite wide class, which contains in particular the standard normal and all bounded random variables.

Let us briefly recall some of the well known properties of the standard normal random variable $X$. The distribution of $X$ has density $\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$ and is denoted $N(0,1)$. Estimating the integral of this density between $t$ and $\infty$ one checks that the tail of a standard normal random variable $X$ decays super-exponentially:

see e.g. [26, Theorem 1.4] for a more precise two-sided inequality. The absolute moments of $X$ can be computed as

The moment generating function of $X$ equals

Now let $X$ be a general random variable. We observe that these three properties are equivalent – a super-exponential tail decay like in (5.5), the moment growth (5.6), and the growth of the moment generating function like in (5.7). We will then focus on the class of random variables that satisfy these properties, which we shall call sub-gaussian random variables.

Let $X$ be a random variable. Then the following properties are equivalent with parameters $K_{i}>0$ differing from each other by at most an absolute constant factor.The precise meaning of this equivalence is the following. There exists an absolute constant $C$ such that property $i$ implies property $j$ with parameter $K_{j}\leq CK_{i}$ for any two properties $i,j=1,2,3$.

Taking the $p$-th root yields property 2 with a suitable absolute constant $K_{2}$.

2. $\Rightarrow$ 3. Assume property 2 holds. As before, by homogeneity we may assume that $K_{2}=1$. Let $c>0$ be a sufficiently small absolute constant. Writing the Taylor series of the exponential function, we obtain

3. $\Rightarrow$ 1. Assume property 3 holds. As before we may assume that $K_{3}=1$. Exponentiating and using Markov’s inequalityThis simple argument is sometimes called exponential Markov’s inequality. and then property 3, we have

4. $\Rightarrow$ 1. Assume property 4 holds; we can also assume that $K_{4}=1$. Let $\lambda>0$ be a parameter to be chosen later. By exponential Markov inequality, and using the bound on the moment generating function given in property 4, we obtain

The constants $1$ and $e$ in properties 1 and 3 respectively are chosen for convenience. Thus the value $1$ can be replaced by any positive number and the value $e$ can be replaced by any number greater than $1$.

A random variable $X$ that satisfies one of the equivalent properties 1 – 3 in Lemma 5.5 is called a sub-gaussian random variable. The sub-gaussian norm of $X$, denoted $\|X\|_{\psi_{2}}$, is defined to be the smallest $K_{2}$ in property 2. In other words,The sub-gaussian norm is also called ${\psi_{2}}$ norm in the literature.

The class of sub-gaussian random variables on a given probability space is thus a normed space. By Lemma 5.5, every sub-gaussian random variable $X$ satisfies:

where $C,c>0$ are absolute constants. Moreover, up to absolute constant factors, $\|X\|_{\psi_{2}}$ is the smallest possible number in each of these inequalities.

Classical examples of sub-gaussian random variables are Gaussian, Bernoulli and all bounded random variables.

(Gaussian): A standard normal random variable $X$ is sub-gaussian with $\|X\|_{\psi_{2}}\leq C$ where $C$ is an absolute constant. This follows from (5.6). More generally, if $X$ is a centered normal random variable with variance $\sigma^{2}$, then $X$ is sub-gaussian with $\|X\|_{\psi_{2}}\leq C\sigma$.

(Bounded): More generally, consider any bounded random variable $X$, thus $|X|\leq M$ almost surely for some $M$. Then $X$ is a sub-gaussian random variable with $\|X\|_{\psi_{2}}\leq M$. We can write this more compactly as $\|X\|_{\psi_{2}}\leq\|X\|_{\infty}$.

A remarkable property of the normal distribution is rotation invariance. Given a finite number of independent centered normal random variables $X_{i}$, their sum $\sum_{i}X_{i}$ is also a centered normal random variable, obviously with $\operatorname{Var}(\sum_{i}X_{i})=\sum_{i}\operatorname{Var}(X_{i})$. Rotation invariance passes onto sub-gaussian random variables, although approximately:

Consider a finite number of independent centered sub-gaussian random variables $X_{i}$. Then $\sum_{i}X_{i}$ is also a centered sub-gaussian random variable. Moreover,

Using the equivalence of properties 2 and 4 in Lemma 5.5 we conclude that $\|\sum_{i}X_{i}\|_{\psi_{2}}\leq C_{1}K$ where $C_{1}$ is an absolute constant. The proof is complete. ∎

The rotation invariance immediately yields a large deviation inequality for sums of independent sub-gaussian random variables:

The rotation invariance (Lemma 5.9) implies the bound $\|\sum_{i}a_{i}X_{i}\|_{\psi_{2}}^{2}\leq C\sum_{i}a_{i}^{2}\|X_{i}\|_{\psi_{2}}^{2}\leq CK^{2}\|a\|_{2}^{2}$. Property (5.10) yields the required tail decay. ∎

Using moment growth (5.11) instead of the tail decay (5.10), we immediately obtain from Lemma 5.9 a general form of the well known Khintchine inequality:

Let $X_{i}$ be a finite number of independent sub-gaussian random variables with zero mean, unit variance, and $\|X_{i}\|_{{\psi_{2}}}\leq K$. Then, for every sequence of coefficients $a_{i}$ and every exponent $p\geq 2$ we have

2.4 Sub-exponential random variables

Although the class of sub-gaussian random variables is natural and quite wide, it leaves out some useful random variables which have tails heavier than gaussian. One such example is a standard exponential random variable – a non-negative random variable with exponential tail decay

To cover such examples, we consider a class of sub-exponential random variables, those with at least an exponential tail decay. With appropriate modifications, the basic properties of sub-gaussian random variables hold for sub-exponentials. In particular, a version of Lemma 5.5 holds with a similar proof for sub-exponential properties, except for property 4 of the moment generating function. Thus for a random variable $X$ the following properties are equivalent with parameters $K_{i}>0$ differing from each other by at most an absolute constant factor:

A random variable $X$ that satisfies one of the equivalent properties (5.14) – (5.16) is called a sub-exponential random variable. The sub-exponential norm of $X$, denoted $\|X\|_{\psi_{1}}$, is defined to be the smallest parameter $K_{2}$. In other words,

A random variable $X$ is sub-gaussian if and only if $X^{2}$ is sub-exponential. Moreover,

This follows easily from the definition. ∎

The moment generating function of a sub-exponential random variable has a similar upper bound as in the sub-gaussian case (property 4 in Lemma 5.5). The only real difference is that the bound only holds in a neighborhood of zero rather than on the whole real line. This is inevitable, as the moment generating function of an exponential random variable (5.13) does not exist for $t\geq 1$.

Let $X$ be a centered sub-exponential random variable. Then, for $t$ such that $|t|\leq c/\|X\|_{\psi_{1}}$, one has

Sub-exponential random variables satisfy a large deviation inequality similar to the one for sub-gaussians (Proposition 5.10). The only significant difference is that two tails have to appear here – a gaussian tail responsible for the central limit theorem, and an exponential tail coming from the tails of each term.

Without loss of generality, we assume that $K=1$ by replacing $X_{i}$ with $X_{i}/K$ and $t$ with $t/K$. We use the exponential Markov inequality for the sum $S=\sum_{i}a_{i}X_{i}$ and with a parameter $\lambda>0$:

If $|\lambda|\leq c/\|a\|_{\infty}$ then $|\lambda a_{i}|\leq c$ for all $i$, so Lemma 5.15 yields

Choosing $\lambda=\min(t/2C\|a\|_{2}^{2},\,c/\|a\|_{\infty})$, we obtain that

Let $X_{1},\ldots,X_{N}$ be independent centered sub-exponential random variables, and let $K=\max_{i}\|X_{i}\|_{\psi_{1}}$. Then, for every $\varepsilon\geq 0$, we have

This follows from Proposition 5.16 for $a_{i}=1$ and $t=\varepsilon N$. ∎

2.5 Isotropic random vectors

We generalize the concepts of sub-gaussian random variables to higher dimensions using one-dimensional marginals.

The definitions of isotropic and sub-gaussian distributions suggest that more generally, natural properties of high-dimensional distributions may be defined via one-dimensional marginals. This is a natural way to generalize properties of random variables to random vectors. For example, we shall call a random vector sub-exponential if all of its one-dimensional marginals are sub-exponential random variables, etc.

This is a direct consequence of the rotation invariance principle, Lemma 5.9. Indeed, for every $x=(x_{1},\ldots,x_{n})\in S^{n-1}$ we have

where we used that $\sum_{i=1}^{n}x_{i}^{2}=1$. This completes the proof. ∎

Let us analyze the basic examples of random vectors introduced earlier in Example 5.21.

(Gaussian, Bernoulli): Gaussian and Bernoulli random vectors are sub-gaussian; their sub-gaussian norms are bounded by an absolute constant. These are particular cases of Lemma 5.24.

(Spherical): A spherical random vector is also sub-gaussian; its sub-gaussian norm is bounded by an absolute constant. Unfortunately, this does not follow from Lemma 5.24 because the coordinates of the spherical vector are not independent. Instead, by rotation invariance, the claim clearly follows from the following geometric fact. For every $\varepsilon\geq 0$, the spherical cap $\{x\in S^{n-1}:\;x_{1}>\varepsilon\}$ makes up at most $\exp(-\varepsilon^{2}n/2)$ proportion of the total area on the sphere.This fact about spherical caps may seem counter-intuitive. For example, for $\varepsilon=0.1$ the cap looks similar to a hemisphere, but the proportion of its area goes to zero very fast as dimension $n$ increases. This is a starting point of the study of the concentration of measure phenomenon, see . This can be proved directly by integration, and also by elementary geometric considerations [9, Lemma 2.2].

(Coordinate): Although the coordinate random vector $X$ is formally sub-gaussian as its support is finite, its sub-gaussian norm is too big: $\|X\|_{\psi_{2}}=\sqrt{n}\gg 1$. So we would not think of $X$ as a sub-gaussian random vector.

2.6 Sums of independent random matrices

For $p=\infty$, the Schatten norm equals the spectral norm $\|A\|=\max_{i\leq n}s_{i}(A)$. Using this one can quickly check that already for $p=\log n$ the Schatten and spectral norms are equivalent: $\|A\|_{C_{p}^{n}}\leq\|A\|\leq e\|A\|_{C_{p}^{n}}$.

Let $A_{1},\ldots,A_{N}$ be self-adjoint $n\times n$ matrices and $\varepsilon_{1},\ldots,\varepsilon_{N}$ be independent symmetric Bernoulli random variables. Then, for every $2\leq p<\infty$, we have

The scalar case of this result, for $n=1$, recovers the classical Khintchine inequality, Corollary 5.12, for $X_{i}=\varepsilon_{i}$.

By the equivalence of Schatten and spectral norms for $p=\log n$, a version of non-commutative Khintchine inequality holds for the spectral norm:

where $C_{1}$ is an absolute constant. The logarithmic factor is unfortunately essential; it role will be clear when we discuss applications of this result to random matrices in the next sections.

Ahlswede and Winter pioneered a different approach to matrix-valued inequalities in probability theory, which was based on trace inequalities like Golden-Thompson inequality. A development of this idea leads to remarkably sharp results. We quote one such inequality from :

Consider a finite sequence $X_{i}$ of independent centered self-adjoint random $n\times n$ matrices. Assume we have for some numbers $K$ and $\sigma$ that

This is a direct matrix generalization of a classical Bernstein’s inequality for bounded random variables. To compare it with our version of Bernstein’s inequality for sub-exponentials, Proposition 5.16, note that the probability bound in (5.19) is equivalent to 2n\cdot\exp\big{[}-c\min\big{(}\frac{t^{2}}{\sigma^{2}},\frac{t}{K}\big{)}\big{]} where $c>0$ is an absolute constant. In both results we see a mixture of gaussian and exponential tails.

3 Random matrices with independent entries

We are ready to study the extreme singular values of random matrices. In this section, we consider the classical model of random matrices whose entries are independent and centered random variables. Later we will study the more difficult models where only the rows or the columns are independent.

The reader may keep in mind some classical examples of $N\times n$ random matrices with independent entries. The most classical example is the Gaussian random matrix $A$ whose entries are independent standard normal random variables. In this case, the $n\times n$ symmetric matrix $A^{*}A$ is called Wishart matrix; it is a higher-dimensional version of chi-square distributed random variables.

The simplest example of discrete random matrices is the Bernoulli random matrix $A$ whose entries are independent symmetric Bernoulli random variables. In other words, Bernoulli random matrices are distributed uniformly in the set of all $N\times n$ matrices with $\pm 1$ entries.

Consider an $N\times n$ random matrix $A$ whose entries are independent centered identically distributed random variables. By now, the limiting behavior of the extreme singular values of $A$, as the dimensions $N,n\to\infty$, is well understood:

Let $A=A_{N,n}$ be an $N\times n$ random matrix whose entries are independent copies of a random variable with zero mean, unit variance, and finite fourth moment. Suppose that the dimensions $N$ and $n$ grow to infinity while the aspect ratio $n/N$ converges to a constant in $$. Then

As we pointed out in the introduction, our program is to find non-asymptotic versions of Bai-Yin’s law. There is precisely one model of random matrices, namely Gaussian, where an exact non-asymptotic result is known:

Let $A$ be an $N\times n$ matrix whose entries are independent standard normal random variables. Then

The proof of the upper bound, which we borrowed from , is based on Slepian’s comparison inequality for Gaussian processes.Recall that a Gaussian process $(X_{t})_{t\in T}$ is a collection of centered normal random variables $X_{t}$ on the same probability space, indexed by points $t$ in an abstract set $T$.

Therefore Lemma 5.33 applies, and it yields the required bound

While Theorem 5.32 is about the expectation of singular values, it also yields a large deviation inequality for them. It can be deduced formally by using the concentration of measure in the Gauss space.

Let $A$ be an $N\times n$ matrix whose entries are independent standard normal random variables. Then for every $t\geq 0$, with probability at least $1-2\exp(-t^{2}/2)$ one has

Later in these notes, we find it more convenient to work with the $n\times n$ positive-definite symmetric matrix $A^{*}A$ rather than with the original $N\times n$ matrix $A$. Observe that the normalized matrix $\bar{A}=\frac{1}{\sqrt{N}}A$ is an approximate isometry (which is our goal) if and only if $\bar{A}^{*}\bar{A}$ is an approximate identity:

Conversely, if $B$ satisfies (5.21) for some $\delta>0$ then $\|B^{*}B-I\|\leq 3\max(\delta,\delta^{2})$.

Inequality (5.20) holds if and only if \big{|}\|Bx\|_{2}^{2}-1\big{|}\leq\max(\delta,\delta^{2}) for all $x\in S^{n-1}$. Similarly, (5.21) holds if and only if \big{|}\|Bx\|_{2}-1\big{|}\leq\delta for all $x\in S^{n-1}$. The conclusion then follows from the elementary inequality

Lemma 5.36 reduces our task of proving inequalities (5.2) to showing an equivalent (but often more convenient) bound

3.2 General random matrices with independent entries

Now we pass to a more general model of random matrices whose entries are independent centered random variables with some general distribution (not necessarily normal). The largest singular value (the spectral norm) can be estimated by Latala’s theorem for general random matrices with non-identically distributed entries:

Let $A$ be a random matrix whose entries $a_{ij}$ are independent centered random variables with finite fourth moment. Then

If the variance and the fourth moments of the entries are uniformly bounded, then Latala’s result yields $s_{\max}(A)=O(\sqrt{N}+\sqrt{n})$. This is slightly weaker than our goal (5.2), which is $s_{\max}(A)=\sqrt{N}+O(\sqrt{n})$ but still satisfactory for most applications. Results of the latter type will appear later in the more general model of random matrices with independent rows or columns.

Similarly, our goal (5.2) for the smallest singular value is $s_{\min}(A)\geq\sqrt{N}-O(\sqrt{n})$. Since the singular values are non-negative anyway, such inequality would only be useful for sufficiently tall matrices, $N\gg n$. For almost square and square matrices, estimating the smallest singular value (known also as the hard edge of spectrum) is considerably more difficult. The progress on estimating the hard edge is summarized in . If $A$ has independent entries, then indeed $s_{\min}(A)\geq c(\sqrt{N}-\sqrt{n})$, and the following is an optimal probability bound:

Let $A$ be an $n\times n$ random matrix whose entries are independent identically distributed subgaussian random variables with zero mean and unit variance. Then for $\varepsilon\geq 0$,

where $C>0$ and $c\in(0,1)$ depend only on the subgaussian norm of the entries.

This result gives an optimal bound for square matrices as well ($N=n$).

4 Random matrices with independent rows

The picture will vary slightly depending on whether the rows of $A$ are sub-gaussian or have arbitrary distribution. For heavy-tailed distributions, an extra logarithmic factor has to appear in our desired inequality (5.2). The analysis of sub-gaussian and heavy-tailed matrices will be completely different.

There is an abundance of examples where the results of this section may be useful. They include all matrices with independent entries, whether sub-gaussian such as Gaussian and Bernoulli, or completely general distributions with mean zero and unit variance. In the latter case one is able to surpass the fourth moment assumption which is necessary in Bai-Yin’s law, Theorem 5.31.

Other examples of interest come from non-product distributions, some of which we saw in Example 5.21. Sampling from discrete objects (matrices and frames) fits well in this framework, too. Given a deterministic matrix $B$, one puts a uniform distribution on the set of the rows of $B$ and creates a random matrix $A$ as before – by sampling some $N$ random rows from $B$. Applications to sampling will be discussed in Section 5.4.4.

The following result goes in the direction of our goal (5.2) for random matrices with independent sub-gaussian rows.

Here $C=C_{K}$, $c=c_{K}>0$ depend only on the subgaussian norm $K=\max_{i}\|A_{i}\|_{\psi_{2}}$ of the rows.

This result is a general version of Corollary 5.35 (up to absolute constants); instead of independent Gaussian entries we allow independent sub-gaussian rows. This of course covers all matrices with independent sub-gaussian entries such as Gaussian and Bernoulli. It also applies to some natural matrices whose entries are not independent. One such example is a matrix whose rows are independent spherical random vectors (Example 5.25).

The proof is a basic version of a covering argument, and it has three steps. We need to control $\|Ax\|_{2}$ for all vectors $x$ on the unit sphere $S^{n-1}$. To this end, we discretize the sphere using a net $\mathcal{N}$ (the approximation step), establish a tight control of $\|Ax\|_{2}$ for every fixed vector $x\in\mathcal{N}$ with high probability (the concentration step), and finish off by taking a union bound over all $x$ in the net. The concentration step will be based on the deviation inequality for sub-exponential random variables, Corollary 5.17.

Step 1: Approximation. Recalling Lemma 5.36 for the matrix $B=A/\sqrt{N}$ we see that the conclusion of the theorem is equivalent to

Using Lemma 5.4, we can evaluate the operator norm in (5.23) on a $\frac{1}{4}$-net $\mathcal{N}$ of the unit sphere $S^{n-1}$:

So to complete the proof it suffices to show that, with the required probability,

By Lemma 5.2, we can choose the net $\mathcal{N}$ so that it has cardinality $|\mathcal{N}|\leq 9^{n}$.

Step 2: Concentration. Let us fix any vector $x\in S^{n-1}$. We can express $\|Ax\|_{2}^{2}$ as a sum of independent random variables

where the last inequality follows by the definition of $\delta$ and using the inequality $(a+b)^{2}\geq a^{2}+b^{2}$ for $a,b\geq 0$.

Step 3: Union bound. Taking the union bound over all vectors $x$ in the net $\mathcal{N}$ of cardinality $|\mathcal{N}|\leq 9^{n}$, we obtain

where the second inequality follows for $C=C_{K}$ sufficiently large, e.g. $C=K^{2}\sqrt{\ln 9/c_{1}}$. As we noted in Step 1, this completes the proof of the theorem. ∎

Here as before $C=C_{K}$, $c=c_{K}>0$ depend only on the subgaussian norm $K=\max_{i}\|A_{i}\|_{\psi_{2}}$ of the rows. This result is a general version of (5.23). It follows by a straighforward modification of the argument of Theorem 5.39.

A more natural, multiplicative form of (5.25) is the following. Assume that $\Sigma^{-1/2}A_{i}$ are isotropic sub-gaussian random vectors, and let $K$ be the maximum of their sub-gaussian norms. Then for every $t\geq 0$, the following inequality holds with probability at least $1-2\exp(-ct^{2})$:

Here again $C=C_{K}$, $c=c_{K}>0$. This result follows from Theorem 5.39 applied to the isotropic random vectors $\Sigma^{-1/2}A_{i}$.

4.2 Heavy-tailed rows

The class of sub-gaussian random variables in Theorem 5.39 may sometimes be too restrictive in applications. For example, if the rows of $A$ are independent coordinate or frame random vectors (Examples 5.21 and 5.25), they are poorly sub-gaussian and Theorem 5.39 is too weak. In such cases, one would use the following result instead, which operates in remarkable generality.

with probability at least $1-2n\cdot\exp(-ct^{2})$, where $c>0$ is an absolute constant.

with probability at least $1-2n\cdot\exp(-c^{\prime}t^{2})$. This is a form of our desired inequality (5.2) for heavy-tailed matrices. We shall discuss this more after the proof.

We shall use the non-commutative Bernstein’s inequality, Theorem 5.29.

We express this random matrix as a sum of independent random matrices:

note that $X_{i}$ are independent centered $n\times n$ random matrices.

We estimate the range of $X_{i}$ using that $\|A_{i}\|_{2}\leq\sqrt{m}$ and $m\geq 1$:

where we again used that $m\geq 1$. This yieldsHere the seemingly crude application of triangle inequality is actually not so loose. If the rows $A_{i}$ are identically distributed, then so are $X_{i}^{2}$, which makes the triangle inequality above into an equality.

Step 3: Application of the non-commutative Bernstein’s inequality. Applying Theorem 5.29 (see Remark 5.30) and recalling the definitions of $\varepsilon$ and $\delta$ in (5.29), we we bound the probability in question as

Inequality (5.28) fits our goal (5.2), but not quite. The reason is that the probability bound is only non-trivial if $t\geq C\sqrt{\log n}$. Therefore, in reality Theorem 5.41 asserts that

with probability, say $0.9$. This achieves our goal (5.2) up to a logarithmic factor.

The logarithmic factor can not be removed from (5.31) for some heavy-tailed distributions. Consider for instance the coordinate distribution introduced in Example 5.21. In order that $s_{\min}(A)>0$ there must be no zero columns in $A$. Equivalently, each coordinate vector $e_{1},\ldots,e_{n}$ must be picked at least once in $N$ independent trials (each row of $A$ picks an independent coordinate vector). Recalling the classical coupon collector’s problem, one must make at least $N\geq Cn\log n$ trials to make this occur with high probability. Thus the logarithm is necessary in the left hand side of (5.31).This argument moreover shows the optimality of the probability bound in Theorem 5.41. For example, for $t=\sqrt{N}/2\sqrt{n}$ the conclusion (5.28) implies that $A$ is well conditioned (i.e. $\sqrt{N}/2\leq s_{\min}(A)\leq s_{\max}(A)\leq 2\sqrt{N}$) with probability $1-n\cdot\exp(-cN/n)$. On the other hand, by the coupon collector’s problem we estimate the probability that $s_{\min}(A)>0$ as $1-n\cdot(1-\frac{1}{n})^{N}\approx 1-n\cdot\exp(-N/n)$.

A version of Theorem 5.41 holds for general, non-isotropic distributions. It is convenient to state it in terms of the equivalent estimate (5.29):

Here $c>0$ is an absolute constant. In particular, this inequality yields

Taking square roots and multiplying both sides by $\sqrt{N}$, we obtain (5.33). ∎

The almost sure boundedness requirement in Theorem 5.41 may sometimes be too restrictive in applications, and it can be relaxed to a bound in expectation:

The proof of this result is similar to that of Theorem 5.41, except that this time we will use Rudelson’s Corollary 5.28 instead of matrix Bernstein’s inequality. To this end, we need a link to symmetric Bernoulli random variables. This is provided by a general symmetrization argument:

Let $(X_{i})$ be a finite sequence of independent random vectors valued in some Banach space, and $(\varepsilon_{i})$ be independent symmetric Bernoulli random variables. Then

We will also need a probabilistic version of Lemma 5.36 on approximate isometries. The proof of that lemma was based on the elementary inequality $|z^{2}-1|\geq\max(|z-1|,|z-1|^{2})$ for $z\geq 0$. Here is a probabilistic version:

Step 1: Application of Rudelson’s inequality. As in the proof of Theorem 5.41, we are going to control

where we used Symmetrization Lemma 5.46 with independent symmetric Bernoulli random variables $\varepsilon_{i}$ (which are independent of $A$ as well). The expectation in the right hand side is taken both with respect to the random matrix $A$ and the signs $(\varepsilon_{i})$. Taking first the expectation with respect to $(\varepsilon_{i})$ (conditionally on $A$) and afterwards the expectation with respect to $A$, we obtain by Rudelson’s inequality (Corollary 5.28) that

This inequality is easy to solve in $E$. Indeed, considering the cases $E\leq 1$ and $E>1$ separately, we conclude that

Step 2: Diagonalization. Diagonalizing the matrix $A^{*}A$ one checks that

(we replaced the expectation of maximum by the maximum of expectations). Using Lemma 5.47 separately for the two terms on the left hand side, we obtain

Multiplying both sides by $\sqrt{N}$ completes the proof. ∎

In a way similar to Theorem 5.44 we note that a version of Theorem 5.45 holds for general, non-isotropic distributions.

Here $C$ is an absolute constant. In particular, this inequality yields

The first part follows by a simple modification of the proof of Theorem 5.45. The second part follows from the first like in Theorem 5.44. ∎

4.3 Applications to estimating covariance matrices

The simplest way to estimate $\Sigma$ is to take some $N$ independent samples $X_{i}$ from the distribution and form the sample covariance matrix $\Sigma_{N}=\frac{1}{N}\sum_{i=1}^{N}X_{i}\otimes X_{i}$. By the law of large numbers, $\Sigma_{N}\to\Sigma$ almost surely as $N\to\infty$. So, taking sufficiently many samples we are guaranteed to estimate the covariance matrix as well as we want. This, however, does not address the quantitative aspect: what is the minimal sample size $N$ that guarantees approximation with a given accuracy?

The relation of this question to random matrix theory becomes clear when we arrange the samples $X_{i}=:A_{i}$ as rows of the $N\times n$ random matrix $A$. Then the sample covariance matrix is expressed as $\Sigma_{N}=\frac{1}{N}A^{*}A$. Note that $A$ is a matrix with independent rows but usually not independent entries (unless we sample from a product distribution). We worked out the analysis of such matrices in Section 5.4, separately for sub-gaussian and general distributions. As an immediate consequence of Theorem 5.39, we obtain:

Here $C=C_{K}$ depends only on the sub-gaussian norm $K=\|X\|_{\psi_{2}}$ of a random vector taken from this distribution.

It follows from (5.25) that for every $s\geq 0$, with probability at least $1-2\exp(-cs^{2})$ we have $\|\Sigma_{N}-\Sigma\|\leq\max(\delta,\delta^{2})$ where $\delta=C\sqrt{n/N}+s/\sqrt{N}$. The conclusion follows for $s=C^{\prime}t\sqrt{n}$ where $C^{\prime}=C^{\prime}_{K}$ is sufficiently large. ∎

Summarizing, Corollary 5.50 shows that the sample size

A weak point of Corollary 5.50 is that the sub-gaussian norm $K$ may in turn depend on $\|\Sigma\|$.

Finally, Theorem 5.44 yields a similar estimation result for arbitrary distributions, possibly heavy-tailed:

It follows from Theorem 5.44 that for every $s\geq 0$, with probability at least $1-n\cdot\exp(-cs^{2})$ we have $\|\Sigma_{N}-\Sigma\|\leq\max(\|\Sigma\|^{1/2}\delta,\delta^{2})$ where $\delta=s\sqrt{m/N}$. Therefore, if $N\geq(s/\varepsilon)^{2}\|\Sigma\|^{-1}m$ then $\|\Sigma_{N}-\Sigma\|\leq\varepsilon\|\Sigma\|$. The conclusion follows with $s=C^{\prime}t\sqrt{\log n}$ where $C^{\prime}$ is a sufficiently large absolute constant. ∎

We can summarize this discussion in the following way: the sample size

Without the boundedness assumption on the distribution, Corollary 5.52 may fail. The reasoning is the same as in Remark 5.42: for an isotropic distribution which is highly concentrated at the origin, the sample covariance matrix will likely equal .

A different way to enforce the boundedness assumption is to reject any sample points $X_{i}$ that fall outside the centered ball of radius $\sqrt{m}$. This is equivalent to sampling from the conditional distribution inside the ball. The conditional distribution satisfies the boundedness requirement, so the results discussed above provide a good covariance estimation for it. In many cases, this estimate works even for the original distribution – namely, if only a small part of the distribution lies outside the ball of radius $\sqrt{m}$. We leave the details for the interested reader; see e.g. .

4.4 Applications to random sub-matrices and sub-frames

The absence of any moment hypotheses on the distribution in Section 5.4.2 (except finite variance) makes these results especially relevant for discrete distributions. One such situation arises when one wishes to sample entries or rows from a given matrix $B$, thereby creating a random sub-matrix $A$. It is a big program to understand what we can learn about $B$ by seeing $A$, see . In other words, we ask – what properties of $B$ pass onto $A$? Here we shall only scratch the surface of this problem: we notice that random sub-matrices of certain size preserve the property of being an approximate isometry.

Consider an $M\times n$ matrix $B$ such thatThe first hypothesis says $B^{*}B=MI$. Equivalently, $\bar{B}:=\frac{1}{\sqrt{M}}B$ is an isometry, i.e. $\|\bar{B}x\|_{2}=\|x\|_{2}$ for all $x$. Equivalently, the columns of $\bar{B}$ are orthonormal. $s_{\min}(B)=s_{\max}(B)=\sqrt{M}$. Let $m$ be such that all rows $B_{i}$ of $B$ satisfy $\|B_{i}\|_{2}\leq\sqrt{m}$. Let $A$ be an $N\times n$ matrix obtained by sampling $N$ random rows from $B$ uniformly and independently. Then for every $t\geq 0$, with probability at least $1-2n\cdot\exp(-ct^{2})$ one has

Note that the conclusion of Corollary 5.55 does not depend on the dimension $M$ of the ambient matrix $B$. This happens because this result is a specific version of sampling from a discrete isotropic distribution (uniform on the rows of $B$), where size $M$ of the support of the distribution is irrelevant.

The hypothesis of Corollary 5.55 impliesTo recall why this is true, take trace of both sides in the identity $I=\frac{1}{M}\sum_{i=1}^{M}B_{i}\otimes B_{i}$. that $\frac{1}{M}\sum_{i=1}^{M}\|B_{i}\|_{2}^{2}=n$. Hence by Markov’s inequality, most of the rows $B_{i}$ satisfy $\|B_{i}\|_{2}=O(\sqrt{n})$. This indicates that Corollary 5.55 would be often used with $m=O(n)$. Also, to ensure a positive probability of success, the useful magnitude of $t$ would be $t\sim\sqrt{\log n}$. With this in mind, the extremal singular values of $A$ will be close to each other (and to $\sqrt{N}$) if $N\gg t^{2}m\sim n\log n$.

Summarizing, Corollary 5.55 states that a random $O(n\log n)\times n$ sub-matrix of an $M\times n$ isometry is an approximate isometry.For the purposes of compressed sensing, we shall study the more difficult uniform problem for random sub-matrices in Section 5.6. There $B$ itself will be chosen as a column sub-matrix of a given $M\times M$ matrix (such as DFT), and one will need to control all such $B$ simultaneously, see Example 5.73.

with bounds $A=(1-\varepsilon)N$, $B=(1+\varepsilon)N$. Here $C$ is an absolute constant.

5 Random matrices with independent columns

In this section we study the extreme singular values of $N\times n$ random matrices $A$ with independent columns $A_{j}$. We are guided by our ideal bounds (5.2) as before. The same phenomenon occurs in the column independent model as in the row independent model – sufficiently tall random matrices $A$ are approximate isometries. As before, being tall will mean $N\gg n$ for sub-gaussian distributions and $N\gg n\log n$ for arbitrary distributions.

i.e. $\frac{1}{N}G$ is an approximate identity for $N\gg n$. Equivalently, by Lemma 5.36, (5.35) would yield the ideal bounds (5.2) on the extreme singular values of $A$.

Unfortunately, the entries of the Gram matrix $G$ are obviously not independent. To overcome this obstacle we shall use the decoupling technique of probability theory . We observe that there is still enough independence encoded in $G$. Consider a principal sub-matrix $(A_{S})^{*}(A_{T})$ of $G=A^{*}A$ with disjoint index sets $S$ and $T$. If we condition on $(A_{k})_{k\in T}$ then this sub-matrix has independent rows. Using an elementary decoupling technique, we will indeed seek to replace the full Gram matrix $G$ by one such decoupled $S\times T$ matrix with independent rows, and finish off by applying results of Section 5.4.

By transposition one can try to reduce our problem to studying the $n\times N$ matrix $A^{*}$. It has independent rows and the same singular values as $A$, so one can apply results of Section 5.4. The conclusion would be that, with high probability,

Such estimate is only good for flat matrices ($N\leq n$). For tall matrices ($N\geq n$) the lower bound would be trivial because of the (possibly large) constant $C$. So, from now on we can focus on tall matrices ($N\geq n$) with independent columns.

Here we prove a version of Theorem 5.39 for matrices with independent columns.

with probability at least $1-2\exp(-ct^{2})$, where $C=C^{\prime}_{K}$, $c=c^{\prime}_{K}>0$ depend only on the subgaussian norm $K=\max_{j}\|A_{j}\|_{\psi_{2}}$ of the columns.

By Lemma 5.36, the conclusion of Theorem 5.58 is equivalent to

Consider a double array of real numbers $(a_{ij})_{i,j=1}^{n}$ such that $a_{ii}=0$ for all $i$. Then

where $T$ is a random subset of $[n]$ with average size $n/2$. In particular,

where the minimum and maximum are over all subsets $T$ of $[n]$.

Step 1: Reductions. Without loss of generality we can assume that the columns $A_{i}$ have zero mean. Indeed, multiplying each column $A_{i}$ by $\pm 1$ arbitrarily preserves the extreme singular values of $A$, the isotropy of $A_{i}$ and the sub-gaussian norms of $A_{i}$. Therefore, by multiplying $A_{i}$ by independent symmetric Bernoulli random variables we achieve that $A_{i}$ have zero mean.

For $t=O(\sqrt{N})$ the conclusion of Theorem 5.58 follows from Theorem 5.39 by transposition. Indeed, the $n\times N$ random matrix $A^{*}$ has independent rows, so for $t\geq 0$ we have

with probability at least $1-2\exp(-c_{K}t^{2})$. Here $c_{K}>0$ and we can obviously assume that $C_{K}\geq 1$. For $t\geq C_{K}\sqrt{N}$ it follows that $s_{\max}(A)\leq\sqrt{N}+\sqrt{n}+2t$, which yields the conclusion of Theorem 5.58 (the left hand side of (5.36) being trivial). So, it suffices to prove the conclusion for $t\leq C_{K}\sqrt{N}$. Let us fix such $t$.

It would be useful to have some a priori control of $s_{\max}(A)=\|A\|$. We thus consider the desired event

Since $3C_{K}\sqrt{N}\geq\sqrt{n}+C_{K}\sqrt{N}+t$, by (5.37) we see that $\mathcal{E}$ is likely to occur:

Step 2: Approximation. This step is parallel to Step 1 in the proof of Theorem 5.39, except now we shall choose $\varepsilon:=\delta$. This way we reduce our task to the following. Let $\mathcal{N}$ be a $\frac{1}{4}$-net of the unit sphere $S^{n-1}$ such that $|\mathcal{N}|\leq 9^{n}$. It suffices to show that with probability at least $1-2\exp(-c^{\prime}_{K}t^{2})$ one has

By (5.38), it is enough to show that the probability

satisfies $p\leq 2\exp(-c_{K}^{\prime\prime}t^{2})$, where $c_{K}^{\prime\prime}>0$ may depend only on $K$.

Step 3: Decoupling. As in the proof of Theorem 5.39, we will obtain the required bound for a fixed $x\in\mathcal{N}$ with high probability, and then take a union bound over $x$. So let us fix any $x=(x_{1},\ldots,x_{n})\in S^{n-1}$. We expand

Since $\|A_{j}\|_{2}^{2}=N$ by assumption and $\|x\|_{2}=1$, the first sum equals $N$. Therefore, subtracting $N$ from both sides and dividing by $N$, we obtain the bound

The sum in the right hand side is $\langle G_{0}x,x\rangle$ where $G_{0}$ is the off-diagonal part of the Gram matrix $G=A^{*}A$. As we indicated in the beginning of Section 5.5, we are going to replace $G_{0}$ by its decoupled version whose rows and columns are indexed by disjoint sets. This is achieved by Decoupling Lemma 5.60: we obtain

We substitute this into (5.39) and take union bound over all choices of $x\in\mathcal{N}$ and $T\subseteq[n]$. As we know, $|\mathcal{N}|\leq 9^{n}$, and there are $2^{n}$ subsets $T$ in $[n]$. This gives

Step 4: Conditioning and concentration. To estimate the probability in (5.5.1), we fix a vector $x\in\mathcal{N}$ and a subset $T\subseteq[n]$ and we condition on a realization of random vectors $(A_{k})_{k\in T^{c}}$. We express

Under our conditioning $z$ is a fixed vector, so $R_{T}(x)$ is a sum of independent random variables. Moreover, if event $\mathcal{E}$ holds then $z$ is nicely bounded:

If in turn (5.43) holds then the terms $\langle A_{j},z\rangle$ in (5.42) are independent centered sub-gaussian random variables with $\|\langle A_{j},z\rangle\|_{\psi_{2}}\leq 3KC_{K}\sqrt{N}$. By Lemma 5.9, their linear combination $R_{T}(x)$ is also a sub-gaussian random variable with

where $\widehat{C}_{K}$ depends only on $K$.

The second inequality follows because $R_{T}(x)$ is a sub-gaussian random variable (5.44) whose tail decay is given by (5.10). Here $c_{1},c_{2}>0$ are absolute constants. The last inequality follows from the definition of $\delta$. Substituting this into (5.5.1) and choosing $C$ sufficiently large (so that $\ln 36\leq c_{2}C^{2}/\widehat{C}_{K}^{2}$), we conclude that

This proves an estimate that we desired in Step 2. The proof is complete. ∎

Some a priori control of the norms of the columns $\|A_{j}\|_{2}$ is necessary for estimating the extreme singular values, since

With this in mind, it is easy to construct an example showing that a normalization assumption $\|A_{i}\|_{2}=\sqrt{N}$ is essential in Theorem 5.58; it can not even be replaced by a boundedness assumption $\|A_{i}\|_{2}=O(\sqrt{N})$.

5.2 Heavy-tailed columns

Here we prove a version of Theorem 5.45 for independent heavy-tailed columns.

We thus consider $N\times n$ random matrices $A$ with independent columns $A_{j}$. In addition to the normalization assumption $\|A_{j}\|_{2}=\sqrt{N}$ already present in Theorem 5.58 for sub-gaussian columns, our new result must also require an a priori control of the off-diagonal part of the Gram matrix $G=A^{*}A=(\langle A_{j},A_{k}\rangle)_{j,k=1}^{n}$.

Our proof of Theorem 5.62 will be based on decoupling, symmetrization and an application of Theorem 5.48 for a decoupled Gram matrix with independent rows. The decoupling is done similarly to Theorem 5.58. However, this time we will benefit from formalizing the decoupling inequality for Gram matrices:

Let $B$ be a $N\times n$ random matrix whose columns $B_{j}$ satisfy $\|B_{j}\|_{2}=1$. Then

We first note that \|B^{*}B-I\|=\sup_{x\in S^{n-1}}\big{|}\|Bx\|_{2}^{2}-1\big{|}. We fix $x=(x_{1},\ldots,x_{n})\in S^{n-1}$ and, expanding as in (5.40), observe that

The first sum equals $1$ since $\|B_{j}\|_{2}=\|x\|_{2}=1$. So by Decoupling Lemma 5.60, a random subset $T$ of $[n]$ with average cardinality $n/2$ satisfies

The conclusion follows by replacing the expectation by the maximum over $T$. ∎

Step 1: Reductions and decoupling. It would be useful to have an a priori bound on $s_{\max}(A)=\|A\|$. We can obtain this by transposing $A$ and applying one of the results of Section 5.4. Indeed, the random $n\times N$ matrix $A^{*}$ has independent rows $A_{i}^{*}$ which by our assumption are normalized as $\|A_{i}^{*}\|_{2}=\|A_{i}\|_{2}=\sqrt{N}$. Applying Theorem 5.45 with the roles of $n$ and $N$ switched, we obtain by the triangle inequality that

We use Matrix Decoupling Lemma 5.63 for $B=\frac{1}{\sqrt{N}}A$ and obtain

where $\Gamma=\Gamma(T)$ denotes the decoupled Gram matrix

Let us fix $T$; our problem then reduces to bounding the expected norm of $\Gamma$.

Let us condition on $A_{T^{c}}$. Treating $(A_{k})_{k\in T^{c}}$ as fixed vectors we see that, conditionally, the random matrix $\Gamma$ has independent rows

So we are going to use Theorem 5.48 to bound the norm of $\Gamma$. To do this we need estimates on (a) the norms and (b) the second moment matrices of the rows $\Gamma_{j}$.

(b) To evaluate the norms of $\Gamma_{j}$, $j\in T$, note that $\|\Gamma_{j}\|_{2}^{2}=\sum_{k\in T^{c}}\langle A_{j},A_{k}\rangle^{2}$. This is easy to bound, because the assumption says that the random variable

Step 3: The norm of the decoupled Gram matrix. We bound the norm of the random $T\times T^{c}$ Gram matrix $\Gamma$ with (conditionally) independent rows using Theorem 5.48 and Remark 5.49. Since by (5.48) we have \big{\|}\frac{1}{|T|}\sum_{j\in T}\Sigma(\Gamma_{j})\big{\|}\leq\frac{1}{|T|}\sum_{j\in T}\|\Sigma(\Gamma_{j})\|\leq\|A_{T^{c}}\|^{2}, we obtain using (5.49) that

The other term that will appear in the expectation of (5.5.2) is

So, taking the expectation in (5.5.2) and using these bounds, we obtain

where we used that $n\leq m$. Finally, using this estimate in (5.47) we conclude

This establishes the first part of Theorem 5.62. The second part follow by the diagonalization argument as in Step 2 of the proof of Theorem 5.45. ∎

6 Restricted isometries

In this section we consider an application of the non-asymptotic random matrix theory in compressed sensing. For a thorough introduction to compressed sensing, see the introductory chapter of this book and .

The interesting regime for compressed sensing is where we take very few measurements, $m\ll n$. Such matrices $A$ are not one-to-one, so recovery of $x$ from $y$ is not possible for all signals $x$. But in practical applications, the amount of “information” contained in the signal is often small. Mathematically this is expressed as sparsity of $x$. In the simplest case, one assumes that $x$ has few non-zero coordinates, say $|\operatorname{supp}(x)|\leq k\ll n$. In this case, using any non-degenerate matrix $A$ one can check that $x$ can be recovered whenever $m>2k$ using the optimization problem $\min\{|\operatorname{supp}(x)|:\;Ax=y\}$.

This optimization problem is highly non-convex and generally NP-complete. So instead one considers a convex relaxation of this problem, $\min\{\|x\|_{1}:\;Ax=y\}$. A basic result in compressed sensing, due to Candès and Tao , is that for sparse signals $|\operatorname{supp}(x)|\leq k$, the convex problem recovers the signal $x$ from its measurement $y$ exactly, provided that the measurement matrix $A$ is quantitatively non-degenerate. Precisely, the non-degeneracy of $A$ means that it satisfies the following restricted isometry property with $\delta_{2k}(A)\leq 0.1$.

An $m\times n$ matrix $A$ satisfies the restricted isometry property of order $k\geq 1$ if there exists $\delta_{k}\geq 0$ such that the inequality

In words, $A$ has a restricted isometry property if $A$ acts as an approximate isometry on all sparse vectors. Clearly,

where the maximum is over all subsets $T\subseteq[n]$ with $|T|\leq k$ or $|T|=\lfloor k\rfloor$.

The concept of restricted isometry can also be expressed via extreme singular values, which brings us to the topic we studied in the previous sections. $A$ is a restricted isometry if and only if all $m\times k$ sub-matrices $A_{T}$ of $A$ (obtained by selecting arbitrary $k$ columns from $A$) are approximate isometries. Indeed, for every $\delta\geq 0$, Lemma 5.36 shows that the following two inequalities are equivalent up to an absolute constant:

More precisely, (5.53) implies (5.54) and (5.54) implies $\delta_{k}(A)\leq 3\max(\delta,\delta^{2})$.

Our goal is thus to find matrices that are good restricted isometries. What good means is clear from the goals of compressed sensing described above. First, we need to keep the restricted isometry constant $\delta_{k}(A)$ below some small absolute constant, say $0.1$. Most importantly, we would like the number of measurements $m$ to be small, ideally proportional to the sparsity $k\ll n$.

This is where non-asymptotic random matrix theory enters. We shall indeed show that, with high probability, $m\times n$ random matrices $A$ are good restricted isometries of order $k$ with $m=O^{*}(k)$. Here the $O^{*}$ notation hides some logarithmic factors of $n$. Specifically, in Theorem 5.65 we will show that

for sub-gaussian random matrices $A$ (with independent rows or columns). This is due to the strong concentration properties of such matrices. A general observation of this kind is Proposition 5.66. It says that if for a given $x$, a random matrix $A$ (taken from any distribution) satisfies inequality (5.51) with high probability, then $A$ is a good restricted isometry.

In Theorem 5.71 we will extend these results to random matrices without concentration properties. Using a uniform extension of Rudelson’s inequality, Corollary 5.28, we shall show that

for heavy-tailed random matrices $A$ (with independent rows). This includes the important example of random Fourier matrices.

In this section we show that $m\times n$ sub-gaussian random matrices $A$ are good restricted isometries. We have in mind either of the following two models, which we analyzed in Sections 5.4.1 and 5.5.1 respectively:

Let $A$ be an $m\times n$ sub-gaussian random matrix with independent rows or columns, which follows either of the two models above. Then the normalized matrix $\bar{A}=\frac{1}{\sqrt{m}}A$ satisfies the following for every sparsity level $1\leq k\leq n$ and every number $\delta\in(0,1)$: