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 \(\bx \in \CC^N\) via a sensing matrix \(\Phi\) as \(\by = \Phi \bx + \be\) where \(\be\) is the measurement error and \(\by\) is the measurement vector. The sparse recovery problem in the presence of noise is:

(21.1)#\[\widehat{\bx} = \text{arg } \underset{\bx \in \CC^N}{\min} \| \bx \|_0 \text{ subject to } \| \by - \Phi \bx \|_2 \leq \epsilon. \]

21.1.1. Stability of sparsest solution using RIP#

Theorem 21.1

Consider an instance of the (21.1) problem defined by the triplet \((\Phi, \by, \epsilon)\). Let \(\Phi\) satisfy RIP of order 2K. Suppose that a sparse vector \(\bx \in \CC^N\) with \(\| \bx \|_0 = K\) is a feasible solution of (21.1). Then, every solution \(\widehat{\bx}\) of (21.1) must obey

\[ \| \widehat{\bx} - \bx \|_2^2 \leq \frac{4 \epsilon^2}{1 - \delta_{2K}}. \]

Further, if

\[ \| \bx \|_0 < \frac{1}{2} \left (1 + \frac{1}{\mu} \right) \]

then the following also holds:

\[ \|\widehat{\bx} - \bx \|_2^2 \leq \frac{4 \epsilon^2}{ 1 - \mu ( 2 \| \bx \|_0 - 1)}. \]

Proof. .

  1. Let \(\widehat{\bx}\) be an alternative solution to (21.1).

  2. Defining \(\bz = \widehat{\bx} - \bx\),

    \[ \| \Phi \bz \|_2 \leq 2 \epsilon. \]

  3. Further

    \[ \| \bz \|_0 = \| \bx - \widehat{\bx} \|_0 \leq \| \bx \|_0 + \| \widehat{\bx} \|_0 \leq 2 K \]

    since \( \| \widehat{\bx} \|_0 \leq \| \bx \|_0 = K\).

  4. Since \(\Phi\) satisfies RIP of order 2K, hence

    \[ (1 - \delta_{2K}) \| \bz \|_2^2 \leq \| \Phi \bz \|_2^2 \leq (1 + \delta_{2K}) \| \bz \|_2^2. \]

  5. This gives us

    \[ (1 - \delta_{2K}) \| \bz \|_2^2 \leq 4 \epsilon^2. \]

  6. Rewriting we get

    \[ \| \bz \|_2^2 \leq \frac{4 \epsilon^2}{1 - \delta_{2K}} \]

    which is the desired result.

Coherence:

  1. We recall from Theorem 18.69 that

    \[ \delta_{2K} \leq (2K - 1) \mu. \]

  2. Thus,

    \[ 1 - \delta_{2K} \geq 1 - (2K - 1) \mu \implies \frac{4 \epsilon^2}{1 - \delta_{2K}} \leq \frac{4 \epsilon^2}{1 - (2K - 1) \mu }. \]

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

    \[ 1 - (2K - 1) \mu > 0 \implies \frac{1}{\mu} > 2K - 1 \implies K < \frac{1}{2} \left (1 + \frac{1}{\mu}\right). \]

  4. Under this condition, we get the result

    \[ \| \bz \|_2^2 \leq \frac{4 \epsilon^2}{1 - (2K - 1) \mu }. \]