ℓ_1 minimization proof

We now establish one of the core lemmas that we will use throughout this course . Specifically, [link] is used in establishing the relationship between the RIP and the NSP as well as establishing results on ${\ell }_1$ minimization in the context of sparse recovery in both the noise-free and noisy settings. In order to establish [link] , we establish the following preliminary lemmas.

Suppose $u,v$ are orthogonal vectors. Then

We begin by defining the $2\times 1$ vector $w={\left[{∥u∥}_2,,,{∥v∥}_2\right]}^T$ . By applying standard bounds on ${\ell }_p$ norms (Lemma 1 from "The RIP and the NSP" ) with $K=2$ , we have ${∥w∥}_1\le \sqrt{2}{∥w∥}_2$ . From this we obtain

Since $u$ and $v$ are orthogonal, ${∥u∥}_2^2+{∥v∥}_2^2={∥u,+,v∥}_2^2$ , which yields the desired result.

If $\Phi$ satisfies the restricted isometry property (RIP) of order $2K$ , then for any pair of vectors $u,v\in {\Sigma }_K$ with disjoint support,

Suppose $u,v\in {\Sigma }_K$ with disjoint support and that ${∥u∥}_2={∥v∥}_2=1.$ Then, $u\pm v\in {\Sigma }_{2K}$ and ${∥u,\pm ,v∥}_2^2=2$ . Using the RIP we have

Finally, applying the parallelogram identity

establishes the lemma.

Let ${\Lambda }_0$ be an arbitrary subset of $\{1,2,...,N\}$ such that $|{\Lambda }_0|\le K$ . For any vector $u\in {\mathbb{R}}^N$ , define ${\Lambda }_1$ as the index set corresponding to the $K$ largest entries of $u_{{\Lambda }_0^c}$ (in absolute value), ${\Lambda }_2$ as the index set corresponding to the next $K$ largest entries, and so on. Then

We begin by observing that for $j\ge 2$ ,

since the ${\Lambda }_j$ sort $u$ to have decreasing magnitude. Applying standard bounds on ${\ell }_p$ norms (Lemma 1 from "The RIP and the NSP" ) we have

proving the lemma.

We are now in a position to prove our main result. The key ideas in this proof follow from  [link] .

Suppose that $\Phi$ satisfies the RIP of order $2K$ . Let ${\Lambda }_0$ be an arbitrary subset of $\{1,2,...,N\}$ such that $|{\Lambda }_0|\le K$ , and let $h\in {\mathbb{R}}^N$ be given. Define ${\Lambda }_1$ as the index set corresponding to the $K$ entries of $h_{{\Lambda }_0^c}$ with largest magnitude, and set $\Lambda ={\Lambda }_0\cup {\Lambda }_1$ . Then

where

Since $h_{\Lambda }\in {\Sigma }_{2K}$ , the lower bound on the RIP immediately yields

Define ${\Lambda }_j$ as in [link] , then since $\Phi h_{\Lambda }=\Phi h-{\sum }_{j\ge 2}\Phi h_{{\Lambda }_j}$ , we can rewrite [link] as

In order to bound the second term of [link] , we use [link] , which implies that

for any $i,j$ . Furthermore, [link] yields ${∥h_{{\Lambda }_0}∥}_2+{∥h_{{\Lambda }_1}∥}_2\le \sqrt{2}{∥h_{\Lambda }∥}_2$ . Substituting into [link] we obtain

From [link] , this reduces to

Combining [link] with [link] we obtain

which yields the desired result upon rearranging.