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 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

\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 \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 where $B_N={x\in R^N:\Vert x\Vert_2\leq 1 }$ \end{lemma}

$\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

\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 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 Apply Proposition 1 to $N$ with $\epsilon=\frac{\delta}{\sqrt{2}}$ to obtain with prob at least that

Note that To obtain lower inequality,

**Applications** sparse aproximation and greedy algorithms.

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