3.3 The rip and the nsp

Next we will show that if a matrix satisfies the restricted isometry property (RIP), then it also satisfies the null space property (NSP). Thus, the RIP is strictly stronger than the NSP.

Suppose that $\Phi$ satisfies the RIP of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ . Then $\Phi$ satisfies the NSP of order $2K$ with constant

The proof of this theorem involves two useful lemmas. The first of these follows directly from standard norm inequality by relating a $K$ -sparse vector to a vector in ${\mathbb{R}}^K$ . We include a simple proof for the sake of completeness.

Suppose $u\in {\Sigma }_K$ . Then

For any $u$ , ${∥u∥}_1=\left|〈u,,,\mathrm{sgn},\left(,u,\right)〉\right|$ . By applying the Cauchy-Schwarz inequality we obtain ${∥u∥}_1\le {∥u∥}_2{∥\mathrm{sgn},\left(,u,\right)∥}_2$ . The lower bound follows since $\mathrm{sgn}\left(u\right)$ has exactly $K$ nonzero entries all equal to $\pm 1$ (since $u\in {\Sigma }_K$ ) and thus $∥\mathrm{sgn},\left(,u,\right)∥=\sqrt{K}$ . The upper bound is obtained by observing that each of the $K$ nonzero entries of $u$ can be upper bounded by ${∥u∥}_{\infty }$ .

Below we state the second key lemma that we will need in order to prove [link] . This result is a general result which holds for arbitrary $h$ , not just vectors $h\in \mathcal{N}\left(\Phi \right)$ . It should be clear that when we do have $h\in \mathcal{N}\left(\Phi \right)$ , the argument could be simplified considerably. However, this lemma will prove immensely useful when we turn to the problem of sparse recovery from noisy measurements later in this course , and thus we establish it now in its full generality. We state the lemma here, which is proven in " ${\ell }_1$ minimization proof" .

Suppose that $\Phi$ satisfies the RIP of order $2K$ , and let $h\in {\mathbb{R}}^N$ , $h\ne 0$ be arbitrary. Let ${\Lambda }_0$ be any subset of $\{1,2,...,N\}$ such that $|{\Lambda }_0|\le K$ . 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

Again, note that [link] holds for arbitrary $h$ . In order to prove [link] , we merely need to apply [link] to the case where $h\in \mathcal{N}\left(\Phi \right)$ .

Towards this end, suppose that $h\in \mathcal{N}\left(\Phi \right)$ . It is sufficient to show that

holds for the case where $\Lambda$ is the index set corresponding to the $2K$ largest entries of $h$ . Thus, we can take ${\Lambda }_0$ to be the index set corresponding to the $K$ largest entries of $h$ and apply [link] .

The second term in [link] vanishes since $\Phi h=0$ , and thus we have

Using [link] ,

resulting in

Since ${∥h_{{\Lambda }_1}∥}_2\le {∥h_{\Lambda }∥}_2$ , we have that

The assumption ${\delta }_{2K}<\sqrt{2}-1$ ensures that $\alpha <1$ , and thus we may divide by $1-\alpha$ without changing the direction of the inequality to establish [link] with constant

as desired.