(sec:ssm:dictionaries)=
# 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.
```{div}
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 {cite}`tropp2006just` described below.
```
## Subdictionaries
```{index} Subdictionary
```
````{prf:definition} Subdictionary
:label: def:ssm: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\}$.
````
````{prf:remark} Rank of subdictionary
:label: res-ssm-subdictionary-rank
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}$ {cite}`tropp2004just`.
```{div}
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$.
```
(sec:ssm:spark)=
## Spark
```{index} Dictionary; spark, Matrix; spark
```
````{prf:definition} Spark
:label: def: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$.
````{prf:example} Spark
:label: ex-ssm-spark-1
1. Spark of the $3 \times 3$ identity matrix
$$
\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
$$
is 4 since all columns are linearly independent.
1. Spark of the $2 \times 4$ matrix
$$
\begin{pmatrix}
1 & 0 & -1 & 0\\
0 & 1 & 0 & -1
\end{pmatrix}
$$
is 2 since column 1 and 3 are linearly dependent.
1. 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.
1. 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.
````{prf:algorithm} A naive algorithm for computing the spark of a matrix
:label: alg:ssm:spark_combinatorial_search
Inputs:
1. $\Phi$: a matrix
Outputs:
1. $s$: Spark of $\Phi$
Algorithm:
1. Let $R \leftarrow \rank (\Phi)$.
1. For every $j \leftarrow 1,\dots, R$:
1. Identify $\binom{D}{j}$ ways of choosing $j$ columns
from $D$ columns of $\Phi$.
1. For every choice of $j$ columns:
1. If columns are linearly dependent:
1. $s \leftarrow j$.
1. Return.
1. All columns are linearly independent.
1. $s \leftarrow R + 1$.
````
### Spark and Nullspace
````{prf:remark} Spark and sparsity of null space vectors
:label: res-ssm-spark-nullspace-vec-sparsity
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).
$$
````
````{prf:proof}
We proceed as follows:
1. If $\bx \in \NullSpace(\Phi)$ then $\Phi \bx = \bzero$.
1. Thus non-zero entries in $\bx$ pick a set of columns in $\Phi$
which are linearly dependent.
1. Clearly $\| \bx \|_0$ indicates the number of columns in the set which are
linearly dependent.
1. By definition, spark of $\Phi$ indicates the minimum number of columns
which are linearly dependent.
1. Hence the result:
$$
\| \bx \|_0 \geq \spark(\Phi) \Forall \bx\in \NullSpace(\Phi).
$$
````
### Uniqueness-Spark
Spark is useful in characterizing the uniqueness of the solution
of a $(\bDDD, K)$-EXACT-SPARSE problem (see {prf:ref}`def-ssm-d-k-exact-sparse-problem`).
We now present a criteria based on spark which characterizes
the uniqueness of a sparse solution to the problem $\by = \Phi \bx$.
````{prf:theorem} Uniqueness of a sparse solution for an underdetermined system via spark
:label: thm:ssm:uniqueness_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.
````
````{prf: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 {prf:ref}`res-ssm-spark-nullspace-vec-sparsity` 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.
````{prf:example} Spark of Gaussian dictionaries
:label: ex-ssm-spark-gaussian
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.
1. We know that with probability $1$ any set of $N$ independent Gaussian random vectors
is linearly independent.
1. Also, since $\bd_i \in \RR^N$ hence a set of $N+1$ atoms is always linearly dependent.
1. 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.
````
````{prf:example} Spark of Dirac Fourier basis
:label: ex-ssm-spark-dirac-fourier
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}$.
````
## 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.
```{index} Coherence
```
````{prf:definition} Coherence of a dictionary
:label: def:ssm:coherence
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 {prf:ref}`def-ssm-mutual-coherence-two-ortho-bases`.
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$.
```{div}
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.
```
```{index} Incoherent dictionary, Dictionary; incoherent
```
````{prf:definition} Incoherent dictionary
:label: def:ssm: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.
````{prf:example} Coherence of two ortho bases
:label: ex-ssm-coherence-2-onb-2
We established in {prf:ref}`res-ssm-2-onb-coherence-bounds` that
coherence of two ortho-bases is bounded by
$$
\frac{1}{\sqrt{N}} \leq \mu \leq 1.
$$
In particular we showed in {prf:ref}`res-ssm-coherence-dirac-fourier` that
coherence of Dirac Fourier basis is $\frac{1}{\sqrt{N}}$.
````
````{prf:example} Coherence: Multi-ONB dictionary
:label: ex-ssm-coherence-multi-onb
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.
````
````{prf:theorem} Coherence lower bound
:label: res-ssm-coherence-lb
A lower bound on the coherence of a general dictionary is given by
$$
\mu \geq \sqrt{\frac{D-N}{N(D-1)}}.
$$
````
```{index} Grassmannian frame
```
````{prf:definition} Grassmannian frame
:label: def:ssm: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}$.
```{index} Coherence; arbitrary matrices
```
````{prf:definition} Coherence for arbitrary matrices
:label: def:ssm:coherence_matrix
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
```{math}
:label: eq:ssm:dict:coherence:arbitrary_matrix
\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.
````
### 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.
````{prf:theorem} Lower bound on spark in terms of coherence
:label: lem:ssm:spark_lower_bound_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)}.
$$
````
````{prf: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$.
1. We note that
$$
\bG_{k k} = 1 \quad \Forall 1 \leq k \leq D
$$
since each column of $\Phi$ is unit norm.
1. Also
$$
|G_{k j}| \leq \mu(\Phi) \quad \Forall 1 \leq k, j \leq D , k \neq j.
$$
1. Consider any $p$ columns from $\Phi$ and construct its Gram matrix.
1. This is nothing but a leading minor of size $p \times p$ from the matrix $\bG$.
1. 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.
1. But
$$
|G_{i i}| = 1
$$
and
$$
\sum_{j \neq i} |G_{i j}| \leq (p-1) \mu(\Phi)
$$
for the minor under consideration.
1. Hence for $p$ columns to be linearly independent
the following condition is sufficient
$$
(p-1) \mu (\Phi) < 1.
$$
1. Thus if
$$
p < 1 + \frac{1}{\mu(\Phi)},
$$
then every set of $p$ columns from $\Phi$ is linearly independent.
1. Hence, the smallest possible set of linearly dependent columns must satisfy
$$
p \geq 1 + \frac{1}{\mu(\Phi)}.
$$
1. 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 {cite}`donoho2003optimally`.
````{prf:theorem} Lower bound on spark for two ortho bases
:label: res:ssm:spark_lower_bound_two_ortho_basis
Let $\bDDD$ be a two ortho-basis. Then
$$
\spark (\bDDD) \geq \frac{2}{\mu(\bDDD)}.
$$
````
````{prf:proof}
From {prf:ref}`res-ssm-2onb-nullspace-vec-sparsity` 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}$.
### Uniqueness-Coherence
We can now establish a uniqueness condition for sparse solution of $\by = \Phi \bx$.
````{prf:theorem} Uniqueness of a sparse solution of an underdetermined system via coherence
:label: thm:ssm:uniqueness_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.
````
````{prf:proof}
This is a straightforward application of {prf:ref}`thm:ssm:uniqueness_spark`
and {prf:ref}`lem:ssm:spark_lower_bound_coherence`.
````
It is interesting to compare the two uniqueness theorems:
{prf:ref}`thm:ssm:uniqueness_spark`
and {prf:ref}`thm:ssm:uniqueness_coherence`.
{prf:ref}`thm:ssm:uniqueness_spark` uses spark, is sharp and is far more powerful
than {prf:ref}`thm:ssm:uniqueness_coherence`.
```{div}
Coherence can never be smaller than $\frac{1}{\sqrt{N}}$, therefore the bound on
$\| \bx^* \|_0$ in {prf:ref}`thm:ssm:uniqueness_coherence` 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 {prf:ref}`res-ssm-sparse-unique-2onb` 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 {prf:ref}`thm:ssm:uniqueness_coherence`
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).
```
### Singular Values of Subdictionaries
````{prf:theorem} Singular values of subdictionaries and coherence
:label: res:ssm:subdictionary_eigenvalue_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}.
$$
````
````{prf: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$.
1. Then
$$
| \lambda - 1 | \leq \sum_{j \neq i} |G_{i j}| \leq \sum_{j \neq i} \mu = (K - 1) \mu.
$$
1. Thus,
$$
- (K - 1) \mu
\leq \lambda - 1 \leq (K - 1) \mu \iff 1 - (K - 1) \mu
\leq \lambda \leq 1 + (K - 1) \mu.
$$
1. This gives us a lower bound on the smallest eigen value.
$$
\lambda_{\min} (\bG) \geq 1 - (K - 1) \mu.
$$
1. 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}.
$$
1. We also get an upper bound on the eigen values of $\bG$ given by
$$
\lambda_{\max} (G) \leq 1 + (K - 1) \mu.
$$
1. The bounds on singular values of $\bDDD_{\Lambda}$ are obtained as a
straight-forward extension by taking square roots on the expressions.
````
### Embeddings using Subdictionaries
````{prf:theorem} Norm bounds for embeddings with real dictionaries
:label: res:ssm:real_dict_norm_bound_coherence
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.
$$
````
````{prf: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.
$$
1. 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.
$$
1. 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 |.
$$
1. We are now left with $K^2 - K$ off diagonal terms.
1. 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 |.
$$
1. 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 |.
$$
1. 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 |.
$$
1. 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 |.
$$
1. 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 |.
$$
1. We note that due to {prf:ref}`res:ssm:ones_matrix_l1_norm`
$$
| \bv |^T \OneMat | \bv | = \| \bv \|_1^2.
$$
1. 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.
$$
1. 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 ) .
$$
1. Finally, due to {prf:ref}`lem:ssm:l1_norm_l2_bounds`
$$
\| \bv \|_1^2 \leq K \| \bv \|_2^2
\implies \| \bv \|_1^2 - \| \bv \|_2^2 \leq (K - 1) \| \bv \|_2^2.
$$
1. 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.
````{prf:theorem} Norm bounds for embeddings with complex dictionaries
:label: res:ssm:subdict_norm_bound_coherence
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.
$$
````
````{prf: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 {prf:ref}`res:ssm:subdictionary_eigenvalue_coherence` 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.
$$
````
## 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 {cite}`tropp2004greed`, 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".
```{index} Babel function
```
````{prf:definition} Babel function
:label: def:babel_function
The *Babel function* for a dictionary $\bDDD$ is defined by
```{math}
:label: eq:ssm:babel_function
\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.
````{prf:remark} Babel function for $p=1$
:label: res-ssm-babel-function-p-1
For $p=1$ we observe that
$$
\mu_1(1) = \mu(\bDDD)
$$
the coherence of $\bDDD$.
````
````{prf:theorem} Monotonicity of babel function
:label: res-ssm-babel-monotonicity
$\mu_1$ is a non-decreasing function of $p$.
````
````{prf: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 {eq}`eq:ssm:babel_function`
is attained.
1. Now pick some column which is not
$\psi^p$ and is not indexed by $\Lambda^p$
and include it for $\Lambda^{p + 1}$.
1. Note that $\Lambda^{p + 1}$ and $\psi^p$ might not be the maximizers
for $\mu_1$ for sparsity level $p+1$ in {eq}`eq:ssm:babel_function`.
1. 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 |.
$$
1. Hence $\mu_1(p+1)$ cannot be less than $\mu_1(p)$.
````
````{prf:theorem} An upper bound for Babel function
:label: lem:ssm:babel_function_upper_bound
Babel function is upper bounded by coherence as per
$$
\mu_1(p) \leq p \; \mu(\bDDD).
$$
````
````{prf: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).
$$
````
### 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.
```{prf:example} Procedure for computing the Babel function
:label: ex-ssm-babel-func-compute-proc
We will demonstrate this through an example in this section.
Our example synthesis matrix will be
$$
\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}
$$
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
$$
|\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}
$$
We now sort every row in descending order to obtain a
new matrix $\bG'$.
$$
\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}
$$
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$.
```
### Babel Function and Spark
We first note that *Babel function* tells something about linear independence
of the columns of $\bDDD$.
````{prf:theorem} Linear independence of atoms and Babel function
:label: lem:ssm:babel_linear_independence_condition
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.
````
````{prf:proof}
We recall from the proof of {prf:ref}`lem:ssm:spark_lower_bound_coherence`
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 {prf:ref}`lem:ssm:babel_function_upper_bound` 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*.
````{prf:lemma} Lower bound on spark based on Babel function
:label: lem:ssm:dict:spark_lower_bound_babel_func
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\}.
$$
````
````{prf: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 {prf:ref}`lem:ssm:babel_linear_independence_condition`).
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
{cite}`donoho2003optimally` theorem 6.
### Babel Function and Singular Values
````{prf:theorem} Subdictionary singular value bounds from Babel function
:label: lem:ssm:subdictionary_singular_value_babel_bounds
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).
$$
````
````{prf: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{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}
$$
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).
$$
````
````{prf:corollary}
:label: lem:ssm:babel_singular_value_condition
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))$.
````
````{prf: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)}.
$$
````
````{prf:theorem} Uncertainty principle : Babel function
:label: res:ssm:babel_uncertainty_principle_K
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.
````
````{prf: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.
$$
````
### 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 |$.
````{prf:theorem} A bound on the norms of Gram matrix
:label: res:ssm:gram_matrix_infty_norm_babel_bound
$$
\| \bG \|_{\infty} = \| \bG \|_{1} \leq 1 + \mu_1(K - 1).
$$
````
````{prf: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.
1. The absolute sum of all the off-diagonal entries in a row is
upper bounded by $\mu_1(K -1)$.
1. Thus, the absolute sum of all the entries in a row is
upper bounded by $1 + \mu_1(K - 1)$.
1. $\| \bG \|_{\infty}$ is nothing but the maximum $\ell_1$ norm of rows of $\bG$.
1. Hence
$$
\| \bG \|_{\infty} \leq 1 + \mu_1(K - 1).
$$
````
````{prf:theorem} A bound on the norms of inverse Gram matrix
:label: res:ssm:inverse_gram_matrix_infty_norm_babel_bound
Suppose that $\mu_1(K - 1) < 1$.
Then
$$
\| \bG^{-1} \|_{\infty} = \| \bG^{-1} \|_{1} \leq \frac{1}{1 - \mu_1(K - 1)}.
$$
````
````{prf: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$.
1. Recall that since atoms are unit norm, hence diagonal entries in $\bG$ are 1.
1. Each row of $\bA$ lists inner products between a fixed atom and $K-1$
other atoms (leaving 0 at the diagonal entry).
1. 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)$.
1. Now $\bG^{-1}$ can be written as a Neumann series
$$
\bG^{-1} = \sum_{k=0}^{\infty}(-\bA)^k.
$$
1. Thus
$$
\| \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}}
$$
since $\| \bA \|_{\infty} < 1$.
1. Finally
$$
& \| \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)}.
$$
1. Thus
$$
\| \bG^{-1} \|_{\infty} \leq \frac{1}{1 - \mu_1(K - 1)}.
$$
````
### Quasi Incoherent Dictionaries
```{index} Quasi incoherent dictionary
```
````{prf:definition} Quasi incoherent dictionary
:label: def:ssm:quasi_incoherent_dictionary
When the *Babel function* of a dictionary grows slowly,
we say that the dictionary is *quasi-incoherent*.
````