4.2 Signal recovery in noise

The ability to perfectly reconstruct a sparse signal from noise-free measurements represents a promising result. However, in most real-world systems the measurements are likely to be contaminated by some form of noise. For instance, in order to process data in a computer we must be able to represent it using a finite number of bits, and hence the measurements will typically be subject to quantization error. Moreover, systems which are implemented in physical hardware will be subject to a variety of different types of noise depending on the setting.

Perhaps somewhat surprisingly, one can show that it is possible to modify

to stably recover sparse signals under a variety of common noise models  [link] , [link] , [link] . As might be expected, the restricted isometry property (RIP) is extremely useful in establishing performance guarantees in noise.

In our analysis we will make repeated use of Lemma 1 from "Noise-free signal recovery" , so we repeat it here for convenience.

Suppose that $\Phi$ satisfies the 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

Bounded noise

We first provide a bound on the worst-case performance for uniformly bounded noise, as first investigated in  [link] .

(theorem 1.2 of [link] )

Suppose that $\Phi$ satisfies the RIP of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ and let $y=\Phi x+e$ where ${∥e∥}_2\le ϵ$ . Then when $\mathcal{B}\left(y\right)=\{z:{∥\Phi ,z,-,y∥}_2\le ϵ\}$ , the solution $\widehat{x}$ to [link] obeys

where

We are interested in bounding ${∥h∥}_2={∥\widehat{x},-,x∥}_2$ . Since ${∥e∥}_2\le ϵ$ , $x\in \mathcal{B}\left(y\right)$ , and therefore we know that ${∥\widehat{x}∥}_1\le {∥x∥}_1$ . Thus we may apply [link] , and it remains to bound $\left|〈\Phi ,h_{\Lambda },,,\Phi ,h〉\right|$ . To do this, we observe that

where the last inequality follows since $x,\widehat{x}\in \mathcal{B}\left(y\right)$ . Combining this with the RIP and the Cauchy-Schwarz inequality we obtain

Thus,

completing the proof.

In order to place this result in context, consider how we would recover a sparse vector $x$ if we happened to already know the $K$ locations of the nonzero coefficients, which we denote by ${\Lambda }_0$ . This is referred to as the oracle estimator . In this case a natural approach is to reconstruct the signal using a simple pseudoinverse:

The implicit assumption in [link] is that ${\Phi }_{{\Lambda }_0}$ has full column-rank (and hence we are considering the case where ${\Phi }_{{\Lambda }_0}$ is the $M\times K$ matrix with the columns indexed by ${\Lambda }_0^c$ removed) so that there is a unique solution to the equation $y={\Phi }_{{\Lambda }_0}{x}_{{\Lambda }_0}$ . With this choice, the recovery error is given by