20.1. Stability of the Sparsest Solution

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

For convenience, we restate the problem. We represent the signal $\mathbf{x}\in {\mathbb{C}}^N$ as $\mathbf{x}=\mathcal{D}\mathbf{a}+\mathbf{e}$ where $\mathbf{a}$ is a sparse approximation of $\mathbf{x}$ in $\mathcal{D}$.

(20.1)$$\hat{\mathbf{a}}=\text{arg }\underset{\mathbf{a}\in {\mathbb{C}}^D}{min}\Vert \mathbf{a}{\Vert }_0\text{ subject to }\Vert \mathbf{x}-\mathcal{D}\mathbf{a}{\Vert }_2\le ϵ.$$

Since we only know $\mathbf{x}$ and $\mathcal{D}$ (both $\mathbf{a}$ and $\mathbf{e}$ are unknown to us), hence in general it is not possible to reconstruct $\mathbf{a}$ exactly. The term $\mathbf{d}=\mathbf{a}-\hat{\mathbf{a}}$ will represent the reconstruction error (note that it is different from the approximation error $\mathbf{e}$). It is important for us to ensure that the solution of the approximation problem is stable; i.e., in the presence of small approximation error $\Vert \mathbf{e}{\Vert }_2$, the reconstruction error $\Vert \mathbf{d}{\Vert }_2$ should also be small. For the sparse approximation problem (20.1), we cannot provide a uniqueness guarantee as such. Still, we can identify criteria which ensure that the solution remains stable when the approximation error is bounded.
Our analysis in this section will focus on identifying criteria which ensures this.

We start with generalizing the notion of spark for the noisy case.

1. Suppose $\mathbf{a}$ and $\mathbf{b}$ are two solutions of (20.1).

2. Then $\Vert \mathcal{D}\mathbf{a}-\mathbf{x}{\Vert }_2\le ϵ$ as well as $\Vert \mathcal{D}\mathbf{b}-\mathbf{x}{\Vert }_2\le ϵ$.

3. Thus, both $\mathcal{D}\mathbf{a}$ and $\mathcal{D}\mathbf{b}$ lie in a ball of radius $ϵ$ around $\mathbf{x}$.

4. Thus, the maximum distance between $\mathcal{D}\mathbf{a}$ and $\mathcal{D}\mathbf{b}$ can be $2ϵ$.

5. Alternatively, using triangle inequality we have

   $$\begin{array}{rl}\Vert \mathcal{D}(\mathbf{a}-\mathbf{b}){\Vert }_2& =\Vert \mathcal{D}\mathbf{a}-\mathbf{x}+\mathbf{x}-\mathcal{D}\mathbf{b}){\Vert }_2\\ & \le \Vert \mathcal{D}\mathbf{a}-\mathbf{x}{\Vert }_2+\Vert \mathbf{x}-\mathcal{D}\mathbf{b}){\Vert }_2\le 2ϵ.\end{array}$$

6. If we define $\mathbf{d}=\mathbf{a}-\mathbf{b}$, then

   $$\Vert \mathcal{D}\mathbf{d}{\Vert }_2\le 2ϵ.$$

20.1.1. Spark $\eta$

Definition 20.1

Let $\mathbf{A}\in {\mathbb{C}}^{N\times D}$ be some matrix. Consider all possible sub-sets of $K$ columns. Let each such set form sub-matrix ${\mathbf{A}}_{\mathrm{\Lambda }}\in {\mathbb{C}}^{N\times K}$ where $\mathrm{\Lambda }$ denotes the index set of $K$ indices chosen. We define ${\mathrm{spark}}_{\eta }(\mathbf{A})$ as the smallest possible $K$ (number of columns) that guarantees

$$\underset{\mathrm{\Lambda }}{min}{\sigma }_K({\mathbf{A}}_{\mathrm{\Lambda }})\le \eta$$

where ${\sigma }_K$ denotes the smallest singular value (i.e. $K$-th singular value) of the sub-matrix ${\mathbf{A}}_{\mathrm{\Lambda }}$. Note that we are minimizing over all possible index sets $\mathrm{\Lambda }$ with $|\mathrm{\Lambda }|=K$.

In words, this is the smallest number of columns (indexed by $\mathrm{\Lambda }$) that can be gathered from $\mathbf{A}$ such that the smallest singular value of ${\mathbf{A}}_{\mathrm{\Lambda }}$ is no larger than $\eta$; i.e., there exists a sub-matrix of $\mathbf{A}$ consisting of ${\mathrm{spark}}_{\eta }(\mathbf{A})$ columns whose smallest singular value is $\eta$ or less. At the same time, all submatrices of $\mathbf{A}$ with number of columns less than ${\mathrm{spark}}_{\eta }(\mathbf{A})$ have the smallest singular value larger than $\eta$.

Relationship with $\mathrm{spark}$:

1. When the smallest singular value is $0$, then the columns are linearly dependent.

2. Thus, by choosing $\eta =0$, we get the smallest number of columns $K$ which are linearly dependent.

3. This matches with the definition of spark.

4. Thus,

   $${\mathrm{spark}}_0(\mathbf{A})=\mathrm{spark}(\mathbf{A}).$$

5. Since singular values are always non-negative, hence $\eta \ge 0$.

Matrix with unit norm columns:

1. When columns of $\mathbf{A}$ are unit-norm (the case of dictionaries), then any single column sub-matrix has a singular value of $1$. Hence,

   $${\mathrm{spark}}_1(\mathbf{A})=1.$$

2. Choosing a value of $\eta >1$ doesn’t make any difference since with a single column sub-matrix, we can show that

   $${\mathrm{spark}}_{\eta }(\mathbf{A})=1\mathrm{\forall }\eta \ge 1.$$

Monotonicity:

1. Let ${\eta }_1>{\eta }_2$. Let

   $$K_2={\mathrm{spark}}_{{\eta }_2}(\mathbf{A}).$$

2. Then there exists a sub-matrix consisting of $K_2$ columns of $\mathbf{A}$ whose smallest singular value is upper bounded by ${\eta }_2$.

3. Since ${\eta }_1>{\eta }_2$, ${\eta }_1$ also serves as an upper bound for the smallest singular value for this sub-matrix.

4. Clearly then $K_1={\mathrm{spark}}_{{\eta }_1}(\mathbf{A})\le K_2$.

5. Thus, we note that ${\mathrm{spark}}_{\eta }$ is a monotone decreasing function of $\eta$. i.e.

   $${\mathrm{spark}}_{{\eta }_1}(\mathbf{A})\le {\mathrm{spark}}_{{\eta }_2}(\mathbf{A}),\text{ whenever }{\eta }_1>{\eta }_2.$$

Maximum value:

1. We recall that the spark of $\mathbf{A}$ is upper bounded by its rank plus one.

2. Assuming $\mathbf{A}$ to be a full rank matrix, we get following inequality:

   $$1\le {\mathrm{spark}}_{\eta }(\mathbf{A})\le {\mathrm{spark}}_0(\mathbf{A})=\mathrm{spark}(\mathbf{A})\le N+1\mathrm{\forall }0\le \eta \le 1.$$

We recall that if $\mathbf{A}\mathbf{v}=\mathbf{0}$ then $\Vert \mathbf{v}{\Vert }_0\ge \mathrm{spark}(\mathbf{A})$. A similar property can be developed for ${\mathrm{spark}}_{\eta }(\mathbf{A})$ also.

Theorem 20.1

If $\Vert \mathbf{A}\mathbf{v}{\Vert }_2\le \eta$ and $\Vert \mathbf{v}{\Vert }_2=1$, then $\Vert \mathbf{v}{\Vert }_0\ge {\mathrm{spark}}_{\eta }(\mathbf{A})$.

Proof. For contradiction, let us assume that $K=\Vert \mathbf{v}{\Vert }_0<{\mathrm{spark}}_{\eta }(\mathbf{A})$.

1. Let $\mathrm{\Lambda }=\mathrm{supp}(\mathbf{v})$.

2. Then $\mathbf{A}\mathbf{v}={\mathbf{A}}_{\mathrm{\Lambda }}{\mathbf{v}}_{\mathrm{\Lambda }}$.

3. Also $\Vert {\mathbf{v}}_{\mathrm{\Lambda }}{\Vert }_2=\Vert \mathbf{v}{\Vert }_2=1$.

4. We recall that the smallest singular value of ${\mathbf{A}}_{\mathrm{\Lambda }}$ is given by

   $${\sigma }_{\text{min}}({\mathbf{A}}_{\mathrm{\Lambda }})=\underset{\Vert \mathbf{x}{\Vert }_2=1}{inf}\Vert {\mathbf{A}}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2.$$

5. Thus,

   $$\Vert {\mathbf{A}}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2\ge {\sigma }_{\text{min}}({\mathbf{A}}_{\mathrm{\Lambda }})\text{ whenever }\Vert \mathbf{x}{\Vert }_2=1.$$

6. Thus, in our particular case

   $$\Vert {\mathbf{A}}_{\mathrm{\Lambda }}{\mathbf{v}}_{\mathrm{\Lambda }}{\Vert }_2\ge {\sigma }_{\text{min}}({\mathbf{A}}_{\mathrm{\Lambda }}).$$

   ${\mathbf{A}}_{\mathrm{\Lambda }}$ has $K$ columns with $K<{\mathrm{spark}}_{\eta }(\mathbf{A})$.

7. Thus, from the definition of ${\mathrm{spark}}_{\eta }(\mathbf{A})$

   $${\sigma }_{\text{min}}({\mathbf{A}}_{\mathrm{\Lambda }})>\eta .$$

8. This gives us

   $$\Vert \mathbf{A}\mathbf{v}{\Vert }_2=\Vert {\mathbf{A}}_{\mathrm{\Lambda }}{\mathbf{v}}_{\mathrm{\Lambda }}{\Vert }_2>\eta$$

   which contradicts with the assumption that $\Vert \mathbf{A}\mathbf{v}{\Vert }_2\le \eta$.

20.1.1.1. Coherence

In the following, we will focus on the ${\mathrm{spark}}_{\eta }$ of a full rank dictionary $\mathcal{D}$. We now establish a connection between ${\mathrm{spark}}_{\eta }$ and coherence of a dictionary.

Theorem 20.2

Let $\mathcal{D}$ be a full rank dictionary with coherence $\mu$. Then

(20.2)$${\mathrm{spark}}_{\eta }(\mathcal{D})\ge \frac{1-{\eta }^2}{\mu }+1.$$

Proof. .

1. We recall from Gershgorin’s theorem that for any square matrix $\mathbf{A}\in {\mathbb{C}}^{K\times K}$, every eigen value $\lambda$ of $\mathbf{A}$ satisfies

   $$|\lambda -a_{ii}|\le \sum _{j,j\ne i}|a_{ij}|\text{ for some }i\in \{1,\dots ,K\}.$$

2. Now consider a matrix $\mathbf{A}$ with diagonal elements equal to 1 and off diagonal elements bounded by a value $\mu$.

3. Then

   $$|\lambda -1|\le \sum _{j,j\ne i}|a_{ij}|\le \sum _{j\ne i}\mu =(K-1)\mu .$$

4. Thus,

   $$\begin{array}{rl}& -(K-1)\mu \le \lambda -1\le (K-1)\mu \\ ⟺& 1-(K-1)\mu \le \lambda \le 1+(K-1)\mu .\end{array}$$

5. This gives us a lower bound on the smallest eigen value.

   $${\lambda }_{min}(\mathbf{A})\ge 1-(K-1)\mu .$$

6. Now consider any index set $\mathrm{\Lambda }\subseteq \{1,\dots ,D\}$ and consider the submatrix ${\mathcal{D}}_{\mathrm{\Lambda }}$ with $|\mathrm{\Lambda }|={\mathrm{spark}}_{\eta }(\mathcal{D})=K$.

7. Define $\mathbf{G}={\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }}$.

8. The diagonal elements of $\mathbf{G}$ are one, while off-diagonal elements are bounded by $\mu$.

9. Thus,

   $$\begin{array}{rl}& {\lambda }_{min}(\mathbf{G})\ge 1-(K-1)\mu \\ ⟺& (K-1)\mu \ge 1-{\lambda }_{min}(\mathbf{G})\\ ⟺& K-1\ge \frac{1-{\lambda }_{min}(\mathbf{G})}{\mu }\\ ⟺& K\ge \frac{1-{\lambda }_{min}(\mathbf{G})}{\mu }+1.\end{array}$$

10. Since this applies to every sub-matrix ${\mathcal{D}}_{\mathrm{\Lambda }}$, this in particular applies to the sub-matrix for which ${\sigma }_{min}({\mathcal{D}}_{\mathrm{\Lambda }})\le \eta$ holds.

11. For this sub-matrix

    $${\lambda }_{min}({\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }})={\sigma }_{min}^2({\mathcal{D}}_{\mathrm{\Lambda }})\le {\eta }^2.$$

12. Thus

    $$K={\mathrm{spark}}_{\eta }(\mathcal{D})\ge \frac{1-{\lambda }_{min}(\mathbf{G})}{\mu }+1\ge \frac{1-{\eta }^2}{\mu }+1.$$

20.1.2. Uncertainty with Spark $\eta$

We now present an uncertainly result for the noisy case.

Theorem 20.3

If ${\mathbf{a}}_1$ and ${\mathbf{a}}_2$ satisfy $\Vert \mathbf{x}-\mathcal{D}{\mathbf{a}}_i{\Vert }_2\le ϵ,i=1,2$, then

(20.3)$$\Vert {\mathbf{a}}_1{\Vert }_0+\Vert {\mathbf{a}}_2{\Vert }_0\ge {\mathrm{spark}}_{\eta }(\mathcal{D}),\text{ where }\eta =\frac{2ϵ}{\Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2}.$$

Proof. .

1. From triangle inequality we have

   $$\Vert \mathcal{D}({\mathbf{a}}_1-{\mathbf{a}}_2){\Vert }_2\le 2ϵ.$$

2. We define $\mathbf{b}={\mathbf{a}}_1-{\mathbf{a}}_2$.

3. Then $\Vert \mathcal{D}\mathbf{b}{\Vert }_2\le 2ϵ$.

4. Further define $\mathbf{v}=\mathbf{b}/\Vert \mathbf{b}{\Vert }_2$ as the normalized vector.

5. Then

   $$\Vert \mathcal{D}\mathbf{v}{\Vert }_2=\frac{\Vert \mathcal{D}\mathbf{b}{\Vert }_2}{\Vert \mathbf{b}{\Vert }_2}\le \frac{2ϵ}{\Vert \mathbf{b}{\Vert }_2}.$$

6. Now define

   $$\eta =\frac{2ϵ}{\Vert \mathbf{b}{\Vert }_2}=\frac{2ϵ}{\Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2}.$$

7. Then from Theorem 20.1 if $\Vert \mathcal{D}\mathbf{v}{\Vert }_2\le \eta$ with $\Vert \mathbf{v}{\Vert }_2=1$, then $\Vert \mathbf{v}{\Vert }_0\ge {\mathrm{spark}}_{\eta }(\mathcal{D})$.

8. Finally,

   $$\Vert {\mathbf{a}}_1{\Vert }_0+\Vert {\mathbf{a}}_2{\Vert }_0\ge \Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_0=\Vert \mathbf{b}{\Vert }_0=\Vert \mathbf{v}{\Vert }_0\ge {\mathrm{spark}}_{\eta }(\mathcal{D}).$$

9. This concludes the proof.

This result gives us a lower bound on the sum of sparsity levels of two different sparse representations of same vector $\mathbf{x}$ under the given bound approximation error.

20.1.3. Localization

We can now develop a localization result for the sparse approximation up to a Euclidean ball. This is analogous to the uniqueness result in noiseless case.

Theorem 20.4

Given a distance $\delta \ge 0$ (bound on distance between two sparse representations) and $ϵ$ (bound on norm of approximation error), set $\eta =2ϵ/\delta$. Suppose there are two approximate representations ${\mathbf{a}}_i,i=1,2$ both obeying

$$\Vert \mathbf{x}-\mathcal{D}{\mathbf{a}}_i{\Vert }_2\le ϵ\text{ and }\Vert {\mathbf{a}}_i{\Vert }_0\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D}).$$

Then $\Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2\le \delta$.

Proof. .

1. Since $\Vert {\mathbf{a}}_i{\Vert }_0\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D})$, hence

   $$\Vert {\mathbf{a}}_1{\Vert }_0+\Vert {\mathbf{a}}_2{\Vert }_0\le {\mathrm{spark}}_{\eta }(\mathcal{D}).$$

2. From Theorem 20.3, if we define

   $$\nu =\frac{2ϵ}{\Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2},$$

   then

   $$\Vert {\mathbf{a}}_1{\Vert }_0+\Vert {\mathbf{a}}_2{\Vert }_0\ge {\mathrm{spark}}_{\nu }(\mathcal{D}).$$

3. Combining the two, we get

   $${\mathrm{spark}}_{\eta }(\mathcal{D})\ge \Vert {\mathbf{a}}_1{\Vert }_0+\Vert {\mathbf{a}}_2{\Vert }_0\ge {\mathrm{spark}}_{\nu }(\mathcal{D}).$$

4. Because of the monotonicity of ${\mathrm{spark}}_{\eta }(\mathcal{D})$, we have

   $$\begin{array}{rl}{\mathrm{spark}}_{\eta }(\mathcal{D})\ge {\mathrm{spark}}_{\nu }(\mathcal{D})& ⟹\eta \le \nu \\ & ⟹\frac{2ϵ}{\delta }\le \frac{2ϵ}{\Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2}\\ & ⟹\delta \ge \Vert {\mathbf{a}}_1-{\mathbf{a}}_2{\Vert }_2\end{array}$$

   which completes our proof.

This theorem says that if $\mathbf{x}$ has two different sufficiently sparse representations ${\mathbf{a}}_i$ with small approximation errors, they fall within a small distance.

20.1.4. Stability using Coherence

We can now develop a stability result for the (20.1) problem in terms of coherence of the dictionary.

Theorem 20.5

Consider an instance of the (20.1) problem defined by the triplet $(\mathcal{D},\mathbf{x},ϵ)$. Suppose that a sparse vector $\mathbf{a}\in {\mathbb{C}}^D$ satisfies the sparsity constraint

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

and gives a representation of $\mathbf{x}$ to within error tolerance $ϵ$ (i.e. $\Vert \mathbf{x}-\mathcal{D}\mathbf{a}{\Vert }_2\le ϵ$). Every solution $\hat{\mathbf{a}}$ of (20.1) must obey

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

Proof. .

1. Note that $\mathbf{a}$ need not be sparsest possible representation of $\mathbf{x}$ within the approximation error $ϵ$.

2. But $\mathbf{a}$ is a feasible point of (20.1).

3. Now since $\hat{\mathbf{a}}$ is an optimal solution of (20.1) (thus sparsest possible), hence it is at least as sparse as $\mathbf{a}$; i.e.,

   $$\Vert \hat{\mathbf{a}}{\Vert }_0\le \Vert \mathbf{a}{\Vert }_0.$$

4. Due to Theorem 18.25,

   $$\frac{1}{2}\mathrm{spark}(\mathcal{D})\ge \frac{1}{2}(1+\frac{1}{\mu })>\Vert \mathbf{a}{\Vert }_0.$$

5. Thus, there exists a value $\eta \ge 0$ such that

   $$\frac{1}{2}\mathrm{spark}(\mathcal{D})\ge \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D})\ge \Vert \mathbf{a}{\Vert }_0\ge \Vert \hat{\mathbf{a}}{\Vert }_0.$$

6. From Theorem 20.2 we recall that

   $${\mathrm{spark}}_{\eta }(\mathcal{D})\ge \frac{1-{\eta }^2}{\mu }+1.$$

7. Thus, we can find a suitable value of $\eta \ge 0$ such that we can enforce a stricter requirement:

   $$\Vert \mathbf{a}{\Vert }_0\le \frac{1}{2}(\frac{1-{\eta }^2}{\mu }+1)\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D}).$$

8. From this we can develop an upper bound on $\eta$ being

   $$\begin{array}{rl}\Vert \mathbf{a}{\Vert }_0\le \frac{1}{2}(\frac{1-{\eta }^2}{\mu }+1)& ⟺2\Vert \mathbf{a}{\Vert }_0\mu \le 1-{\eta }^2+\mu \\ & ⟺{\eta }^2\le 1-\mu (2\Vert \mathbf{a}{\Vert }_0-1).\end{array}$$

9. If we choose ${\eta }^2=1-\mu (2\Vert \mathbf{a}{\Vert }_0-1)$, then

   $$\begin{array}{rl}\Vert \mathbf{a}{\Vert }_0=\frac{1}{2}(\frac{1-{\eta }^2}{\mu }+1)& ⟹\Vert \mathbf{a}{\Vert }_0\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D})\\ & ⟹\Vert \hat{\mathbf{a}}{\Vert }_0\le \Vert \mathbf{a}{\Vert }_0\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D})\end{array}$$

   continues to hold.

10. We have two solutions $\mathbf{a}$ and $\hat{\mathbf{a}}$ both of which satisfy

    $$\Vert \mathbf{a}{\Vert }_0,\Vert \hat{\mathbf{a}}{\Vert }_0\le \frac{1}{2}{\mathrm{spark}}_{\eta }(\mathcal{D})$$

    and

    $$\Vert \mathbf{x}-\mathcal{D}\mathbf{a}{\Vert }_2,\Vert \mathbf{x}-\mathcal{D}\hat{\mathbf{a}}{\Vert }_2\le ϵ.$$

11. If we choose a $\delta =\frac{2ϵ}{\eta }$, then applying Theorem 20.4, we will get

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