Lecture 13: Gaussian Width Revisited
Sparse vectors, random projections, and random cones
Lecture 3 introduced the Gaussian width \(w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle\) as a measure of the size of a set, computed it for a few standard sets, and left two things unfinished: the width of the set of sparse vectors, and the proof of Sudakov’s minoration. Lecture 12 supplied the proof. This lecture uses the tools of Lectures 10 through 12 to finish the sparse example and then to show what Gaussian width is for. It governs the size of a random projection of a set, with a phase transition at a dimension-like quantity built from the width, and it governs whether two randomly rotated cones intersect. In both problems the ambient dimension is the wrong parameter and the width is the right one.
Throughout, \(g\sim N(0,I_n)\) and \(w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle\) for bounded \(T\subseteq\mathbb R^n\). Recall from Lecture 3 that \(w(T)=w(\operatorname{conv}T)\) and \(w(T-T)=2w(T)\), and from Lecture 12 that Sudakov’s minoration reads \[ \log N(T,\varepsilon)\leq\frac{C\,w(T)^2}{\varepsilon^2} \qquad(\varepsilon>0). \]
1 Sparse vectors
Let \(1\leq s\leq n\) and let \[ U_s:=\{x\in\mathbb R^n:\|x\|_2\leq1,\ |\operatorname{supp}x|\leq s\} \] be the set of \(s\)-sparse vectors in the unit ball. Lecture 3 claimed \(w(U_s)\asymp\sqrt{s\log(en/s)}\) and observed that \(U_s\) is neither finite nor convex, so that neither tool available then applied. Both bounds are now within reach.
Proposition 1 (Width of the sparse vectors) There are absolute constants \(c,C>0\) such that, for \(1\leq s\leq n/2\) with \(n/s\) larger than an absolute constant, \[ c\sqrt{s\log(en/s)}\leq w(U_s)\leq C\sqrt{s\log(en/s)} . \]
Upper bound. This is Problem 4 of Exercise Sheet 3. The supremum over \(U_s\) is \(\max_{|S|=s}\|g_S\|_2\), a maximum over \(\binom ns\) chi variables, and the exponential-moment argument of Lecture 3 for finite sets, applied to the squares, gives \(\mathbb E\max_S\|g_S\|_2^2\leq Cs\log(en/s)\). Jensen’s inequality finishes.
Lower bound. The packing lemma of Lecture 2 provides a family \(X\) of \(s\)-element subsets of \(\{1,\ldots,n\}\) with \(|I\triangle J|\geq s/2\) for distinct \(I,J\in X\) and \(\log|X|\gtrsim s\log(n/s)\). The unit vectors \(x_I:=s^{-1/2}\sum_{i\in I}e_i\) lie in \(U_s\) and satisfy \[ \|x_I-x_J\|_2^2=\frac{|I\triangle J|}s\geq\frac12 , \] so they form a \(2^{-1/2}\)-separated subset of \(U_s\), and \(\log N(U_s,\tfrac12)\geq\log|X|\gtrsim s\log(n/s)\). Sudakov’s minoration with \(\varepsilon=\frac12\) gives \(w(U_s)\geq c\sqrt{s\log(n/s)}\), and \(\log(n/s)\asymp\log(en/s)\) in the stated range.
The lower bound is a first instance of Sudakov’s inequality being sharp: the entropy at the single scale \(\varepsilon=\frac12\) already accounts for the whole width. Compare the \(\ell^p\) balls of Lecture 12, where Sudakov is sharp at \(p=1\) and far from sharp for \(p>2\).
2 Random projections of sets
Let \(G\) be an \(m\times n\) matrix with independent \(N(0,1)\) entries and let \(T\subseteq\mathbb R^n\) be bounded. The Johnson–Lindenstrauss lemma of Lecture 6 says that if \(T\) is finite and \(m\gtrsim\log|T|\), then \(G/\sqrt m\) acts on \(T\) as an approximate isometry, so in particular \(\operatorname{diam}(GT)\approx\sqrt m\operatorname{diam}(T)\). For \(T=B_2^n\) nothing of the kind can hold when \(m<n\), since then \(\operatorname{diam}(GB_2^n)=2\|G\|_{\mathrm{op}}\approx2(\sqrt m+\sqrt n)\) is dominated by \(\sqrt n\), a quantity that does not shrink with \(m\). What happens in between is decided by the Gaussian width.
Theorem 1 (Diameter of a random projection) There are absolute constants \(c,C>0\) such that, for every bounded \(T\subseteq\mathbb R^n\) and every \(m\geq1\), \[ c\big(w(T)+\sqrt m\operatorname{diam}(T)\big) \leq\mathbb E\operatorname{diam}(GT) \leq C\big(w(T)+\sqrt m\operatorname{diam}(T)\big). \] Moreover, with probability at least \(1-e^{-m}\), \[ \operatorname{diam}(GT)\leq4w(T)+C\sqrt m\operatorname{diam}(T). \]
Write \(D=\operatorname{diam}(T)\) and \(T'=T-T\), so that \(\sup_{x\in T'}\|x\|_2=D\) and \(w(T')=2w(T)\).
Upper bound, reduction to a net. For \(z\in\mathbb R^m\) define \[ \varphi(z):=\sup_{x\in T'}\langle Gx,z\rangle=\sup_{x\in T'}\langle G^{\mathsf T}z,x\rangle , \] so that \[ \operatorname{diam}(GT)=\sup_{x\in T'}\|Gx\|_2=\sup_{z\in S^{m-1}}\varphi(z). \] Since \(T'\) is symmetric, \(\varphi\) is a seminorm on \(\mathbb R^m\), and the net argument of Lecture 8 applies to it: if \(N\) is a \(\frac12\)-net of \(S^{m-1}\) then \(\varphi(z)\leq\varphi(y)+\varphi(z-y)\leq\max_N\varphi+\frac12\sup_{S^{m-1}}\varphi\) for a net point \(y\) within \(\frac12\) of \(z\), hence \[ \sup_{z\in S^{m-1}}\varphi(z)\leq2\max_{y\in N}\varphi(y), \qquad|N|\leq6^m . \]
Upper bound, one direction. Fix \(y\in S^{m-1}\). By rotation invariance, \(G^{\mathsf T}y\sim N(0,I_n)\), so \[ \mathbb E\varphi(y)=\mathbb E\sup_{x\in T'}\langle G^{\mathsf T}y,x\rangle=w(T')=2w(T). \] As a function of the \(mn\) Gaussian entries of \(G\), \(\varphi(y)\) is a supremum of linear functions and hence Lipschitz with constant \[ \sup_{x\in T'}\|xy^{\mathsf T}\|_F=\sup_{x\in T'}\|x\|_2=D , \] because \(\langle Gx,y\rangle=\langle G,yx^{\mathsf T}\rangle_F\). Gaussian concentration (Lecture 11) gives, for \(u\geq0\), \[ \mathbb P\{\varphi(y)\geq2w(T)+u\}\leq e^{-u^2/(2D^2)}. \]
Upper bound, union bound. Over the net, \[ \mathbb P\Big\{\max_{y\in N}\varphi(y)\geq2w(T)+u\Big\}\leq6^me^{-u^2/(2D^2)}\leq e^{-m} \] once \(u=C_0\sqrt m\,D\) with \(C_0^2/2\geq1+\log6\). On the complementary event, \(\operatorname{diam}(GT)\leq2(2w(T)+C_0\sqrt mD)\), which is the high-probability claim. The bound in expectation follows by integrating the tail: for \(u\geq C_0\sqrt mD\) the same computation gives \(\mathbb P\{\operatorname{diam}(GT)\geq4w(T)+2u\}\leq6^me^{-u^2/(2D^2)}\), and \[ \mathbb E\operatorname{diam}(GT)\leq4w(T)+2C_0\sqrt mD+2\int_{C_0\sqrt mD}^\infty6^me^{-u^2/(2D^2)}\,du \leq4w(T)+C\sqrt mD . \]
Lower bound. Two different pairs of points witness the two terms. For the width, restrict attention to the first coordinate of \(Gx\): the first row \(G_1\) of \(G\) is \(N(0,I_n)\), and \[ \mathbb E\operatorname{diam}(GT)=\mathbb E\sup_{x\in T'}\|Gx\|_2 \geq\mathbb E\sup_{x\in T'}\langle G_1,x\rangle=w(T')=2w(T). \] For the diameter, fix \(x\in T'\). Then \(Gx\sim N(0,\|x\|_2^2I_m)\), so by Lecture 3 \[ \mathbb E\operatorname{diam}(GT)\geq\mathbb E\|Gx\|_2=\|x\|_2\,\mathbb E\|h\|_2\geq c_1\sqrt m\,\|x\|_2 , \qquad h\sim N(0,I_m), \] and taking the supremum over \(x\in T'\) gives \(\mathbb E\operatorname{diam}(GT)\geq c_1\sqrt mD\). Averaging the two lower bounds gives the claim with \(c=\min\{1,c_1\}/2\).
The proof has the same shape as the sharp bound on \(\|G\|_{\mathrm{op}}\) in Lecture 12, and indeed \(T=B_2^n\) recovers it up to constants. There the supremum over the sphere \(S^{n-1}\) was handled by comparison; here the supremum over the general set \(T'\) is handled by concentration around the width, and only the supremum over the target sphere \(S^{m-1}\) needs a net. The net costs \(6^m\), which is exactly what makes \(\sqrt m\) the price of the target dimension.
2.1 The phase transition
Write the theorem as \[ \mathbb E\operatorname{diam}(GT)\asymp\max\Big\{w(T),\ \sqrt m\operatorname{diam}(T)\Big\}. \] The two terms balance when \(m\asymp w(T)^2/\operatorname{diam}(T)^2\).
Definition 1 (Stable dimension) The stable dimension of a bounded set \(T\subseteq\mathbb R^n\) is \[ d(T):=\frac{w(T)^2}{\operatorname{diam}(T)^2}. \]
In these terms:
- If \(m\gtrsim d(T)\), then \(\mathbb E\operatorname{diam}(GT)\asymp\sqrt m\operatorname{diam}(T)\). The projection behaves like the scaled isometry \(\sqrt m\cdot I\) on the diameter of \(T\), as it does for a finite set in the Johnson–Lindenstrauss regime.
- If \(m\lesssim d(T)\), then \(\mathbb E\operatorname{diam}(GT)\asymp w(T)\). The image is no smaller than the width of \(T\) no matter how few dimensions are kept. Projecting into fewer than \(d(T)\) dimensions does not compress the set any further.
The name is justified by two facts. First, \(d(T)\leq\dim T\), where \(\dim T\) is the dimension of the affine span of \(T\): if \(T\) lies in a \(k\)-dimensional subspace, then \(T-T\) lies in \(\operatorname{diam}(T)\cdot B_2^k\) up to a rotation, so \(2w(T)=w(T-T)\leq\operatorname{diam}(T)\,\mathbb E\|g'\|_2\leq\operatorname{diam}(T)\sqrt k\) with \(g'\sim N(0,I_k)\), and \(d(T)\leq k/4\). Second, \(d(T)\) is stable under perturbation of \(T\) in a way that the algebraic dimension is not: shrinking one axis of \(B_2^n\) to zero drops \(\dim\) from \(n\) to \(n-1\) only at the last instant, while \(d\) decreases continuously. For a finite set, \(d(T)\lesssim\log|T|\) by the finite-set bound of Lecture 3, which is the Johnson–Lindenstrauss dimension again.
The theorem is stated for a Gaussian matrix, which is not a projection. If \(P\) is the orthogonal projection onto a uniformly random \(m\)-dimensional subspace of \(\mathbb R^n\), then \(\|Px\|_2\) has the law of \(\|Qx\|_2\), where \(Q\) consists of the first \(m\) rows of a Haar-distributed orthogonal matrix. The rows of \(Q\) are orthonormal, while the rows of \(G/\sqrt n\) are only approximately so; running the proof above with \(Q\) in place of \(G\), and using the spherical concentration inequality of Lecture 11 in place of the Gaussian one, gives \[ \mathbb E\operatorname{diam}(PT)\asymp\frac{w(T)}{\sqrt n}+\sqrt{\frac mn}\operatorname{diam}(T), \] with the same phase transition at \(m\asymp d(T)\). The quantity \(w(T)/\sqrt n\) is the spherical width of \(T\), the expected width in a uniformly random direction. We do not carry out the reduction here.
3 Overlap of random cones
The second application replaces sets by cones and projection by rotation. A closed convex cone is a closed convex set \(K\subseteq\mathbb R^n\) with \(\lambda K\subseteq K\) for all \(\lambda\geq0\). Let \(Q\) be a Haar distributed random orthogonal matrix, so that \(QC\) is a uniformly random rotation of a cone \(C\). Two cones in general position intersect only at the origin if they are small, and along a nontrivial set if they are large. The question is what “small” and “large” mean, and the answer is a width.
Lemma 1 (Projection onto a cone) Let \(C\) be a closed convex cone and let \(\Pi_C(x)\) denote the nearest point of \(C\) to \(x\). Then \[ \|\Pi_C(x)\|_2=\sup_{y\in C,\ \|y\|_2\leq1}\langle y,x\rangle . \]
Write \(p=\Pi_C(x)\). The nearest-point characterization for a closed convex set gives \(\langle x-p,y-p\rangle\leq0\) for all \(y\in C\). Taking \(y=2p\) and \(y=0\), both in \(C\) because \(C\) is a cone, gives \(\langle x-p,p\rangle=0\), and then \(\langle x-p,y\rangle\leq0\) for all \(y\in C\). Hence for \(y\in C\) with \(\|y\|_2\leq1\), \[ \langle y,x\rangle=\langle y,p\rangle+\langle y,x-p\rangle\leq\langle y,p\rangle\leq\|p\|_2 , \] with equality at \(y=p/\|p\|_2\) when \(p\neq0\). If \(p=0\) both sides vanish.
Definition 2 (Statistical dimension) The statistical dimension of a closed convex cone \(C\subseteq\mathbb R^n\) is \[ \delta(C):=\mathbb E\|\Pi_C(g)\|_2^2=\mathbb E\Big(\sup_{y\in C\cap B_2^n}\langle y,g\rangle\Big)^2 . \]
This is a squared Gaussian width, up to an additive constant.
Lemma 2 (Statistical dimension and width) For every closed convex cone \(C\subseteq\mathbb R^n\), \[ w(C\cap B_2^n)^2\leq\delta(C)\leq\big(w(C\cap B_2^n)+2\big)^2 . \]
Let \(Z=\sup_{y\in C\cap B_2^n}\langle y,g\rangle\), so \(\mathbb EZ=w(C\cap B_2^n)\) and \(\delta(C)=\mathbb EZ^2\). The lower bound is Jensen. For the upper bound, \(Z\) is the support function of a set of radius \(1\), hence \(1\)-Lipschitz in \(g\), and Gaussian concentration (Lecture 11) gives \[ \operatorname{Var}Z=\int_0^\infty2t\,\mathbb P\{|Z-\mathbb EZ|\geq t\}\,dt \leq\int_0^\infty4te^{-t^2/2}\,dt=4 . \] Hence \(\mathbb EZ^2=\operatorname{Var}Z+(\mathbb EZ)^2\leq(\mathbb EZ)^2+4\leq(\mathbb EZ+2)^2\). The Gaussian Poincaré inequality, which we do not prove, gives \(\operatorname{Var}Z\leq1\) and hence the sharper bound \((w(C\cap B_2^n)+1)^2\).
Some examples. A linear subspace \(E\) of dimension \(k\) is a cone with \(\delta(E)=\mathbb E\|\Pi_Eg\|_2^2=k\), so statistical dimension extends linear dimension. The nonnegative orthant \(\mathbb R^n_{\geq0}\) has \(\Pi(g)=(g_i^+)_i\) and \(\delta=n/2\). A circular cone of half-angle \(\theta\) has \(\delta\approx n\sin^2\theta\). In each case \(\delta(C)\) is the dimension of the subspace that the cone most resembles.
Theorem 2 (Approximate kinematic formula) There is an absolute constant \(C\) such that for all closed convex cones \(K,C\subseteq\mathbb R^n\), all \(\eta\in(0,1)\), and \(Q\) Haar orthogonal, \[ \delta(K)+\delta(C)\leq n-C\sqrt{n\log(1/\eta)} \quad\Longrightarrow\quad \mathbb P\{K\cap QC\neq\{0\}\}\leq\eta , \] \[ \delta(K)+\delta(C)\geq n+C\sqrt{n\log(1/\eta)} \quad\Longrightarrow\quad \mathbb P\{K\cap QC\neq\{0\}\}\geq1-\eta . \]
This is due to Amelunxen, Lotz, McCoy and Tropp (Amelunxen et al. 2014), and we state it without proof. Its content is that a randomly rotated pair of cones behaves like a pair of subspaces of dimensions \(\delta(K)\) and \(\delta(C)\). Two subspaces in general position intersect nontrivially if and only if their dimensions add up to more than \(n\), and the theorem says the same is true of cones, with statistical dimension in place of dimension and a transition window of width \(\sqrt n\) around the threshold. Since the window is of order \(\sqrt n\) while the dimensions are of order \(n\), the transition is sharp: for a family of cones with \((\delta(K)+\delta(C))/n\to\rho\), the intersection is trivial with probability tending to \(1\) if \(\rho<1\) and nontrivial with probability tending to \(1\) if \(\rho>1\).
Let \(A\) be an \(m\times n\) Gaussian matrix and let \(x_0\in\mathbb R^n\) be \(s\)-sparse. Basis pursuit recovers \(x_0\) from \(y=Ax_0\) as the minimizer of \(\|x\|_1\) subject to \(Ax=y\). The recovery succeeds exactly when the kernel of \(A\), a uniformly random subspace of dimension \(n-m\), meets the descent cone of the \(\ell^1\) norm at \(x_0\), \[ D(x_0):=\{h:\|x_0+\tau h\|_1\leq\|x_0\|_1\text{ for some }\tau>0\}, \] only at the origin. The kernel is a cone with \(\delta=n-m\), and a computation gives \(\delta(D(x_0))\approx2s\log(n/s)\) for \(s\ll n\). So the theorem predicts that basis pursuit succeeds with high probability when \(m\gtrsim2s\log(n/s)\) and fails with high probability when \(m\lesssim2s\log(n/s)\), with a transition window of width \(\sqrt n\). This is the empirically observed phase transition of compressed sensing, and it is a statement about the Gaussian width of a descent cone. We return to sparse recovery near the end of the course.
4 Where we go next
Gaussian width has now appeared in three roles: as the expected supremum of a Gaussian process, which is what the comparison inequalities compute; as a geometric size that controls covering numbers through Sudakov’s minoration; and as the parameter that governs random projections and random cones. The next two lectures leave Gaussian processes for a different use of Gaussian vectors, rounding the solution of a semidefinite program to a point of the discrete cube, before the course returns to suprema of processes with Dudley’s inequality and chaining.