18.6. Dictionaries

In this section we review various properties associated with a dictionary \(\bDDD\) which are useful in understanding the behavior and capabilities of a dictionary.

We recall that a dictionary \(\bDDD\) consists of a finite number of unit norm vectors in \(\CC^N\) called atoms which span the signal space \(\CC^N\). Atoms of the dictionary are indexed by an index set \(\Omega\); i.e.,

\[ \bDDD = \{ \bd_{\omega} : \omega \in \Omega \} \]

with \(|\Omega| = D\) and \(N \leq D\) with \(\| d_{\omega} \|_2 = 1\) for every atom.

The vectors \(\bx \in \CC^N\) can be represented by a synthesis matrix consisting of the atoms of \(\bDDD\) by a vector \(\ba \in \CC^D\) as

\[ \bx = \bDDD \ba. \]

Note that we are using the same symbol \(\bDDD\) to represent the dictionary as a set of atoms as well as the corresponding synthesis matrix. We can write the matrix \(\bDDD\) consisting of its columns as

\[ \bDDD = \begin{bmatrix} \bd_1 & \dots & \bd_D \end{bmatrix} \]

This shouldn’t be causing any confusion. When we write the subscript as \(\bd_{\omega}\) where \(\omega \in \Omega\) we are referring to the atoms of the dictionary \(\bDDD\) indexed by the set \(\Omega\), while when we write the subscript as \(\bd_i\) we are referring to a column of corresponding synthesis matrix. In this case, \(\Omega\) will simply mean the index set \(\{ 1, \dots, D \}\). Obviously \(|\Omega| = D\) holds still.

Often, we will be working with a subset of atoms in a dictionary. Usually such a subset of atoms will be indexed by an index set \(\Lambda \subseteq \Omega\). \(\Lambda\) will take the form of \(\Lambda \subseteq \{\omega_1, \dots, \omega_D\}\) or \(\Lambda \subseteq \{1, \dots, D\}\) depending upon whether we are talking about the subset of atoms in the dictionary or a subset of columns from the corresponding synthesis matrix.

Often we will need the notion of a subdictionary [79] described below.

18.6.1. Subdictionaries

Definition 18.16 (Subdictionary)

A subdictionary is a linearly independent collection of atoms. Let \(\Lambda \subset \{\omega_1, \dots, \omega_D\}\) be the index set for the atoms in the subdictionary. We denote the subdictionary as \(\bDDD_{\Lambda}\). We also use \(\bDDD_{\Lambda}\) to denote the corresponding matrix with \(\Lambda \subset \{1, \dots, D\}\).

Remark 18.5 (Rank of subdictionary)

A subdictionary is full rank.

This is obvious since it is a collection of linearly independent atoms.

For subdictionaries, often we will say \(K = | \Lambda |\) and \(\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}\) as its Gram matrix. Sometimes, we will also be considering \(\bG^{-1}\). \(\bG^{-1}\) has a useful interpretation in terms of the dual vectors for the atoms in \(\bDDD_{\Lambda}\) [78].

Let \(\{ \bd_{\lambda} \}_{\lambda \in \Lambda}\) denote the atoms in \(\bDDD_{\Lambda}\). Let \(\{ \bc_{\lambda} \}_{\lambda \in \Lambda}\) be chosen such that

\[ \langle \bd_{\lambda} , \bc_{\lambda} \rangle = 1 \]

and

\[ \langle \bd_{\lambda} , \bc_{\omega} \rangle = 0 \text { for } \lambda, \omega \in \Lambda, \lambda \neq \omega. \]

Each dual vector \(\bc_{\lambda}\) is orthogonal to atoms in the subdictionary at different indices and is long enough so that its inner product with \(\bd_{\lambda}\) is one. The dual system somehow inverts the sub-dictionary. In fact the dual vectors are nothing but the columns of the matrix \(\bB = (\bDDD_{\Lambda}^{\dag})^H\). Now, a simple calculation shows that:

\[ \bB^H \bB = (\bDDD_{\Lambda}^{\dag}) (\bDDD_{\Lambda}^{\dag})^H = (\bDDD_{\Lambda}^H \bDDD_{\Lambda})^{-1} \bDDD_{\Lambda}^H \bDDD_{\Lambda} (\bDDD_{\Lambda}^H \bDDD_{\Lambda})^{-1} = (\bDDD_{\Lambda}^H \bDDD_{\Lambda})^{-1} = \bG^{-1}. \]

Therefore, the inverse Gram matrix lists the inner products between the dual vectors.

Sometimes we will be discussing tools which apply for general matrices. We will use the symbol \(\Phi\) for representing general matrices. Whenever the dictionary is an orthonormal basis, we will use the symbol \(\Psi\).

18.6.2. Spark

Definition 18.17 (Spark)

The spark of a given matrix \(\Phi\) is the smallest number of columns of \(\Phi\) that are linearly dependent. If all columns are linearly independent, then the spark is defined to be number of columns plus one.

Note that the definition of spark applies to all matrices (wide, tall or square). It is not restricted to the synthesis matrices for a dictionary.

Correspondingly, the spark of a dictionary is defined as the minimum number of atoms which are linearly dependent.

We recall that rank of a matrix is defined as the maximum number of columns which are linearly independent. Definition of spark bears remarkable resemblance yet its very hard to obtain as it requires a combinatorial search over all possible subsets of columns of \(\Phi\).

Example 18.21 (Spark)

1. Spark of the \(3 \times 3\) identity matrix

   \[\begin{split} \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{split}\]

   is 4 since all columns are linearly independent.

2. Spark of the \(2 \times 4\) matrix

   \[\begin{split} \begin{pmatrix} 1 & 0 & -1 & 0\\ 0 & 1 & 0 & -1 \end{pmatrix} \end{split}\]

   is 2 since column 1 and 3 are linearly dependent.

3. If a matrix has a column with all zero entries, then the spark of such a matrix is 1. This is a trivial case and we will not consider such matrices in the sequel.

4. In general for an \(N \times D\) synthesis matrix, \(\spark(\bDDD) \in [2, N+1]\).

A naive combinatorial algorithm to calculate the spark of a matrix is given below.

Algorithm 18.1 (A naive algorithm for computing the spark of a matrix)

Inputs:

1. \(\Phi\): a matrix

Outputs:

1. \(s\): Spark of \(\Phi\)

Algorithm:

1. Let \(R \leftarrow \rank (\Phi)\).

2. For every \(j \leftarrow 1,\dots, R\):

   1. Identify \(\binom{D}{j}\) ways of choosing \(j\) columns from \(D\) columns of \(\Phi\).

   2. For every choice of \(j\) columns:

      1. If columns are linearly dependent:

         1. \(s \leftarrow j\).

         2. Return.

3. All columns are linearly independent.

4. \(s \leftarrow R + 1\).

18.6.2.1. Spark and Nullspace

Remark 18.6 (Spark and sparsity of null space vectors)

The \(\ell_0\)-“norm” of vectors belonging to null space of a matrix \(\Phi\) is greater than or equal to \(\spark(\Phi)\):

\[ \| \bx \|_0 \geq \spark(\Phi) \Forall \bx \in \NullSpace(\Phi). \]

Proof. We proceed as follows:

1. If \(\bx \in \NullSpace(\Phi)\) then \(\Phi \bx = \bzero\).

2. Thus non-zero entries in \(\bx\) pick a set of columns in \(\Phi\) which are linearly dependent.

3. Clearly \(\| \bx \|_0\) indicates the number of columns in the set which are linearly dependent.

4. By definition, spark of \(\Phi\) indicates the minimum number of columns which are linearly dependent.

5. Hence the result:

   \[ \| \bx \|_0 \geq \spark(\Phi) \Forall \bx\in \NullSpace(\Phi). \]

18.6.2.2. Uniqueness-Spark

Spark is useful in characterizing the uniqueness of the solution of a \((\bDDD, K)\)-EXACT-SPARSE problem (see Definition 18.8). We now present a criteria based on spark which characterizes the uniqueness of a sparse solution to the problem \(\by = \Phi \bx\).

Theorem 18.23 (Uniqueness of a sparse solution for an underdetermined system via spark)

Consider a solution \(\bx^*\) to the underdetermined system \(\by = \Phi \bx\). If \(\bx^*\) obeys

\[ \| \bx^* \|_0 < \frac{\spark(\Phi)}{2} \]

then it is necessarily the sparsest solution.

Proof. Let \(\bx'\) be some other solution to the problem. Then

\[ \Phi \bx' = \Phi \bx^* \implies \Phi (\bx' - \bx^*) = \bzero \implies (\bx' - \bx^*) \in \NullSpace(\Phi). \]

Due to Remark 18.6 we have

\[ \| \bx' - \bx^* \|_0 \geq \spark(\Phi). \]

Now

\[ \| \bx' \|_0 + \| \bx^* \|_0 \geq \| \bx' - \bx^* \|_0 \geq \spark(\Phi). \]

Hence, if \(\| \bx^* \|_0 < \frac{\spark(\Phi)}{2}\), then we have

\[ \| \bx' \|_0 > \frac{\spark(\Phi)}{2} \]

for any other solution \(\bx'\) to the equation \(\by = \Phi \bx\). Thus \(\bx^*\) is necessarily the sparsest possible solution.

This result is quite useful as it establishes a global optimality criterion for the \((\bDDD, K)\)-EXACT-SPARSE problem.

As long as \(K < \frac{1}{2}\spark(\Phi)\) this theorem guarantees that the solution to \((\bDDD, K)\)-EXACT-SPARSE problem is unique. This is quite surprising result for a non-convex combinatorial optimization problem. We are able to guarantee a global uniqueness for the solution based on a simple check on the sparsity of the solution.

Note that we are only saying that if a sufficiently sparse solution is found then it is unique. We are not claiming that it is possible to find such a solution.

Obviously, the larger the spark, we can guarantee uniqueness for signals with higher sparsity levels. So a natural question is: How large can spark of a dictionary be? We consider few examples.

Example 18.22 (Spark of Gaussian dictionaries)

Consider a dictionary \(\bDDD\) whose atoms \(\bd_{i}\) are random vectors independently drawn from normal distribution.

1. Since a dictionary requires all its atoms to be unit-norms, hence we divide the each of the random vectors with their norms.

2. We know that with probability \(1\) any set of \(N\) independent Gaussian random vectors is linearly independent.

3. Also, since \(\bd_i \in \RR^N\) hence a set of \(N+1\) atoms is always linearly dependent.

4. Thus \(\spark(\bDDD) = N +1\).

Thus, if a solution to EXACT-SPARSE problem contains \(\frac{N}{2}\) or fewer non-zero entries then it is necessarily unique with probability 1.

Example 18.23 (Spark of Dirac Fourier basis)

For

\[ \bDDD = \begin{bmatrix} \bI & \bF \end{bmatrix} \in \CC^{N \times 2N} \]

it can be shown that

\[ \spark(\bDDD) = 2 \sqrt{N}. \]

In this case, the sparsity level of a unique solution must be less than \(\sqrt{N}\).

18.6.3. Coherence

Finding out the spark of a dictionary \(\bDDD\) is NP-hard since it involves considering combinatorially large number of selections of columns from \(\bDDD\). In this section we consider the coherence of a dictionary which is computationally tractable and quite useful in characterizing the solutions of sparse approximation problems.

Definition 18.18 (Coherence of a dictionary)

The coherence of a dictionary \(\bDDD\) is defined as the maximum absolute inner product between two distinct atoms in the dictionary:

\[ \mu = \underset{j \neq k}{\max} | \langle \bd_{\omega_j}, \bd_{\omega_k} \rangle | = \underset{j \neq k}{\max} | (\bDDD^H \bDDD)_{j k} |. \]

If the dictionary consists of two orthonormal bases, then coherence is also known as mutual coherence or proximity; see Definition 18.1.

We note that \(d_{\omega_i}\) is the \(i\)-th column of synthesis matrix \(\bDDD\). Also \(\bDDD^H \bDDD\) is the Gram matrix for \(\bDDD\) whose elements are nothing but the inner-products of columns of \(\bDDD\).

We note that by definition \(\| d_{\omega} \|_2 = 1\) hence \(\mu \leq 1\) and since absolute values are considered hence \(\mu \geq 0\). Thus, \(0 \leq \mu \leq 1\).

For an orthonormal basis \(\Psi\) all atoms are orthogonal to each other, hence

\[ | \langle \psi_{\omega_j}, \psi_{\omega_k} \rangle |= 0 \text{ whenever } j \neq k. \]

Thus \(\mu = 0\) for an orthonormal basis.

In the following, we will use the notation \(|\bA|\) to denote a matrix consisting of absolute values of entries in a matrix \(\bA\); i.e.,

\[ | \bA |_{i j} = | \bA _{i j} |. \]

The off-diagonal entries of the Gram matrix are captured by the matrix \(\bDDD^H \bDDD - I\). Note that all diagonal entries in \(\bDDD^H \bDDD - I\) are zero since atoms of \(\bDDD\) are unit norm. Moreover, each of the entries in \( | \bDDD^H \bDDD - I |\) is dominated by \(\mu(\bDDD)\).

The inner product between any two atoms \(| \langle \bd_{\omega_j}, \bd_{\omega_k} \rangle |\) is a measure of how much they look alike or how much they are correlated. Coherence just picks up the two vectors which are most alike and returns their correlation. In a way \(\mu\) is quite a blunt measure of the quality of a dictionary, yet it is quite useful.

If a dictionary is uniform in the sense that there is not much variation in \(| \langle \bd_{\omega_j}, \bd_{\omega_k} \rangle |\), then \(\mu\) captures the behavior of the dictionary quite well.

Definition 18.19 (Incoherent dictionary)

We say that a dictionary is incoherent if the coherence of the dictionary is small.

We are looking for dictionaries which are incoherent. In the sequel we will see how incoherence plays a role in sparse approximation.

Example 18.24 (Coherence of two ortho bases)

We established in Theorem 18.3 that coherence of two ortho-bases is bounded by

\[ \frac{1}{\sqrt{N}} \leq \mu \leq 1. \]

In particular we showed in Theorem 18.4 that coherence of Dirac Fourier basis is \(\frac{1}{\sqrt{N}}\).

Example 18.25 (Coherence: Multi-ONB dictionary)

A dictionary of concatenated orthonormal bases is called a multi-ONB. For some \(N\), it is possible to build a multi-ONB which contains \(N\) or even \(N+1\) bases yet retains the minimal coherence \(\mu = \frac{1}{\sqrt{N}}\) possible.

Theorem 18.24 (Coherence lower bound)

A lower bound on the coherence of a general dictionary is given by

\[ \mu \geq \sqrt{\frac{D-N}{N(D-1)}}. \]

Definition 18.20 (Grassmannian frame)

If each atomic inner product meets this bound, the dictionary is called an optimal Grassmannian frame.

The definition of coherence can be extended to arbitrary matrices \(\Phi \in \CC^{N \times D}\).

Definition 18.21 (Coherence for arbitrary matrices)

The coherence of a matrix \(\Phi \in \CC^{N \times D}\) is defined as the maximum absolute normalized inner product between two distinct columns in the matrix. Let

\[ \Phi = \begin{bmatrix} \phi_1 & \phi_2 & \dots & \phi_D \end{bmatrix}. \]

Then coherence of \(\Phi\) is given by

(18.32)\[\mu(\Phi) = \underset{j \neq k}{\text{max}} \frac{ | \langle \phi_j, \phi_k \rangle |} {\| \phi_j \|_2 \| \phi_k \|_2}\]

It is assumed that none of the columns in \(\Phi\) is a zero vector.

18.6.3.1. Lower Bounds for Spark

Coherence of a matrix is easy to compute. More interestingly it also provides a lower bound on the spark of a matrix.

Theorem 18.25 (Lower bound on spark in terms of coherence)

For any matrix \(\Phi \in \CC^{N \times D}\) (with non-zero columns) the following relationship holds

\[ \spark(\Phi) \geq 1 + \frac{1}{\mu(\Phi)}. \]

Proof. We note that scaling of a column of \(\Phi\) doesn’t change either the spark or coherence of \(\Phi\). Therefore, we assume that the columns of \(\Phi\) are normalized.

1. We now construct the Gram matrix of \(\Phi\) given by \(\bG = \Phi^H \Phi\).

2. We note that

   \[ \bG_{k k} = 1 \quad \Forall 1 \leq k \leq D \]

   since each column of \(\Phi\) is unit norm.

3. Also

   \[ |G_{k j}| \leq \mu(\Phi) \quad \Forall 1 \leq k, j \leq D , k \neq j. \]

4. Consider any \(p\) columns from \(\Phi\) and construct its Gram matrix.

5. This is nothing but a leading minor of size \(p \times p\) from the matrix \(\bG\).

6. From the Gershgorin disk theorem, if this minor is diagonally dominant, i.e. if

   \[ \sum_{j \neq i} |G_{i j}| < | G_{i i}| \Forall i \]

   then this sub-matrix of \(\bG\) is positive definite and so corresponding \(p\) columns from \(\Phi\) are linearly independent.

7. But

   \[ |G_{i i}| = 1 \]

   and

   \[ \sum_{j \neq i} |G_{i j}| \leq (p-1) \mu(\Phi) \]

   for the minor under consideration.

8. Hence for \(p\) columns to be linearly independent the following condition is sufficient

   \[ (p-1) \mu (\Phi) < 1. \]

9. Thus if

   \[ p < 1 + \frac{1}{\mu(\Phi)}, \]

   then every set of \(p\) columns from \(\Phi\) is linearly independent.

10. Hence, the smallest possible set of linearly dependent columns must satisfy

    \[ p \geq 1 + \frac{1}{\mu(\Phi)}. \]

11. This establishes the lower bound that

    \[ \spark(\Phi) \geq 1 + \frac{1}{\mu(\Phi)}. \]

This bound on spark doesn’t make any assumptions on the structure of the dictionary. In fact, imposing additional structure on the dictionary can give better bounds. Let us look at an example for a two ortho-basis [28].

Theorem 18.26 (Lower bound on spark for two ortho bases)

Let \(\bDDD\) be a two ortho-basis. Then

\[ \spark (\bDDD) \geq \frac{2}{\mu(\bDDD)}. \]

Proof. From Theorem 18.6 we know that for any vector \(\bv \in \NullSpace(\bDDD)\)

\[ \| \bv \|_0 \geq \frac{2}{\mu(\bDDD)}. \]

But

\[ \spark(\bDDD) = \underset{\bv \in \NullSpace(\bDDD)} {\min}( \| \bv \|_0). \]

Thus

\[ \spark(\bDDD) \geq \frac{2}{\mu(\bDDD)}. \]

For maximally incoherent two orthonormal bases, we know that \(\mu = \frac{1}{\sqrt{N}}\). A perfect example is the pair of Dirac and Fourier bases. In this case \(\spark(\bDDD) \geq 2 \sqrt{N}\).

18.6.3.2. Uniqueness-Coherence

We can now establish a uniqueness condition for sparse solution of \(\by = \Phi \bx\).

Theorem 18.27 (Uniqueness of a sparse solution of an underdetermined system via coherence)

Consider a solution \(\bx^*\) to the under-determined system \(\by = \Phi \bx\). If \(\bx^*\) obeys

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

then it is necessarily the sparsest solution.

Proof. This is a straightforward application of Theorem 18.23 and Theorem 18.25.

It is interesting to compare the two uniqueness theorems: Theorem 18.23 and Theorem 18.27.

Theorem 18.23 uses spark, is sharp and is far more powerful than Theorem 18.27.

Coherence can never be smaller than \(\frac{1}{\sqrt{N}}\), therefore the bound on \(\| \bx^* \|_0\) in Theorem 18.27 can never be larger than \(\frac{\sqrt{N} + 1}{2}\).

However, spark can be easily as large as \(N\) and then bound on \(\| \bx^* \|_0\) can be as large as \(\frac{N}{2}\).

We recall from Theorem 18.8 that the bound for sparsity level of sparest solution in two-ortho basis \(\Eta = \begin{bmatrix}\Psi & \Chi \end{bmatrix}\) is given by

\[ \| \bx^* \|_0 < \frac{1}{\mu(\Eta)} \]

which is a larger bound than Theorem 18.27 for general dictionaries by a factor of 2.

Thus, we note that coherence gives a weaker bound than spark for supportable sparsity levels of unique solutions. The advantage that coherence has is that it is easily computable and doesn’t require any special structure on the dictionary (two ortho basis has a special structure).

18.6.3.3. Singular Values of Subdictionaries

Theorem 18.28 (Singular values of subdictionaries and coherence)

Let \(\bDDD\) be a dictionary and \(\bDDD_{\Lambda}\) be a subdictionary. Let \(\mu\) be the coherence of \(\bDDD\). Let \(K = | \Lambda |\). Then the eigen values of \(\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}\) satisfy:

\[ 1 - (K - 1) \mu \leq \lambda \leq 1 + (K - 1) \mu. \]

Moreover, the singular values of the sub-dictionary \(\bDDD_{\Lambda}\) satisfy

\[ \sqrt{1 - (K - 1) \mu} \leq \sigma (\bDDD_{\Lambda}) \leq \sqrt{1 + (K - 1) \mu}. \]

Proof. We recall from Gershgorin’s circle theorem that for any square matrix \(\bA \in \CC^{K \times K}\), every eigen value \(\lambda\) of \(\bA\) satisfies

\[ | \lambda - a_{ii} | \leq \sum_{j \neq i} |a_{i j}| \text{ for some } i \in \{ 1, \dots, K\}. \]

1. Now consider the matrix \(\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}\) with diagonal elements equal to 1 and off diagonal elements bounded by the coherence \(\mu\).

2. Then

   \[ | \lambda - 1 | \leq \sum_{j \neq i} |G_{i j}| \leq \sum_{j \neq i} \mu = (K - 1) \mu. \]

3. Thus,

   \[ - (K - 1) \mu \leq \lambda - 1 \leq (K - 1) \mu \iff 1 - (K - 1) \mu \leq \lambda \leq 1 + (K - 1) \mu. \]

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

   \[ \lambda_{\min} (\bG) \geq 1 - (K - 1) \mu. \]

5. Since \(\bG\) is positive definite (\(\bDDD_{\Lambda}\) is full-rank), hence its eigen values are positive. Thus, the above lower bound is useful only if

   \[ 1 - (K - 1) \mu > 0 \iff 1 > (K - 1) \mu \iff \mu < \frac{1}{K - 1}. \]

6. We also get an upper bound on the eigen values of \(\bG\) given by

   \[ \lambda_{\max} (G) \leq 1 + (K - 1) \mu. \]

7. The bounds on singular values of \(\bDDD_{\Lambda}\) are obtained as a straight-forward extension by taking square roots on the expressions.

18.6.3.4. Embeddings using Subdictionaries

Theorem 18.29 (Norm bounds for embeddings with real dictionaries)

Let \(\bDDD\) be a real dictionary and \(\bDDD_{\Lambda}\) be a subdictionary with \(K = |\Lambda|\). Let \(\mu\) be the coherence of \(\bDDD\). Let \(\bv \in \RR^K\) be an arbitrary vector. Then

\[ | \bv |^T [I - \mu (\OneMat - I)] | \bv | \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq | \bv |^T [I + \mu (\OneMat - I)] | \bv | \]

where \(\OneMat\) is a \(K\times K\) matrix of all ones. Moreover

\[ (1 - (K - 1) \mu) \| \bv \|_2^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq (1 + (K - 1) \mu)\| \bv \|_2^2. \]

Proof. We can see that

\[ \| \bDDD_{\Lambda} \bv \|_2^2 = \bv^T \bDDD_{\Lambda}^T \bDDD_{\Lambda} \bv. \]

1. Expanding we have

   \[ \bv^T \bDDD_{\Lambda}^T \bDDD_{\Lambda} \bv = \sum_{i=1}^K \sum_{j=1}^K v_i \bd_{\lambda_i}^T \bd_{\lambda_j} v_j. \]

2. The terms in the R.H.S. for \(i = j\) are given by

   \[ v_i \bd_{\lambda_i}^T \bd_{\lambda_i} v_i = | v_i |^2. \]

3. Summing over \(i = 1, \dots, K\), we get

   \[ \sum_{i=1}^K | v_i |^2 = \| \bv \|_2^2 = \bv^T \bv = | \bv |^T | \bv | = | \bv |^T \bI | \bv |. \]

4. We are now left with \(K^2 - K\) off diagonal terms.

5. Each of these terms is bounded by

   \[ - \mu |v_i| |v_j | \leq v_i \bd_{\lambda_i}^T \bd_{\lambda_j} v_j \leq \mu |v_i| |v_j |. \]

6. Summing over the \(K^2 - K\) off-diagonal terms we get:

   \[ \sum_{i \neq j} |v_i| |v_j | = \sum_{i, j} |v_i| |v_j | - \sum_{i = j} |v_i| |v_j | = | \bv |^T(\OneMat - \bI ) | \bv |. \]

7. Thus,

   \[ - \mu | \bv |^T (\OneMat - \bI ) | \bv | \leq \sum_{i \neq j} v_i \bd_{\lambda_i}^T \bd_{\lambda_j} v_j \leq \mu | \bv |^T (\OneMat - \bI ) | \bv |. \]

8. Thus,

   \[ | \bv |^T \bI | \bv |- \mu | \bv |^T (\OneMat - \bI ) | \bv | \leq \bv^T \bDDD_{\Lambda}^T \bDDD_{\Lambda} \bv \leq | \bv |^T \bI | \bv |+ \mu | \bv |^T (\OneMat - \bI )| \bv |. \]

9. We get the result by slight reordering of terms:

   \[ | \bv |^T [\bI - \mu (\OneMat - \bI)] | \bv | \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq | \bv |^T [\bI + \mu (\OneMat - \bI)] | \bv |. \]

10. We note that due to Theorem 18.15

    \[ | \bv |^T \OneMat | \bv | = \| \bv \|_1^2. \]

11. Thus, the inequalities can be written as

    \[ (1 + \mu) \|\bv \|_2^2 - \mu \| \bv \|_1^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq (1 - \mu) \| \bv \|_2^2 + \mu \| \bv \|_1^2. \]

12. Alternatively,

    \[ \| \bv \|_2^2 - \mu \left (\| \bv \|_1^2 - \| \bv \|_2^2 \right ) \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq \| \bv \|_2^2 + \mu \left (\| \bv \|_1^2 - \| \bv \|_2^2\right ) . \]

13. Finally, due to Theorem 18.11

    \[ \| \bv \|_1^2 \leq K \| \bv \|_2^2 \implies \| \bv \|_1^2 - \| \bv \|_2^2 \leq (K - 1) \| \bv \|_2^2. \]

14. This gives us

    \[ ( 1- (K - 1) \mu ) \| \bv \|_2^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq ( 1 + (K - 1) \mu ) \| \bv \|_2^2 . \]

We now present the above theorem for the complex case. The proof is based on singular values. This proof is simpler and more general than the one presented above.

Theorem 18.30 (Norm bounds for embeddings with complex dictionaries)

Let \(\bDDD\) be a dictionary and \(\bDDD_{\Lambda}\) be a sub-dictionary with \(K = |\Lambda|\). Let \(\mu\) be the coherence of \(\bDDD\). Let \(\bv \in \CC^K\) be an arbitrary vector. Then

\[ (1 - (K - 1) \mu) \| \bv \|_2^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq (1 + (K - 1) \mu)\| \bv \|_2^2. \]

Proof. Recall that

\[ \sigma_{\min}^2(\bDDD_{\Lambda}) \| \bv \|_2^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq \sigma_{\max}^2(\bDDD_{\Lambda}) \| \bv \|_2^2. \]

The Theorem 18.28 tells us:

\[ 1 - (K - 1) \mu \leq \sigma^2 (\bDDD_{\Lambda}) \leq 1 + (K - 1) \mu. \]

Thus,

\[ \sigma_{\min}^2(\bDDD_{\Lambda}) \| \bv \|_2^2 \geq (1 - (K - 1) \mu) \| \bv \|_2^2 \]

and

\[ \sigma_{\max}^2(\bDDD_{\Lambda}) \| \bv \|_2^2 \leq (1 + (K - 1) \mu)\| \bv \|_2^2. \]

This gives us the result

\[ (1 - (K - 1) \mu) \| \bv \|_2^2 \leq \| \bDDD_{\Lambda} \bv \|_2^2 \leq (1 + (K - 1) \mu)\| \bv \|_2^2. \]

18.6.4. Babel Function

Recalling the definition of coherence, we note that it reflects only the extreme correlations between atoms of dictionary. If most of the inner products are small compared to one dominating inner product, then the value of coherence is highly misleading.

In [77], Tropp introduced Babel function, which measures the maximum total coherence between a fixed atom and a collection of other atoms. The Babel function quantifies an idea as to how much the atoms of a dictionary are “speaking the same language”.

Definition 18.22 (Babel function)

The Babel function for a dictionary \(\bDDD\) is defined by

(18.33)\[\mu_1(p) \triangleq \underset{|\Lambda| = p}{\max} \; \underset {\psi}{\max} \sum_{\lambda \in \Lambda} | \langle \psi, \bd_{\lambda} \rangle |,\]

where the vector \(\psi\) ranges over the atoms indexed by \(\Omega \setminus \Lambda\). We define

\[ \mu_1(0) = 0 \]

for sparsity level \(p=0\).

Let us dig deeper into what is going on here. For each value of \(p\) we consider all possible \(\binom{D}{p}\) subspaces by choosing \(p\) vectors from \(\bDDD\).

Let the atoms spanning one such subspace be identified by an index set \(\Lambda \subset \Omega\).

All other atoms are indexed by the index set \(\Gamma = \Omega \setminus \Lambda\). Let

\[ \Psi = \{ \psi_{\gamma} \ST \gamma \in \Gamma \} \]

denote the atoms indexed by \(\Gamma\). We pickup a vector \(\psi \in \Psi\) and compute its inner product with all atoms indexed by \(\Lambda\). We compute the sum of absolute value of these inner products over all \(\{ \bd_{\lambda} : \lambda \in \Lambda\}\).

We run it for every \(\psi \in \Psi\) and then pickup the maximum value of above sum over all \(\psi\).

We finally compute the maximum over all possible \(p\)-subspaces. This number is considered at the Babel number for sparsity level \(p\).

We first make a few observations over the properties of Babel function. Babel function is a generalization of coherence.

Remark 18.7 (Babel function for \(p=1\))

For \(p=1\) we observe that

\[ \mu_1(1) = \mu(\bDDD) \]

the coherence of \(\bDDD\).

Theorem 18.31 (Monotonicity of babel function)

\(\mu_1\) is a non-decreasing function of \(p\).

Proof. This is easy to see since the sum

\[ \sum_{\lambda \in \Lambda} | \langle \psi, \bd_{\lambda} \rangle | \]

cannot decrease as \(p = | \Lambda|\) increases. The following argument provides the details.

1. For some value of \(p\) let \(\Lambda^p\) and \(\psi^p\) denote the set and vector for which the maximum in (18.33) is attained.

2. Now pick some column which is not \(\psi^p\) and is not indexed by \(\Lambda^p\) and include it for \(\Lambda^{p + 1}\).

3. Note that \(\Lambda^{p + 1}\) and \(\psi^p\) might not be the maximizers for \(\mu_1\) for sparsity level \(p+1\) in (18.33).

4. Clearly

   \[ \sum_{\lambda \in \Lambda^{p + 1}} | \langle \psi^p, \bd_{\lambda} \rangle | \geq \sum_{\lambda \in \Lambda^{p}} | \langle \psi^p, \bd_{\lambda} \rangle |. \]

5. Hence \(\mu_1(p+1)\) cannot be less than \(\mu_1(p)\).

Theorem 18.32 (An upper bound for Babel function)

Babel function is upper bounded by coherence as per

\[ \mu_1(p) \leq p \; \mu(\bDDD). \]

Proof. Note that

\[ \sum_{\lambda \in \Lambda} | \langle \psi, \bd_{\lambda} \rangle | \leq p \; \mu(\bDDD). \]

This leads to

\[ \mu_1(p) = \underset{|\Lambda| = p}{\max} \; \underset {\psi}{\max} \sum_{\lambda \in \Lambda} | \langle \psi, \bd_{\lambda} \rangle | \leq \underset{|\Lambda| = p}{\max} \; \underset {\psi}{\max} \left (p \; \mu(\bDDD)\right) = p \; \mu(\bDDD). \]

18.6.4.1. Computation of Babel Function

It might seem at first that computation of Babel function is combinatorial and hence prohibitively expensive. But it is not true.

Example 18.26 (Procedure for computing the Babel function)

We will demonstrate this through an example in this section. Our example synthesis matrix will be

\[\begin{split} \bDDD = \begin{bmatrix} 0.5 & 0 & 0 & 0.6533 & 1 & 0.5 & -0.2706 & 0\\ 0.5 & 1 & 0 & 0.2706 & 0 & -0.5 & 0.6533 & 0\\ 0.5 & 0 & 1 & -0.2706 & 0 & -0.5 & -0.6533 & 0\\ 0.5 & 0 & 0 & -0.6533 & 0 & 0.5 & 0.2706 & 1 \end{bmatrix} \end{split}\]

From the synthesis matrix \(\bDDD\) we first construct its Gram matrix given by

\[ \bG = \bDDD^H \bDDD. \]

We then take absolute value of each entry in \(\bG\) to construct \(|\bG|\). For the running example

\[\begin{split} |\bG| = \begin{bmatrix} 1 & 0.5 & 0.5 & 0 & 0.5 & 0 & 0 & 0.5\\ 0.5 & 1 & 0 & 0.2706 & 0 & 0.5 & 0.6533 & 0\\ 0.5 & 0 & 1 & 0.2706 & 0 & 0.5 & 0.6533 & 0\\ 0 & 0.2706 & 0.2706 & 1 & 0.6533 & 0 & 0 & 0.6533\\ 0.5 & 0 & 0 & 0.6533 & 1 & 0.5 & 0.2706 & 0\\ 0 & 0.5 & 0.5 & 0 & 0.5 & 1 & 0 & 0.5\\ 0 & 0.6533 & 0.6533 & 0 & 0.2706 & 0 & 1 & 0.2706\\ 0.5 & 0 & 0 & 0.6533 & 0 & 0.5 & 0.2706 & 1 \end{bmatrix} \end{split}\]

We now sort every row in descending order to obtain a new matrix \(\bG'\).

\[\begin{split} \bG' = \begin{bmatrix} 1 & 0.5 & 0.5 & 0.5 & 0.5 & 0 & 0 & 0\\ 1 & 0.6533 & 0.5 & 0.5 & 0.2706 & 0 & 0 & 0\\ 1 & 0.6533 & 0.5 & 0.5 & 0.2706 & 0 & 0 & 0\\ 1 & 0.6533 & 0.6533 & 0.2706 & 0.2706 & 0 & 0 & 0\\ 1 & 0.6533 & 0.5 & 0.5 & 0.2706 & 0 & 0 & 0\\ 1 & 0.5 & 0.5 & 0.5 & 0.5 & 0 & 0 & 0\\ 1 & 0.6533 & 0.6533 & 0.2706 & 0.2706 & 0 & 0 & 0\\ 1 & 0.6533 & 0.5 & 0.5 & 0.2706 & 0 & 0 & 0 \end{bmatrix} \end{split}\]

First entry in each row is now \(1\). This corresponds to \(\langle \bd_i, \bd_i \rangle\) and it doesn’t appear in the calculation of \(\mu_1(p)\). Hence we disregard whole of first column.

Now look at column 2 in \(\bG'\). In the \(i\)-th row it is nothing but

\[ \underset{j \neq i}{\max} | \langle \bd_i, \bd_j \rangle |. \]

Thus,

\[ \mu (\bDDD) = \mu_1(1) = \underset{1 \leq j \leq D} {\max} {\bG'}_{j, 2} \]

i.e. the coherence is given by the maximum in the 2nd column of \(\bG'\). In the running example

\[ \mu (\bDDD) = \mu_1(1) = 0.6533. \]

Looking carefully we can note that for \(\psi = \bd_i\) the maximum value of sum

\[ \sum_{\Lambda} | \langle \psi, \bd_{\lambda} \rangle | \]

while \(| \Lambda| = p\) is given by the sum over elements from 2nd to \((p+1)\)-th columns in \(i\)-th row. Thus

\[ \mu_1 (p) = \underset{1 \leq i \leq D} {\max} \sum_{j = 2}^{p + 1} G'_{i j}. \]

For the running example the Babel function values are given by

\[ \begin{pmatrix} 0.6533 & 1.3066 & 1.6533 & 2 & 2 & 2 & 2 \end{pmatrix}. \]

We see that Babel function stops increasing after \(p=4\). Actually \(\bDDD\) is constructed by shuffling the columns of two orthonormal bases. Hence many of the inner products are 0 in \(\bG\).

18.6.4.2. Babel Function and Spark

We first note that Babel function tells something about linear independence of the columns of \(\bDDD\).

Theorem 18.33 (Linear independence of atoms and Babel function)

Let \(\mu_1\) be the Babel function for a dictionary \(\bDDD\). If

\[ \mu_1(p) < 1 \]

then all selections of \(p+1\) columns from \(\bDDD\) are linearly independent.

Proof. We recall from the proof of Theorem 18.25 that if

\[ p + 1 < 1 + \frac{1}{\mu(\bDDD)} \implies p < \frac{1}{\mu(\bDDD)} \]

then every set of \((p+1)\) columns from \(\bDDD\) are linearly independent. We also know from Theorem 18.32 that

\[ p \; \mu(\bDDD) \geq \mu_1(p) \implies \mu(\bDDD) \geq \frac{\mu_1(p)}{p} \implies \frac{1}{\mu(\bDDD)} \leq \frac{p} {\mu_1(p)}. \]

Thus if

\[ p < \frac{p} {\mu_1(p)} \implies 1 < \frac{1} {\mu_1(p)} \implies \mu_1(p) < 1 \]

then all selections of \(p+1\) columns from \(\bDDD\) are linearly independent.

This leads us to a lower bound on spark from Babel function.

Lemma 18.1 (Lower bound on spark based on Babel function)

A lower bound of spark of a dictionary \(\bDDD\) is given by

\[ \spark(\bDDD) \geq \underset{1 \leq p \leq N} {\min}\{p \ST \mu_1(p-1)\geq 1\}. \]

Proof. For all \(j \leq p-2\) we are given that \(\mu_1(j) < 1\). Thus all sets of \(p-1\) columns from \(\bDDD\) are linearly independent (using Theorem 18.33).

Finally \(\mu_1(p-1) \geq 1\), hence we cannot say definitively whether a set of \(p\) columns from \(\bDDD\) is linearly dependent or not. This establishes the lower bound on spark.

An earlier version of this result also appeared in [28] theorem 6.

18.6.4.3. Babel Function and Singular Values

Theorem 18.34 (Subdictionary singular value bounds from Babel function)

Let \(\bDDD\) be a dictionary and \(\Lambda\) be an index set with \(|\Lambda| = K\). The singular values of \(\bDDD_{\Lambda}\) are bounded by

\[ 1 - \mu_1(K - 1) \leq \sigma^2 \leq 1 + \mu_1 (K - 1). \]

Proof. Consider the Gram matrix

\[ \bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}. \]

\(G\) is a \(K\times K\) square matrix.

Also let

\[ \Lambda = \{ \lambda_1, \lambda_2, \dots, \lambda_K\} \]

so that

\[ \bDDD_{\Lambda} = \begin{bmatrix} \bd_{\lambda_1} & \bd_{\lambda_2} & \dots & \bd_{\lambda_K} \end{bmatrix}. \]

The Gershgorin Disc Theorem states that every eigenvalue of \(\bG\) lies in one of the \(K\) discs

\[ \Delta_k = \left \{ z \ST |z - G_{k k}| \leq \sum_{j \neq k } | G_{j k}| \right \} \]

Since \(\bd_i\) are unit norm, hence \(G_{k k} = 1\).

Also we note that

\[ \sum_{j \neq k } | G_{j k}| = \sum_{j \neq k } | \langle \bd_{\lambda_j}, \bd_{\lambda_k} \rangle | \leq \mu_1(K-1) \]

since there are \(K-1\) terms in sum and \(\mu_1(K-1)\) is an upper bound on all such sums.

Thus if \(z\) is an eigen value of \(\bG\) then we have

\[\begin{split} \begin{aligned} &| z -1 | \leq \mu_1(K-1) \\ \implies &- \mu_1(K-1) \leq z - 1 \leq \mu_1(K-1) \\ \implies &1 - \mu_1(K-1) \leq z \leq 1 + \mu_1(K-1). \end{aligned} \end{split}\]

This is OK since \(\bG\) is positive semi-definite, thus the eigen values of \(G\) are real.

But the eigen values of \(\bG\) are nothing but the squared singular values of \(\bDDD_{\Lambda}\). Thus we get

\[ 1 - \mu_1(K-1) \leq \sigma^2 \leq 1 + \mu_1(K-1). \]

Corollary 18.2

Let \(\bDDD\) be a dictionary and \(\Lambda\) be an index set with \(|\Lambda| = K\). If \(\mu_1(K-1) < 1\) then the squared singular values of \(\bDDD_{\Lambda}\) exceed \((1 - \mu_1 (K-1))\).

Proof. From previous theorem we have

\[ 1 - \mu_1(K-1) \leq \sigma^2 \leq 1 + \mu_1(K-1). \]

Since the singular values are always non-negative, the lower bound is useful only when \(\mu_1(K-1) < 1\). When it holds we have

\[ \sigma(\bDDD_{\Lambda}) \geq \sqrt{1 - \mu_1(K-1)}. \]

Theorem 18.35 (Uncertainty principle : Babel function)

Let \(\mu_1(K -1 ) < 1\). If a signal can be written as a linear combination of \(k\) atoms, then any other exact representation of the signal requires at least \((K - k + 1)\) atoms.

Proof. If \(\mu_1(K -1 ) < 1\), then the singular values of any sub-matrix of \(K\) atoms are non-zero. Thus, the minimum number of atoms required to form a linear dependent set is \(K + 1\). Let the number of atoms in any other exact representation of the signal be \(l\). Then

\[ k + l \geq K + 1 \implies l \geq K - k + 1. \]

18.6.4.4. Babel Function and Gram Matrix of Subdictionaries

Let \(\Lambda\) index a subdictionary and let \(\bG = \bDDD_{\Lambda}^H \bDDD_{\Lambda}\) denote the Gram matrix of the subdictionary \(\bDDD_{\Lambda}\). Assume \(K = | \Lambda |\).

Theorem 18.36 (A bound on the norms of Gram matrix)

\[ \| \bG \|_{\infty} = \| \bG \|_{1} \leq 1 + \mu_1(K - 1). \]

Proof. Since \(\bG\) is Hermitian, hence the two norms are equal:

\[ \| \bG \|_{\infty} = \| \bG^H \|_{1} = \| \bG \|_{1}. \]

1. Now each row consists of a diagonal entry \(1\) and \(K-1\) off diagonal entries.

2. The absolute sum of all the off-diagonal entries in a row is upper bounded by \(\mu_1(K -1)\).

3. Thus, the absolute sum of all the entries in a row is upper bounded by \(1 + \mu_1(K - 1)\).

4. \(\| \bG \|_{\infty}\) is nothing but the maximum \(\ell_1\) norm of rows of \(\bG\).

5. Hence

   \[ \| \bG \|_{\infty} \leq 1 + \mu_1(K - 1). \]

Theorem 18.37 (A bound on the norms of inverse Gram matrix)

Suppose that \(\mu_1(K - 1) < 1\). Then

\[ \| \bG^{-1} \|_{\infty} = \| \bG^{-1} \|_{1} \leq \frac{1}{1 - \mu_1(K - 1)}. \]

Proof. Since \(G\) is Hermitian, hence the two operator norms are equal:

\[ \| \bG^{-1} \|_{\infty} = \| \bG^{-1} \|_{1}. \]

1. We can write \(\bG\) as \(\bG = \bI + \bA\) where \(\bA\) consists of off-diagonal entries in \(\bG\).

2. Recall that since atoms are unit norm, hence diagonal entries in \(\bG\) are 1.

3. Each row of \(\bA\) lists inner products between a fixed atom and \(K-1\) other atoms (leaving 0 at the diagonal entry).

4. Therefore

   \[ \| \bA \|_{\infty} \leq \mu_1(K - 1). \]

   since \(\ell_1\) norm of any row is upper bounded by the babel number \(\mu_1(K - 1)\).

5. Now \(\bG^{-1}\) can be written as a Neumann series

   \[ \bG^{-1} = \sum_{k=0}^{\infty}(-\bA)^k. \]

6. Thus

   \[\begin{split} \| \bG^{-1} \|_{\infty} &= \left \| \sum_{k=0}^{\infty}(-\bA)^k \right \|_{\infty} \\ &\leq \sum_{k=0}^{\infty} \| (-\bA)^k \|_{\infty}\\ &= \sum_{k=0}^{\infty} \| \bA \|_{\infty}^k\\ &= \frac{1}{1 - \| \bA \|_{\infty}} \end{split}\]

   since \(\| \bA \|_{\infty} < 1\).

7. Finally

   \[\begin{split} & \| \bA \|_{\infty} \leq \mu_1(K - 1)\\ \iff & 1 - \| \bA \|_{\infty} \geq 1 - \mu_1(K - 1)\\ \iff & \frac{1}{1 - \| \bA \|_{\infty}} \leq \frac{1}{1 - \mu_1(K - 1)}. \end{split}\]

8. Thus

   \[ \| \bG^{-1} \|_{\infty} \leq \frac{1}{1 - \mu_1(K - 1)}. \]

18.6.4.5. Quasi Incoherent Dictionaries

Definition 18.23 (Quasi incoherent dictionary)

When the Babel function of a dictionary grows slowly, we say that the dictionary is quasi-incoherent.