Lecture 8: The Smallest and Largest Singular Values
Nets, small-ball estimates, and rectangular random matrices
In the dimension reduction problem of Lecture 6 we took a random \(m\times n\) matrix \(A\) and showed that \(\|Ax\|_2/\sqrt m\) is close to \(\|x\|_2\) for every \(x\) in a finite set of vectors. This lecture asks what happens for every \(x\in\mathbb R^n\) at once. The answer is governed by the largest and smallest singular values of \(A\). For a tall matrix a net and a union bound suffice. When \(m\) is only a constant factor larger than \(n\), the union bound fails, and we need a new ingredient: estimates on the probability that \(\|Ax\|_2\) is small, called small-ball estimates.
Throughout, \(A=(\xi_{ij})\) is an \(m\times n\) matrix with \(m\geq n\), whose entries are i.i.d., mean-zero, of variance \(1\), and \(K\)-subgaussian. All constants \(c,C,C_0,\ldots\) depend only on \(K\) unless stated otherwise.
1 Singular values as extremal problems
Lecture 6 controlled \(\|Ax\|_2\) for one fixed vector. We restate that bound in the form used here.
Lemma 1 (One vector) There is a constant \(c>0\) such that, for every nonzero \(x\in\mathbb R^n\) and every \(t\geq0\), \[ \mathbb P\left\{\left|\frac{\|Ax\|_2}{\sqrt m}-\|x\|_2\right|>t\|x\|_2\right\} \leq2\exp\big(-cmt^2\big). \]
By homogeneity we may take \(\|x\|_2=1\). Exactly as in Lecture 6, the coordinates \((Ax)_j\) are i.i.d., mean-zero, \(K\)-subgaussian, and have second moment \(\|x\|_2^2=1\). Hence \(\|(Ax)_j^2\|_{\psi_1}\leq4K\), and Bernstein’s inequality gives, for every \(\varepsilon\geq0\), \[ \mathbb P\left\{\left|\frac{\|Ax\|_2^2}m-1\right|>\varepsilon\right\} \leq2\exp\big(-cm\min\{\varepsilon,\varepsilon^2\}\big). \] Write \(a=\|Ax\|_2/\sqrt m\geq0\) and suppose \(|a-1|>t\). If \(a>1+t\) then \(a^2-1>2t+t^2\geq\max\{t,t^2\}\). If \(a<1-t\), which forces \(t<1\), then \(1-a^2=(1-a)(1+a)>t=\max\{t,t^2\}\). In both cases \(|a^2-1|>\varepsilon\) with \(\varepsilon=\max\{t,t^2\}\), and \(\min\{\varepsilon,\varepsilon^2\}=t^2\).
Definition 1 (Extreme singular values) For an \(m\times n\) matrix \(A\), the largest singular value is \[ s_{\max}(A):=\sup_{\|x\|_2=1}\|Ax\|_2 =\sup_{\|x\|_2=\|y\|_2=1}\langle Ax,y\rangle =\|A\|_{\mathrm{op}}, \] the operator norm of \(A\) from \(\ell_2^n\) to \(\ell_2^m\). The smallest singular value is \[ s_{\min}(A):=\inf_{\|x\|_2=1}\|Ax\|_2 . \]
If \(n>m\), then \(A\) has a nontrivial kernel and \(s_{\min}(A)=0\). This is why we assume \(m\geq n\). With this convention, the statement \[ (1-\eta)\sqrt m\leq s_{\min}(A)\leq s_{\max}(A)\leq(1+\eta)\sqrt m \] says exactly that \(A/\sqrt m\) is an approximate isometry: it distorts the length of every vector by a factor at most \(1\pm\eta\).
2 Nets on the sphere
The passage from one vector to all vectors goes through a net of the unit sphere \(S^{n-1}\). Two facts are needed: nets are not too large, and a bound on a net transfers to the whole sphere at the price of the operator norm.
Lemma 2 (Nets of the sphere) Let \(0<\varepsilon\leq1\).
- \(S^{n-1}\) has an \(\varepsilon\)-net of cardinality at most \((3/\varepsilon)^n\).
- More generally, every subset \(T\subseteq S^{n-1}\) has an \(\varepsilon\)-net \(N\subseteq T\) of cardinality at most \((3/\varepsilon)^n\).
Let \(N\) be a maximal \(\varepsilon\)-separated subset of \(T\). By maximality \(N\) is an \(\varepsilon\)-net of \(T\), as in the covering–packing comparison of Lecture 1. The balls of radius \(\varepsilon/2\) around the points of \(N\) are disjoint and contained in \((1+\varepsilon/2)B_2^n\), so comparing volumes, \[ |N|\left(\frac\varepsilon2\right)^n\leq\left(1+\frac\varepsilon2\right)^n, \qquad\text{i.e.}\qquad |N|\leq\left(1+\frac2\varepsilon\right)^n\leq\left(\frac3\varepsilon\right)^n . \] This proves (2), and (1) is the case \(T=S^{n-1}\). Note that the bound on \(|N|\) used only that \(N\) is an \(\varepsilon\)-separated subset of the sphere, not what \(T\) is.
Lemma 3 (From a net to the sphere) Let \(N\) be an \(\varepsilon\)-net of \(S^{n-1}\) with \(\varepsilon\in(0,1)\), and let \(A\) be any \(m\times n\) matrix. Then \[ \|A\|_{\mathrm{op}}\leq\frac1{1-\varepsilon}\max_{y\in N}\|Ay\|_2 , \] and for every \(x\in S^{n-1}\) there is \(y\in N\) with \[ \big|\|Ax\|_2-\|Ay\|_2\big|\leq\varepsilon\|A\|_{\mathrm{op}} . \]
Given \(x\in S^{n-1}\), pick \(y\in N\) with \(\|x-y\|_2\leq\varepsilon\). By the triangle inequality, \[ \big|\|Ax\|_2-\|Ay\|_2\big|\leq\|A(x-y)\|_2\leq\varepsilon\|A\|_{\mathrm{op}} , \] which is the second claim. For the first, it gives \(\|Ax\|_2\leq\max_N\|Ay\|_2+\varepsilon\|A\|_{\mathrm{op}}\); take the supremum over \(x\) and rearrange.
3 Tall matrices: a straight union bound
Theorem 1 (Extreme singular values of a tall matrix) For every \(\eta\in(0,1)\) there are constants \(C_0,c>0\), depending only on \(K\) and \(\eta\), such that if \(m\geq C_0n\) then \[ \mathbb P\Big\{(1-\eta)\sqrt m\leq s_{\min}(A)\leq s_{\max}(A)\leq(1+\eta)\sqrt m\Big\} \geq1-2e^{-cm} . \]
Let \(\varepsilon=t=\eta/4\), and let \(N\) be an \(\varepsilon\)-net of \(S^{n-1}\) with \(|N|\leq(12/\eta)^n\). Consider the event \[ E=\left\{\left|\frac{\|Ay\|_2}{\sqrt m}-1\right|\leq t\ \text{ for every }y\in N\right\}. \] By Lemma 1 and a union bound, \[ \mathbb P\{E^c\}\leq2\left(\frac{12}\eta\right)^ne^{-cmt^2} =2\exp\Big(n\log\frac{12}\eta-\frac{cm\eta^2}{16}\Big) \leq2\exp\Big(-\frac{cm\eta^2}{32}\Big), \] where the last step holds once \(m\geq C_0n\) with \(C_0=32\log(12/\eta)/(c\eta^2)\).
On \(E\), the first part of Lemma 3 gives \[ \frac{\|A\|_{\mathrm{op}}}{\sqrt m}\leq\frac{1+t}{1-\varepsilon}. \] Now let \(x\in S^{n-1}\) be arbitrary. The second part of Lemma 3 provides \(y\in N\) with \[ \left|\frac{\|Ax\|_2}{\sqrt m}-1\right| \leq\left|\frac{\|Ay\|_2}{\sqrt m}-1\right|+\varepsilon\frac{\|A\|_{\mathrm{op}}}{\sqrt m} \leq t+\frac{\varepsilon(1+t)}{1-\varepsilon}. \] With \(\varepsilon=t=\eta/4\) the right-hand side is at most \(\eta/4+5\eta/12<\eta\). Taking the supremum and infimum over \(x\) gives the two-sided bound on the event \(E\).
The same net argument gives a bound on the operator norm that holds for every \(m\geq n\), with no requirement that \(m\) be much larger than \(n\). It is crude, but it is all the later arguments need.
Corollary 1 (A crude operator norm bound) There is a constant \(C_2\) such that, for every \(m\geq n\), \[ \mathbb P\big\{\|A\|_{\mathrm{op}}>C_2\sqrt m\big\}\leq2e^{-m}. \]
Take a \(\frac12\)-net \(N\) of \(S^{n-1}\) with \(|N|\leq6^n\), and choose \(t\) with \(ct^2=1+\log6\). By Lemma 1 and a union bound, \[ \mathbb P\Big\{\exists y\in N:\ \|Ay\|_2>(1+t)\sqrt m\Big\} \leq2\cdot6^ne^{-cmt^2}=2e^{n\log6-m(1+\log6)}\leq2e^{-m}, \] using \(n\leq m\). On the complementary event, Lemma 3 gives \(\|A\|_{\mathrm{op}}\leq2(1+t)\sqrt m\). Set \(C_2=2(1+t)\).
The true behavior of the extreme singular values is \[ \sqrt m-C\sqrt n\ \lesssim\ s_{\min}(A)\leq s_{\max}(A)\ \lesssim\ \sqrt m+C\sqrt n , \] so the distortion of \(A/\sqrt m\) is of order \(\sqrt{n/m}\) rather than the \(\eta\) produced above. We return to this sharper form later in the course.
The more serious limitation concerns the smallest singular value when \(m=(1+\eta)n\) for a fixed \(\eta>0\), or when \(m=n\). To show \(s_{\min}(A)\geq c\sqrt m\) by the argument above we need \(\|Ay\|_2\geq c\sqrt m\) for every \(y\) in a net of \((3/\varepsilon)^n\) points, and Lemma 1 bounds each failure probability by \(2e^{-c'm}\) at best. The union bound then requires \(c'(1+\eta)>\log(3/\varepsilon)\), which is false for small \(\eta\). The problem is not the net. It is that Lemma 1 treats the event \(\|Ay\|_2\leq c\sqrt m\) as a large deviation of size \(1\), whereas it is a much rarer event: \(\|Ay\|_2\) has to be small, not merely off by a constant. We need bounds that reflect this.
4 The Gaussian case: small-ball estimates
Suppose first that the entries of \(A\) are standard Gaussian. For a unit vector \(x\), the coordinates \((Ax)_j\) are i.i.d. \(N(0,1)\), so \(\|Ax\|_2^2\) is a sum of \(m\) independent squared standard Gaussians. The square \(Z^2\) of a standard Gaussian has density \[ \frac{e^{-s/2}}{\sqrt{2\pi s}}\qquad(s>0), \] which blows up only like \(s^{-1/2}\) at the origin. This mild singularity is what makes the following estimate work.
Proposition 1 (Gaussian small-ball estimate) Let \(Z_1,\ldots,Z_m\) be i.i.d. \(N(0,1)\). For every \(\varepsilon\in(0,1)\), \[ \mathbb P\Big\{\sum_{j=1}^mZ_j^2\leq\varepsilon m\Big\}\leq(e\varepsilon)^{m/2}. \]
For \(t>0\), a Gaussian integral gives \[ \mathbb Ee^{-tZ^2}=\frac1{\sqrt{1+2t}}. \] Chernoff’s method, applied to the lower tail, gives for every \(t>0\) \[ \mathbb P\Big\{\sum_jZ_j^2\leq\varepsilon m\Big\} \leq\mathbb E\exp\Big(-t\sum_jZ_j^2+t\varepsilon m\Big) =\Big[\frac{e^{t\varepsilon}}{\sqrt{1+2t}}\Big]^m . \] The exponent \(t\varepsilon-\frac12\log(1+2t)\) is minimized where \(\varepsilon=1/(1+2t)\), that is at \(t=(1/\varepsilon-1)/2>0\). There the bracket equals \[ e^{(1-\varepsilon)/2}\,\varepsilon^{1/2}\leq(e\varepsilon)^{1/2}. \]
The point is the rate in \(\varepsilon\). The probability that \(\|Ax\|_2^2\leq\varepsilon m\) is not merely exponentially small in \(m\); it is exponentially small with a constant that can be made as large as we like by shrinking \(\varepsilon\). That is exactly what a union bound over a net of exponential size needs.
The proof used only \(\mathbb Ee^{-tZ^2}\lesssim t^{-1/2}\) for large \(t\). If \(Y\) is any random variable whose density is bounded by \(B\), then \[ \mathbb Ee^{-tY^2}\leq\int_{-\infty}^\infty Be^{-ts^2}\,ds=B\sqrt{\pi/t}, \] and the same optimization gives \(\mathbb P\{\sum_jY_j^2\leq\varepsilon m\}\leq(CB^2\varepsilon)^{m/2}\) for i.i.d. copies \(Y_j\). So the Gaussian argument below extends, with little extra work, to matrices whose entries have a uniformly bounded density, provided one knows that \(\langle\text{row},x\rangle\) also has a bounded density for every unit \(x\). That this is so, with the density of the linear form bounded by \(\sqrt2B\), is a theorem of Rudelson and Vershynin (Rudelson and Vershynin 2015) resting on Ball’s cube-slicing inequality. For entries without a density, such as random signs, a new idea is needed, and it is the subject of the last two sections.
Theorem 2 (Smallest singular value, Gaussian case) Let \(A\) have i.i.d. \(N(0,1)\) entries and let \(m\geq(1+\eta)n\) for some \(\eta>0\). There is \(c_0>0\), depending only on \(\eta\), such that \[ \mathbb P\big\{s_{\min}(A)\leq c_0\sqrt m\big\}\leq3e^{-n}. \]
Let \(C_2\) be the constant of Corollary 1 and let \(\varepsilon\in(0,1)\) be a parameter to be chosen. Take an \(\varepsilon_0\)-net \(N\) of \(S^{n-1}\) with \[ \varepsilon_0=\frac{\sqrt\varepsilon}{2C_2}, \qquad |N|\leq\Big(\frac3{\varepsilon_0}\Big)^n=\Big(\frac{6C_2}{\sqrt\varepsilon}\Big)^n . \] For each \(y\in N\), \(\|Ay\|_2^2\) is a sum of \(m\) i.i.d. squared standard Gaussians, so by Proposition 1 and a union bound, \[ \mathbb P\Big\{\exists y\in N:\ \|Ay\|_2\leq\sqrt{\varepsilon m}\Big\} \leq\Big(\frac{6C_2}{\sqrt\varepsilon}\Big)^n(e\varepsilon)^{m/2} \leq\Big[6C_2\,e^{(1+\eta)/2}\,\varepsilon^{\eta/2}\Big]^n , \] using \(m\geq(1+\eta)n\) and \(e\varepsilon<1\) in the second step. Choose \(\varepsilon=\varepsilon(\eta)\) so small that the bracket is at most \(e^{-1}\); this makes the probability at most \(e^{-n}\).
On the complement of this event, intersected with \(\{\|A\|_{\mathrm{op}}\leq C_2\sqrt m\}\), every \(x\in S^{n-1}\) has a net point \(y\) with \(\|x-y\|_2\leq\varepsilon_0\), and \[ \|Ax\|_2\geq\|Ay\|_2-\|A\|_{\mathrm{op}}\varepsilon_0 \geq\sqrt{\varepsilon m}-C_2\sqrt m\cdot\frac{\sqrt\varepsilon}{2C_2} =\frac{\sqrt\varepsilon}2\sqrt m . \] So \(s_{\min}(A)\geq c_0\sqrt m\) with \(c_0=\sqrt\varepsilon/2\), and the exceptional probability is at most \(e^{-n}+2e^{-m}\leq3e^{-n}\).
Note where \(\eta>0\) entered: the net has \(e^{Cn}\) points, the small-ball probability is \(\varepsilon^{m/2}\), and the two balance in favor of the small-ball estimate only if \(m/2\) exceeds \(n/2\) by a definite margin. The square case \(m=n\) needs finer tools, and we return to it at the end of the course.
5 Small-ball estimates for sub-Gaussian entries
For general sub-Gaussian entries, \((Ax)_j=\sum_i\xi_{ji}x_i\) need not have a density at all. The replacement for the Gaussian computation is the central limit theorem in a quantitative form.
Theorem 3 (Berry–Esseen) Let \(Y_1,\ldots,Y_n\) be independent, mean-zero, with \(\sigma^2=\sum_i\mathbb EY_i^2\) and \(\sum_i\mathbb E|Y_i|^3<\infty\). Then \[ \sup_{s\in\mathbb R}\left|\mathbb P\Big\{\sum_{i=1}^nY_i\leq\sigma s\Big\}-\Phi(s)\right| \leq C_{\mathrm{BE}}\,\frac{\sum_i\mathbb E|Y_i|^3}{\sigma^3}, \] where \(\Phi\) is the standard normal distribution function and \(C_{\mathrm{BE}}\) is an absolute constant.
We use this without proof. For a linear form in i.i.d. variables it gives a small-ball estimate that is uniform in the center.
Proposition 2 (Small-ball estimate for a linear form) Let \(\xi_1,\ldots,\xi_n\) be i.i.d., mean-zero, of variance \(1\), with \(\mu_3:=\mathbb E|\xi_1|^3<\infty\). For every nonzero \(x\in\mathbb R^n\), every \(a\in\mathbb R\), and every \(t\geq0\), \[ \mathbb P\Big\{\Big|\sum_{i=1}^n\xi_ix_i-a\Big|\leq t\Big\} \leq\sqrt{\frac2\pi}\,\frac t{\|x\|_2}+\rho(x), \qquad \rho(x):=2C_{\mathrm{BE}}\,\mu_3\,\frac{\|x\|_3^3}{\|x\|_2^3}. \]
Apply Theorem 3 to \(Y_i=\xi_ix_i\), for which \(\sigma=\|x\|_2\) and \(\sum_i\mathbb E|Y_i|^3=\mu_3\|x\|_3^3\). Writing \(S=\sum_i\xi_ix_i\), \[ \begin{aligned} \mathbb P\{|S-a|\leq t\} &\leq\mathbb P\{S\leq a+t\}-\mathbb P\{S<a-t\}\\ &\leq\Phi\Big(\frac{a+t}{\|x\|_2}\Big)-\Phi\Big(\frac{a-t}{\|x\|_2}\Big)+2C_{\mathrm{BE}}\,\mu_3\frac{\|x\|_3^3}{\|x\|_2^3}. \end{aligned} \] The density of \(\Phi\) is at most \(1/\sqrt{2\pi}\), so the difference of the two values of \(\Phi\) is at most \(2t/(\sqrt{2\pi}\|x\|_2)\).
The first term is what a Gaussian with the same variance would give. The second is the Berry–Esseen error, and it is small exactly when \(\|x\|_3\ll\|x\|_2\), that is, when \(x\) is spread over many coordinates. Compare the flatness condition of Lecture 7: for a vector with \(k\) equal nonzero coordinates, \(\|x\|_2/\|x\|_3=k^{1/6}\).
Now pass to the Laplace transform, as in the Gaussian case.
Corollary 2 (Laplace transform of a squared linear form) In the setting of Proposition 2, for every \(a\in\mathbb R\) and \(\lambda>0\), \[ \mathbb E\exp\Big(-\lambda\Big(\sum_{i=1}^n\xi_ix_i-a\Big)^2\Big) \leq\frac1{\|x\|_2\sqrt{2\lambda}}+\rho(x). \] In particular, if \(\lambda\leq\lambda_0(x):=\dfrac1{2\|x\|_2^2\rho(x)^2}\), then \[ \mathbb E\exp\Big(-\lambda\Big(\sum_{i=1}^n\xi_ix_i-a\Big)^2\Big) \leq\frac{\sqrt2}{\|x\|_2\sqrt\lambda}. \]
For a nonnegative random variable \(Y\), writing \(e^{-\lambda Y}=\int_Y^\infty\lambda e^{-\lambda s}\,ds\) and using Tonelli, \[ \mathbb Ee^{-\lambda Y}=\int_0^\infty\lambda e^{-\lambda s}\,\mathbb P\{Y\leq s\}\,ds . \] Take \(Y=(\sum_i\xi_ix_i-a)^2\), so that \(\{Y\leq s\}=\{|\sum_i\xi_ix_i-a|\leq\sqrt s\}\), and insert Proposition 2: \[ \mathbb Ee^{-\lambda Y} \leq\sqrt{\frac2\pi}\,\frac1{\|x\|_2}\int_0^\infty\lambda e^{-\lambda s}\sqrt s\,ds+\rho(x) =\sqrt{\frac2\pi}\,\frac1{\|x\|_2}\cdot\frac{\sqrt\pi}{2\sqrt\lambda}+\rho(x), \] using \(\int_0^\infty\lambda e^{-\lambda s}\sqrt s\,ds=\Gamma(3/2)\lambda^{-1/2}\). This is the first bound. If \(\lambda\leq\lambda_0(x)\) then \(\rho(x)\leq1/(\|x\|_2\sqrt{2\lambda})\), and the two terms together are at most \(2/(\|x\|_2\sqrt{2\lambda})\).
For comparison, a Gaussian linear form with the same variance has \(\mathbb Ee^{-\lambda(\cdot)^2}=(1+2\lambda\|x\|_2^2)^{-1/2}\), which is also of order \(1/(\|x\|_2\sqrt\lambda)\) for large \(\lambda\). So for \(\lambda\leq\lambda_0(x)\) the sub-Gaussian linear form has the same Laplace transform as a Gaussian, up to a factor \(\sqrt2\), and the window \(\lambda\leq\lambda_0(x)\) is large exactly when \(x\) is spread out.
The uniformity in the center \(a\) is what allows the next statement to control \(\|Ax\|_2\) using only a subset of the coordinates of \(x\).
Corollary 3 (Small-ball estimate for spread vectors) There is an absolute constant \(C\) such that the following holds. Let \(x\in\mathbb R^n\) and let \(S\subseteq\{1,\ldots,n\}\) with \(x_S\neq0\), where \(x_S\) denotes the restriction of \(x\) to the coordinates in \(S\). For every \(\varepsilon\in(0,1)\), if \[ \frac{\|x_S\|_2}{\|x_S\|_3}\geq M(\varepsilon):=\Big(\frac{8C_{\mathrm{BE}}^2\mu_3^2}\varepsilon\Big)^{1/6}, \] then \[ \mathbb P\Big\{\|Ax\|_2^2\leq\varepsilon m\|x_S\|_2^2\Big\}\leq(C\varepsilon)^{m/2}. \]
Set \(\lambda=1/(\varepsilon\|x_S\|_2^2)\). The hypothesis on \(\|x_S\|_2/\|x_S\|_3\) says precisely that \(\rho(x_S)^2\leq\varepsilon/2\), which is the condition \(\lambda\leq\lambda_0(x_S)\).
Fix a row \(j\) and split \((Ax)_j\) according to \(S\): \[ (Ax)_j=\sum_{i\in S}\xi_{ji}x_i+a_j, \qquad a_j:=\sum_{i\notin S}\xi_{ji}x_i . \] The two pieces are independent. Conditioning on \(a_j\) and applying Corollary 2 to the vector \(x_S\) with center \(-a_j\), \[ \mathbb E\big[e^{-\lambda(Ax)_j^2}\,\big|\,a_j\big]\leq\frac{\sqrt2}{\|x_S\|_2\sqrt\lambda}=\sqrt{2\varepsilon}. \] The rows are independent, so \(\mathbb Ee^{-\lambda\|Ax\|_2^2}\leq(2\varepsilon)^{m/2}\), and Chernoff’s method for the lower tail gives \[ \mathbb P\Big\{\|Ax\|_2^2\leq\varepsilon m\|x_S\|_2^2\Big\} \leq e^{\lambda\varepsilon m\|x_S\|_2^2}\,\mathbb Ee^{-\lambda\|Ax\|_2^2} \leq e^m(2\varepsilon)^{m/2}=(2e^2\varepsilon)^{m/2}. \]
6 The Litvak–Pajor–Rudelson–Tomczak-Jaegermann theorem
Theorem 4 (Smallest singular value of a rectangular sub-Gaussian matrix) Let \(A=(\xi_{ij})\) be \(m\times n\) with i.i.d., mean-zero, variance-\(1\), \(K\)-subgaussian entries, and let \(m\geq(1+\eta)n\) for some \(\eta>0\). There are constants \(c_0,c>0\) and \(n_0\), depending only on \(K\) and \(\eta\), such that for all \(n\geq n_0\), \[ \mathbb P\big\{s_{\min}(A)\leq c_0\sqrt m\big\}\leq e^{-cn}. \]
This is due to Litvak, Pajor, Rudelson and Tomczak-Jaegermann (Litvak et al. 2005). The proof follows the Gaussian template, but the small-ball estimate of Corollary 3 is only available for spread vectors. The vectors that are not spread turn out to be nearly sparse, and for those a much smaller net suffices.
Step 0: parameters. Let \(c\) be the constant of Lemma 1 and \(C_2\) that of Corollary 1. Fix \[ \delta:=\frac1{16C_2}, \qquad \varepsilon_2:=\frac1{8C_2}. \] Let \(C\) be the constant of Corollary 3 and choose \(\varepsilon_1\in(0,1/C)\) so small that \[ \frac{6C_2}{\delta}\,C^{(1+\eta)/2}\,\varepsilon_1^{\eta/2}\leq e^{-1}. \] Then set \(M:=M(\varepsilon_1)\) as in Corollary 3, and \(k:=\lceil(M/\delta)^6\rceil\). All of these depend only on \(K\) and \(\eta\). Throughout we work on the event \(\{\|A\|_{\mathrm{op}}\leq C_2\sqrt m\}\), whose complement has probability at most \(2e^{-m}\).
Step 1: the partition. Call \(x\in S^{n-1}\) spread if there is a set \(S\subseteq\{1,\ldots,n\}\) with \[ \|x_S\|_2\geq\delta \qquad\text{and}\qquad \frac{\|x_S\|_2}{\|x_S\|_3}\geq M , \] and compressible otherwise. Write \(\mathcal S\) for the spread vectors and \(\mathcal E=S^{n-1}\setminus\mathcal S\) for the compressible ones.
Step 2: spread vectors. Let \[ \varepsilon_0:=\frac{\sqrt{\varepsilon_1}\,\delta}{2C_2} \] and let \(N_{\mathcal S}\subseteq\mathcal S\) be an \(\varepsilon_0\)-net of \(\mathcal S\) with \(|N_{\mathcal S}|\leq(3/\varepsilon_0)^n\), which exists by Lemma 2. Each \(y\in N_{\mathcal S}\) is spread, so Corollary 3 applies to it with its witnessing set \(S\) and \(\varepsilon=\varepsilon_1\), and \(\|y_S\|_2\geq\delta\) gives \[ \mathbb P\Big\{\|Ay\|_2\leq\sqrt{\varepsilon_1m}\,\delta\Big\} \leq\mathbb P\Big\{\|Ay\|_2^2\leq\varepsilon_1m\|y_S\|_2^2\Big\} \leq(C\varepsilon_1)^{m/2}. \] A union bound over the net, together with \(m\geq(1+\eta)n\) and \(C\varepsilon_1<1\), gives \[ \mathbb P\Big\{\exists y\in N_{\mathcal S}:\ \|Ay\|_2\leq\sqrt{\varepsilon_1m}\,\delta\Big\} \leq\Big(\frac{6C_2}{\sqrt{\varepsilon_1}\,\delta}\Big)^n(C\varepsilon_1)^{(1+\eta)n/2} =\Big[\frac{6C_2}\delta\,C^{(1+\eta)/2}\,\varepsilon_1^{\eta/2}\Big]^n \leq e^{-n} \] by the choice of \(\varepsilon_1\). On the complementary event, every \(x\in\mathcal S\) has a net point \(y\) with \(\|x-y\|_2\leq\varepsilon_0\), and \[ \|Ax\|_2\geq\|Ay\|_2-C_2\sqrt m\,\varepsilon_0 \geq\sqrt{\varepsilon_1m}\,\delta-\frac{\sqrt{\varepsilon_1m}\,\delta}2 =\frac{\sqrt{\varepsilon_1}\,\delta}2\sqrt m . \]
Step 3: compressible vectors are nearly sparse. Let \(x\in\mathcal E\). Split its coordinates into big and small ones, \[ B:=\Big\{i:|x_i|\geq\frac{\delta^3}{M^3}\Big\}, \qquad S:=B^c . \] We claim \(\|x_S\|_2<\delta\). Otherwise \(\|x_S\|_2\geq\delta\), and since \(x\) is not spread, \(\|x_S\|_2<M\|x_S\|_3\). But every coordinate of \(x_S\) is smaller than \(\delta^3/M^3\), so \[ \|x_S\|_3^3\leq\max_{i\in S}|x_i|\cdot\|x_S\|_2^2<\frac{\delta^3}{M^3}, \qquad\text{hence}\qquad \|x_S\|_2<M\|x_S\|_3<\delta , \] a contradiction. Next, every coordinate in \(B\) contributes at least \(\delta^6/M^6\) to \(\|x\|_2^2=1\), so \[ |B|\leq\frac{M^6}{\delta^6}\leq k . \] Finally, \(\|x_B\|_2^2=1-\|x_S\|_2^2>1-\delta^2\), and the unit vector \(y:=x_B/\|x_B\|_2\) is supported on at most \(k\) coordinates with \[ \|x-y\|_2\leq\|x_S\|_2+\big(1-\|x_B\|_2\big)\leq\delta+\delta^2\leq2\delta . \] So every compressible vector is within \(2\delta\) of a \(k\)-sparse unit vector.
Step 4: sparse vectors. Let \(\mathrm{Sparse}(k)\) be the set of unit vectors with at most \(k\) nonzero coordinates. It is a union of \(\binom nk\) spheres of dimension \(k-1\), one for each coordinate subset, so by Lemma 2 it has an \(\varepsilon_2\)-net \(N_k\) with \[ |N_k|\leq\binom nk\Big(\frac3{\varepsilon_2}\Big)^k\leq\Big(\frac{en}k\Big)^k(24C_2)^k . \] For each \(z\in N_k\), Lemma 1 with \(t=\frac12\) gives \(\mathbb P\{\|Az\|_2\leq\frac12\sqrt m\}\leq2e^{-cm/4}\), so \[ \mathbb P\Big\{\exists z\in N_k:\ \|Az\|_2\leq\tfrac12\sqrt m\Big\} \leq2\Big(\frac{en}k\Big)^k(24C_2)^ke^{-cm/4} \leq2e^{-cm/8} \] for \(n\geq n_0(K,\eta)\), since \(k\) is a constant and the prefactor grows only polynomially in \(n\). On the complementary event, take \(x\in\mathcal E\), a \(k\)-sparse unit vector \(y\) with \(\|x-y\|_2\leq2\delta\) from Step 3, and \(z\in N_k\) with \(\|y-z\|_2\leq\varepsilon_2\). Then \[ \|Ax\|_2\geq\|Az\|_2-C_2\sqrt m\,(2\delta+\varepsilon_2) \geq\Big(\frac12-\frac18-\frac18\Big)\sqrt m=\frac{\sqrt m}4 . \]
Step 5: conclusion. Outside an event of probability at most \[ 2e^{-m}+e^{-n}+2e^{-cm/8}\leq e^{-c'n}, \] every \(x\in S^{n-1}\), spread or compressible, satisfies \(\|Ax\|_2\geq c_0\sqrt m\) with \(c_0=\min\{\sqrt{\varepsilon_1}\,\delta/2,\ 1/4\}\).
The two halves of the proof use the two different kinds of probability bound we have. Spread vectors have a small-ball estimate with an arbitrarily good rate in \(\varepsilon\), which pays for a net of the full sphere. Compressible vectors have no such estimate, but they live near a set of sparse vectors whose net is tiny, so the crude bound of Lemma 1 is enough. Dividing the sphere according to how flat its vectors are is a recurring device, and it returns when we study the square case \(m=n\).
7 Where we go next
We have now seen the three basic tools for random matrices: nets, the one-vector concentration bound, and small-ball estimates. The next lectures sharpen the tall-matrix result to the form \(\sqrt m\pm C\sqrt n\) and use random matrices in a first optimization application, before Gaussian matrices are treated in their own right.