.md .pdf

repository open issue

Contents

12.5. Sparse and Redundant Representations

12.5.1. Dictionaries

Definition 12.3 (Dictionary)

A dictionary for ${\mathbb{C}}^N$ is a finite collection $\mathcal{D}$ of unit-norm vectors which span the whole space.

The elements of a dictionary are called atoms and they are denoted by ${\varphi }_{\omega }$ where $\omega$ is drawn from an index set $\mathrm{\Omega }$.

The dictionary is written as

$$\mathcal{D}=\{{\varphi }_{\omega }:\omega \in \mathrm{\Omega }\}$$

where

$$\Vert {\varphi }_{\omega }{\Vert }_2=1\mathrm{\forall }\omega \in \mathrm{\Omega }$$

and every signal $\mathbf{x}\in {\mathbb{C}}^N$ can be expressed as

$$\mathbf{x}=\sum _{\omega \in \mathrm{\Omega }}{c}_{\omega }{\varphi }_{\omega }.$$

We use the letter $D$ to denote the number of elements in the dictionary; i.e.,

$$D=|\mathrm{\Omega }|.$$

This definition is adapted from [35].

The indices may have an interpretation, such as the time-frequency or time-scale localization of an atom, or they may simply be labels without any underlying meaning.

Note that the dictionary need not provide a unique representation for any vector $\mathbf{x}\in {\mathbb{C}}^N$, but it provides at least one representation for each $\mathbf{x}\in {\mathbb{C}}^N$.

When $D=N$ we have a set of unit norm vectors which span the whole of ${\mathbb{C}}^N$. Thus we have a basis (not-necessarily an orthonormal basis). A dictionary cannot have $D<N$. The more interesting case is when $D>N$.

12.5.2. Redundant Dictionaries and Sparse Signals

With $D>N$, clearly there are more atoms than necessary to provide a representation of every signal $\mathbf{x}\in {\mathbb{C}}^N$. Thus such a dictionary is able provide multiple representations to same vector $\mathbf{x}$. We call such dictionaries redundant dictionaries or over-complete dictionaries.

In contrast a basis with $D=N$ is called a complete dictionary. A special class of signals is those signals which have a sparse representation in a given dictionary $\mathcal{D}$.

Definition 12.4 ($(\mathcal{D},K)$-sparse signals)

A signal $\mathbf{x}\in {\mathbb{C}}^N$ is called $(\mathcal{D},K)$-sparse if it can be expressed as a linear combination of at-most $K$ atoms from the dictionary $\mathcal{D}$.

Normally, for sparse signals, we have $K\ll D$. It is usually expected that $K\ll N$ also holds.

Let $\mathrm{\Lambda }\subset \mathrm{\Omega }$ be a subset of indices with $|\mathrm{\Lambda }|=K$.

Let $\mathbf{x}$ be any signal in ${\mathbb{C}}^N$ such that $\mathbf{x}$ can be expressed as

$$\mathbf{x}=\sum _{\lambda \in \mathrm{\Lambda }}{b}_{\lambda }{\varphi }_{\lambda }\text{where }{b}_{\lambda }\in \mathbb{C}.$$

Note that this is not the only possible representation of $\mathbf{x}$ in $\mathcal{D}$. This is just one of the possible representations of $\mathbf{x}$. The special feature of this representation is that it is $K$-sparse i.e. only at most $K$ atoms from the dictionary are being used.

Now there are $(\genfrac{}{}{0ex}{}{D}{K})$ ways in which we can choose a set of $K$ atoms from the dictionary $\mathcal{D}$.

Thus the set of $(\mathcal{D},K)$-sparse signals is given by

$${\mathrm{\Sigma }}_{(\mathcal{D},K)}=\{\mathbf{x}\in {\mathbb{C}}^N|\mathbf{x}=\sum _{\lambda \in \mathrm{\Lambda }}{b}_{\lambda }{\varphi }_{\lambda },\mathrm{\Lambda }\subseteq \mathrm{\Omega },|\mathrm{\Lambda }|=K\}.$$

This set ${\mathrm{\Sigma }}_{(\mathcal{D},K)}$ is dependent on the chosen dictionary $\mathcal{D}$. In the sequel, we will simply refer to it as ${\mathrm{\Sigma }}_K$.

Example 12.15 ($K$-sparse signals for standard basis)

For the special case where $\mathcal{D}$ is nothing but the standard basis of ${\mathbb{C}}^N$, then

$${\mathrm{\Sigma }}_K=\{\mathbf{x}\in {\mathbb{C}}^N|\Vert \mathbf{x}{\Vert }_0\le K\};$$

i.e., the set of signals which have $K$ or less non-zero elements.

Example 12.16 ($K$-sparse signals for orthonormal basis)

In contrast if we choose an orthonormal basis $\mathrm{\Psi }$ such that every $\mathbf{x}\in {\mathbb{C}}^N$ can be expressed as

$$\mathbf{x}=\mathrm{\Psi }\mathbf{a}$$

then with the dictionary $\mathcal{D}=\mathrm{\Psi }$, the set of $K$-sparse signals is given by

$${\mathrm{\Sigma }}_K=\{\mathbf{x}=\mathrm{\Psi }\mathbf{a}|\Vert \mathbf{a}{\Vert }_0\le K\}.$$

We also note that for a specific choice of $\mathrm{\Lambda }\subseteq \mathrm{\Omega }$ with $|\mathrm{\Lambda }|=K$, the set of vectors

$$\{\mathbf{x}\in {\mathbb{C}}^N|\mathbf{x}=\sum _{\lambda \in \mathrm{\Lambda }}{b}_{\lambda }{\varphi }_{\lambda }\}=\mathrm{span}\{{\varphi }_{\lambda }|\lambda \in \mathrm{\Lambda }\}$$

form a subspace of ${\mathbb{C}}^N$.

So we have $(\genfrac{}{}{0ex}{}{D}{K})$ $K$-sparse subspaces contained in the dictionary $\mathcal{D}$. And the $K$-sparse signals lie in the union of these subspaces.

12.5.3. Sparse Approximation Problem

In sparse approximation problem, we attempt to approximate a given signal $\mathbf{x}\in {\mathbb{C}}^N$ as a linear combination of $K$ atoms from the dictionary $\mathcal{D}$ where $K\ll N$ and typically $N\ll D$; i.e., the number of atoms in a dictionary $\mathcal{D}$ is typically much larger than the ambient signal space dimension $N$.

Naturally, we wish to obtain a best possible sparse representation of $\mathbf{x}$ over the atoms ${\varphi }_{\omega }\in \mathcal{D}$ which minimizes the approximation error.

Let $\mathrm{\Lambda }$ denote the index set of atoms which are used to create a $K$-sparse representation of $\mathbf{x}$ where $\mathrm{\Lambda }\subset \mathrm{\Omega }$ with $|\mathrm{\Lambda }|=K$.

Let ${\mathbf{x}}_{\mathrm{\Lambda }}$ denote an approximation of $\mathbf{x}$ over the set of atoms indexed by $\mathrm{\Lambda }$.

Then we can write ${\mathbf{x}}_{\mathrm{\Lambda }}$ as

$${\mathbf{x}}_{\mathrm{\Lambda }}=\sum _{\lambda \in \mathrm{\Lambda }}{b}_{\lambda }{\varphi }_{\lambda }\text{where }{b}_{\lambda }\in \mathbb{C}.$$

We put all complex valued coefficients $b_{\lambda }$ in the sum into a list ${\mathbf{b}}_{\mathrm{\Lambda }}$. The approximation error is given by

$$\mathbf{e}=\Vert \mathbf{x}-{\mathbf{x}}_{\mathrm{\Lambda }}{\Vert }_2.$$

Clearly we would like to minimize the approximation error over all possible choices of $K$ atoms and corresponding set of coefficients ${\mathbf{b}}_{\mathrm{\Lambda }}$.

Thus the sparse approximation problem can be cast as a minimization problem given by

(12.17)$$\underset{|\mathrm{\Lambda }|=K}{\text{min}}\underset{{\mathbf{b}}_{\mathrm{\Lambda }}}{\text{min}}{\Vert \mathbf{x}-\sum _{\lambda \in \mathrm{\Lambda }}{b}_{\lambda }{\varphi }_{\lambda }\Vert }_2.$$

If we choose a particular $\mathrm{\Lambda }$, then the inner minimization problem becomes a straight-forward least squares problem. But there are $(\genfrac{}{}{0ex}{}{D}{K})$ possible choices of $\mathrm{\Lambda }$ and solving the inner least squares problem for each of them becomes prohibitively expensive.

We reemphasize here that in this formulation we are using a fixed dictionary $\mathcal{D}$ while the vector $\mathbf{x}\in {\mathbb{C}}^N$ is arbitrary.

This problem is known as $(\mathcal{D},K)$-SPARSE approximation problem.

A related problem is known as $(\mathcal{D},K)$-EXACT-SPARSE problem where it is known a-priori that $\mathbf{x}$ is a linear combination of at-most $K$ atoms from the given dictionary $\mathcal{D}$ i.e. $\mathbf{x}$ is a $K$-sparse signal as defined above for the dictionary $\mathcal{D}$.

This formulation simplifies the minimization problem (12.17) since it is known a priori that for $K$-sparse signals, a $0$ approximation error can be achieved. The only problem is to find a set of subspaces from the $(\genfrac{}{}{0ex}{}{D}{K})$ possible $K$-sparse subspaces which are able to provide a $K$-sparse representation of $\mathbf{x}$ and among them choose one. It is imperative to note that even the $K$-sparse representation need not be unique.

Clearly the EXACT-SPARSE problem is simpler than the SPARSE approximation problem. Thus if EXACT-SPARSE problem is NP-Hard then so is the harder SPARSE-approximation problem. It is expected that solving the EXACT-SPARSE problem will provide insights into solving the SPARSE problem.

In Theorem 12.8 we identified conditions under which a sparse representation for a given vector $\mathbf{x}$ in a two-ortho-basis is unique. It would be useful to get similar conditions for general dictionaries. such conditions would help us guarantee the uniqueness of EXACT-SPARSE problem.

12.5.4. Synthesis and Analysis

The atoms of a dictionary $\mathcal{D}$ can be organized into a $N\times D$ matrix as follows:

$$\mathrm{\Phi }\triangleq \left[\begin{array}{cccc}{\varphi }_{{\omega }_1}& {\varphi }_{{\omega }_2}& \dots & {\varphi }_{{\omega }_D}\end{array}\right].$$

where $\mathrm{\Omega }=\{{\omega }_1,{\omega }_2,\dots ,{\omega }_N\}$ is the index set for the atoms of $\mathcal{D}$. We recall that ${\varphi }_{\omega }\in {\mathbb{C}}^N$, hence they have a column vector representation in the standard basis for ${\mathbb{C}}^N$. The order of columns doesn’t matter as long as it remains fixed once chosen.

Thus in matrix terminology a representation of $\mathbf{x}\in {\mathbb{C}}^N$ in the dictionary can be written as

$$\mathbf{x}=\mathrm{\Phi }\mathbf{b}$$

where $\mathbf{b}\in {\mathbb{C}}^D$ is a vector of coefficients to produce a superposition $\mathbf{x}$ from the atoms of dictionary $\mathcal{D}$. Clearly with $D>N$, $\mathbf{b}$ is not unique. Rather for every vector $\mathbf{z}\in \mathcal{N}(\mathrm{\Phi })$, we have:

$$\mathrm{\Phi }(\mathbf{b}+\mathbf{z})=\mathrm{\Phi }\mathbf{b}+\mathrm{\Phi }\mathbf{z}=\mathbf{x}+\mathbf{0}=\mathbf{x}.$$

Definition 12.5 (Synthesis matrix)

The matrix $\mathrm{\Phi }$ is called a synthesis matrix since $\mathbf{x}$ is synthesized from the columns of $\mathrm{\Phi }$ with the coefficient vector $\mathbf{b}$.

We can also view the synthesis matrix $\mathrm{\Phi }$ as a linear operator from ${\mathbb{C}}^D$ to ${\mathbb{C}}^N$.

There is another way to look at $\mathbf{x}$ through $\mathrm{\Phi }$.

Definition 12.6 (Analysis matrix)

The conjugate transpose ${\mathrm{\Phi }}^H$ of the synthesis matrix $\mathrm{\Phi }$ is called the analysis matrix. It maps a given vector $\mathbf{x}\in {\mathbb{C}}^N$ to a list of inner products with the dictionary:

$$\mathbf{c}={\mathrm{\Phi }}^H\mathbf{x}$$

where $\mathbf{c}\in {\mathbb{C}}^D$.

Note that in general $\mathbf{x}\ne \mathrm{\Phi }({\mathrm{\Phi }}^H\mathbf{x})$ unless $\mathcal{D}$ is an orthonormal basis.

Definition 12.7 ($(\mathcal{D},K)$ EXACT SPARSE problem)

With the help of synthesis matrix $\mathrm{\Phi }$, the $(\mathcal{D},K)$ EXACT SPARSE problem can now be written as

(12.18)$$\begin{array}{rlrl}& \underset{\mathbf{a}}{\text{minimize}}& & \Vert \mathbf{a}{\Vert }_0\\ & \text{subject to }& & \mathbf{x}=\mathrm{\Phi }\mathbf{a}\\ & \text{and }& & \Vert \mathbf{a}{\Vert }_0\le K\end{array}$$

If $\mathbf{x}\notin {\mathrm{\Sigma }}_K$, then the EXACT SPARSE problem is infeasible. Otherwise, we are looking to find the sparsest possible solution.

Definition 12.8 ($(\mathcal{D},K)$ SPARSE approximation problem)

With the help of synthesis matrix $\mathrm{\Phi }$, the $(\mathcal{D},K)$ SPARSE approximation problem can now be written as

(12.19)$$\begin{array}{rlrl}& \underset{\mathbf{a}}{\text{minimize}}& & \Vert \mathbf{x}-\mathrm{\Phi }\mathbf{a}{\Vert }_2\\ & \text{subject to }& & \Vert \mathbf{a}{\Vert }_0\le K.\end{array}$$

This problem can be visualized as a projection of $\mathbf{x}$ on to the set ${\mathrm{\Sigma }}_K$. Hence, it always has a solution.

12.5.5. P-Norms

There are some simple and useful results on relationships between different $p$-norms listed in this section. We also discuss some interesting properties of $l_1$-norm specifically.

Definition 12.9 (Complex sign vector)

Let $\mathbf{v}\in {\mathbb{C}}^N$. Let the entries in $\mathbf{v}$ be represented as

$$v_k=r_k\exp (i{\theta }_k)$$

where $r_k=|v_k|$ with the convention that ${\theta }_k=0$ whenever $r_k=0$.

The sign vector for $\mathbf{v}$ denoted by $\mathrm{sgn}(\mathbf{v})$ is defined as

$$\begin{array}{r}\mathrm{sgn}(\mathbf{v})=\left[\begin{array}{c}\mathrm{sgn}(v_1)\\ ⋮\\ \mathrm{sgn}(v_N)\end{array}\right]\end{array}$$

where

$$\begin{array}{r}\mathrm{sgn}(v_k)=\{\begin{array}{ll}\exp (i{\theta }_k)& \text{ if }{r}_k\ne 0;\\ 0& \text{ if }{r}_k=0.\end{array}\end{array}$$

Theorem 12.9 (${\ell }_1$ norm as product of vector with its sign)

For any $\mathbf{v}\in {\mathbb{C}}^N$:

$$\Vert \mathbf{v}{\Vert }_1=\mathrm{sgn}(\mathbf{v}{)}^H\mathbf{v}=⟨\mathbf{v},\mathrm{sgn}(\mathbf{v})⟩.$$

Proof. This follows from:

$$\Vert \mathbf{v}{\Vert }_1=\sum _{k=1}^N{r}_k=\sum _{k=1}^N\left[r_k{e}^{i{\theta }_k}\right]e^{-i{\theta }_k}=\sum _{k=1}^N{v}_k{e}^{-i{\theta }_k}=\mathrm{sgn}(\mathbf{v}{)}^H\mathbf{v}.$$

Note that whenever $v_k=0$, corresponding $0$ entry in $\mathrm{sgn}(\mathbf{v})$ has no effect on the sum.

Theorem 12.10 (Equivalence of ${\ell }_1$ and ${\ell }_2$ norms)

Suppose $\mathbf{v}\in {\mathbb{C}}^N$. Then

$$\Vert \mathbf{v}{\Vert }_2\le \Vert \mathbf{v}{\Vert }_1\le \sqrt{N}\Vert \mathbf{v}{\Vert }_2.$$

Proof. For the lower bound, we go as follows

$$\Vert \mathbf{v}{\Vert }_2^2=\sum _{i=1}^N|v_i{|}^2\le (\sum _{i=1}^N|v_i{|}^2+2\sum _{i,j,i\ne j}|v_i||v_j|)={\left(\sum _{i=1}^N|v_i|\right)}^2=\Vert \mathbf{v}{\Vert }_1^2.$$

This gives us

$$\Vert \mathbf{v}{\Vert }_2\le \Vert \mathbf{v}{\Vert }_1.$$

We can write ${\ell }_1$ norm as

$$\Vert \mathbf{v}{\Vert }_1=⟨\mathbf{v},\mathrm{sgn}(\mathbf{v})⟩.$$

By Cauchy-Schwartz inequality we have

$$⟨\mathbf{v},\mathrm{sgn}(\mathbf{v})⟩\le \Vert \mathbf{v}{\Vert }_2\Vert \mathrm{sgn}(\mathbf{v}){\Vert }_2.$$

Since $\mathrm{sgn}(\mathbf{v})$ can have at most $N$ non-zero values, each with magnitude 1,

$$\Vert \mathrm{sgn}(\mathbf{v}){\Vert }_2^2\le N⟹\Vert \mathrm{sgn}(\mathbf{v}){\Vert }_2\le \sqrt{N}.$$

Thus, we get

$$\Vert \mathbf{v}{\Vert }_1\le \sqrt{N}\Vert \mathbf{v}{\Vert }_2.$$

Theorem 12.11 (Equivalence of ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms)

Let $\mathbf{v}\in {\mathbb{C}}^N$. Then

$$\Vert \mathbf{v}{\Vert }_2\le \sqrt{N}\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}.$$

Proof. This follows from:

$$\Vert \mathbf{v}{\Vert }_2^2=\sum _{i=1}^N|v_i{|}^2\le N\underset{1\le i\le N}{max}(|v_i{|}^2)=N\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}^2.$$

Thus

$$\Vert \mathbf{v}{\Vert }_2\le \sqrt{N}\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}.$$

Theorem 12.12 (Relationship between $p$-norms)

Let $\mathbf{v}\in {\mathbb{C}}^N$. Let $1\le p,q\le \mathrm{\infty }$. Then

$$\Vert \mathbf{v}{\Vert }_q\le \Vert \mathbf{v}{\Vert }_p\text{ whenever }p\le q.$$

Proof. TBD

Theorem 12.13

Let $\mathbf{1}\in {\mathbb{C}}^N$ be the vector of all ones; i.e., $\mathbf{1}=(1,\dots ,1)$. Let $\mathbf{v}\in {\mathbb{C}}^N$ be some arbitrary vector. Let $|\mathbf{v}|$ denote the vector of absolute values of entries in $\mathbf{v}$; i.e., $|v{|}_i=|v_i|\mathrm{\forall }1\le i\le N$. Then

$$\Vert \mathbf{v}{\Vert }_1={\mathbf{1}}^T|\mathbf{v}|={\mathbf{1}}^H|\mathbf{v}|.$$

Proof. This follows from:

$${\mathbf{1}}^T|\mathbf{v}|=\sum _{i=1}^N|v{|}_i=\sum _{i=1}^N|v_i|=\Vert \mathbf{v}{\Vert }_1.$$

Finally since $\mathbf{1}$ consists only of real entries, hence its transpose and Hermitian transpose are same.

Theorem 12.14

Let $\mathbb{1}\in {\mathbb{C}}^{N\times N}$ be a square matrix of all ones. Let $\mathbf{v}\in {\mathbb{C}}^N$ be some arbitrary vector. Then

$$|\mathbf{v}{|}^T\mathbb{1}|\mathbf{v}|=\Vert \mathbf{v}{\Vert }_1^2.$$

Proof. We know that

$$\mathbb{1}=\mathbf{1}{\mathbf{1}}^T$$

Thus,

$$|\mathbf{v}{|}^T\mathbb{1}|\mathbf{v}|=|\mathbf{v}{|}^T\mathbf{1}{\mathbf{1}}^T|\mathbf{v}|=({\mathbf{1}}^T|\mathbf{v}|{)}^T({\mathbf{1}}^T|\mathbf{v}|)=\Vert \mathbf{v}{\Vert }_1\Vert \mathbf{v}{\Vert }_1=\Vert \mathbf{v}{\Vert }_1^2.$$

We used the fact that $\Vert \mathbf{v}{\Vert }_1={\mathbf{1}}^T|\mathbf{v}|$.

Theorem 12.15 (An upper bound on the $k$-th largest value)

$k$-th largest (magnitude) entry in a vector $\mathbf{x}\in {\mathbb{C}}^N$ denoted by $x_{(k)}$ obeys

(12.20)$$|x_{(k)}|\le \frac{\Vert \mathbf{x}{\Vert }_1}{k}.$$

Proof. Let $n_1,n_2,\dots ,n_N$ be a permutation of $\{1,2,\dots ,N\}$ such that

$$|x_{n_1}|\ge |x_{n_2}|\ge \cdots \ge |x_{n_N}|.$$

Thus, the $k$-th largest entry in $\mathbf{x}$ is $x_{n_k}$. It is clear that

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^N|x_i|=\sum _{i=1}^N|x_{n_i}|.$$

Obviously

$$|x_{n_1}|\le \sum _{i=1}^N|x_{n_i}|=\Vert \mathbf{x}{\Vert }_1.$$

Similarly

$$k|x_{n_k}|=|x_{n_k}|+\cdots +|x_{n_k}|\le |x_{n_1}|+\cdots +|x_{n_k}|\le \sum _{i=1}^N|x_{n_i}|\le \Vert \mathbf{x}{\Vert }_1.$$

Thus

$$|x_{n_k}|\le \frac{\Vert \mathbf{x}{\Vert }_1}{k}.$$

12.5.6. Sparse Signals

In this subsection we explore some useful properties of ${\mathrm{\Sigma }}_K$, the set of $K$-sparse signals in standard basis for ${\mathbb{C}}^N$.

We recall that

$${\mathrm{\Sigma }}_K=\{\mathbf{x}\in {\mathbb{C}}^N|\Vert \mathbf{x}{\Vert }_0\le K\}.$$

We established before that this set is a union of $(\genfrac{}{}{0ex}{}{N}{K})$ subspaces of ${\mathbb{C}}^N$ each of which is is constructed by an index set $\mathrm{\Lambda }\subset \{1,\dots ,N\}$ with $|\mathrm{\Lambda }|=K$ choosing $K$ specific dimensions of ${\mathbb{C}}^N$.

We first present some results which connect the $l_1$, $l_2$ and $l_{\mathrm{\infty }}$ norms of vectors in ${\mathrm{\Sigma }}_K$.

Theorem 12.16 (Relation between norms of sparse vectors)

Suppose $\mathbf{u}\in {\mathrm{\Sigma }}_K$. Then

$$\frac{\Vert \mathbf{u}{\Vert }_1}{\sqrt{K}}\le \Vert \mathbf{u}{\Vert }_2\le \sqrt{K}\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}.$$

Proof. Due to Theorem 12.9, we can write ${\ell }_1$ norm as

$$\Vert \mathbf{u}{\Vert }_1=⟨\mathbf{u},\mathrm{sgn}(\mathbf{u})⟩.$$

By Cauchy-Schwartz inequality we have

$$⟨\mathbf{u},\mathrm{sgn}(\mathbf{u})⟩\le \Vert \mathbf{u}{\Vert }_2\Vert \mathrm{sgn}(\mathbf{u}){\Vert }_2$$

Since $\mathbf{u}\in {\mathrm{\Sigma }}_K$, $\mathrm{sgn}(\mathbf{u})$ can have at most $K$ non-zero values each with magnitude 1. Thus, we have

$$\Vert \mathrm{sgn}(\mathbf{u}){\Vert }_2^2\le K⟹\Vert \mathrm{sgn}(\mathbf{u}){\Vert }_2\le \sqrt{K}.$$

Thus we get the lower bound

$$\Vert \mathbf{u}{\Vert }_1\le \Vert \mathbf{u}{\Vert }_2\sqrt{K}⟹\frac{\Vert \mathbf{u}{\Vert }_1}{\sqrt{K}}\le \Vert \mathbf{u}{\Vert }_2.$$

Now $|u_i|\le max(|u_i|)=\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}$. So we have

$$\Vert \mathbf{u}{\Vert }_2^2=\sum _{i=1}^N|u_i{|}^2\le K\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}^2$$

since there are only $K$ non-zero terms in the expansion of $\Vert \mathbf{u}{\Vert }_2^2$. This establishes the upper bound:

$$\Vert \mathbf{u}{\Vert }_2\le \sqrt{K}\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}.$$

12.5.7. Compressible Signals

In this subsection, we first look at some general results and definitions related to $K$-term approximations of arbitrary signals $\mathbf{x}\in {\mathbb{C}}^N$. We then define the notion of a compressible signal and study properties related to it.

12.5.7.1. K-term Approximation of General Signals

Definition 12.10 (Restriction of a signal)

Let $\mathbf{x}\in {\mathbb{C}}^N$. Let $T\subset \{1,2,\dots ,N\}$ be any index set. Further let

$$T=\{t_1,t_2,\dots ,t_{|T|}\}$$

such that

$$t_1<t_2<\cdots <t_{|T|}.$$

Let ${\mathbf{x}}_T\in {\mathbb{C}}^{|T|}$ be defined as

(12.21)$${\mathbf{x}}_T=\left(\begin{array}{cccc}{x}_{t_1}& x_{t_2}& \dots & x_{t_{|T|}}\end{array}\right).$$

Then ${\mathbf{x}}_T$ is a restriction of the signal $\mathbf{x}$ on the index set $T$.

Alternatively let ${\mathbf{x}}_T\in {\mathbb{C}}^N$ be defined as

(12.22)$$\begin{array}{r}{\mathbf{x}}_T(i)=\{\begin{array}{ll}\mathbf{x}(i)& \text{ if }i\in T;\\ 0& \text{ otherwise}.\end{array}\end{array}$$

In other words, ${\mathbf{x}}_T\in {\mathbb{C}}^N$ keeps the entries in $\mathbf{x}$ indexed by $T$ while sets all other entries to 0. Then we say that ${\mathbf{x}}_T$ is obtained by masking $\mathbf{x}$ with $T$.

As an abuse of notation, we will use any of the two definitions whenever we are referring to ${\mathbf{x}}_T$. The definition being used should be obvious from the context.

Example 12.17 (Restrictions on index sets)

$$\mathbf{x}=\left(\begin{array}{cccccccccc}-1& 5& 8& 0& 0& -3& 0& 0& 0& 0\end{array}\right)\in {\mathbb{C}}^{10}.$$

Let

$$T=\{1,3,7,8\}.$$

Then

$${\mathbf{x}}_T=\left(\begin{array}{cccccccccc}-1& 0& 8& 0& 0& 0& 0& 0& 0& 0\end{array}\right)\in {\mathbb{C}}^{10}.$$

Since $|T|=4$, sometimes we will also write

$$\mathbf{x}=\left(\begin{array}{cccc}-1& 8& 0& 0\end{array}\right)\in {\mathbb{C}}^4.$$

Definition 12.11 ($K$-term signal approximation)

Let $\mathbf{x}\in {\mathbb{C}}^N$ be an arbitrary signal. Consider any index set $T\subset \{1,\dots ,N\}$ with $|T|=K$. Then ${\mathbf{x}}_T$ is a $K$-term approximation of $\mathbf{x}$.

Clearly for any $\mathbf{x}\in {\mathbb{C}}^N$ there are $(\genfrac{}{}{0ex}{}{N}{K})$ possible $K$-term approximations of $\mathbf{x}$.

Example 12.18 ($K$-term approximation)

Let

$$\mathbf{x}=\left(\begin{array}{cccccccccc}-1& 5& 8& 0& 0& -3& 0& 0& 0& 0\end{array}\right)\in {\mathbb{C}}^{10}.$$

Let $T=\{1,6\}$. Then

$${\mathbf{x}}_T=\left(\begin{array}{cccccccccc}-1& 0& 0& 0& 0& -3& 0& 0& 0& 0\end{array}\right)$$

is a $2$-term approximation of $\mathbf{x}$.

If we choose $T=\{7,8,9,10\}$, the corresponding $4$-term approximation of $\mathbf{x}$ is

$$\left(\begin{array}{cccccccccc}0& 0& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right).$$

Definition 12.12 ($K$-largest entries approximation)

Let $\mathbf{x}\in {\mathbb{C}}^N$ be an arbitrary signal. Let ${\lambda }_1,\dots ,{\lambda }_N$ be indices of entries in $\mathbf{x}$ such that

$$|x_{{\lambda }_1}|\ge |x_{{\lambda }_2}|\ge \cdots \ge |x_{{\lambda }_N}|.$$

In case of ties, the order is resolved lexicographically; i.e., if $|x_i|=|x_j|$ and $i<j$ then $i$ will appear first in the sequence $\{{\lambda }_k\}$.

Consider the index set ${\mathrm{\Lambda }}_K=\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_K\}$. The restriction of $\mathbf{x}$ on ${\mathrm{\Lambda }}_K$ given by $x_{{\mathrm{\Lambda }}_K}$ contains the $K$ largest entries $\mathbf{x}$ while setting all other entries to 0. This is known as the $K$ largest entries approximation of $\mathbf{x}$.

This signal is denoted henceforth as $\mathbf{x}{|}_K$; i.e.

(12.23)$$\mathbf{x}{|}_K={\mathbf{x}}_{{\mathrm{\Lambda }}_K}$$

where ${\mathrm{\Lambda }}_K$ is the index set corresponding to $K$ largest entries in $\mathbf{x}$ (magnitude wise).

Example 12.19 (Largest entries approximation)

Let

$$\mathbf{x}=\left(\begin{array}{cccccccccc}-1& 5& 8& 0& 0& -3& 0& 0& 0& 0\end{array}\right).$$

Then

$$\mathbf{x}{|}_1=\left(\begin{array}{cccccccccc}0& 0& 8& 0& 0& 0& 0& 0& 0& 0\end{array}\right).$$

$$\mathbf{x}{|}_2=\left(\begin{array}{cccccccccc}0& 5& 8& 0& 0& 0& 0& 0& 0& 0\end{array}\right).$$

$$\mathbf{x}{|}_3=\left(\begin{array}{cccccccccc}0& 5& 8& 0& 0& -3& 0& 0& 0& 0\end{array}\right)$$

$$\mathbf{x}{|}_4=\mathbf{x}.$$

All further $K$ largest entries approximations are same as $\mathbf{x}$.

A pertinent question at this point is: which $K$-term approximation of $\mathbf{x}$ is the best $K$-term approximation? Certainly in order to compare two approximations we need some criterion. Let us choose ${\ell }_p$ norm as the criterion. The next result gives an interesting result for best $K$-term approximations in ${\ell }_p$ norm sense.

Theorem 12.17 (Best $K$-term approximation for ${\ell }_p$ norms)

Let $\mathbf{x}\in {\mathbb{C}}^N$. Let the best $K$ term approximation of $\mathbf{x}$ be obtained by the following optimization program:

(12.24)$$\begin{array}{rlrl}& \underset{T\subset \{1,\dots ,N\}}{\text{maximize}}& & \Vert {\mathbf{x}}_T{\Vert }_p\\ & \text{subject to }& & |T|=K.\end{array}$$

where $p\in [1,\mathrm{\infty }]$.

Let an optimal solution for this optimization problem be denoted by ${\mathbf{x}}_{T^{\ast }}$. Then

$$\Vert \mathbf{x}{|}_K{\Vert }_p=\Vert {\mathbf{x}}_{T^{\ast }}{\Vert }_p;$$

i.e., the $K$-largest entries approximation of $\mathbf{x}$ is an optimal solution to (12.24).

Proof. For $p=\mathrm{\infty }$, the result is obvious. In the following, we focus on $p\in [1,\mathrm{\infty })$.

We note that maximizing $\Vert {\mathbf{x}}_T{\Vert }_p$ is equivalent to maximizing $\Vert {\mathbf{x}}_T{\Vert }_p^p$.

Let ${\lambda }_1,\dots ,{\lambda }_N$ be indices of entries in $x$ such that

$$|x_{{\lambda }_1}|\ge |x_{{\lambda }_2}|\ge \cdots \ge |x_{{\lambda }_N}|.$$

Further let $\{{\omega }_1,\dots ,{\omega }_N\}$ be any permutation of $\{1,\dots ,N\}$. Clearly

$$\Vert \mathbf{x}{|}_K{\Vert }_p^p=\sum _{i=1}^K|{\mathbf{x}}_{{\lambda }_i}{|}^p\ge \sum _{i=1}^K|{\mathbf{x}}_{{\omega }_i}{|}^p.$$

Thus if $T^{\ast }$ corresponds to an optimal solution of (12.24) then

$$\Vert \mathbf{x}{|}_K{\Vert }_p^p=\Vert {\mathbf{x}}_{T^{\ast }}{\Vert }_p^p.$$

Thus $\mathbf{x}{|}_K$ is an optimal solution to (12.24).

This result helps us establish that whenever we are looking for a best $K$-term approximation of $\mathbf{x}$ under any ${\ell }_p$ norm, all we have to do is to pickup the $K$-largest entries in $\mathbf{x}$.

Definition 12.13 (Restriction of a matrix)

Let $\mathrm{\Phi }\in {\mathbb{C}}^{M\times N}$. Let $T\subset \{1,2,\dots ,N\}$ be any index set. Further let

$$T=\{t_1,t_2,\dots ,t_{|T|}\}$$

such that

$$t_1<t_2<\cdots <t_{|T|}.$$

Let ${\mathrm{\Phi }}_T\in {\mathbb{C}}^{M\times |T|}$ be defined as

(12.25)$${\mathrm{\Phi }}_T=\left[\begin{array}{cccc}{\varphi }_{t_1}& {\varphi }_{t_2}& \dots & {\varphi }_{t_{|T|}}\end{array}\right].$$

Then ${\mathrm{\Phi }}_T$ is a restriction of the matrix $\mathrm{\Phi }$ on the index set $T$.

Alternatively let ${\mathrm{\Phi }}_T\in {\mathbb{C}}^{M\times N}$ be defined as

(12.26)$$\begin{array}{r}({\mathrm{\Phi }}_T{)}_i=\{\begin{array}{ll}{\varphi }_i& \text{if }i\in T;\\ \mathbf{0}& \text{otherwise}.\end{array}\end{array}$$

In other words, ${\mathrm{\Phi }}_T\in {\mathbb{C}}^{M\times N}$ keeps the columns in $\mathrm{\Phi }$ indexed by $T$ while sets all other columns to $\mathbf{0}$. Then we say that ${\mathrm{\Phi }}_T$ is obtained by masking $\mathrm{\Phi }$ with $T$.

As an abuse of notation, we will use any of the two definitions whenever we are referring to ${\mathrm{\Phi }}_T$. The definition being used should be obvious from the context.

Theorem 12.18

Let $\mathrm{supp}(\mathbf{x})=\mathrm{\Lambda }$. Then

$$\mathrm{\Phi }\mathbf{x}={\mathrm{\Phi }}_{\mathrm{\Lambda }}{\mathbf{x}}_{\mathrm{\Lambda }}.$$

Proof. This follows from:

$$\mathrm{\Phi }\mathbf{x}=\sum _{i=1}^N{x}_i{\varphi }_i=\sum _{{\lambda }_i\in \mathrm{\Lambda }}{x}_{{\lambda }_i}{\varphi }_{{\lambda }_i}={\mathrm{\Phi }}_{\mathrm{\Lambda }}{x}_{\mathrm{\Lambda }}.$$

The result remains valid whether we use the restriction or the mask version of ${\mathbf{x}}_{\mathrm{\Lambda }}$ notation as long as same version is used for both $\mathrm{\Phi }$ and $\mathbf{x}$.

Corollary 12.1

Let $S$ and $T$ be two disjoint index sets such that for some $\mathbf{x}\in {\mathbb{C}}^N$

$$\mathbf{x}=x_T+x_S$$

using the mask version of $x_{\mathrm{\Lambda }}$ notation. Then the following holds

$$\mathrm{\Phi }\mathbf{x}={\mathrm{\Phi }}_T{\mathbf{x}}_T+{\mathrm{\Phi }}_S{\mathbf{x}}_S.$$

Proof. Straightforward application of Theorem 12.18:

$$\mathrm{\Phi }\mathbf{x}=\mathrm{\Phi }{\mathbf{x}}_T+\mathrm{\Phi }{\mathbf{x}}_S={\mathrm{\Phi }}_T{\mathbf{x}}_T+{\mathrm{\Phi }}_S{\mathbf{x}}_S.$$

Theorem 12.19

Let $T$ be any index set. Let $\mathrm{\Phi }\in {\mathbb{C}}^{M\times N}$ and $\mathbf{y}\in {\mathbb{C}}^M$. Then

$$[{\mathrm{\Phi }}^H\mathbf{y}{]}_T={\mathrm{\Phi }}_T^H\mathbf{y}.$$

Proof. Note that

$$\begin{array}{r}{\mathrm{\Phi }}^H\mathbf{y}=\left[\begin{array}{c}⟨{\varphi }_1,\mathbf{y}⟩\\ ⋮\\ ⟨{\varphi }_N,\mathbf{y}⟩\end{array}\right]\end{array}$$

Now let

$$T=\{t_1,\dots ,t_K\}.$$

Then

$$\begin{array}{r}[{\mathrm{\Phi }}^H\mathbf{y}{]}_T=\left[\begin{array}{c}⟨{\varphi }_{t_1},\mathbf{y}⟩\\ ⋮\\ ⟨{\varphi }_{t_K},\mathbf{y}⟩\end{array}\right]={\mathrm{\Phi }}_T^H\mathbf{y}.\end{array}$$

The result remains valid whether we use the restriction or the mask version of ${\mathrm{\Phi }}_T$ notation.

12.5.7.2. Compressible Signals

We will now define the notion of a compressible signal in terms of the decay rate of magnitude of its entries when sorted in descending order.

Definition 12.14 (Compressible signal)

Let $\mathbf{x}\in {\mathbb{C}}^N$ be an arbitrary signal. Let ${\lambda }_1,\dots ,{\lambda }_N$ be indices of entries in $\mathbf{x}$ such that

$$|x_{{\lambda }_1}|\ge |x_{{\lambda }_2}|\ge \cdots \ge |x_{{\lambda }_N}|.$$

In case of ties, the order is resolved lexicographically, i.e. if $|x_i|=|x_j|$ and $i<j$ then $i$ will appear first in the sequence $\{{\lambda }_k\}$. Define

(12.27)$$\hat{\mathbf{x}}=(x_{{\lambda }_1},x_{{\lambda }_2},\dots ,x_{{\lambda }_N}).$$

The signal $\mathbf{x}$ is called $p$-compressible with magnitude $R$ if there exists $p\in (0,1]$ such that

(12.28)$$|{\hat{x}}_i|\le R\cdot i^{-\frac{1}{p}}\mathrm{\forall }i=1,2,\dots ,N.$$

Theorem 12.20 ($1$-compressible signals)

Let $\mathbf{x}$ be be $p$-compressible with $p=1$. Then

$$\Vert \mathbf{x}{\Vert }_1\le R(1+\ln (N)).$$

Proof. Recalling $\hat{x}$ from (12.27) it is straightforward to see that

$$\Vert \mathbf{x}{\Vert }_1=\Vert \hat{\mathbf{x}}{\Vert }_1$$

since the ${\ell }_1$ norm doesn’t depend on the ordering of entries in $\mathbf{x}$.

Now since $\mathbf{x}$ is $1$-compressible, hence from (12.28) we have

$$|{\hat{x}}_i|\le R\frac{1}{i}.$$

This gives us

$$\Vert \hat{x}{\Vert }_1\le \sum _{i=1}^{N}R\frac{1}{i}=R\sum _{i=1}^N\frac{1}{i}.$$

The sum on the R.H.S. is the $N$-th Harmonic number (sum of reciprocals of first $N$ natural numbers). A simple upper bound on Harmonic numbers is

$$H_k\le 1+\ln (k).$$

This completes the proof.

We now demonstrate how a compressible signal is well approximated by a sparse signal.

Theorem 12.21 (Sparse approximation of compressible signals)

Let $\mathbf{x}$ be a $p$-compressible signal and let $\mathbf{x}{|}_K$ be its best $K$-term approximation. Then the ${\ell }_1$ norm of approximation error satisfies

(12.29)$$\Vert \mathbf{x}-\mathbf{x}{|}_K{\Vert }_1\le C_p\cdot R\cdot K^{1-\frac{1}{p}}$$

with

$$C_p={(\frac{1}{p}-1)}^{-1}.$$

Moreover the ${\ell }_2$ norm of approximation error satisfies

(12.30)$$\Vert \mathbf{x}-\mathbf{x}{|}_K{\Vert }_2\le D_p\cdot R\cdot K^{1-\frac{1}{p}}$$

with

$$D_p={(\frac{2}{p}-1)}^{-1/2}.$$

Proof. Expanding the ${\ell }_1$ approximation error

$$\Vert \mathbf{x}-\mathbf{x}{|}_K{\Vert }_1=\sum _{i=K+1}^N|x_{{\lambda }_i}|\le R\sum _{i=K+1}^N{i}^{-\frac{1}{p}}.$$

We now approximate the R.H.S. sum with an integral.

$$\sum _{i=K+1}^N{i}^{-\frac{1}{p}}\le {\int }_{x=K}^N{x}^{-\frac{1}{p}}dx\le {\int }_{x=K}^{\mathrm{\infty }}{x}^{-\frac{1}{p}}dx.$$

Now

$${\int }_{x=K}^{\mathrm{\infty }}{x}^{-\frac{1}{p}}dx={\left[\frac{x^{1-\frac{1}{p}}}{1-\frac{1}{p}}\right]}_K^{\mathrm{\infty }}=C_p{K}^{1-\frac{1}{p}}.$$

We can similarly show the result for ${\ell }_2$ norm.

Example 12.20 (Sparse approximation for $\frac{1}{2}$-compressible signals)

Let $p=\frac{1}{2}$. Then

$$C_p={(\frac{1}{p}-1)}^{-1}=1\text{ and }{D}_p={(\frac{2}{p}-1)}^{-1/2}=\frac{1}{\sqrt{3}}.$$

Hence

$$\Vert \mathbf{x}-\mathbf{x}{|}_K{\Vert }_1\le \frac{R}{K}$$

and

$$\Vert \mathbf{x}-\mathbf{x}{|}_K{\Vert }_2\le \frac{1}{\sqrt{3}}\frac{R}{K}.$$

Both ${\ell }_1$ and ${\ell }_2$ approximation error bounds decrease as $K$ increases at the same rate.

previous

12.4. Sparsity in Orthonormal Bases

next

12.6. Dictionaries