G. Kutyniok. Theory and Applications of Compressed Sensing. Computing Research Repository, abs/1203.3815, 2012.

Kutyniok gives a thorough yet succinct introduction to compressed sensing - theory as well as applications. Research on compressed sensing was initiated by Donoho [1] and evolves around the problem of recovering $x \in \mathbb{R}^n$ from knowledge of $y = Ax$ with $A \in \mathbb{R}^{m \times n}$ called sensing matrix with $m \ll n$. Key idea to compressed sensing is the sparsity of $x$. Usually, the $l_0$-norm (which is not a norm in the mathematical sense) is used to describe sparsity:

$\|x\|_0 = |\{i | x_i \neq 0\}|$

In a few words, a sparse signal contains few non-zero entries. Kutyniok gives several examples of sparse signals in practice, including some examples form image processing as for example wavelets.

Intuitive approaches to the problem are the following:

$\arg\min_{x \in \mathbb{R}^n} \|x\|_0\quad\text{s.t.}\quad Ax = y$($l_0$)

$\arg\min_{x \in \mathbb{R}^n} \|x\|_1\quad\text{s.t.}\quad Ax = y$($l_1$)

where $(l_1)$ represents a convex approximation of the problem and is termed basis pursuit. A key question in compressed sensing is whether (or under which assumptions) "$(l_0) = (l_1)$" holds.

To formally work with sparsity, Kutyniok uses the following definition of sparse signals:

Definition. A signal $x \in \mathbb{R}^n$ is called $k$-sparse, if $\|x\|_0 \leq k$. The set of all $k$-sparse signals is denoted by $\Sigma_k$.

Based on this definition, Kutyniok presents several results regarding the uniqueness of $(l_0)$ and $(l_1)$ as well as sufficient conditions for "$(l_0) = (l_1)$. Two important concepts regarding the uniqueness are the spark of $A$ and the null-space property of order $k$:

Definition. For $A \in \mathbb{R}^{m \times n}$, the spark of $A$ is defined as:

$\text{spark}(A) = \min\{k | \mathcal{N}(A) \cap \Sigma_k \neq \emptyset\}$

where $\mathcal{N}(A)$ denotes the null space of $A$.

Definition. For $h \in \mathbb{R}^n$ and $\Lambda \subseteq \{1, \ldots, n\}$, we let

$1_\Lambda h = h_i \Leftrightarrow i \in \Lambda\quad\text{and}\quad1_\Lambda h = 0\Leftrightarrow i \notin \Lambda$

Then, $A \in \mathbb{R}^{m \times n}$ has the null-space property of order $k$, if for all $h \in \mathcal{N}(A)\setminus\{0\}$ it holds

$\|1_\Lambda h\|_1 < \frac{1}{2} \|h\|_1$

for all index sets $|\Lambda| \leq k$.

In words, $\text{spark}(A)$ is the minimum $k \in [2, M + 1]$ such that a sparse signal $x \in \Sigma_k$ exists with $Ax = 0$ (i.e. $x \in \mathcal{N}(A)$). The null-space property of order $k$, in contrast, says that for all $x \in \mathcal{N}(A)$, the $l_1$-norm halves if only $j \leq k$ elements are taken while the others are set to zero. Then it can be shown that $(l_0)$ has a unique solution $x$ with $\|x\|_0 \leq k$ iff $k < \text{spark}(A)/2$. Similarly, it holds that $(l_1)$ has a unique solution $x$ with $\|x\|_0 \leq 0$ iff $A$ satisfies the null-space property of order $k$.

Kutyniok discusses several conditions sufficient for "$(l_0) = (l_1)$" to holds. One of these is mutual coherence:

Definition. For $A \in \mathbb{R}^{m \times n}$, the mutual coherence $\mu(A)$ is defined as

$\mu(A) = \max_{i \neq j} \frac{|a_i^Ta_j|}{\|a_i\|_2 \|a_j\|_2}.$

In other words, mutual coherence is the smallest angle between a pair of columns of $A$. As result, $\mu(A)$ is easily measures in practice (in contrast to other concepts such as the restricted isometry property, see the paper). The following theorem then states the sufficient condition:

Theorem. For $A \in \mathbb{R}^{m \times n}$ with $0 \neq x \in \mathbb{R}^n$ being a solution of $(l_0)$ satisfying

$\|x\|_0 < \frac{1}{2}(1 + \mu(A)^{-1})$,

$x$ is the unique solution of $(l_0)$ and $(l_1)$.

Note that, as discussed by Kutyniok, the presented properties (spark, null-space property and mutual coherence) can be related, see Lemma 4.1 in the paper.

Finally, Kutyniok discusses algorithmic approaches. First, convex optimization is suited to solve $(l_1)$ in the following form:

$\arg\min_{x \in \mathbb{R}^n} \frac{1}{2}\|Ax - y\|_2^2 + \lambda \|x\|_1$.

where $\lambda$ is a regularization parameter; forward-backward splitting is applicable here, see [2]. Second, she briefly discusses orthonormal matching pursuit (OMP), a greedy algorithm.

  • [1] D. L. Donoho. Compressed sensing. Transactions on Information Theory, 52, 2006.
  • [2] P. L. Combettes and J.-C. Pesquet.Proximal Splitting Methods in Signal Processing. Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, 2011.
What is your opinion on this article? Let me know your thoughts on Twitter @davidstutz92 or LinkedIn in/davidstutz92.