18.9. Dictionaries II

This section continues the development of dictionaries for sparse and redundant representations.

18.9.1. Spark

We present some more results on spark of a dictionary.

18.9.1.1. Upper Bounds for Spark

Whenever a set of atoms in a dictionary are linearly dependent, the dependence corresponds to some vector in its null space. Thus, identifying the spark of a dictionary essentially amounts of sifting through the vectors in its null space and finding one with smallest ${\ell }_0$-“norm”. This can be cast as an optimization problem:

(18.57)$$\begin{array}{rlrl}& \underset{\mathbf{v}}{\text{minimize}}& & \Vert \mathbf{v}{\Vert }_0\\ & \text{subject to }& & \mathcal{D}\mathbf{v}=\mathbf{0}.\end{array}$$

Note that the solution ${\mathbf{v}}^{\ast }$ of this problem is not unique. If ${\mathbf{v}}^{\ast }$ is a solution that $c{\mathbf{v}}^{\ast }$ for any $c\ne 0$ is also a solution. Spark is the optimum value of the objective function $\Vert \mathbf{v}{\Vert }_0$. We now define a sequence of optimization problems for $k=1,\dots ,D$

(18.58)$$\begin{array}{rlrl}& \underset{\mathbf{v}}{\text{minimize}}& & \Vert \mathbf{v}{\Vert }_0\\ & \text{subject to }& & \mathcal{D}\mathbf{v}=\mathbf{0},v_k=1.\end{array}$$

1. The $k$-th problem constrains the solution to choose atom ${\mathbf{d}}_k$ from the dictionary.

2. Since the minimal set of linearly dependent atoms in $\mathcal{D}$ will contain at least two vectors, hence $\mathrm{spark}(\mathcal{D})$ would correspond to the optimal value of one (or more) of the problems (18.58).

3. Formally, if we denote ${\mathbf{v}}_k^{0,\ast }$ as an optimal vector for the problem (18.58), then

   $$\mathrm{spark}(\mathcal{D})=\underset{1\le k\le D}{\text{minimize }}\Vert {\mathbf{v}}_k^{0,\ast }{\Vert }_0.$$

4. Thus, solving (18.57) is equivalent to solving all $D$ problems specified by (18.58) and then finding the minimum ${\ell }_0$-“norm” among them.

5. The problems (18.58) are still computationally intractable.

We now change each of the ${\ell }_0$-“norm” (18.58) minimization problems to ${\ell }_1$-“norm” minimization problems.

(18.59)$$\begin{array}{rlrl}& \underset{\mathbf{v}}{\text{minimize }}& & \Vert \mathbf{v}{\Vert }_1\\ & \text{subject to }& & \mathcal{D}\mathbf{v}=\mathbf{0},v_k=1.\end{array}$$

1. We have a convex objective and convex (linear) constraints. These are tractable problems.

2. Let us indicate an optimal solution of (18.59) as ${\mathbf{v}}_k^{1,\ast }$.

3. Since $\mathcal{D}{\mathbf{v}}_k^{1,\ast }=\mathbf{0}$, hence ${\mathbf{v}}_k^{1,\ast }$ is feasible for (18.58).

4. Thus,

   $$\Vert {\mathbf{v}}_k^{0,\ast }{\Vert }_0\le \Vert {\mathbf{v}}_k^{1,\ast }{\Vert }_0.$$

5. This gives us the relationship

   $$\mathrm{spark}(\mathcal{D})\le \underset{1\le k\le D}{\text{minimize }}\Vert {\mathbf{v}}_k^{1,\ast }{\Vert }_0.$$

We formally state the upper bound on $\mathrm{spark}(\mathcal{D})$ in the following theorem [28].

Theorem 18.70

Let $\mathcal{D}$ be a dictionary. Then

$$\mathrm{spark}(\mathcal{D})\le \underset{1\le k\le D}{\text{minimize }}\Vert {\mathbf{v}}_k^{1,\ast }{\Vert }_0$$

where ${\mathbf{v}}_k^{1,\ast }$ is a solution of the problem (18.59).

18.9.2. Coherence

In this subsection we develop some more bounds using coherence of a dictionary. As usual, we will be considering an overcomplete dictionary $\mathcal{D}\in {\mathbb{C}}^{N\times D}$ consisting of $D$ atoms. The coherence of $\mathcal{D}$ is denoted by $\mu (\mathcal{D})$. In short we will simply write it as $\mu$. A subdictionary will be indexed by an index set $\mathrm{\Lambda }$ consisting of linearly independent atoms.

Theorem 18.71

Suppose that $(K-1)\mu <1$ and assume that $|\mathrm{\Lambda }|\le K$. Then

$$\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\Vert }_{2\to \mathrm{\infty }}\le \frac{1}{\sqrt{1-(K-1)\mu }}.$$

Equivalently, the rows of ${\mathcal{D}}_{\mathrm{\Lambda }}^{†}$ have ${\ell }_2$ norms no greater than $\frac{1}{\sqrt{1-(K-1)\mu }}$.

Proof. We recall that the operator norm $\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\Vert }_{2\to \mathrm{\infty }}$ computes the maximum ${\ell }_2$ norm among the rows of ${\mathcal{D}}_{\mathrm{\Lambda }}^{†}$. TODO COMPLETE ITS PROOF.

The following definition is due to [22, 28].

Definition 18.33

Let $\mathbf{G}={\mathcal{D}}^H\mathcal{D}$ be the Gram matrix for dictionary $\mathcal{D}$. We define ${\mu }_{1/2}(\mathbf{G})$ as the smallest number $m$ such that the sum of magnitudes of a collection of $m$ off-diagonal entries in a single row or column of the Gram matrix $\mathbf{G}$ is at least $\frac{1}{2}$.

This quantity was introduced in [28] for developing more accurate bounds compared to bounds based on coherence. At that time the idea of Babel function was not available. A careful examination reveals that ${\mu }_{1/2}(\mathbf{G})$ can be related to Babel function.

Theorem 18.72

$${\mu }_{1/2}(\mathbf{G})\ge \frac{1}{2\mu }.$$

Proof. Since $\mu$ is the maximum absolute value of any off diagonal term in $\mathbf{G}={\mathcal{D}}^H\mathcal{D}$, hence sum of any $m$ terms, say $T$, is bounded by

$$T\le m\mu .$$

Thus

$$T\ge \frac{1}{2}⟹m\mu \ge \frac{1}{2}⟹m\ge \frac{1}{2\mu }.$$

Since ${\mu }_{1/2}(\mathbf{G})$ is the minimum number of off diagonal terms whose sum exceeds $1/2$, hence

$${\mu }_{1/2}(\mathbf{G})\ge \frac{1}{2\mu }.$$

The following result is due to [28].

Theorem 18.73

$$\mathrm{spark}(\mathcal{D})\ge 2{\mu }_{1/2}(G)+1.$$

Proof. We proceed as follows.

1. Let $\mathbf{h}\in \mathcal{N}(\mathcal{D})$.

2. Then

   $$\mathcal{D}\mathbf{h}=\mathbf{0}⟹\mathbf{G}\mathbf{h}={\mathcal{D}}^H\mathcal{D}\mathbf{h}=\mathbf{0}.$$

3. Subtracting both sides with $\mathbf{h}$ we get

   $$\mathbf{G}\mathbf{h}-\mathbf{h}=(\mathbf{G}-\mathbf{I})\mathbf{h}=-\mathbf{h}.$$

4. Let $\mathrm{\Lambda }=\mathrm{supp}(\mathbf{h})$.

5. By taking columns indexed by $\mathrm{\Lambda }$ from $\mathbf{G}-\mathbf{I}$ and corresponding entries in $\mathbf{h}$, we can write:

   $$(\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\mathbf{h}}_{\lambda }=-\mathbf{h}.$$

6. Taking ${\ell }_{\mathrm{\infty }}$ norm on both sides we get

   $$\Vert \mathbf{h}{\Vert }_{\mathrm{\infty }}=\Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\mathbf{h}}_{\lambda }{\Vert }_{\mathrm{\infty }}.$$

7. We know that

   $$\Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\mathbf{h}}_{\lambda }{\Vert }_{\mathrm{\infty }}\le \Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\Vert }_{\mathrm{\infty }}\Vert {\mathbf{h}}_{\lambda }{\Vert }_{\mathrm{\infty }}$$

8. It is easy to see that:

   $$\Vert {\mathbf{h}}_{\lambda }{\Vert }_{\mathrm{\infty }}=\Vert \mathbf{h}{\Vert }_{\mathrm{\infty }}.$$

9. Thus

   $$\Vert \mathbf{h}{\Vert }_{\mathrm{\infty }}\le \Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\Vert }_{\mathrm{\infty }}\Vert \mathbf{h}{\Vert }_{\mathrm{\infty }}.$$

10. This gives us

    $$\Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\Vert }_{\mathrm{\infty }}\ge 1.$$

11. But $\Vert (\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}{\Vert }_{\mathrm{\infty }}$ is nothing but the maximum sum of magnitudes of off diagonal entries in $\mathbf{G}$ along a row in ${\mathbf{G}}_{\mathrm{\Lambda }}$.

12. Consider any row in $(\mathbf{G}-\mathbf{I}{)}_{\mathrm{\Lambda }}$.

13. One of the entries in the row (on the main diagonal of $\mathbf{G}-\mathbf{I}$) is 0.

14. Thus, there are a maximum of $|\mathrm{\Lambda }|-1$ nonzero entries in the row.

15. $\mathrm{\Lambda }$ is smallest when $|\mathrm{\Lambda }|=\mathrm{spark}(\mathcal{D})$.

16. For such a $\mathrm{\Lambda }$, there exists a row in $\mathbf{G}$ such that the sum of $\mathrm{spark}(\mathcal{D})-1$ off diagonal entries in the row exceeds 1.

17. Let $n$ denote the minimum number of off diagonal elements on a row or a column of $\mathbf{G}$ such that the sum of their magnitudes exceeds one.

18. Clearly

    $$\mathrm{spark}(\mathcal{D})-1\ge n.$$

19. It is easy to see that

    $$n\ge 2{\mu }_{1/2}(\mathbf{G})$$

    i.e. minimum number of off diagonal elements summing up to 1 or more is at least twice the minimum number of off diagonal elements summing up to $\frac{1}{2}$ or more on any row (or column due to Hermitian property).

20. Thus

    $$\mathrm{spark}(\mathcal{D})-1\ge 2{\mu }_{1/2}(G).$$

21. Rewriting, we get

    $$\mathrm{spark}(\mathcal{D})\ge 2{\mu }_{1/2}(G)+1.$$

18.9.3. Babel function

In this subsection, we provide a more general development of Babel function for a pair of dictionaries.

1. When we consider a single dictionary, we will use $\mathcal{D}$ as the dictionary.

2. When considering a pair of dictionaries of equal size, we would typically label them as $\mathrm{\Phi }$ and $\mathrm{\Psi }$ with both $\mathrm{\Phi },\mathrm{\Psi }\in {\mathbb{C}}^{N\times D}$.

3. We will assume that the dictionaries are full rank as they span the signal space ${\mathbb{C}}^N$.

4. Why a pair of dictionaries?

   1. We consider $\mathrm{\Phi }$ as a modeling dictionary from which the sparse signals

      $$\mathbf{x}\approx \mathrm{\Phi }\mathbf{a}$$

      are built.

   2. $\mathrm{\Psi }$ on the other hand is the sensing dictionary which will be used to compute correlations with the signal $\mathbf{x}$ and try to estimate the approximation $\mathbf{a}$.

   3. Ideally, $\mathrm{\Phi }$ and $\mathrm{\Psi }$ should be same.

   4. But in real life, we may not know $\mathrm{\Phi }$ correctly.

   5. Hence, $\mathrm{\Psi }$ would be a dictionary slightly different from $\mathrm{\Phi }$.

18.9.4. p-Babel Function

See [43] for reference.

Definition 18.34 ($p$-Babel function over $\mathrm{\Lambda }$)

Consider an index set $\mathrm{\Lambda }\subset \{1,\dots ,D\}$ indexing a subset of atoms in $\mathrm{\Phi }$ and $\mathrm{\Psi }$. The $p$-Babel function over $\mathrm{\Lambda }$ is defined as

(18.60)$${\mu }_p(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda })\triangleq \underset{l\notin \mathrm{\Lambda }}{sup}{(\sum _{j\in \mathrm{\Lambda }}|⟨{\varphi }_j,{\psi }_l⟩{|}^p)}^{\frac{1}{p}}.$$

What is going on here?

1. Consider the row vector

   $${\mathbf{v}}^l={\psi }_l^H{\mathrm{\Phi }}_{\mathrm{\Lambda }}.$$

2. This vector contains inner products of modeling atoms in $\mathrm{\Phi }$ indexed by $\mathrm{\Lambda }$ with the sensing atom ${\psi }_l$.

3. Now

   $$\Vert {\mathbf{v}}^l{\Vert }_p={\left(\sum _i|v_i^l{|}^p\right)}^{\frac{1}{p}}={(\sum _{j\in \mathrm{\Lambda }}|⟨{\varphi }_j,{\psi }_l⟩{|}^p)}^{\frac{1}{p}}$$

4. This is the term in (18.60).

5. Thus

   $${\mu }_p(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda })=\underset{l\notin \mathrm{\Lambda }}{sup}\Vert v^l{\Vert }_p.$$

6. $\Vert v^l{\Vert }_p$ is a measure of the correlation of the sensing atom ${\psi }_l$ with a group of modeling atoms in $\mathrm{\Phi }$ indexed by $\mathrm{\Lambda }$ using the $p$-norm.

7. ${\mu }_p(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda })$ attempts to find out a sensing atom from $\mathrm{\Psi }$ outside the index set $\mathrm{\Lambda }$ which is most correlated to the group of modeling atoms in $\mathrm{\Phi }$ indexed by $\mathrm{\Lambda }$ and returns the maximum correlation value.

8. Different choices of $p$-norm lead to different correlation values.

We can also measure a correlation of sensing and modeling atoms inside the index set $\mathrm{\Lambda }$.

Definition 18.35 (Complementary $p$-Babel function over $\mathrm{\Lambda }$)

A complement to the $p$-Babel function measures the amount of correlation between atoms inside the support $\mathrm{\Lambda }$:

(18.61)$${\mu }_p^{\text{in}}(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda })\triangleq \underset{i\in \mathrm{\Lambda }}{sup}{\mu }_p({\mathrm{\Phi }}_{\mathrm{\Lambda }},{\mathrm{\Psi }}_{\mathrm{\Lambda }},\mathrm{\Lambda }\setminus \{i\}).$$

${\mu }_p({\mathrm{\Phi }}_{\mathrm{\Lambda }},{\mathrm{\Psi }}_{\mathrm{\Lambda }},\mathrm{\Lambda }\setminus \{i\})$ computes the correlation of $i$-th sensing atom in $\mathrm{\Psi }$ with the modeling atoms in $\mathrm{\Phi }$ indexed by $\mathrm{\Lambda }\setminus \{i\}$ i.e. all modeling atoms in $\mathrm{\Lambda }$ except the $i$-th modeling atom.

Finally ${\mu }_p^{\text{in}}(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda })$ finds the maximum correlation of any sensing atom inside $\mathrm{\Lambda }$ with modeling atoms inside $\mathrm{\Lambda }$ (leaving the corresponding modeling atom).

So far, we have focused our attention to a specific index set $\mathrm{\Lambda }$. We now consider all index sets with $|\mathrm{\Lambda }|\le K$.

Definition 18.36 ($p$ Babel function)

The Babel function for a pair of dictionaries $\mathrm{\Phi }$ and $\mathrm{\Psi }$ as a function of the sparsity level $K$ is defined as

(18.62)$${\mu }_p(\mathrm{\Phi },\mathrm{\Psi },K)\triangleq \underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_p(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda }).$$

Correspondingly, the complement of Babel function is defined as

(18.63)$${\mu }_p^{\text{in}}(\mathrm{\Phi },\mathrm{\Psi },K)\triangleq \underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_p^{\text{in}}(\mathrm{\Phi },\mathrm{\Psi },\mathrm{\Lambda }).$$

It is straightforward to see that

(18.64)$${\mu }_p^{\text{in}}(\mathrm{\Phi },\mathrm{\Psi },K)\le {\mu }_p(\mathrm{\Phi },\mathrm{\Psi },K-1).$$

Now consider the special case where $\mathcal{D}=\mathrm{\Phi }=\mathrm{\Psi }$. In other words, the sensing and modeling dictionaries are same.

We obtain

(18.65)$${\mu }_p(\mathcal{D},\mathrm{\Lambda })=\underset{l\notin \mathrm{\Lambda }}{sup}{(\sum _{j\in \mathrm{\Lambda }}|⟨{\mathbf{d}}_j,{\mathbf{d}}_l⟩{|}^p)}^{\frac{1}{p}}.$$

(18.66)$${\mu }_p^{\text{in}}(\mathcal{D},\mathrm{\Lambda })=\underset{i\in \mathrm{\Lambda }}{sup}{\mu }_p({\mathcal{D}}_{\mathrm{\Lambda }},\mathrm{\Lambda }\setminus \{i\}).$$

(18.67)$${\mu }_p(\mathcal{D},K)=\underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_p(\mathcal{D},\mathrm{\Lambda }).$$

(18.68)$${\mu }_p^{\text{in}}(\mathcal{D},K)=\underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_p^{\text{in}}(\mathcal{D},\mathrm{\Lambda }).$$

Further by choosing $p=1$, we get

(18.69)$${\mu }_1(\mathcal{D},\mathrm{\Lambda })=\underset{l\notin \mathrm{\Lambda }}{sup}(\sum _{j\in \mathrm{\Lambda }}|⟨{\mathbf{d}}_j,{\mathbf{d}}_l⟩|).$$

(18.70)$${\mu }_1^{\text{in}}(\mathcal{D},\mathrm{\Lambda })=\underset{i\in \mathrm{\Lambda }}{sup}{\mu }_1({\mathcal{D}}_{\mathrm{\Lambda }},\mathrm{\Lambda }\setminus \{i\}).$$

(18.71)$${\mu }_1(\mathcal{D},K)=\underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_1(\mathcal{D},\mathrm{\Lambda }).$$

(18.72)$${\mu }_1^{\text{in}}(\mathcal{D},K)=\underset{|\mathrm{\Lambda }|\le K}{sup}{\mu }_1^{\text{in}}(\mathcal{D},\mathrm{\Lambda }).$$

Finally compare this definition of ${\mu }_1(\mathcal{D},K)$ with the standard definition of Babel function as

(18.73)$${\mu }_1(K)=\underset{|\mathrm{\Lambda }|=K}{max}\underset{\psi }{max}\sum _{\mathrm{\Lambda }}|⟨\psi ,{\mathbf{d}}_{\lambda }⟩|,$$

where the vector $\psi$ ranges over the atoms indexed by $\mathrm{\Omega }\setminus \mathrm{\Lambda }$.

We also know that ${\mu }_1(K)$ is an increasing function of $K$. Thus, replacing $|\mathrm{\Lambda }|=K$ with $|\mathrm{\Lambda }|\le K$ doesn’t make any difference to the value of ${\mu }_1(K)$.

Careful observation shows that the definitions of ${\mu }_1(K)$ in (18.73) and ${\mu }_1(\mathcal{D},K)$ in (18.71) are exactly the same.

18.9.5. Exact Recovery Coefficient

we introduce a measure of similarity between a subdictionary and the remaining atoms from the dictionary known as the exact recovery coefficient.

Definition 18.37 (Exact recovery coefficient)

The Exact Recovery Coefficient [77, 78, 79] for a subdictionary ${\mathcal{D}}_{\mathrm{\Lambda }}$ is defined as

$$\mathrm{ERC}({\mathcal{D}}_{\mathrm{\Lambda }})=1-\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1.$$

We will also use the notation $\mathrm{ERC}(\mathrm{\Lambda })$ when the dictionary is clear from context.

The quantity is called exact recovery coefficient since for a number of algorithms the criteria $\mathrm{ERC}(\mathrm{\Lambda })>0$ is a sufficient condition for exact recovery of sparse representations.

18.9.5.1. ERC and Babel Function

We present a lower bound on $\mathrm{ERC}(\mathrm{\Lambda })$ in terms of Babel function.

Theorem 18.74 (ERC lower bound: babel function)

Suppose that $|\mathrm{\Lambda }|=k\le K$. A lower bound on Exact Recovery Coefficient is

$$\mathrm{ERC}(\mathrm{\Lambda })\ge \frac{1-{\mu }_1(K-1)-{\mu }_1(K)}{1-{\mu }_1(K-1)}.$$

It follows that $\mathrm{ERC}(\mathrm{\Lambda })>0$ whenever

$${\mu }_1(K-1)+{\mu }_1(K)<1.$$

Proof. 1. Let us expand the pseudo-inverse ${\mathcal{D}}_{\mathrm{\Lambda }}^{†}$.

$$\begin{array}{rl}\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1& =\underset{\omega \notin \mathrm{\Lambda }}{max}{\Vert {\left({\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }}\right)}^{-1}{\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathbf{d}}_{\omega }\Vert }_1\\ & \le \Vert {\left({\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }}\right)}^{-1}{\Vert }_{1\to 1}\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathbf{d}}_{\omega }{\Vert }_1.\end{array}$$

1. For the Gram matrix $\mathbf{G}={\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }}$ we recall from Theorem 18.37 that:

   $$\Vert {\mathbf{G}}^{-1}{\Vert }_1\le \frac{1}{1-{\mu }_1(k-1)}\le \frac{1}{1-{\mu }_1(K-1)}.$$

2. For the other term we have

   $$\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathbf{d}}_{\omega }{\Vert }_1=\underset{\omega \notin \mathrm{\Lambda }}{max}\sum _{\lambda \in \mathrm{\Lambda }}|⟨{\mathbf{d}}_{\omega },{\mathbf{d}}_{\lambda }⟩|\le {\mu }_1(k)\le {\mu }_1(K).$$

3. Thus, we get

   $$\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1\le \frac{{\mu }_1(K)}{1-{\mu }_1(K-1)}.$$

4. Putting back in the definition of Exact Recovery Coefficient:

   $$\mathrm{ERC}(\mathrm{\Lambda })=1-\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1\ge 1-\frac{{\mu }_1(K)}{1-{\mu }_1(K-1)}.$$

5. This completes the bound on ERC.

6. Now, we verify the condition for $\mathrm{ERC}(\mathrm{\Lambda })>0$.

   $$\begin{array}{rl}{\mu }_1(K)+{\mu }_1(K-1)<1& ⟺{\mu }_1(K)<1-{\mu }_1(K-1)\\ & ⟺\frac{{\mu }_1(K)}{1-{\mu }_1(K-1)}<1\\ & ⟺1-\frac{{\mu }_1(K)}{1-{\mu }_1(K-1)}>0.\end{array}$$

7. Thus, if ${\mu }_1(K)+{\mu }_1(K-1)<1$, then the lower bound on $\mathrm{ERC}(\mathrm{\Lambda })$ is positive leading to $\mathrm{ERC}(\mathrm{\Lambda })>0$.

18.9.5.2. ERC and Coherence

On the same lines we develop a coherence bound for ERC.

Theorem 18.75 (ERC lower bound: coherence)

Suppose that $|\mathrm{\Lambda }|=k\le K$. A lower bound on Exact Recovery Coefficient is

$$\mathrm{ERC}(\mathrm{\Lambda })\ge \frac{1-(2K-1)\mu }{1-(K-1)\mu }.$$

It follows that $\mathrm{ERC}(\mathrm{\Lambda })>0$ whenever

$$K\mu \le \frac{1}{2}.$$

Proof. .

1. Following the proof of Theorem 18.74 for the Gram matrix $\mathbf{G}={\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathcal{D}}_{\mathrm{\Lambda }}$ have:

   $$\Vert {\mathbf{G}}^{-1}{\Vert }_1\le \frac{1}{1-{\mu }_1(K-1)}\le \frac{1}{1-(K-1)\mu }.$$

2. For the other term we have

   $$\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^H{\mathbf{d}}_{\omega }{\Vert }_1\le {\mu }_1(K)\le K\mu .$$

3. Thus, we get

   $$\underset{\omega \notin \mathrm{\Lambda }}{max}\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1\le \frac{K\mu }{1-(K-1)\mu }.$$

4. Putting back in the definition of Exact Recovery Coefficient:

   $$\mathrm{ERC}(\mathrm{\Lambda })\ge 1-\frac{K\mu }{1-(K-1)\mu }=\frac{1-(2K-1)\mu }{1-(K-1)\mu }.$$

5. This completes the bound on ERC.

6. Now, we verify the condition for $\mathrm{ERC}(\mathrm{\Lambda })>0$.

   $$K\mu \le \frac{1}{2}⟹2K\mu \le 1⟹1-2K\mu \ge 0⟹1-2K\mu +\mu >0.$$

7. And

   $$K\mu \le \frac{1}{2}⟹1-K\mu \ge \frac{1}{2}⟹1-K\mu +\mu \ge \frac{1}{2}+\mu .$$

8. Thus $K\mu \le \frac{1}{2}$ ensures that both numerator and denominator for the coherence lower bound on $\mathrm{ERC}(\mathrm{\Lambda })$ are positive leading to $\mathrm{ERC}(\mathrm{\Lambda })>0$.

A more accurate bound on $K$ is presented in the next theorem.

Theorem 18.76

$\mathrm{ERC}(\mathrm{\Lambda })>0$ holds whenever

$$K<\frac{1}{2}(1+\frac{1}{\mu })$$

where $K=|\mathrm{\Lambda }|$.

Proof. .

1. Assuming $1-(K-1)\mu >0$, we have

   $$\begin{array}{rl}& \frac{1-(2K-1)\mu }{1-(K-1)\mu }>0\\ ⟺& 1-(2K-1)\mu >0\\ ⟺& 1>(2K-1)\mu \\ ⟺& 2K-1<\frac{1}{\mu }\\ ⟺& K<\frac{1}{2}(1+\frac{1}{\mu }).\end{array}$$

2. From Theorem 18.75, we have

   $$\mathrm{ERC}(\mathrm{\Lambda })\ge \frac{1-(2K-1)\mu }{1-(K-1)\mu }.$$

3. Thus under the given conditions, we have

   $$\mathrm{ERC}(\mathrm{\Lambda })>0.$$

4. We also need to show that under these conditions

   $$1-(K-1)\mu >0.$$

5. We can see that:

   $$\begin{array}{rl}& 2K-1<\frac{1}{\mu }\\ ⟹& 2K-2<\frac{1}{\mu }-1\\ ⟹& 2(K-1)\mu <1-\mu \\ ⟹& -(K-1)\mu >\frac{\mu }{2}-\frac{1}{2}\\ ⟹& 1-(K-1)\mu >\frac{1}{2}+\frac{\mu }{2}\\ ⟹& 1-(K-1)\mu >0.\end{array}$$

18.9.5.3. Geometrical Interpretation of ERC

Definition 18.38 (Antipodal convex hull of a subdictionary)

The antipodal convex hull [78] of a subdictionary ${\mathcal{D}}_{\mathrm{\Lambda }}$ is defined as the set of signals given by

$${\mathcal{A}}_1(\mathrm{\Lambda })=\{{\mathcal{D}}_{\mathrm{\Lambda }}\mathbf{x}|\mathbf{x}\in {\mathbb{C}}^{\mathrm{\Lambda }}\text{ and }\Vert \mathbf{x}{\Vert }_1\le 1\}.$$

It is the smallest convex set that contains every unit multiple of every atom.

1. We recall that ${\mathbf{P}}_{\mathrm{\Lambda }}={\mathcal{D}}_{\mathrm{\Lambda }}{\mathcal{D}}_{\mathrm{\Lambda }}^{†}$ is the orthogonal projector on to the column space of ${\mathcal{D}}_{\mathrm{\Lambda }}$.

2. Therefore ${\mathbf{c}}_{\omega }={\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }\in {\mathbb{C}}^{\mathrm{\Lambda }}$ is a coefficient vector which can be used to synthesize this projection.

3. In other words:

   $${\mathbf{P}}_{\mathrm{\Lambda }}{\mathbf{d}}_{\omega }={\mathcal{D}}_{\mathrm{\Lambda }}{\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }={\mathcal{D}}_{\mathrm{\Lambda }}{\mathbf{c}}_{\omega }.$$

4. Thus, the quantity $1-\Vert {\mathcal{D}}_{\mathrm{\Lambda }}^{†}{\mathbf{d}}_{\omega }{\Vert }_1$ measures how far the projected atom ${\mathbf{P}}_{\mathrm{\Lambda }}{\mathbf{d}}_{\omega }$ lies from the boundary of ${\mathcal{A}}_1(\mathrm{\Lambda })$.

5. If every projected atom lies well within the antipodal convex hull, then it is possible to recover superpositions of atoms from $\mathrm{\Lambda }$.

6. This happens because coefficient associated with an atom outside $\mathrm{\Lambda }$ must be quite large to represent anything in the span of the subdictionary whenever $\mathrm{ERC}(\mathrm{\Lambda })>0$.

18.9.6. Dirac DCT Dictionary

Theorem 18.77

The $p$-Babel function for Dirac-DCT dictionary is given by

$${\mu }_p(k)=k^{\frac{1}{p}}\mu \mathrm{\forall }1\le k\le N.$$

In particular, the standard Babel function is given by

$${\mu }_1(k)=k\mu$$

Proof. TODO prove it.