Review of Johnson-Lindenstrauss Lemma

Possible to construct low-dimensional linear embedding that preserves geometry. Works as long as dimension of space is logaritmic in number of points.

Original proof was existential, but recent developments have shown that almost any random projection will do and there exist more structured solutions.

Generalizes to stable embedding that preserves.

\begin{proposition} Let $x\in\mathbb{R}^n$ be fixed and $\Phi$ an $M\times N$ matrix with iid entries $\Phi_{m,n}\sim\mathcal{N}(0,\frac{1}{M})$. Fix $\epsilon\in(0,\frac{1}{2})$, then $(1-\epsilon)\Vert x\Vert_2^2 \leq \Vert \Phi x \Vert_2^2\leq (1+\epsilon)\Vert x\Vert_2^2$ with probabiltiy at least $1-2e^{-\epsilon^2M/8}$ \end{proposition}

A $\gamma$-net $N_\gamma$ for a set $\mathcal{S}\subset\mathbb{R}^N$ is a finite set of points $u_1,\dots,u_Q$ such that $\forall x\in\mathcal{S}\qquad\min_{u\in N_\gamma}\Vert u-x\Vert_2 \leq \gamma$

\begin{lemma} Let $\mathcal{S}^{N-1}={x\in R^N:\Vert x\Vert_2=1}$ and fix $\gamma\in(0,1)$. There exists a $\gamma$-net $N_\gamma\subset S^{N-1}$ satisfying $|N_\gamma|\leq (1+\frac{2}{\gamma})^N \leq (\frac{3}{\gamma})^N$ \end{lemma}

\begin{lemma} Fix $\gamma\in(0\frac{1}{2})$. Let $H$ be a symmetric $N\times N$ matrix and $N_\gamma$ be a $\gamma$-net for $S^{N-1}$. then $\max_{u\in N_\gamma} |u^T H u|\leq \sup_{x\in B_N} |x^THx| \leq \frac{1}{1-2\gamma}\max_{u\in N_\gamma} |u^T H u|$ where $B_N={x\in R^N:\Vert x\Vert_2\leq 1 }$ \end{lemma}

Union of subspaces

 $\Sigma_K={x\in R^N:\Vert x \Vert_0\leq k}$ with $\Vert x \Vert_0= \text{supp}(x)$. This is a union of ${N\choose K}$ subspaces.

RIP A matrix $\Phi$ satisfies the RIP of order $K$ if $\exists \delta\in(0,1)$ such that $\forall x\in\Sigma_K\quad (1-\delta)\Vert x\Vert_2^2\leq \Vert\Phi x \Vert_2^2\leq (1+\delta)\Vert x\Vert_2^2$

\begin{theorem} Fix $\delta\in(0,1)$, $\Phi$ as in Proposition 1. If $M\geq \delta^{-2}(K\log(\frac{N}{K\delta}-\log \eta))$ then $\Phi$ satisfies the RIP of order $K$ with $\delta$ with probability at least $1-\eta$. \end{theorem}

It is sufficient to show that $\forall x\in\Sigma_K\quad (1-\delta)\leq \Vert\Phi x \Vert_2^2\leq (1+\delta)$ for unit norm vectors.

 First fix $T\subseteq {1,\dots,N}$ with $T =K$. Set $S_T={x\in R^n:\text{supp}(x)=T}$ (grabbing columns). Let $N_\gamma^{(T)}$ be a $\gamma$-net for the unit sphere in $S_T$ with $\gamma=\frac{\delta}{14}$. From previous discussiong $N_\gamma^{(T)} \leq (1+\frac{28}{\delta})^K$.

Define $N=\bigcup_{T:|T|=K}N_\gamma^{(T)}$. Then $|N| \leq {N \choose K}(1+\frac{28}{\delta})^K \leq (\frac{eN}{K})^K(1+\frac{28}{\delta})^K.$ Apply Proposition 1 to $N$ with $\epsilon=\frac{\delta}{\sqrt{2}}$ to obtain with prob at least $1-2 (\frac{eN}{K})^K(1+\frac{28}{\delta})^K e^{-\delta^2M/16}$ that $\forall u\in N\quad (1-\frac{\delta}{\sqrt{2}})\leq \Vert\Phi u \Vert_2^2\leq (1+\frac{\delta}{\sqrt{2}})$

Note that $\Vert\Phi x \Vert_2^2 = x^T\underbrace{\Phi^T\Phi}_{\text{symmetric}} x \leq (\frac{1}{1-\delta/7})(1+\frac{\delta}{\sqrt{2}})\leq 1+\delta.$ To obtain lower inequality, $\Vert\Phi x \Vert_2 \geq \Vert\Phi u \Vert_2 - \Vert\Phi (x-u) \Vert_2 \geq (1-\frac{\delta}{\sqrt{2}}) - \sqrt{1+\delta}\Vert x - u\Vert_2 \geq \sqrt{1-\delta}.$

Applications sparse aproximation and greedy algorithms.

Choice of $\Phi$ doesn’t matter too much (sub-Gaussian would work). Fast JL Transform also works.