Lecture 12: Gaussian Comparison and Gaussian Matrices
Slepian, Sudakov–Fernique, sharp bounds on Gaussian matrices, and Sudakov’s minoration
Lecture 11 reduced the study of the supremum of a Gaussian process to the study of its mean. This lecture develops the main tool for the mean. The idea is to compare two Gaussian processes on the same index set: if the increments of \(X\) are smaller than those of \(Y\) in the canonical metric, then \(\mathbb E\sup X\leq\mathbb E\sup Y\). The proof is Stein’s lemma along an interpolation between the two covariances, in the same way that the concentration inequality was Stein’s lemma along an interpolation between a Gaussian vector and an independent copy. The two applications are the norm of a Gaussian random matrix, where comparison with a process that can be computed exactly gives the sharp bound \(\sqrt m+\sqrt n\), and Sudakov’s minoration, whose proof Lecture 3 postponed to this point.
1 Gaussian interpolation
Let \(X\sim N(0,\Sigma^X)\) and \(Y\sim N(0,\Sigma^Y)\) be independent Gaussian vectors in \(\mathbb R^n\), and for \(u\in[0,1]\) set \[ Z(u):=\sqrt u\,X+\sqrt{1-u}\,Y . \] Then \(Z(u)\sim N\big(0,\,u\Sigma^X+(1-u)\Sigma^Y\big)\): the covariance interpolates linearly between \(\Sigma^Y\) at \(u=0\) and \(\Sigma^X\) at \(u=1\). The question is how \(\mathbb Ef(Z(u))\) varies along the path.
Lemma 1 (Gaussian interpolation) Let \(f:\mathbb R^n\to\mathbb R\) be \(C^2\) with bounded first and second derivatives. Then for \(0<u<1\), \[ \frac d{du}\mathbb Ef(Z(u)) =\frac12\sum_{i,j=1}^n\big(\Sigma^X_{ij}-\Sigma^Y_{ij}\big)\,\mathbb E\,\partial_{ij}f(Z(u)). \]
By the chain rule and differentiation under the expectation, which the bounded gradient justifies, \[ \frac d{du}\mathbb Ef(Z(u)) =\sum_{i=1}^n\mathbb E\Big[\partial_if(Z(u))\Big(\frac{X_i}{2\sqrt u}-\frac{Y_i}{2\sqrt{1-u}}\Big)\Big]. \] Consider the terms containing \(X_i\). Condition on \(Y\); then \(x\mapsto\partial_if(\sqrt u\,x+\sqrt{1-u}\,Y)\) is Lipschitz with gradient \(\sqrt u\,\nabla\partial_if(Z(u))\), and the multivariate Stein lemma of Lecture 10 gives \[ \mathbb E\big[X_i\,\partial_if(Z(u))\,\big|\,Y\big] =\sqrt u\sum_{j=1}^n\Sigma^X_{ij}\,\mathbb E\big[\partial_{ij}f(Z(u))\,\big|\,Y\big]. \] Taking expectations and summing over \(i\), the \(X\) terms contribute \(\frac12\sum_{ij}\Sigma^X_{ij}\mathbb E\partial_{ij}f(Z(u))\). The \(Y\) terms are handled in the same way, conditioning on \(X\), and contribute \(-\frac12\sum_{ij}\Sigma^Y_{ij}\mathbb E\partial_{ij}f(Z(u))\).
Everything that follows is a choice of \(f\) for which the sign of the right side can be read off from the covariances.
2 Slepian’s inequality
Lemma 2 (Slepian’s lemma) Let \(X\sim N(0,\Sigma^X)\) and \(Y\sim N(0,\Sigma^Y)\) in \(\mathbb R^n\) with \[ \Sigma^X_{ii}=\Sigma^Y_{ii}\quad\text{for all }i, \qquad \Sigma^X_{ij}\geq\Sigma^Y_{ij}\quad\text{for all }i\neq j . \] Let \(f\) be \(C^2\) with bounded derivatives and \(\partial_{ij}f\geq0\) for all \(i\neq j\). Then \(\mathbb Ef(X)\geq\mathbb Ef(Y)\).
We may take \(X\) and \(Y\) independent, since the conclusion involves only their individual laws. In Lemma 1 the diagonal terms vanish because \(\Sigma^X_{ii}=\Sigma^Y_{ii}\), and each off-diagonal term is a product of the nonnegative quantities \(\Sigma^X_{ij}-\Sigma^Y_{ij}\) and \(\mathbb E\partial_{ij}f(Z(u))\). So \(u\mapsto\mathbb Ef(Z(u))\) is nondecreasing on \([0,1]\), and \(\mathbb Ef(Y)=\mathbb Ef(Z(0))\leq\mathbb Ef(Z(1))=\mathbb Ef(X)\).
In the language of processes, the hypotheses say that \(X\) and \(Y\) have the same variances and \(X\) has the smaller increments: \[ \mathbb E(X_i-X_j)^2=\Sigma^X_{ii}+\Sigma^X_{jj}-2\Sigma^X_{ij} \leq\Sigma^Y_{ii}+\Sigma^Y_{jj}-2\Sigma^Y_{ij}=\mathbb E(Y_i-Y_j)^2 . \] The process with smaller increments is the more correlated one, and its maximum should be smaller, because its coordinates cannot spread out as far. Slepian’s inequality makes this precise at the level of tails.
Theorem 1 (Slepian’s inequality) Let \((X_t)_{t\in T}\) and \((Y_t)_{t\in T}\) be centered Gaussian processes on a set \(T\) whose canonical metric spaces are separable, and suppose that for all \(s,t\in T\), \[ \mathbb EX_t^2=\mathbb EY_t^2 \qquad\text{and}\qquad \mathbb E(X_t-X_s)^2\leq\mathbb E(Y_t-Y_s)^2 . \] Then for every \(\tau\in\mathbb R\), \[ \mathbb P\Big\{\sup_{t\in T}X_t>\tau\Big\}\leq\mathbb P\Big\{\sup_{t\in T}Y_t>\tau\Big\}, \] and consequently \(\mathbb E\sup_{t\in T}X_t\leq\mathbb E\sup_{t\in T}Y_t\) whenever either side is finite.
Finite \(T\). Let \(T=\{1,\ldots,n\}\). Fix \(\tau\) and let \(h:\mathbb R\to[0,1]\) be \(C^2\), nonincreasing, with bounded derivatives, equal to \(1\) on \((-\infty,\tau]\) and to \(0\) on \([\tau+\varepsilon,\infty)\). Set \(f(x)=\prod_{i=1}^nh(x_i)\). For \(i\neq j\), \[ \partial_{ij}f(x)=h'(x_i)h'(x_j)\prod_{k\neq i,j}h(x_k)\geq0, \] since \(h'\leq0\) and \(h\geq0\). By Lemma 2, \(\mathbb Ef(X)\geq\mathbb Ef(Y)\). Now \(\mathbb 1\{\max_ix_i\leq\tau\}\leq f(x)\leq\mathbb 1\{\max_ix_i\leq\tau+\varepsilon\}\), so \[ \mathbb P\Big\{\max_iX_i\leq\tau+\varepsilon\Big\}\geq\mathbb Ef(X)\geq\mathbb Ef(Y)\geq\mathbb P\Big\{\max_iY_i\leq\tau\Big\}. \] Letting \(\varepsilon\downarrow0\) and using right-continuity of distribution functions, \(\mathbb P\{\max X\leq\tau\}\geq\mathbb P\{\max Y\leq\tau\}\), which is the claim.
Expectations. For an integrable random variable \(W\), \[ \mathbb EW=\int_0^\infty\mathbb P\{W>\tau\}\,d\tau-\int_{-\infty}^0\mathbb P\{W\leq\tau\}\,d\tau, \] and both integrals compare in the right direction.
Separable \(T\). Take finite sets \(T_n\) increasing to a countable dense subset \(T_0\), as in the proof of the Borell–TIS inequality in Lecture 11. The events \(\{\sup_{T_n}X>\tau\}\) increase to \(\{\sup_{T_0}X>\tau\}\), so the tail inequality passes to the limit, and the expectations follow by monotone convergence.
3 The Sudakov–Fernique inequality
Slepian’s inequality requires equal variances. The Sudakov–Fernique inequality drops that requirement, at the price of comparing only expectations rather than tails. The proof replaces the product of cutoffs by a smooth version of the maximum.
Theorem 2 (Sudakov–Fernique inequality) Let \((X_t)_{t\in T}\) and \((Y_t)_{t\in T}\) be centered Gaussian processes on a set \(T\) whose canonical metric spaces are separable, and suppose that for all \(s,t\in T\), \[ \mathbb E(X_t-X_s)^2\leq\mathbb E(Y_t-Y_s)^2 . \] Then \(\mathbb E\sup_{t\in T}X_t\leq\mathbb E\sup_{t\in T}Y_t\).
By the monotone limit argument it suffices to treat \(T=\{1,\ldots,n\}\), and we may take \(X\) and \(Y\) independent. For \(\beta>0\) consider the soft maximum \[ f_\beta(x):=\frac1\beta\log\sum_{i=1}^ne^{\beta x_i}, \qquad \max_ix_i\leq f_\beta(x)\leq\max_ix_i+\frac{\log n}\beta . \] Its derivatives are, with \(p_i(x):=e^{\beta x_i}/\sum_ke^{\beta x_k}\), \[ \partial_if_\beta=p_i, \qquad \partial_{ij}f_\beta=\beta\big(\delta_{ij}p_i-p_ip_j\big). \] The \(p_i\) are positive and sum to \(1\), so all derivatives are bounded and Lemma 1 applies. Writing \(D_{ij}:=\Sigma^X_{ij}-\Sigma^Y_{ij}\) and evaluating at \(Z(u)\), \[ \sum_{i,j}D_{ij}\,\partial_{ij}f_\beta =\beta\Big(\sum_iD_{ii}p_i-\sum_{i,j}D_{ij}p_ip_j\Big). \] Since \(\sum_jp_j=1\), the first sum equals \(\sum_{i,j}D_{ii}p_ip_j\), and symmetrizing in \(i\) and \(j\) it also equals \(\frac12\sum_{i,j}(D_{ii}+D_{jj})p_ip_j\). Hence \[ \sum_{i,j}D_{ij}\,\partial_{ij}f_\beta =\frac\beta2\sum_{i,j}p_ip_j\big(D_{ii}+D_{jj}-2D_{ij}\big) =\frac\beta2\sum_{i,j}p_ip_j\Big(\mathbb E(X_i-X_j)^2-\mathbb E(Y_i-Y_j)^2\Big)\leq0 . \] By Lemma 1, \(u\mapsto\mathbb Ef_\beta(Z(u))\) is nonincreasing, so \(\mathbb Ef_\beta(X)\leq\mathbb Ef_\beta(Y)\). Therefore \[ \mathbb E\max_iX_i\leq\mathbb Ef_\beta(X)\leq\mathbb Ef_\beta(Y)\leq\mathbb E\max_iY_i+\frac{\log n}\beta , \] and \(\beta\to\infty\) finishes the proof.
The inequality has a striking geometric reading. By the Karhunen–Loève theorem of Lecture 10, a centered Gaussian process is the isonormal process restricted to a subset of Hilbert space, and \(\mathbb E\sup X\) is the Gaussian width of that subset. Sudakov–Fernique says that Gaussian width is monotone under contractions: if \(\varphi:x(T)\to y(T)\) is a map between two subsets of Hilbert space that does not increase distances, in the sense that \(\|y(t)-y(s)\|\leq\|x(t)-x(s)\|\), then the width of the image is at most the width of the domain. Nothing about the ambient dimension or the shape of the sets enters.
The functional form of Slepian’s lemma needs \(\Sigma^X_{ii}=\Sigma^Y_{ii}\) because the diagonal terms of the interpolation formula carry \(\partial_{ii}f\), whose sign is uncontrolled for a general \(f\) with nonnegative mixed derivatives. The soft maximum is special: its Hessian has the form \(\beta(\operatorname{diag}(p)-pp^{\mathsf T})\), which annihilates constants, and this is what allows the diagonal and off-diagonal terms to be regrouped into increments. The price is that \(f_\beta\) approximates only the maximum, not the indicator of \(\{\max\leq\tau\}\), so one obtains expectations and not tails. Tails can be recovered afterwards from Borell–TIS.
4 Norms of Gaussian random matrices
Lecture 9 proved that an \(m\times n\) matrix with independent isotropic sub-Gaussian rows has \(s_{\max}(A)\leq\sqrt m+CK\sqrt n\) with high probability, by a net argument. For Gaussian entries, comparison gives the constant \(1\).
Theorem 3 (Norm of a Gaussian matrix) Let \(A\) be an \(m\times n\) matrix with independent \(N(0,1)\) entries. Then \[ \mathbb E\|A\|_{\mathrm{op}}\leq\sqrt m+\sqrt n . \]
Write the norm as the supremum of a Gaussian process on \(T=S^{n-1}\times S^{m-1}\): \[ \|A\|_{\mathrm{op}}=\sup_{(u,v)\in T}\langle Au,v\rangle=\sup_{(u,v)\in T}X_{uv}, \qquad X_{uv}:=\langle Au,v\rangle=\sum_{i,j}A_{ij}u_jv_i . \] Each \(X_{uv}\) is \(N(0,1)\), and \(T\) is compact with the process continuous in \((u,v)\), so the supremum convention of Lecture 10 applies.
Increments of \(X\). For \((u,v),(w,z)\in T\), independence of the entries gives \[ \mathbb E(X_{uv}-X_{wz})^2 =\sum_{i,j}\big(u_jv_i-w_jz_i\big)^2 =\|vu^{\mathsf T}-zw^{\mathsf T}\|_F^2 =2-2\langle u,w\rangle\langle v,z\rangle, \] using \(\|vu^{\mathsf T}\|_F=\|zw^{\mathsf T}\|_F=1\) and \(\langle vu^{\mathsf T},zw^{\mathsf T}\rangle_F=\langle u,w\rangle\langle v,z\rangle\). Now write \(\langle u,w\rangle=1-a\) and \(\langle v,z\rangle=1-b\) with \(a=\|u-w\|_2^2/2\) and \(b=\|v-z\|_2^2/2\), both in \([0,2]\). Then \[ 2-2(1-a)(1-b)=2a+2b-2ab=\|u-w\|_2^2+\|v-z\|_2^2-\frac{\|u-w\|_2^2\|v-z\|_2^2}2 \leq\|u-w\|_2^2+\|v-z\|_2^2 . \]
A simpler process. Let \(g\sim N(0,I_n)\) and \(h\sim N(0,I_m)\) be independent and set \(Y_{uv}:=\langle g,u\rangle+\langle h,v\rangle\). Then \[ \mathbb E(Y_{uv}-Y_{wz})^2=\mathbb E\langle g,u-w\rangle^2+\mathbb E\langle h,v-z\rangle^2 =\|u-w\|_2^2+\|v-z\|_2^2 . \]
Comparison. The increments of \(X\) are dominated by those of \(Y\), so Theorem 2 gives \[ \mathbb E\|A\|_{\mathrm{op}}=\mathbb E\sup_TX\leq\mathbb E\sup_TY =\mathbb E\sup_{u\in S^{n-1}}\langle g,u\rangle+\mathbb E\sup_{v\in S^{m-1}}\langle h,v\rangle =\mathbb E\|g\|_2+\mathbb E\|h\|_2 , \] and \(\mathbb E\|g\|_2\leq(\mathbb E\|g\|_2^2)^{1/2}=\sqrt n\), similarly for \(h\).
The proof is the template for every use of comparison. The process of interest is complicated because its index set is a product of spheres and its covariance \(\langle u,w\rangle\langle v,z\rangle\) is a product. The comparison process decouples the two factors into a sum, whose supremum splits and reduces to Gaussian widths of spheres, which Lecture 3 computed. What is lost in the comparison is the product term \(\|u-w\|_2^2\|v-z\|_2^2/2\), and it costs nothing at leading order: in fact \(\mathbb E\|A\|_{\mathrm{op}}=\sqrt m+\sqrt n-o(\sqrt n)\) as \(n\to\infty\), though we do not prove this.
Concentration turns the expectation into a tail bound.
Corollary 1 (Tail bound for the norm) In the setting of Theorem 3, for every \(t\geq0\), \[ \mathbb P\big\{\|A\|_{\mathrm{op}}\geq\sqrt m+\sqrt n+t\big\}\leq e^{-t^2/2}. \]
View \(A\) as a standard Gaussian vector in \(\mathbb R^{mn}\). The map \(A\mapsto\|A\|_{\mathrm{op}}\) is \(1\)-Lipschitz with respect to the Euclidean norm on \(\mathbb R^{mn}\), which is the Frobenius norm, because \(\big|\|A\|_{\mathrm{op}}-\|B\|_{\mathrm{op}}\big|\leq\|A-B\|_{\mathrm{op}}\leq\|A-B\|_F\). The Gaussian concentration theorem of Lecture 11 gives \(\mathbb P\{\|A\|_{\mathrm{op}}\geq\mathbb E\|A\|_{\mathrm{op}}+t\}\leq e^{-t^2/2}\), and Theorem 3 bounds the mean. Equivalently, this is the Borell–TIS inequality for the process \(X_{uv}\), which has \(\sigma=1\).
The smallest singular value is a min-max rather than a max, \[ s_{\min}(A)=\min_{u\in S^{n-1}}\max_{v\in S^{m-1}}\langle Au,v\rangle , \] and Sudakov–Fernique does not apply to it directly. Gordon’s inequality is the extension of Slepian’s lemma to min-max functionals: for doubly indexed processes \(X_{uv}\) and \(Y_{uv}\) with \(\mathbb E(X_{uv}-X_{uz})^2\leq\mathbb E(Y_{uv}-Y_{uz})^2\) for all \(u,v,z\) and \(\mathbb E(X_{uv}-X_{wz})^2\geq\mathbb E(Y_{uv}-Y_{wz})^2\) for \(u\neq w\), one has \(\mathbb E\min_u\max_vX_{uv}\leq\mathbb E\min_u\max_vY_{uv}\). The proof is the interpolation lemma applied to \(f(x)=\prod_u\big(1-\prod_vh(x_{uv})\big)\), with a sign check for the mixed derivatives that distinguishes pairs sharing the first index from pairs that do not. Applied to the same processes \(X\) and \(Y\) as above, it gives \[ \mathbb Es_{\min}(A)\geq\mathbb E\|h\|_2-\mathbb E\|g\|_2\geq\sqrt m-\sqrt n-\tfrac12 , \] using \(\mathbb E\|h\|_2\geq\sqrt m-1/(2\sqrt m)\) from Lecture 3 (the lower bound has the same leading order and the correction is small in practice). Since \(s_{\min}\) is also \(1\)-Lipschitz in the Frobenius norm, \(\mathbb P\{s_{\min}(A)\leq\sqrt m-\sqrt n-\tfrac12-t\}\leq e^{-t^2/2}\). We do not prove Gordon’s inequality here.
Together with Corollary 1, this is the sharp form of the statement that a tall Gaussian matrix is an approximate isometry: with probability \(1-2e^{-t^2/2}\), \[ \sqrt m-\sqrt n-\tfrac12-t\ \leq\ s_{\min}(A)\ \leq\ s_{\max}(A)\ \leq\ \sqrt m+\sqrt n+t . \] Compare Lecture 9, where the constants in front of \(\sqrt n\) depended on the sub-Gaussian constant of the rows, and Lecture 8, where the distortion did not tend to zero at all.
Let \(A\) be a symmetric \(n\times n\) matrix whose entries above the diagonal are independent \(N(0,1)\) and whose diagonal entries are independent \(N(0,2)\). Show that \(\mathbb E\|A\|_{\mathrm{op}}\leq2\sqrt n\) and \(\mathbb P\{\|A\|_{\mathrm{op}}\geq2\sqrt n+t\}\leq e^{-t^2/4}\).
Hint. Check that \(\mathbb E\langle Au,u\rangle\langle Aw,w\rangle=2\langle u,w\rangle^2\) for unit \(u,w\). For \(\lambda_{\max}(A)=\sup_u\langle Au,u\rangle\) compare with \(Y_u=2\langle g,u\rangle\) using \(1-c^2\leq2(1-c)\) for \(|c|\leq1\). For \(\|A\|_{\mathrm{op}}=\sup_{(u,\varepsilon)}\varepsilon\langle Au,u\rangle\) over \(S^{n-1}\times\{\pm1\}\) compare with \(Y_{u,\varepsilon}=2\varepsilon\langle g,u\rangle\), checking the increments for pairs with opposite signs separately. The tail bound uses that \(\|A\|_{\mathrm{op}}\) is \(\sqrt2\)-Lipschitz in the Gaussian coordinates that parametrize \(A\).
5 Sudakov’s minoration
Lecture 3 stated that Gaussian width controls covering numbers at every scale and left the proof as a roadmap, because it needed a comparison theorem. Here is the proof, for a general Gaussian process.
Theorem 4 (Sudakov’s minoration inequality) There is an absolute constant \(c>0\) such that for every centered Gaussian process \((X_t)_{t\in T}\) with separable canonical metric \(d\), and every \(\varepsilon>0\), \[ \mathbb E\sup_{t\in T}X_t\geq c\,\varepsilon\sqrt{\log N(T,d,\varepsilon)} . \] For the Gaussian width process \(X_t=\langle g,t\rangle\) on \(T\subseteq\mathbb R^d\) this reads \(w(T)\geq c\varepsilon\sqrt{\log N(T,\|\cdot\|_2,\varepsilon)}\).
We need a lower bound on the expected maximum of independent Gaussians: for \(N\geq2\) and \(g\sim N(0,I_N)\), \[ \mathbb E\max_{i\leq N}g_i\geq c_0\sqrt{\log N} . \] Indeed, \(\max_i|g_i|\leq\max_ig_i+\max_i(-g_i)\), and the two terms on the right have the same law, so \(\mathbb E\max_ig_i\geq\frac12\mathbb E\|g\|_\infty\), and Exercise Sheet 2 showed \(\mathbb E\|g\|_\infty\geq\sqrt{2\log N}-o(1)\) as \(N\to\infty\). For each fixed \(N\geq2\) the left side is positive, so a single constant \(c_0\) works for all \(N\geq2\).
Now let \(N:=N(T,d,\varepsilon)\), which we may assume finite and at least \(2\), the statement being trivial otherwise (if \(N=\infty\), run the argument on finite subsets). By the covering–packing comparison of Lecture 1, \(T\) contains an \(\varepsilon\)-separated set \(t_1,\ldots,t_N\). Let \(Y_1,\ldots,Y_N\) be independent \(N(0,\varepsilon^2/2)\). For \(i\neq j\), \[ \mathbb E(X_{t_i}-X_{t_j})^2=d(t_i,t_j)^2\geq\varepsilon^2=\mathbb E(Y_i-Y_j)^2 . \] So \(Y\) has the smaller increments, and Theorem 2 applied to the processes \((Y_i)\) and \((X_{t_i})\) on the finite set \(\{1,\ldots,N\}\) gives \[ \mathbb E\sup_{t\in T}X_t\geq\mathbb E\max_{i\leq N}X_{t_i}\geq\mathbb E\max_{i\leq N}Y_i =\frac\varepsilon{\sqrt2}\,\mathbb E\max_{i\leq N}g_i\geq\frac{c_0}{\sqrt2}\,\varepsilon\sqrt{\log N} . \]
Sudakov’s inequality is a statement about a single scale: it says nothing about how the covering numbers at different scales combine. Its converse direction, an upper bound on \(\mathbb E\sup X\) from the covering numbers, requires all scales at once and is Dudley’s inequality, the subject of the chaining lectures. The two together bracket the expected supremum between the entropy at the worst single scale and the integral of the entropy over all scales.
For the Gaussian width process the inequality reads \[ \log N(T,\varepsilon)\leq\frac{C\,w(T)^2}{\varepsilon^2} \qquad\text{for every }\varepsilon>0 . \] This is a purely geometric statement about subsets of \(\mathbb R^d\), proved by probabilistic means. For the \(\ell^p\) balls with \(1\leq p\leq2\), Lecture 3 and its exercises give \(w(B_p^d)\asymp d^{1-1/p}\) up to logarithmic factors at \(p=1\), so \[ \log N(B_p^d,\varepsilon)\lesssim\frac{d^{2-2/p}}{\varepsilon^2}, \] which for \(p<2\) is subexponential in \(d\) at fixed \(\varepsilon\), far below the volumetric bound \(d\log(C/\varepsilon)\). At \(p=1\) this recovers the Maurey bound of Lecture 2 up to logarithms, by a completely different argument. For \(p>2\) the volumetric bound is the better one, and Sudakov is not sharp.
6 Where we go next
Comparison inequalities compute expected suprema by trading a complicated process for a simpler one with larger increments. The next lecture returns to Gaussian width with these tools in hand: Sudakov’s minoration as a geometric measurement, the width of sparse vectors and of \(\ell^p\) balls, and Gaussian width as the quantity that governs the diameter of a random projection of a set and the intersection of randomly rotated cones. After that, the semidefinite relaxation lectures use the Gaussian tools of Lectures 10 and 11 in a different direction, to round the solution of a convex program to a point of the discrete cube.