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{split}& \underset{\bv}{\text{minimize}} & & \| \bv \|_0 \\ & \text{subject to } & & \bDDD \bv = \bzero.\end{split}$

Note that the solution $$\bv^*$$ of this problem is not unique. If $$\bv^*$$ is a solution that $$c \bv^*$$ for any $$c \neq 0$$ is also a solution. Spark is the optimum value of the objective function $$\| \bv \|_0$$. We now define a sequence of optimization problems for $$k = 1, \dots, D$$

(18.58)#$\begin{split} & \underset{\bv}{\text{minimize}} & & \| \bv \|_0 \\ & \text{subject to } & & \bDDD \bv = \bzero, v_k = 1.\end{split}$
1. The $$k$$-th problem constrains the solution to choose atom $$\bd_k$$ from the dictionary.

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

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

$\spark(\bDDD) = \underset{1 \leq k \leq D} {\text{minimize }}\| \bv_k^{0, *}\|_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{split} & \underset{\bv}{\text{minimize }} & & \| \bv \|_1 \\ & \text{subject to } & & \bDDD \bv = \bzero, v_k = 1.\end{split}$
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 $$\bv_k^{1, *}$$.

3. Since $$\bDDD \bv_k^{1, *} = \bzero$$, hence $$\bv_k^{1, *}$$ is feasible for (18.58).

4. Thus,

$\| \bv_k^{0, *}\|_0 \leq \| \bv_k^{1, *}\|_0.$
5. This gives us the relationship

$\spark(\bDDD) \leq \underset{1 \leq k \leq D}{\text{minimize }} \| \bv_k^{1, *}\|_0.$

We formally state the upper bound on $$\spark(\bDDD)$$ in the following theorem [28].

Theorem 18.70

Let $$\bDDD$$ be a dictionary. Then

$\spark(\bDDD) \leq \underset{1 \leq k \leq D}{\text{minimize }} \| \bv_k^{1, *}\|_0$

where $$\bv_k^{1, *}$$ 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 $$\bDDD \in \CC^{N \times D}$$ consisting of $$D$$ atoms. The coherence of $$\bDDD$$ is denoted by $$\mu (\bDDD)$$. In short we will simply write it as $$\mu$$. A subdictionary will be indexed by an index set $$\Lambda$$ consisting of linearly independent atoms.

Theorem 18.71

Suppose that $$(K - 1) \mu < 1$$ and assume that $$| \Lambda | \leq K$$. Then

$\| \bDDD_{\Lambda}^{\dag} \|_{2 \to \infty} \leq \frac{1}{\sqrt{ 1 - ( K - 1) \mu}}.$

Equivalently, the rows of $$\bDDD_{\Lambda}^{\dag}$$ have $$\ell_2$$ norms no greater than $$\frac{1}{\sqrt{ 1 - ( K - 1) \mu}}$$.

Proof. We recall that the operator norm $$\| \bDDD_{\Lambda}^{\dag} \|_{2 \to \infty}$$ computes the maximum $$\ell_2$$ norm among the rows of $$\bDDD_{\Lambda}^{\dag}$$. TODO COMPLETE ITS PROOF.

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

Definition 18.33

Let $$\bG = \bDDD^H \bDDD$$ be the Gram matrix for dictionary $$\bDDD$$. We define $$\mu_{1/2}(\bG)$$ 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 $$\bG$$ 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}(\bG)$$ can be related to Babel function.

Theorem 18.72

$\mu_{1/2}(\bG) \geq \frac{1}{2\mu}.$

Proof. Since $$\mu$$ is the maximum absolute value of any off diagonal term in $$\bG = \bDDD^H \bDDD$$, hence sum of any $$m$$ terms, say $$T$$, is bounded by

$T \leq m \mu.$

Thus

$T \geq \frac{1}{2} \implies m \mu \geq \frac{1}{2} \implies m \geq \frac{1}{2\mu}.$

Since $$\mu_{1/2}(\bG)$$ is the minimum number of off diagonal terms whose sum exceeds $$1/2$$, hence

$\mu_{1/2}(\bG) \geq \frac{1}{2\mu}.$

The following result is due to [28].

Theorem 18.73

$\spark(\bDDD) \geq 2 \mu_{1/2}(G) +1.$

Proof. We proceed as follows.

1. Let $$\bh \in \NullSpace(\bDDD)$$.

2. Then

$\bDDD \bh = \bzero \implies \bG \bh = \bDDD^H \bDDD \bh = \bzero.$
3. Subtracting both sides with $$\bh$$ we get

$\bG \bh - \bh = (\bG - \bI) \bh = -\bh.$
4. Let $$\Lambda = \supp(\bh)$$.

5. By taking columns indexed by $$\Lambda$$ from $$\bG - \bI$$ and corresponding entries in $$\bh$$, we can write:

$(\bG - \bI)_{\Lambda} \bh_{\lambda} = - \bh.$
6. Taking $$\ell_{\infty}$$ norm on both sides we get

$\| \bh \|_{\infty} = \| (\bG - \bI)_{\Lambda} \bh_{\lambda} \|_{\infty}.$
7. We know that

$\| (\bG - \bI)_{\Lambda} \bh_{\lambda} \|_{\infty} \leq \| (\bG - \bI)_{\Lambda} \|_{\infty} \| \bh_{\lambda} \|_{\infty}$
8. It is easy to see that:

$\| \bh_{\lambda} \|_{\infty} = \| \bh \|_{\infty}.$
9. Thus

$\| \bh \|_{\infty} \leq \| (\bG - \bI)_{\Lambda} \|_{\infty} \| \bh \|_{\infty}.$
10. This gives us

$\| (\bG - \bI)_{\Lambda} \|_{\infty} \geq 1.$
11. But $$\| (\bG - \bI)_{\Lambda} \|_{\infty}$$ is nothing but the maximum sum of magnitudes of off diagonal entries in $$\bG$$ along a row in $$\bG_{\Lambda}$$.

12. Consider any row in $$(\bG - \bI)_{\Lambda}$$.

13. One of the entries in the row (on the main diagonal of $$\bG - \bI$$) is 0.

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

15. $$\Lambda$$ is smallest when $$|\Lambda | = \spark(\bDDD)$$.

16. For such a $$\Lambda$$, there exists a row in $$\bG$$ such that the sum of $$\spark(\bDDD) - 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 $$\bG$$ such that the sum of their magnitudes exceeds one.

18. Clearly

$\spark(\bDDD) - 1 \geq n.$
19. It is easy to see that

$n \geq 2 \mu_{1/2} (\bG)$

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

$\spark(\bDDD) - 1 \geq 2 \mu_{1/2} (G).$
21. Rewriting, we get

$\spark(\bDDD) \geq 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 $$\bDDD$$ as the dictionary.

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

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

4. Why a pair of dictionaries?

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

$\bx \approx \Phi \ba$

are built.

2. $$\Psi$$ on the other hand is the sensing dictionary which will be used to compute correlations with the signal $$\bx$$ and try to estimate the approximation $$\ba$$.

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

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

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

18.9.4. p-Babel Function#

See [43] for reference.

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

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

(18.60)#$\mu_p(\Phi, \Psi, \Lambda) \triangleq \underset{l \notin \Lambda}{\sup} \left (\sum_{j \in \Lambda} |\langle \phi_j, \psi_l \rangle |^p \right )^{\frac{1}{p}}.$

What is going on here?

1. Consider the row vector

$\bv^l = \psi_l^H \Phi_{\Lambda}.$
2. This vector contains inner products of modeling atoms in $$\Phi$$ indexed by $$\Lambda$$ with the sensing atom $$\psi_l$$.

3. Now

$\| \bv^l \|_p = \left ( \sum_{i} | v^l_i |^p \right )^{\frac{1}{p}} = \left ( \sum_{j \in \Lambda} | \langle \phi_j, \psi_l \rangle |^p \right )^{\frac{1}{p}}$
4. This is the term in (18.60).

5. Thus

$\mu_p(\Phi, \Psi, \Lambda) = \underset{l \notin \Lambda}{\sup} \| v^l \|_p.$
6. $$\| v^l \|_p$$ is a measure of the correlation of the sensing atom $$\psi_l$$ with a group of modeling atoms in $$\Phi$$ indexed by $$\Lambda$$ using the $$p$$-norm.

7. $$\mu_p(\Phi, \Psi, \Lambda)$$ attempts to find out a sensing atom from $$\Psi$$ outside the index set $$\Lambda$$ which is most correlated to the group of modeling atoms in $$\Phi$$ indexed by $$\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 $$\Lambda$$.

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

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

(18.61)#$\mu_p^{\text{in}}(\Phi, \Psi, \Lambda) \triangleq \underset{i \in \Lambda}{\sup} \, \mu_p \left (\Phi_{\Lambda}, \Psi_{\Lambda}, \Lambda \setminus \{i \} \right).$

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

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

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

Definition 18.36 ($$p$$ Babel function)

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

(18.62)#$\mu_p(\Phi, \Psi, K) \triangleq \underset{|\Lambda| \leq K}{\sup}\, \mu_p(\Phi, \Psi, \Lambda).$

Correspondingly, the complement of Babel function is defined as

(18.63)#$\mu_p^{\text{in}}(\Phi, \Psi, K) \triangleq \underset{|\Lambda| \leq K}{\sup}\, \mu_p^{\text{in}}(\Phi, \Psi, \Lambda).$

It is straightforward to see that

(18.64)#$\mu_p^{\text{in}}(\Phi, \Psi, K) \leq \mu_p(\Phi, \Psi, K-1).$

Now consider the special case where $$\bDDD=\Phi=\Psi$$. In other words, the sensing and modeling dictionaries are same.

We obtain

(18.65)#$\mu_p(\bDDD, \Lambda) = \underset{l \notin \Lambda}{\sup} \left (\sum_{j \in \Lambda} |\langle \bd_j, \bd_l \rangle |^p \right )^{\frac{1}{p}}.$
(18.66)#$\mu_p^{\text{in}}(\bDDD, \Lambda) = \underset{i \in \Lambda}{\sup} \, \mu_p \left (\bDDD_{\Lambda}, \Lambda \setminus \{i \} \right).$
(18.67)#$\mu_p(\bDDD, K) = \underset{|\Lambda| \leq K}{\sup}\, \mu_p(\bDDD, \Lambda).$
(18.68)#$\mu_p^{\text{in}}(\bDDD, K) = \underset{|\Lambda| \leq K}{\sup}\, \mu_p^{\text{in}}(\bDDD, \Lambda).$

Further by choosing $$p=1$$, we get

(18.69)#$\mu_1(\bDDD, \Lambda) = \underset{l \notin \Lambda}{\sup} \left (\sum_{j \in \Lambda} |\langle \bd_j, \bd_l \rangle | \right ).$
(18.70)#$\mu_1^{\text{in}}(\bDDD, \Lambda) = \underset{i \in \Lambda}{\sup} \, \mu_1 \left ( \bDDD_{\Lambda}, \Lambda \setminus \{i \} \right).$
(18.71)#$\mu_1(\bDDD, K) = \underset{|\Lambda| \leq K}{\sup}\, \mu_1(\bDDD, \Lambda).$
(18.72)#$\mu_1^{\text{in}}(\bDDD, K) = \underset{|\Lambda| \leq K}{\sup}\, \mu_1^{\text{in}}(\bDDD, \Lambda).$

Finally compare this definition of $$\mu_1(\bDDD, K)$$ with the standard definition of Babel function as

(18.73)#$\mu_1(K) = \underset{|\Lambda| = K}{\max} \; \underset {\psi}{\max} \sum_{\Lambda} | \langle \psi, \bd_{\lambda} \rangle |,$

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

We also know that $$\mu_1(K)$$ is an increasing function of $$K$$. Thus, replacing $$|\Lambda| = K$$ with $$|\Lambda| \leq 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(\bDDD, 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 $$\bDDD_{\Lambda}$$ is defined as

$\ERC(\bDDD_{\Lambda}) = 1 - \underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1.$

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

The quantity is called exact recovery coefficient since for a number of algorithms the criteria $$\ERC(\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 $$\ERC(\Lambda)$$ in terms of Babel function.

Theorem 18.74 (ERC lower bound: babel function)

Suppose that $$|\Lambda| = k \leq K$$. A lower bound on Exact Recovery Coefficient is

$\ERC(\Lambda) \geq \frac{1 - \mu_1(K- 1) - \mu_1(K)}{1 - \mu_1(K-1)}.$

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

$\mu_1(K- 1) + \mu_1 (K) < 1.$

Proof. 1. Let us expand the pseudo-inverse $$\bDDD_{\Lambda}^{\dag}$$.

$\begin{split} \underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1 &= \underset{\omega \notin \Lambda}{\max} \left \|\left (\bDDD_{\Lambda}^H \bDDD_{\Lambda} \right )^{-1} \bDDD_{\Lambda}^H \bd_{\omega} \right \|_1\\ &\leq \|\left (\bDDD_{\Lambda}^H \bDDD_{\Lambda} \right )^{-1} \|_{1 \to 1} \underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^H \bd_{\omega} \|_1. \end{split}$
1. For the Gram matrix $$\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}$$ we recall from Theorem 18.37 that:

$\| \bG^{-1} \|_{1} \leq \frac{1}{1 - \mu_1(k - 1)} \leq \frac{1}{1 - \mu_1(K - 1)} .$
2. For the other term we have

$\underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^H \bd_{\omega} \|_1 = \underset{\omega \notin \Lambda}{\max} \sum_{\lambda \in \Lambda}| \langle \bd_{\omega}, \bd_{\lambda} \rangle | \leq \mu_1(k) \leq \mu_1(K).$
3. Thus, we get

$\underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1 \leq \frac{\mu_1(K)}{1 - \mu_1(K - 1)}.$
4. Putting back in the definition of Exact Recovery Coefficient:

$\ERC(\Lambda) = 1 - \underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1 \geq 1 - \frac{\mu_1(K)}{1 - \mu_1(K - 1)}.$
5. This completes the bound on ERC.

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

$\begin{split} \mu_1(K) + \mu_1(K - 1) < 1 &\iff \mu_1(K) < 1 - \mu_1(K - 1) \\ &\iff \frac{\mu_1(K)}{1 - \mu_1(K - 1)} < 1 \\ &\iff 1 - \frac{\mu_1(K)}{1 - \mu_1(K - 1)} > 0. \end{split}$
7. Thus, if $$\mu_1(K) + \mu_1(K - 1) < 1$$, then the lower bound on $$\ERC(\Lambda)$$ is positive leading to $$\ERC(\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 $$|\Lambda| = k \leq K$$. A lower bound on Exact Recovery Coefficient is

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

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

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

Proof. .

1. Following the proof of Theorem 18.74 for the Gram matrix $$\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}$$ have:

$\| \bG^{-1} \|_{1} \leq \frac{1}{1 - \mu_1(K - 1)} \leq \frac{1}{1 - (K - 1)\mu}.$
2. For the other term we have

$\underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^H \bd_{\omega} \|_1 \leq \mu_1(K) \leq K \mu.$
3. Thus, we get

$\underset{\omega \notin \Lambda}{\max} \|\bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1 \leq \frac{K \mu}{1 - (K - 1)\mu}.$
4. Putting back in the definition of Exact Recovery Coefficient:

$\ERC(\Lambda) \geq 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 $$\ERC(\Lambda) > 0$$.

$K \mu \leq \frac{1}{2} \implies 2 K \mu \leq 1 \implies 1 - 2K \mu \geq 0 \implies 1 - 2K \mu + \mu > 0.$
7. And

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

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

Theorem 18.76

$$\ERC(\Lambda) > 0$$ holds whenever

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

where $$K = | \Lambda|$$.

Proof. .

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

$\begin{split} &\frac{1 - (2K - 1) \mu}{1 - (K - 1)\mu} > 0 \\ \iff & 1 - (2K - 1) \mu > 0\\ \iff & 1 > (2K - 1) \mu \\ \iff & 2K - 1 < \frac{1}{\mu}\\ \iff & K < \frac{1}{2} \left (1 + \frac{1}{\mu} \right ). \end{split}$
2. From Theorem 18.75, we have

$\ERC(\Lambda) \geq \frac{1 - (2K - 1) \mu}{1 - (K - 1)\mu}.$
3. Thus under the given conditions, we have

$\ERC(\Lambda) > 0.$
4. We also need to show that under these conditions

$1 - (K - 1)\mu > 0.$
5. We can see that:

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

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 $$\bDDD_{\Lambda}$$ is defined as the set of signals given by

$\AAA_1 (\Lambda) = \{\bDDD_{\Lambda} \bx \ST \bx \in \CC^{\Lambda} \text{ and } \| \bx \|_1 \leq 1\}.$

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

1. We recall that $$\bP_{\Lambda} = \bDDD_{\Lambda} \bDDD_{\Lambda}^{\dag}$$ is the orthogonal projector on to the column space of $$\bDDD_{\Lambda}$$.

2. Therefore $$\bc_{\omega} = \bDDD_{\Lambda}^{\dag} \bd_{\omega} \in \CC^{\Lambda}$$ is a coefficient vector which can be used to synthesize this projection.

3. In other words:

$\bP_{\Lambda} \bd_{\omega} = \bDDD_{\Lambda} \bDDD_{\Lambda}^{\dag} \bd_{\omega} = \bDDD_{\Lambda} \bc_{\omega}.$
4. Thus, the quantity $$1 - \| \bDDD_{\Lambda}^{\dag} \bd_{\omega} \|_1$$ measures how far the projected atom $$\bP_{\Lambda} \bd_{\omega}$$ lies from the boundary of $$\AAA_1 (\Lambda)$$.

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

6. This happens because coefficient associated with an atom outside $$\Lambda$$ must be quite large to represent anything in the span of the subdictionary whenever $$\ERC(\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 \Forall 1\leq k \leq N.$

In particular, the standard Babel function is given by

$\mu_1(k) = k\mu$

Proof. TODO prove it.