Restricted Isometry Property

If $A$ satisfies RIP of order $2s$ with $\delta_{2s} < \sqrt{2} - 1$, then for every $s$-sparse vector $x$, the solution to basis pursuit:

$\hat{x} = \arg\min_{z} \|z\|_1 \quad \text{subject to} \quad Az = y$

satisfies $\hat{x} = x$. Moreover, in the noisy case $y = Ax + e$ with $\|e\|_2 \leq \epsilon$, basis pursuit denoising recovers $\hat{x}$ with:

$\|\hat{x} - x\|_2 \leq C_0 \epsilon$

where $C_0$ depends only on $\delta_{2s}$.

RIP of order $2s$ ensures that $A$ preserves distances between pairs of $s$-sparse vectors (their difference is $2s$-sparse). This means no two distinct $s$-sparse vectors can produce the same measurements. Among all vectors consistent with the measurements, the $s$-sparse one is the unique L1 minimizer because L1 favors sparsity (the L1 ball has corners at the coordinate axes).

This theorem converts the NP-hard problem of finding the sparsest solution ($\min \|z\|_0$ subject to $Az = y$) into a polynomial-time linear program ($\min \|z\|_1$ subject to $Az = y$). The condition $\delta_{2s} < \sqrt{2} - 1$ is the price of this computational tractability.

The threshold $\delta_{2s} < \sqrt{2} - 1 \approx 0.4142$ is sufficient but not tight. Improved analyses (Cai & Zhang, 2014) show that $\delta_{2s} < 0.4531$ suffices. Also, verifying that a specific matrix satisfies RIP is NP-hard (Bandeira et al., 2012), so in practice we rely on probabilistic constructions.

Let $A \in \mathbb{R}^{m \times n}$ have i.i.d. entries from $\mathcal{N}(0, 1/m)$. There exist universal constants $c_1, c_2 > 0$ such that if:

$m \geq c_1 \delta^{-2} s \log(en/s)$

then $A$ satisfies RIP of order $s$ with constant $\delta_s \leq \delta$ with probability at least $1 - 2e^{-c_2 \delta^2 m}$.

A random Gaussian matrix is "incoherent" with every sparse basis simultaneously. For any fixed $s$-sparse vector, $\|Ax\|_2^2$ concentrates around $\|x\|_2^2$ by subgaussian concentration. The challenge is making this hold for all $\binom{n}{s}$ possible supports simultaneously. The epsilon-net argument handles this: cover the unit sphere restricted to each support by a finite net, apply concentration to each net point, then use a union bound over the net.

This theorem says you can construct RIP matrices by simply drawing random entries. No careful design is needed. The measurement count $m = O(s \log(n/s))$ is nearly optimal: information-theoretic arguments show $m \geq 2s$ is necessary, so the gap is only the $\log(n/s)$ factor.

The constant $c_1$ in the bound can be large in practice. For small $s$ and moderate $n$, the bound may require more measurements than are practical. Also, Gaussian matrices are dense ($O(mn)$ storage), which is problematic when $n$ is very large. Structured random matrices (partial Fourier, random sparse) achieve similar guarantees with $O(n \log n)$ or $O(mn/\log n)$ storage and faster matrix-vector products.

The Johnson-Lindenstrauss (JL) lemma states: for any set of $N$ points in $\mathbb{R}^n$, a random projection into $\mathbb{R}^m$ with $m = O(\epsilon^{-2} \log N)$ preserves all pairwise distances to within factor $(1 \pm \epsilon)$.

RIP states: a random projection into $\mathbb{R}^m$ with $m = O(\delta^{-2} s \log(en/s))$ preserves norms of all $s$-sparse vectors to within factor $(1 \pm \delta)$.

Both results follow from the same concentration inequality for subgaussian random projections. The difference is what set of vectors must be preserved: JL preserves a finite point set; RIP preserves the (infinite) union of $s$-dimensional subspaces.

A random low-dimensional projection preserves structure because most of the "action" is in a low-dimensional subspace. For JL, the structure is $N$ points (effective dimension $\log N$). For RIP, the structure is $s$-dimensional subspaces (effective dimension $s \log(en/s)$ accounting for the $\binom{n}{s}$ possible supports).

Understanding this connection reveals that RIP, JL, and random embedding results are all manifestations of the same phenomenon: subgaussian random projections approximately preserve low-dimensional geometry. This unifying view helps you apply the right tool: JL for dimensionality reduction of point sets, RIP for sparse recovery.

The JL dimension $O(\log N)$ depends on the number of points but not on the ambient dimension $n$. The RIP dimension $O(s \log(n/s))$ depends on both sparsity and ambient dimension. These are not interchangeable: JL does not imply RIP and RIP does not imply JL in general, though they share the same proof machinery.