Stability of the Sparsest Solution
Contents
15.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:
15.1.1. Stability of sparsest solution using RIP¶
Theorem 15.1
Consider an instance of the (15.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 (15.1). Then, every solution \(\widehat{\bx}\) of (15.1) must obey
Further, if
then the following also holds:
Proof. .
Let \(\widehat{\bx}\) be an alternative solution to (15.1).
Defining \(\bz = \widehat{\bx} - \bx\),
\[ \| \Phi \bz \|_2 \leq 2 \epsilon. \]Further
\[ \| \bz \|_0 = \| \bx - \widehat{\bx} \|_0 \leq \| \bx \|_0 + \| \widehat{\bx} \|_0 \leq 2 K \]since \( \| \widehat{\bx} \|_0 \leq \| \bx \|_0 = K\).
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. \]This gives us
\[ (1 - \delta_{2K}) \| \bz \|_2^2 \leq 4 \epsilon^2. \]Rewriting we get
\[ \| \bz \|_2^2 \leq \frac{4 \epsilon^2}{1 - \delta_{2K}} \]which is the desired result.
Coherence:
We recall from Theorem 12.68 that
\[ \delta_{2K} \leq (2K - 1) \mu. \]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 }. \]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). \]Under this condition, we get the result
\[ \| \bz \|_2^2 \leq \frac{4 \epsilon^2}{1 - (2K - 1) \mu }. \]