4.1 Noise-free signal recovery

We now begin our analysis of

for various specific choices of $\mathcal{B}\left(y\right)$ . In order to do so, we require the following general result which builds on Lemma 4 from " ${\ell }_1$ minimization proof" . The key ideas in this proof follow from  [link] .

Suppose that $\Phi$ satisfies the restricted isometry property (RIP) of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ . Let $x,\widehat{x}\in {\mathbb{R}}^N$ be given, and define $h=\widehat{x}-x$ . Let ${\Lambda }_0$ denote the index set corresponding to the $K$ entries of $x$ with largest magnitude and ${\Lambda }_1$ the index set corresponding to the $K$ entries of $h_{{\Lambda }_0^c}$ with largest magnitude. Set $\Lambda ={\Lambda }_0\cup {\Lambda }_1$ . If ${∥\widehat{x}∥}_1\le {∥x∥}_1$ , then

where

We begin by observing that $h=h_{\Lambda }+h_{{\Lambda }^c}$ , so that from the triangle inequality

We first aim to bound ${∥h_{{\Lambda }^c}∥}_2$ . From Lemma 3 from " ${\ell }_1$ minimization proof" we have

where the ${\Lambda }_j$ are defined as before, i.e., ${\Lambda }_1$ is the index set corresponding to the $K$ largest entries of $h_{{\Lambda }_0^c}$ (in absolute value), ${\Lambda }_2$ as the index set corresponding to the next $K$ largest entries, and so on.

We now wish to bound ${∥h_{{\Lambda }_0^c}∥}_1$ . Since ${∥x∥}_1\ge {∥\widehat{x}∥}_1$ , by applying the triangle inequality we obtain

Rearranging and again applying the triangle inequality,

Recalling that ${\sigma }_K{\left(x\right)}_1={∥x_{{\Lambda }_0^c}∥}_1={∥x,-,x_{{\Lambda }_0}∥}_1$ ,

Combining this with [link] we obtain

where the last inequality follows from standard bounds on ${\ell }_p$ norms (Lemma 1 from "The RIP and the NSP" ). By observing that ${∥h_{{\Lambda }_0}∥}_2\le {∥h_{\Lambda }∥}_2$ this combines with [link] to yield

We now turn to establishing a bound for ${∥h_{\Lambda }∥}_2$ . Combining Lemma 4 from " ${\ell }_1$ minimization proof" with [link] and again applying standard bounds on ${\ell }_p$ norms we obtain

Since ${∥h_{{\Lambda }_0}∥}_2\le {∥h_{\Lambda }∥}_2$ ,

The assumption that ${\delta }_{2K}<\sqrt{2}-1$ ensures that $\alpha <1$ . Dividing by $(1-\alpha )$ and combining with [link] results in

Plugging in for $\alpha$ and $\beta$ yields the desired constants.

[link] establishes an error bound for the class of ${\ell }_1$ minimization algorithms described by [link] when combined with a measurement matrix $\Phi$ satisfying the RIP. In order to obtain specific bounds for concrete examples of $\mathcal{B}\left(y\right)$ , we must examine how requiring $\widehat{x}\in \mathcal{B}\left(y\right)$ affects $\left|〈\Phi ,h_{\Lambda },,,\Phi ,h〉\right|$ . As an example, in the case of noise-free measurements we obtain the following theorem.

(theorem 1.1 of [link] )

Suppose that $\Phi$ satisfies the RIP of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ and we obtain measurements of the form $y=\Phi x$ . Then when $\mathcal{B}\left(y\right)=\{z:\Phi z=y\}$ , the solution $\widehat{x}$ to [link] obeys

Since $x\in \mathcal{B}\left(y\right)$ we can apply [link] to obtain that for $h=\widehat{x}-x$ ,

Furthermore, since $x,\widehat{x}\in \mathcal{B}\left(y\right)$ we also have that $y=\Phi x=\Phi \widehat{x}$ and hence $\Phi h=0$ . Therefore the second term vanishes, and we obtain the desired result.

[link] is rather remarkable. By considering the case where $x\in {\Sigma }_K=\left\{x,:,{∥x∥}_0,\le ,K\right\}$ we can see that provided $\Phi$ satisfies the RIP — which as shown earlier allows for as few as $O(Klog(N/K\left)\right)$ measurements — we can recover any $K$ -sparse $x$ exactly . This result seems improbable on its own, and so one might expect that the procedure would be highly sensitive to noise, but we will see next that [link] can also be used to demonstrate that this approach is actually stable.

Note that [link] assumes that $\Phi$ satisfies the RIP. One could easily modify the argument to replace this with the assumption that $\Phi$ satisfies the null space property (NSP) instead. Specifically, if we are only interested in the noiseless setting, in which case $h$ lies in the null space of $\Phi$ , then [link] simplifies and its proof could be broken into two steps: ( $i$ ) show that if $\Phi$ satisfies the RIP then it satisfies the NSP (as shown in "The RIP and the NSP" ), and ( $ii$ ) the NSP implies the simplified version of [link] . This proof directly mirrors that of [link] . Thus, by the same argument as in the proof of [link] , it is straightforward to show that if $\Phi$ satisfies the NSP then it will obey the same error bound.