21.1. Stability of the Sparsest Solution

We discuss various results related to the stability of the sparsest solution for the sparse recovery problem.

For convenience, we restate the problem. We measure the sparse signal $\mathbf{x}\in {\mathbb{C}}^N$ via a sensing matrix $\mathrm{\Phi }$ as $\mathbf{y}=\mathrm{\Phi }\mathbf{x}+\mathbf{e}$ where $\mathbf{e}$ is the measurement error and $\mathbf{y}$ is the measurement vector. The sparse recovery problem in the presence of noise is:

(21.1)$$\hat{\mathbf{x}}=\text{arg }\underset{\mathbf{x}\in {\mathbb{C}}^N}{min}\Vert \mathbf{x}{\Vert }_0\text{ subject to }\Vert \mathbf{y}-\mathrm{\Phi }\mathbf{x}{\Vert }_2\le ϵ.$$

21.1.1. Stability of sparsest solution using RIP

Theorem 21.1

Consider an instance of the (21.1) problem defined by the triplet $(\mathrm{\Phi },\mathbf{y},ϵ)$. Let $\mathrm{\Phi }$ satisfy RIP of order 2K. Suppose that a sparse vector $\mathbf{x}\in {\mathbb{C}}^N$ with $\Vert \mathbf{x}{\Vert }_0=K$ is a feasible solution of (21.1). Then, every solution $\hat{\mathbf{x}}$ of (21.1) must obey

$$\Vert \hat{\mathbf{x}}-\mathbf{x}{\Vert }_2^2\le \frac{4{ϵ}^2}{1-{\delta }_{2K}}.$$

Further, if

$$\Vert \mathbf{x}{\Vert }_0<\frac{1}{2}(1+\frac{1}{\mu })$$

then the following also holds:

$$\Vert \hat{\mathbf{x}}-\mathbf{x}{\Vert }_2^2\le \frac{4{ϵ}^2}{1-\mu (2\Vert \mathbf{x}{\Vert }_0-1)}.$$

Proof. .

1. Let $\hat{\mathbf{x}}$ be an alternative solution to (21.1).

2. Defining $\mathbf{z}=\hat{\mathbf{x}}-\mathbf{x}$,

   $$\Vert \mathrm{\Phi }\mathbf{z}{\Vert }_2\le 2ϵ.$$

3. Further

   $$\Vert \mathbf{z}{\Vert }_0=\Vert \mathbf{x}-\hat{\mathbf{x}}{\Vert }_0\le \Vert \mathbf{x}{\Vert }_0+\Vert \hat{\mathbf{x}}{\Vert }_0\le 2K$$

   since $\Vert \hat{\mathbf{x}}{\Vert }_0\le \Vert \mathbf{x}{\Vert }_0=K$.

4. Since $\mathrm{\Phi }$ satisfies RIP of order 2K, hence

   $$(1-{\delta }_{2K})\Vert \mathbf{z}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{z}{\Vert }_2^2\le (1+{\delta }_{2K})\Vert \mathbf{z}{\Vert }_2^2.$$

5. This gives us

   $$(1-{\delta }_{2K})\Vert \mathbf{z}{\Vert }_2^2\le 4{ϵ}^2.$$

6. Rewriting we get

   $$\Vert \mathbf{z}{\Vert }_2^2\le \frac{4{ϵ}^2}{1-{\delta }_{2K}}$$

   which is the desired result.

Coherence:

1. We recall from Theorem 18.69 that

   $${\delta }_{2K}\le (2K-1)\mu .$$

2. Thus,

   $$1-{\delta }_{2K}\ge 1-(2K-1)\mu ⟹\frac{4{ϵ}^2}{1-{\delta }_{2K}}\le \frac{4{ϵ}^2}{1-(2K-1)\mu }.$$

3. This is useful only if the denominator is positive, i.e.

   $$1-(2K-1)\mu >0⟹\frac{1}{\mu }>2K-1⟹K<\frac{1}{2}(1+\frac{1}{\mu }).$$

4. Under this condition, we get the result

   $$\Vert \mathbf{z}{\Vert }_2^2\le \frac{4{ϵ}^2}{1-(2K-1)\mu }.$$