4.2 Signal recovery in noise  (Page 2/2)

We now consider the worst-case bound for this error. Using standard properties of the singular value decomposition, it is straightforward to show that if $\Phi$ satisfies the RIP of order $2K$ (with constant ${\delta }_{2K}$ ), then the largest singular value of ${\Phi }_{{\Lambda }_0}^{†}$ lies in the range $[1/\sqrt{1+{\delta }_{2K}},1/\sqrt{1-{\delta }_{2K}}]$ . Thus, if we consider the worst-case recovery error over all $e$ such that ${∥e∥}_2\le ϵ$ , then the recovery error can be bounded by

Therefore, if $x$ is exactly $K$ -sparse, then the guarantee for the pseudoinverse recovery method, which is given perfect knowledge of the true support of $x$ , cannot improve upon the bound in [link] by more than a constant value.

We now examine a slightly different noise model. Whereas [link] assumed that the noise norm ${∥e∥}_2$ was small, the theorem below analyzes a different recovery algorithm known as the Dantzig selector in the case where ${∥{\Phi }^T,e∥}_{\infty }$ is small  [link] . We will see below that this will lead to a simple analysis of the performance of this algorithm in Gaussian noise.

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+e$ where ${∥{\Phi }^T,e∥}_{\infty }\le \lambda$ . Then when $\mathcal{B}\left(y\right)=\{z:{∥{\Phi }^T,(\Phi z-y)∥}_{\infty }\le \lambda \}$ , the solution $\widehat{x}$ to [link] obeys

where

The proof mirrors that of [link] . Since ${∥{\Phi }^T,e∥}_{\infty }\le \lambda$ , we again have that $x\in \mathcal{B}\left(y\right)$ , so ${∥\widehat{x}∥}_1\le {∥x∥}_1$ and thus [link] applies. We follow a similar approach as in [link] to bound $\left|〈\Phi ,h_{\Lambda },,,\Phi ,h〉\right|$ . We first note that

where the last inequality again follows since $x,\widehat{x}\in \mathcal{B}\left(y\right)$ . Next, note that $\Phi h_{\Lambda }={\Phi }_{\Lambda }{h}_{\Lambda }$ . Using this we can apply the Cauchy-Schwarz inequality to obtain

Finally, since ${∥{\Phi }^T,\Phi ,h∥}_{\infty }\le 2\lambda$ , we have that every coefficient of ${\Phi }^T\Phi h$ is at most $2\lambda$ , and thus ${∥{\Phi }_{\Lambda }^T,\Phi ,h∥}_2\le \sqrt{2K}\left(2\lambda \right)$ . Thus,

as desired.

Gaussian noise

Finally, we also examine the performance of these approaches in the presence of Gaussian noise. The case of Gaussian noise was first considered in  [link] , which examined the performance of ${\ell }_0$ minimization with noisy measurements. We now see that [link] and  [link] can be leveraged to provide similar guarantees for ${\ell }_1$ minimization. To simplify our discussion we will restrict our attention to the case where $x\in {\Sigma }_K=\left\{x,:,{∥x∥}_0,\le ,K\right\}$ , so that ${\sigma }_K{\left(x\right)}_1=0$ and the error bounds in [link] and  [link] depend only on the noise $e$ .

To begin, suppose that the coefficients of $e\in {\mathbb{R}}^M$ are i.i.d. according to a Gaussian distribution with mean zero and variance ${\sigma }^2$ . Since the Gaussian distribution is itself sub-Gaussian, we can apply results such as Corollary 1 from "Concentration of measure for sub-Gaussian random variables" to show that there exists a constant $c_0>0$ such that for any $ϵ>0$ ,

Applying this result to [link] with $ϵ=1$ , we obtain the following result for the special case of Gaussian noise.

Suppose that $\Phi$ satisfies the RIP of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ . Furthermore, suppose that $x\in {\Sigma }_K$ and that we obtain measurements of the form $y=\Phi x+e$ where the entries of $e$ are i.i.d. $\mathcal{N}(0,{\sigma }^2)$ . Then when $\mathcal{B}\left(y\right)=\{z:{∥\Phi ,z,-,y∥}_2\le 2\sqrt{M}\sigma \}$ , the solution $\widehat{x}$ to [link] obeys

with probability at least $1-exp(-c_{0}M)$ .

We can similarly consider [link] in the context of Gaussian noise. If we assume that the columns of $\Phi$ have unit norm, then each coefficient of ${\Phi }^{T}e$ is a Gaussian random variable with mean zero and variance ${\sigma }^2$ . Using standard tail bounds for the Gaussian distribution (see Theorem 1 from "Sub-Gaussian random variables" ), we have that

for $i=1,2,...,n$ . Thus, using the union bound over the bounds for different $i$ , we obtain

Applying this to [link] , we obtain the following result, which is a simplified version of Theorem 1.1 of  [link] .

Suppose that $\Phi$ has unit-norm columns and satisfies the RIP of order $2K$ with ${\delta }_{2K}<\sqrt{2}-1$ . Furthermore, suppose that $x\in {\Sigma }_K$ and that we obtain measurements of the form $y=\Phi x+e$ where the entries of $e$ are i.i.d. $\mathcal{N}(0,{\sigma }^2)$ . Then when $\mathcal{B}\left(y\right)=\{z:{∥{\Phi }^T,(\Phi z-y)∥}_{\infty }\le 2\sqrt{logN}\sigma \}$ , the solution $\widehat{x}$ to [link] obeys

with probability at least $1-\frac{1}{N}$ .

Ignoring the precise constants and the probabilities with which the bounds hold (which we have made no effort to optimize), we observe that if $M=O(KlogN)$ then these results appear to be essentially the same. However, there is a subtle difference. Specifically, if $M$ and $N$ are fixed and we consider the effect of varying $K$ , we can see that [link] yields a bound that is adaptive to this change, providing a stronger guarantee when $K$ is small, whereas the bound in [link] does not improve as $K$ is reduced. Thus, while they provide very similar guarantees, there are certain circumstances where the Dantzig selector is preferable. See  [link] for further discussion of the comparative advantages of these approaches.