A Tour of the RIP

Let $\Phi$ satisfy the RIP with $\delta_{2k} < 1 / \sqrt{2}$. Assume the $\ell_1$ optimum $\hat x$ has at most $k$ nonzeros, but now there is another feasible $\tilde x$ with at most $k$ nonzeros. Then, $h = \tilde x - \hat x$ has at most $2k$ nonzeros, and $\Phi h = 0$ holds (since both $\hat x, \tilde x$ are feasible). Then the RIP gives: $$ 0 = \lVert \Phi h \rVert_2^2 \geq (1 - \delta_{2k}) \lVert h \rVert_2^2 $$ By this, any $\delta_{2k} \neq 1$ implies $\lVert h \rVert_2^2 = 0 \Rightarrow h=0$, and thus $\hat x = \tilde x$ is the unique $k$-sparse feasible candidate.

Set $\alpha = \lVert h_S \rVert_1 / k$ and partition $h_{\bar S} = h_\uparrow + h_\downarrow$, where $h_\uparrow$ contains all $h_{\bar S}$ entries greater than $\alpha$, and $h_\downarrow$ all the other entries. Then, $h_\uparrow$ is at most $k$-sparse (can’t have more than $k$ entries larger than $\alpha$), and $h_\downarrow$ is in the polytope $T(\alpha, s)$ with $\ell_0$ bound $\alpha$ (by definition) and $\ell_1$ bound $s\alpha = (k - \lVert h_\uparrow \rVert_0)\alpha$, since the cone constraint gives: $$ \lVert h_\downarrow \rVert_1 = \lVert h_{\bar S} \rVert_1 - \lVert h_\uparrow \rVert_1 \leq \underbrace{\lVert h_{S} \rVert_1}_{= k \alpha} - \underbrace{\lVert h_\uparrow \rVert_1}_{\geq \lVert h_{\uparrow} \rVert_0 \alpha} \leq \underbrace{(k - \lVert h_\uparrow \rVert_0)}_{s} \alpha $$

With this, we can now bound the $\ell_2^2$ norm of $h_\downarrow \in T(\alpha, s)$, since polytope elements can be expressed as a convex sum of $s$-sparse, $\alpha$-bounded vectors: $$ \begin{align*} \lVert h_\downarrow \rVert_2^2 &\leq \sum_i \lambda_i \lVert u_i\rVert_2^2 \leq \max_i \lVert u_i \rVert_2^2 \leq s \alpha^2 \leq k \alpha^2 = \Big(\frac{\lVert h_S\rVert_1}{\sqrt{k}}\Big)^2 \\ &\leq \lVert h_S \rVert_2^2 \leq \lVert h_S + h_\uparrow \rVert_2^2 = \lVert w \rVert_2^2 \end{align*} $$

This is good: $w = h_S + h_\uparrow$ is $2k$-sparse, and its $\ell_2$ norm dominates all other entries in $h$. Therefore, if we can show that $\lVert w \rVert_2^2 = 0$, then the whole $h$ must be 0 and thus $\hat x = \dot x$: $$ \lVert w \rVert_2^2 = 0 \Rightarrow h_\downarrow=0 \Rightarrow h = w + h_\downarrow = 0 $$ But how do we find the conditions that give $w=0$? Like in the previous green block, we want a result that looks something like $0 \leq f_\delta \lVert w \rVert_2^2$, so we know that $w=0$ whenever $f_\delta < 0$. Unfortunately, we cannot leverage the feasibility constraint $\Phi h = 0 \Rightarrow \Phi w = - \Phi h_\downarrow$, since the RIP does not apply to $h_\downarrow$. Also, applying the RIP on a generic $w$ is vacuous: $$ (1 - \delta) \lVert w \rVert_2^2 \leq \lVert \Phi w \rVert_2^2 \leq (1 + \delta) \lVert w \rVert_2^2 \Rightarrow (1 - \delta) \leq (1 + \delta) $$ The plan is to find two vectors that depend on $w$, are both $2k$-sparse and have different norm. Then, we can apply the RIP to both of them, putting the bigger on the left and the smaller on the right, leaving a nonzero gap in which the only solution is that everything is 0 via $w=0$. This is often called the “RIP squeeze” step.

To achieve this, we go back to the polytope satisfying the convex sum $h_\downarrow = \sum_i \lambda_i u_i$, and construct the vectors $z_i = w + \mu u_i$, for some constant $\mu \in (0, 1)$. This construction allows us to smuggle $h$ inside sparse vectors (last line given by the parallelogram identity): $$ \begin{align*} \bar z = &\sum_i \lambda_i z_i = w + \mu h_\downarrow = w + \mu h - \mu w = (1 - \mu) w + \mu h \\ \bar z - \frac{1}{2} z_i = &[(1 - \mu) w + \mu h] - \frac{w + \mu u_i}{2} = \underbrace{(\frac{1}{2} - \mu) w - \frac{\mu}{2} u_i}_{z_i’ \text{, $2k$-sparse}} + \mu h \\ &\sum_i \lambda_i \lVert \underbrace{ \Phi (\bar z - \frac{1}{2} z_i)}_{= \Phi \bar z_i’} \rVert_2^2 = \frac{1}{4} \sum_i \lambda_i \lVert \Phi z_i \rVert_2^2 \end{align*} $$

Note that these properties are true for all $\mu \in (0, 1)$. This will be useful later. Furthermore,

$~$

• All linear combinations of $w$ and $u_i$ are $2k$-sparse, since $w$ has $2k-s$ nonzeros, and each $u_i$ has $s$ nonzeros, so the RIP applies to all $z_i$ (right-hand side of the parallelogram identity)
• The $h$ component vanishes under $\Phi$, so the RIP also applies to the left-hand side of the parallelogram identity using $z_i'$
• Crucially, $z_i’$ is missing the $h$ component: Wrapping the last identity with the RIP creates a discrepancy between different norms on the signal domain and equal norms under the image of $\Phi$. We put the “smaller” one on the right to force the “squeeze”:

$$ \frac{1 - \delta_{2k}}{4} \sum_i \lambda_i \lVert z_i \rVert_2^2 \leq \frac{1}{4} \sum_i \lambda_i \lVert \Phi z_i \rVert_2^2 = \sum_i \lambda_i \lVert \Phi z_i’ \rVert_2^2 \leq (1 + \delta_{2k}) \sum_i \lambda_i \lVert z_i’ \rVert_2^2 $$ Expanding, and simplifying with $\sum_i \lambda_i \lVert u_i \rVert_2^2 = \xi^2 \leq \lVert w \rVert_2^2$ (from the previous chain of inequalities) and $(1/2 - \mu)^2 - 1/4 = \mu^2 - \mu$, we can expose the squeeze:

$$ \begin{align*} &\frac{1 - \delta_{2k}}{4} \sum_i \lambda_i \Big[ \lVert w \rVert_2^2 + \mu^2 \lVert u_i \rVert_2^2 \Big] \leq (1+\delta_{2k}) \sum_i \lambda_i \Big[ \Big(\frac{1}{2}-\mu \Big)^2 \lVert w \rVert_2^2 + \frac{\mu^2}{4} \lVert u_i \rVert_2^2 \Big] \\ &\Longrightarrow \frac{1 - \delta_{2k}}{4} (\lVert w \rVert_2^2 + \mu^2 \xi^2 ) \leq (1+\delta_{2k}) \Big[ \Big(\frac{1}{2}-\mu \Big)^2 \lVert w \rVert_2^2 + \frac{\mu^2}{4} \xi^2 \Big] \\ &\Longrightarrow \frac{1 - \delta_{2k}}{4} \lVert w \rVert_2^2 \leq (1+\delta_{2k}) (\mu^2 - \mu + 1/4) \lVert w \rVert_2^2 + \delta_{2k} \frac{\mu^2}{2} \underbrace{\xi^2}_{\leq \lVert w \rVert_2^2} \\ &\Longrightarrow 0 \leq \big[ (1+\delta_{2k}) (4\mu^2 - 4\mu + 1) + 2 \delta_{2k} \mu^2 - (1 - \delta_{2k}) \big] \lVert w \rVert_2^2 \\ &\Longrightarrow 0 \leq \big[ 2 (\underbrace{\mu^2 - \mu}_{\leq 0}) + \delta_{2k} (\underbrace{3 \mu^2 - 2 \mu + 1}_{> 0}) \big] \lVert w \rVert_2^2 \quad \text{(recall that $\mu \in (0, 1)$)} \end{align*} $$ We can see now that this inequality is now nonvacuous: $\lVert w \rVert_2^2 = 0$ is forced if the square brackets are negative, and this is guaranteed for every $\delta_{2k} < (2 (\mu - \mu^2)) / (3 \mu^2 - 2 \mu + 1)$. And since we are free to pick $\mu$ (this is a nuisance parameter we introduced, and the derivations hold for all $\mu \in (0, 1)$), we seek the value of $\mu$ that maximizes this ratio: $$ \begin{equation*} \max_{\mu \in (0, 1)} \frac{2(\mu - \mu^2)}{3 \mu^2 - 2\mu + 1} = \frac{1}{\sqrt{2}} \qquad \text{(achieved at $\mu=\sqrt{2} - 1$)} \end{equation*} $$ Thus, if we reproduce the above RIP squeeze with $\mu=\sqrt{2}-1$, any $\delta_{2k} < \frac{1}{\sqrt{2}}$ will force $\lVert w \rVert_2^2 = 0 \Rightarrow \lVert h \rVert_2^2 = 0 \Rightarrow \hat x = \dot x$, concluding that the $\ell_1$ recovery is unique and correct.

---

Addendum: to maximize the ratio, note that setting its derivative to 0 yields a quadratic equation (using $f$ as the numerator and $g$ as the denominator): $$ \nabla_\mu = \frac{f’ g - g’ f}{g’’} = 0 \Rightarrow f’g = g’f \Rightarrow \mu^2 + 2 \mu - 1 = 0. $$ Wth the only positive solution at the established $\mu = \sqrt{2} - 1$. Replacing in the ratio and using $\mu^2 = 1 - 2\mu$ yields the bound for $\delta$: $$ \frac{2(\mu - \mu^2)}{3 \mu^2 - 2\mu + 1} = \frac{6\mu - 2}{4 - 8 \mu} = \frac{6 \sqrt{2} - 8}{12 - 8\sqrt{2}} = \frac{1}{\sqrt{2}} \frac{6 \sqrt{2} - 8}{12/\sqrt{2} - 8} = \frac{1}{\sqrt{2}} $$

Let $\Phi \in \mathbb{R}^{n \times N}$ be a random matrix with independent centered entries with variance $\mathbb{E}[\phi_{ij}^2] = 1/n$ and subgaussian tail bounds (with scale parameter $K$). Then, for all $k$-sparse $x$ simultaneously, and for $\delta \in (0, 1)$, the RIP: $$ (1 - \delta) \lVert x \rVert_2 \leq \lVert \Phi x \rVert_2 \leq (1 + \delta) \lVert x \rVert_2 $$ Holds for constants $c_1=12e$ and $c_2 > 0$ depending only on $K$, with probability of at least $$ 1 - 2 \exp\Big(k \log \Big( c_1 \frac{N}{k \delta} \Big) - c_2 n \delta^2 \Big) $$

And thus, for a fixed $\delta$ and $n = \mu k \log (\frac{c_1}{\delta} \frac{N}{k} )$ with $\mu > 1 / (c_2 \delta^2)$, the exponent becomes: $$ -\eta := -\big( c_2 \delta^2 \mu - 1 \big) k \log \Big( \frac{c_1}{\delta} \frac{N}{k} \Big) $$ and thus for $n \asymp k \log(N/k)$, $\Phi$ satisfies the RIP with probability of at least $1 - 2 e^{-\eta}$.

---

To see this, consider the set of all unit norm vectors with a particular (fixed) $k$-sparse support. By our definitions before, this is an instance of $S_X$, the unit sphere of a $k$-dimensional linear space. We will also make use of $Q$, the $\rho$-net of $S_X$, composed by at most $(3 / \rho)^k$ unit norm vectors (recall: $\rho \in (0, 1)$).

We start observing that, for each fixed $q \in Q$ (and for $0 < \epsilon < 1$), the matrix $\Phi$ satisfies the following inequality (using $\lVert q \rVert_2 = 1$ and the probability tail bound from before): $$ \begin{align*} P\big( \lVert \Phi q \rVert_2 \notin & [1-\epsilon, 1+\epsilon] \big) \leq P\big( \lVert \Phi q \rVert_2^2 \notin [1-\epsilon, 1+\epsilon] \big) \\ = &P\big( \big| \lVert \Phi q \rVert_2^2 - \lVert q \rVert_2^2 \big| \geq \epsilon \lVert q \rVert_2^2 \big) \leq 2 \exp\Big( -cn \frac{\epsilon^2}{\nu^2 \kappa^4} \Big) \end{align*} $$ Since we know the cardinality of $Q$, we can bound the probability of isometry for the best element over all $Q$, via union bound and complement: $$ P(\lVert \Phi q \rVert_2 \in [1 - \epsilon, 1 + \epsilon]) \geq 1 - 2 \Big( \frac{3}{\rho} \Big)^k \exp \Big( -cn \Big(\frac{\epsilon^2}{ \nu^2 \kappa^4} \Big) \Big) $$

Another quite useful property of $Q$ is that, for reasonable values of $\epsilon, \rho$, the above is “already enough” to extend the above bound from $Q$ to all of $S_X$. To show this, first define $A$ as the smallest number such that $\lVert \Phi x \rVert_2 \leq (1 + A) \lVert x \rVert_2 = 1 + A$ for all $x \in S_X$ (this also applies to $\lVert \Phi (x - q) \rVert_2 \leq (1 + A) \rho$, since $q$ is also in $S_X$). By the triangle inequality and definition of $Q$, the following bound for $A$ holds with the above probability: $$ \begin{align*} &\lVert \Phi x \rVert_2 \leq (1 + A) \leq \underbrace{\lVert \Phi q \rVert_2}_{\leq 1 + \epsilon} + \underbrace{\lVert \Phi (x - q) \rVert_2}_{\leq (1 + A)\rho} \leq 1 + \epsilon + (1 + A)\rho \\ \Rightarrow & (1 + A) (1 - \rho) \leq 1 + \epsilon \Rightarrow A \leq \frac{1 + \epsilon}{1 - \rho} - 1 \Rightarrow A \leq \frac{\epsilon + \rho}{1 - \rho} \end{align*} $$ Now, let’s say we want to satisfy the RIP for some $\delta \in (0, 1)$. If we choose the density of our net to satisfy $\rho = \frac{\delta}{4}$, and set our tail bound threshold to $\epsilon = \frac{\delta}{2}$, we get the desired $A \leq \delta$ bound (also applying $1 - \delta/4 \geq 3/4$): $$ A \leq \frac{\delta/2 + \delta/4}{1 - \delta/4} \leq \frac{3 \delta/4}{3/4} = \delta $$ From this, we can also obtain the lower bound: $$ \begin{align*} \lVert \Phi x \rVert_2 \geq \underbrace{\lVert \Phi q \rVert_2}_{\geq 1 - \delta/2} - \underbrace{\lVert \Phi (x - q) \rVert_2}_{\geq (1 - \delta)\frac{\delta}{4}} \geq 1 - \frac{\delta}{2} - \frac{\delta}{4} + \frac{\delta^2}{4} \geq 1 - \delta \end{align*} $$ And thus we obtain probability bounds that apply for every $x \in S_X$ (replacing $\epsilon$ and $\rho$): $$ \begin{align*} P(\lVert \Phi x \rVert_2 \in [1 - \delta, 1 + \delta]) \geq &1 - 2 \Big(\frac{12}{\delta} \Big)^k \exp \Big( -cn \Big(\frac{\delta^2}{2^2 \nu^2 \kappa^4} \Big) \Big)\\ &\text{For every $x \in S_X$.} \end{align*} $$

But this result only applies to $k$-sparse vectors on one particular, fixed support. There are $\binom{N}{k} \leq (eN / k)^k$ distinct subspaces like $S_X$ inside of $\mathbb{R}^N$. To obtain isometry guarantees for all $k$-sparse vectors jointly, we can apply one last union bound:

$$ \begin{align*} P(\lVert \Phi x \rVert_2 \in [1 - \delta, 1 + \delta]) \geq &1 - 2 \Big(\frac{eN}{k}\Big)^k \Big(\frac{12}{\delta} \Big)^k \exp \Big( -cn \Big(\frac{\delta^2}{2^2 \nu^2 \kappa^4} \Big) \Big)\\ &\text{For every $k$-sparse $x$.} \end{align*} $$

We can also obtain the associated measurement bounds. Regrouping parameters we get: $$ \begin{align*} &\Big(\frac{eN}{k}\Big)^k \Big(\frac{12}{\delta} \Big)^k \exp \Big( -cn \Big(\frac{\delta^2}{2^2 \nu^2 \kappa^4} \Big) \Big) \\ = &\exp \Big(k \log \Big( \underbrace{12e}_{c_1} \frac{N}{k \delta} \big) - \Big(\underbrace{\frac{c}{4 \nu^2 \kappa^4}}_{c_2} n \delta^2 \Big) \Big) \end{align*} $$ For the bound to be useful, the exponent needs to be negative: $$ k \log \Big( c_1 \frac{N}{k \delta} \Big) \leq c_2 n \delta^2 \Rightarrow n \geq \frac{1}{c_2 \delta^2} k \log \Big( c_1 \frac{N}{k \delta} \Big) $$ Yielding the final measurement bounds.

A small detail missing: we proved this for all $k$-sparse $x$ with unit norm, but it is easy to show the statement applies to $k$-sparse $x$ of all norms. Let $x’ = \xi x$ for any $\xi > 0$. Then, $\lVert x’ \rVert_2 = \xi$ and $$ \lVert \Phi x \rVert_2 \in [1 - \delta, 1 + \delta] \iff \frac{\lVert \Phi \xi x \rVert_2}{\xi} \in [1 - \delta, 1 + \delta] \iff \lVert \Phi x’ \rVert_2 \in [(1 - \delta) \lVert x’ \rVert_2, (1 + \delta) \lVert x’ \rVert_2] $$