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:
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:
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
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:
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.
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.