IAM

OPENSOURCEFAN STUDYING
STUDYINGCOMPUTERSCIENCEANDMATH COMPUTERSCIENCE

DAVIDSTUTZ

Check out the latest superpixel benchmark — Superpixel Benchmark (2016) — and let me know your opinion! @david_stutz
06thMAY2016

READING

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 the summarized work? Or do you know related work that is of interest? Let me know your thoughts in the comments below or using the following platforms: