Lecture 7: Coordinate Embeddings
Sampling coordinates instead of projecting
The Johnson–Lindenstrauss map of Lecture 6 is a dense random matrix: every output coordinate is a combination of every input coordinate. A cheaper idea is to keep a random subset of the coordinates and discard the rest. This works for some vectors and fails badly for others. The dividing line is how evenly a vector spreads its mass over its coordinates, and making that precise is the main business of this lecture.
1 Sampling coordinates
Fix \(\delta\in(0,1)\). Let \(I\subseteq\{1,\ldots,n\}\) be a random set that contains each index independently with probability \(\delta\). For \(x\in\mathbb R^n\), let \[ x_I:=\sum_{i\in I}\langle x,e_i\rangle e_i \] be the vector \(x\) with every coordinate outside \(I\) set to zero. Each coordinate survives with probability \(\delta\), so \[ \mathbb E\|x_I\|_2^2=\delta\|x\|_2^2 , \] and \(\|x_I\|_2^2/\delta\) is an unbiased estimate of \(\|x\|_2^2\). For a class \(T\) of vectors of interest we would like \[ \sup_{x\in T}\left|\frac{\|x_I\|_2^2}{\delta\|x\|_2^2}-1\right| \qquad\text{to be small,} \] while sampling as few coordinates as possible. The number of sampled coordinates is \(|I|\), whose expectation is \(\delta n\).
2 Sparsity defeats coordinate sampling
No choice of \(\delta<1\) works for every bounded set. Consider \[ T=\{\sqrt n\,e_j:1\leq j\leq n\}, \] so that every \(x\in T\) has \(\|x\|_2^2=n\). For \(x=\sqrt n\,e_j\), \[ \frac{\|x_I\|_2^2}{\delta\|x\|_2^2} =\begin{cases}1/\delta&\text{if }j\in I,\\[2pt]0&\text{if }j\notin I.\end{cases} \] The estimate is never close to \(1\) unless \(\delta\) is close to \(1\). A vector whose mass sits in a single coordinate is either fully sampled or fully missed.
Definition 1 (Flat vectors) A vector \(x\in\mathbb R^n\) is flat with constant \(C\) if \[ \|x\|_\infty^2\leq\frac Cn\|x\|_2^2 . \]
The reverse inequality holds for every vector, since \[ \|x\|_2^2=\sum_{i=1}^nx_i^2\leq n\|x\|_\infty^2 . \] Flatness therefore says that no single coordinate carries more than \(C\) times its fair share \(1/n\) of the squared norm. The vectors \(\sqrt n\,e_j\) above are as far from flat as possible.
Let \(x\) have i.i.d. \(N(0,1)\) entries. Then \[ \|x\|_2^2\approx n \qquad\text{but}\qquad \|x\|_\infty^2\approx2\log n . \] So \(x\) is flat only with a constant \(C\approx2\log n\) that grows with \(n\). This gap will cost a factor of \(\log n\) in the first bound below. Removing it is the point of the second half of the lecture.
3 A first concentration bound
Fix \(x\in\mathbb R^n\) and write \[ \|x_I\|_2^2=\sum_{i=1}^nY_i, \qquad Y_i:=\mathbb 1\{i\in I\}\,x_i^2 . \] The \(Y_i\) are independent. Each equals \(x_i^2\) with probability \(\delta\) and \(0\) otherwise, so \[ \mathbb EY_i=\delta x_i^2, \qquad |Y_i|\leq\|x\|_\infty^2, \qquad \mathbb EY_i^2=\delta x_i^4 . \] This is exactly the setting of the \(L^2\)–\(L^\infty\) version of Bernstein’s inequality from Lecture 6.
Proposition 1 (A first coordinate-sampling bound) There is an absolute constant \(c>0\) such that, for every \(x\in\mathbb R^n\) and every \(t\geq0\), \[ \begin{aligned} &\mathbb P\left\{\left|\|x_I\|_2^2-\delta\|x\|_2^2\right|\geq t\right\}\\ &\quad\leq2\exp\left(-c\min\left\{\frac t{\|x\|_\infty^2},\ \frac{t^2}{\delta\|x\|_4^4}\right\}\right). \end{aligned} \]
Apply the \(L^2\)–\(L^\infty\) Bernstein inequality to \(\sum_iY_i\), using \[ \max_i\|Y_i\|_{L^\infty}\leq\|x\|_\infty^2 \qquad\text{and}\qquad \sum_i\mathbb EY_i^2=\delta\sum_ix_i^4=\delta\|x\|_4^4 . \]
The bound is more useful in relative form.
Corollary 1 (Relative error, first version) For every \(x\in\mathbb R^n\) and every \(\varepsilon\in(0,1]\), \[ \begin{aligned} &\mathbb P\left\{\left|\frac{\|x_I\|_2^2}{\delta\|x\|_2^2}-1\right|\geq\varepsilon\right\}\\ &\quad\leq2\exp\left(-c\,\varepsilon^2\delta n\cdot\frac{\|x\|_2^2}{n\|x\|_\infty^2}\right). \end{aligned} \]
Take \(t=\varepsilon\delta\|x\|_2^2\) in Proposition 1. The two terms in the minimum become \[ \frac t{\|x\|_\infty^2}=\varepsilon\delta\,\frac{\|x\|_2^2}{\|x\|_\infty^2} \qquad\text{and}\qquad \frac{t^2}{\delta\|x\|_4^4}=\varepsilon^2\delta\,\frac{\|x\|_2^4}{\|x\|_4^4}. \] Since \(\|x\|_4^4=\sum_ix_i^4\leq\|x\|_\infty^2\|x\|_2^2\), the second term is at least \(\varepsilon^2\delta\|x\|_2^2/\|x\|_\infty^2\). As \(\varepsilon\leq1\), so is the first.
The exponent has a natural shape. The factor \(\varepsilon^2\delta n\) is what a sample of \(\delta n\) independent coordinates would give at relative accuracy \(\varepsilon\). It is multiplied by the ratio \[ \frac{\|x\|_2^2}{n\|x\|_\infty^2}\in\Big[\frac1n,\,1\Big], \] which equals \(1\) for a vector with all coordinates of equal size, is at least \(1/C\) for a vector that is flat with constant \(C\), and is \(1/n\) for \(\sqrt n\,e_j\).
Union bound. Let \(x_1,\ldots,x_N\) be fixed vectors. By Corollary 1 and a union bound, every one of the \(N\) relative errors is at most \(\varepsilon\) with probability at least \[ 1-2N\exp\left(-c\,\varepsilon^2\delta n\cdot\min_j\frac{\|x_j\|_2^2}{n\|x_j\|_\infty^2}\right), \] which is positive as soon as \[ \delta n\;\geq\;\frac{C\log(2N)}{\varepsilon^2}\cdot\max_j\frac{n\|x_j\|_\infty^2}{\|x_j\|_2^2}. \] For vectors that are flat with a fixed constant this is \(\delta n\gtrsim(\log N)/\varepsilon^2\): the same number of coordinates as the Johnson–Lindenstrauss dimension of Lecture 6. For i.i.d. \(N(0,1)\) vectors the ratio is \(\|x\|_2^2/(n\|x\|_\infty^2)\approx1/(2\log n)\), so we need \[ \delta n\gtrsim\frac{(\log N)(\log n)}{\varepsilon^2}. \] This is a factor \(\log n\) more than we would like, and it is exactly the flatness gap noted above.
4 A sharper bound: the empirical Orlicz norm
The loss came from bounding every coordinate by the single largest one, \(\|x\|_\infty\). For a Gaussian vector only a handful of coordinates are as large as \(\sqrt{2\log n}\), and a sharper argument should pay only for how many coordinates are actually large. The right bookkeeping device is an Orlicz norm applied not to a random variable but to the empirical distribution of a vector’s own coordinates.
Definition 2 (The empirical \(\chi_\alpha^n\) norm) For \(a\in\mathbb R^n\), let \(A\) be a uniformly random coordinate of \(a\), so \(A=a_j\) with probability \(1/n\) for each \(j\). Define \[ \|a\|_{\chi_\alpha^n}:=\|A\|_{\psi_\alpha}. \]
One consequence of the definition is immediate. Lecture 5 showed \(\sqrt{\mathbb EX^2}\leq\|X\|_{\psi_2}\) for every random variable \(X\), and here \(\mathbb EA^2=\|a\|_2^2/n\). Hence \[ \|a\|_2^2\leq n\|a\|_{\chi_2^n}^2 \qquad\text{for every }a\in\mathbb R^n . \tag{1}\]
To see what the \(\chi_2^n\) norm measures, translate the tail bound on \(A\) into a statement about the sorted coordinates of \(a\).
Lemma 1 (A tail bound is a decay condition on order statistics) Let \(|a_1^*|\geq|a_2^*|\geq\cdots\geq|a_n^*|\) be the absolute values of the coordinates of \(a\) in decreasing order, and let \(V>0\). Then \[ \begin{aligned} &\mathbb P\{|A|\geq t\}\leq2e^{-t^2/V}\quad\text{for every }t>0\\ &\qquad\Longleftrightarrow\\ &|a_j^*|^2\leq V\log\frac{2n}j\quad\text{for every }1\leq j\leq n . \end{aligned} \]
Since \(A\) is uniform on the \(n\) coordinates, \[ \begin{aligned} \mathbb P\{|A|\geq t\}&=\frac1n\#\{i:|a_i|\geq t\},\\ \#\{i:|a_i|\geq t\}\geq j&\iff|a_j^*|\geq t . \end{aligned} \]
Forward direction. Fix \(j\) with \(a_j^*\neq0\) and take \(t=|a_j^*|\). At least \(j\) coordinates are at least \(t\) in absolute value, so the tail bound gives \[ \frac jn\leq2e^{-|a_j^*|^2/V}, \qquad\text{i.e.}\qquad |a_j^*|^2\leq V\log\frac{2n}j . \] If \(a_j^*=0\) the right-hand inequality is trivial.
Reverse direction. Fix \(t>0\). If \(t>|a_1^*|\) the left-hand side is \(0\). Otherwise let \(j\) be the number of coordinates with \(|a_i|\geq t\), so \(1\leq j\leq n\) and \(t\leq|a_j^*|\). Then \[ \mathbb P\{|A|\geq t\}=\frac jn\leq2e^{-|a_j^*|^2/V}\leq2e^{-t^2/V}, \] where the first inequality is the assumed decay condition at index \(j\).
So a bound on \(\|a\|_{\chi_2^n}\) says that the sorted coordinates of \(a\) decay at least as fast as the order statistics of \(n\) independent variables with a Gaussian tail. This is a global shape condition on \(a\), not a worst-case bound on a single coordinate. Taking \(j=1\) shows the two are related by at most a logarithm: \[ \|a\|_\infty^2\leq\|a\|_{\chi_2^n}^2\log(2n). \]
Proposition 2 (Random vectors have bounded \(\chi_2^n\) norm) Let \(a\in\mathbb R^n\) have independent, mean-zero, \(V\)-subgaussian entries, and let \(r>0\). With probability at least \(1-3(2n)^{-r}\), \[ |a_j^*|^2\leq2(3+r)V\log\frac{2n}j \qquad\text{for every }1\leq j\leq n . \] On this event, \(\mathbb P\{|A|\geq t\}\leq2\exp\big(-t^2/(2(3+r)V)\big)\) for every \(t>0\), and consequently \[ \|a\|_{\chi_2^n}\leq\sqrt{6(3+r)V}. \]
By the sub-Gaussian tail bound of Lecture 4, each entry satisfies \(\mathbb P\{|a_i|\geq t\}\leq2e^{-t^2/(2V)}\). Set \[ t_j:=\sqrt{2(3+r)V\log(2n/j)}, \qquad\text{so that}\qquad 2e^{-t_j^2/(2V)}=2\Big(\frac j{2n}\Big)^{3+r}. \] The event \(\{|a_j^*|\geq t_j\}\) requires at least \(j\) of the entries to exceed \(t_j\) in absolute value. Taking a union bound over the \(\binom nj\) choices of which \(j\) entries, and using independence, \[ \begin{aligned} \mathbb P\{|a_j^*|\geq t_j\} &\leq\binom nj\Big[2\Big(\frac j{2n}\Big)^{3+r}\Big]^j\\ &\leq\Big(\frac{en}j\Big)^j\Big[2\Big(\frac j{2n}\Big)^{3+r}\Big]^j\\ &=\Big[\frac e4\Big(\frac jn\Big)^2\Big(\frac j{2n}\Big)^r\Big]^j . \end{aligned} \] Now \((j/n)^2\leq1\), and since \(j\leq n\) and \(j\leq2^{j-1}\), \[ \Big(\frac j{2n}\Big)^{rj} =\Big(\frac{j^j}{2^jn^j}\Big)^r \leq\Big(\frac j{2^jn}\Big)^r \leq(2n)^{-r}. \] Hence \(\mathbb P\{|a_j^*|\geq t_j\}\leq(e/4)^j(2n)^{-r}\), and summing over \(j\), \[ \mathbb P\{\exists j:|a_j^*|\geq t_j\} \leq(2n)^{-r}\sum_{j\geq1}\Big(\frac e4\Big)^j =\frac e{4-e}(2n)^{-r} \leq3(2n)^{-r}. \] On the complementary event, \(|a_j^*|^2<2(3+r)V\log(2n/j)\) for every \(j\), so Lemma 1 with \(V\) replaced by \(2(3+r)V\) gives the stated tail bound for \(A\). Finally, the tail-to-\(\psi_2\) direction of the equivalence theorem of Lecture 5, with prefactor \(2\) and scale \(\sigma=\sqrt{2(3+r)V}\), gives \(\|A\|_{\psi_2}\leq\sqrt3\,\sigma=\sqrt{6(3+r)V}\).
The bound on \(\|a\|_{\chi_2^n}\) is dimension-free: it does not grow with \(n\), whereas \(\|a\|_\infty\approx\sqrt{2V\log n}\) does. The empirical norm discards exactly the information that made \(\|\cdot\|_\infty\) pessimistic.
Let \(a\) be uniform on the sphere of radius \(\sqrt n\), so that \(\|a\|_2^2=n\) exactly. Write \(a=\sqrt n\,g/\|g\|_2\) with \(g\) a standard Gaussian vector. By Bernstein’s inequality (Lecture 6) applied to \(\|g\|_2^2=\sum_ig_i^2\), \[ \mathbb P\{\|g\|_2^2\leq n/2\}\leq2e^{-cn}. \] On the complementary event \(|a_j^*|\leq\sqrt2\,|g_j^*|\) for every \(j\), so Proposition 2 for \(g\) (with \(V=1\)) transfers to \(a\) with the constant \(2(3+r)\) replaced by \(4(3+r)\). So a random direction also has \(\|a\|_{\chi_2^n}=O(1)\) with probability \(1-O(n^{-r})\).
We can now redo the concentration bound with \(\|a\|_{\chi_2^n}\) in place of \(\|a\|_\infty\).
Theorem 1 (Coordinate sampling controlled by the \(\chi_2^n\) norm) There is an absolute constant \(c>0\) such that, for every \(a\in\mathbb R^n\) with \(\|a\|_{\chi_2^n}\leq r\) and every \(t\geq0\), \[ \begin{aligned} &\mathbb P\left\{\left|\|a_I\|_2^2-\delta\|a\|_2^2\right|\geq t\right\}\\ &\quad\leq2\exp\left(-c\min\left\{\frac t{r^2},\ \frac{t^2}{\delta nr^4}\right\}\right). \end{aligned} \]
Step 1: the moment generating function. As before, \(\|a_I\|_2^2=\sum_jY_j\) with \(Y_j=\mathbb 1\{j\in I\}a_j^2\) independent. For each \(j\) and every real \(\lambda\), \[ \begin{aligned} \mathbb Ee^{\lambda(Y_j-\delta a_j^2)} &=\Big(1+\delta\big[e^{\lambda a_j^2}-1\big]\Big)e^{-\lambda\delta a_j^2}\\ &\leq\exp\Big(\delta\big[e^{\lambda a_j^2}-1-\lambda a_j^2\big]\Big), \end{aligned} \] using \(1+u\leq e^u\). Multiplying over \(j\) and recognizing an average over the uniformly random coordinate \(A\) of Definition 2, \[ \mathbb Ee^{\lambda(\|a_I\|_2^2-\delta\|a\|_2^2)} \leq\exp\big(\delta n\,\varphi(\lambda)\big), \] where \[ \varphi(\lambda):=\mathbb E\big[e^{\lambda A^2}-1-\lambda A^2\big]. \]
Step 2: bounding \(\varphi\). Since \(\|A\|_{\psi_2}\leq r\) we have \(\mathbb Ee^{A^2/r^2}\leq2\). Each Taylor term of \(e^{A^2/r^2}-1\) is at most the whole, so \[ \mathbb EA^4\leq2!\,r^4=2r^4, \qquad \mathbb EA^8\leq4!\,r^8=24r^8. \] For \(\lambda\leq0\), the inequality \(e^{-u}-1+u\leq u^2/2\) for \(u\geq0\) gives \[ \varphi(\lambda)\leq\frac{\lambda^2}2\mathbb EA^4\leq\lambda^2r^4 . \] For \(0\leq\lambda\leq1/(2r^2)\), we have \(\varphi(0)=\varphi'(0)=0\) and, by Cauchy–Schwarz, \[ \begin{aligned} \varphi''(\lambda)=\mathbb E\big[A^4e^{\lambda A^2}\big] &\leq\big(\mathbb EA^8\big)^{1/2}\big(\mathbb Ee^{2\lambda A^2}\big)^{1/2}\\ &\leq\sqrt{24}\,r^4\cdot\sqrt2 =\sqrt{48}\,r^4, \end{aligned} \] using \(2\lambda\leq1/r^2\) in the last step. Integrating twice, \(\varphi(\lambda)\leq\sqrt{12}\,\lambda^2r^4\leq4\lambda^2r^4\). In either case, \[ \mathbb Ee^{\lambda(\|a_I\|_2^2-\delta\|a\|_2^2)}\leq\exp\big(4\delta nr^4\lambda^2\big) \qquad\text{for }|\lambda|\leq\frac1{2r^2}. \]
Step 3: Chernoff. This is the situation of the proof of Bernstein’s inequality in Lecture 6, with \(R=r^2\) in the role of the range and \(V=\delta nr^4\) in the role of the variance. Explicitly, for \(t\geq0\), \[ \mathbb P\{\|a_I\|_2^2-\delta\|a\|_2^2\geq t\} \leq\inf_{0\leq\lambda\leq1/(2r^2)}\exp\big(4\delta nr^4\lambda^2-\lambda t\big). \] The unconstrained minimizer is \(\lambda=t/(8\delta nr^4)\). If it is feasible, it gives \(\exp(-t^2/(16\delta nr^4))\). Otherwise \(t>4\delta nr^2\), and the boundary value \(\lambda=1/(2r^2)\) gives \[ \exp\Big(\delta n-\frac t{2r^2}\Big) \leq\exp\Big(\frac t{4r^2}-\frac t{2r^2}\Big) =\exp\Big(-\frac t{4r^2}\Big). \] The lower tail is identical, using the bound for \(\lambda\leq0\). A union bound over the two tails gives the claim with \(c=1/16\).
Corollary 2 (Relative error, sharp version) For every \(a\in\mathbb R^n\) and every \(\varepsilon\in(0,1]\), \[ \begin{aligned} &\mathbb P\left\{\left|\frac{\|a_I\|_2^2}{\delta\|a\|_2^2}-1\right|\geq\varepsilon\right\}\\ &\quad\leq2\exp\left(-c\,\varepsilon^2\delta n\cdot\Big(\frac{\|a\|_2^2}{n\|a\|_{\chi_2^n}^2}\Big)^2\right). \end{aligned} \]
Take \(r=\|a\|_{\chi_2^n}\) and \(t=\varepsilon\delta\|a\|_2^2\) in Theorem 1. The two terms in the minimum are \[ \frac t{r^2}=\varepsilon\delta\,\frac{\|a\|_2^2}{r^2} \qquad\text{and}\qquad \frac{t^2}{\delta nr^4}=\varepsilon^2\delta n\Big(\frac{\|a\|_2^2}{nr^2}\Big)^2 . \] Their ratio, second over first, is \(\varepsilon\|a\|_2^2/(nr^2)\), which is at most \(1\) by Equation 1 and \(\varepsilon\leq1\). So the second term is the minimum.
Compare this with Corollary 1. The exponent is again \(\varepsilon^2\delta n\) times a flatness ratio, but the ratio now involves \(\|a\|_{\chi_2^n}\) instead of \(\|a\|_\infty\). By Equation 1 the new ratio lies in \((0,1]\), and it equals a constant precisely when the coordinates of \(a\) are spread out in the order-statistics sense of Lemma 1.
Union bound, sharp version. Let \(a\) have i.i.d. \(N(0,1)\) entries. Then \(\|a\|_2^2\approx n\), and by Proposition 2 \(\|a\|_{\chi_2^n}\) is bounded by an absolute constant with probability \(1-O(n^{-r})\). On that event the flatness ratio is bounded below by an absolute constant, so \[ \begin{aligned} &\mathbb P\left\{\left|\frac{\|a_I\|_2^2}{\delta\|a\|_2^2}-1\right|\geq\varepsilon\right\}\\ &\quad\leq2\exp\big(-c\,\varepsilon^2\delta n\big). \end{aligned} \] For \(N\) such vectors a union bound succeeds once \[ \delta n\gtrsim\frac{\log N}{\varepsilon^2}, \] with no factor of \(\log n\). The expected number of sampled coordinates now matches the Johnson–Lindenstrauss dimension of Lecture 6, and the flatness gap of the first bound is gone.
5 Where we go next
Coordinate sampling is our first example of a genuinely structured random matrix, sparse rather than dense like Johnson–Lindenstrauss. Its success hinged on a geometric property of the vectors involved, flatness, rather than on the sampling scheme alone. The next several lectures turn to random matrices in general, starting with the extreme singular values of a random matrix and the net arguments used to control them.