0.7 Compressed sensing  (Page 2/5)

The CS theory tells us that when certain conditions hold, namely that the functions $\left\{{\phi }_m\right\}$ cannot sparsely represent the elements of the basis $\left\{{\psi }_n\right\}$ (a condition known as incoherence of the two dictionaries [link] , [link] , [link] , [link] ) and the number of measurements $M$ is large enough, then it is indeed possible to recover the set of large $\left\{\alpha \right(n\left)\right\}$ (and thus the signal $x$ ) from a similarly sized set of measurements $y$ . This incoherence property holds for many pairs of bases, including forexample, delta spikes and the sine waves of a Fourier basis, or the Fourier basis and wavelets. Significantly, this incoherencealso holds with high probability between an arbitrary fixed basis and a randomly generated one.

Methods for signal recovery

Although the problem of recovering $x$ from $y$ is ill-posed in general (because $x\in {\mathbb{R}}^N$ , $y\in {\mathbb{R}}^M$ , and $M<N$ ), it is indeed possible to recover sparse signals from CS measurements. Given the measurements $y=\Phi x$ , there exist an infinite number of candidate signals in the shifted nullspace $\mathcal{N}\left(\Phi \right)+x$ that could generate the same measurements $y$ (see Linear Models from Low-Dimensional Signal Models ). Recovery of the correct signal $x$ can be accomplished by seeking a sparse solution among these candidates.

Recovery via combinatorial optimization

Supposing that $x$ is exactly $K$ -sparse in the dictionary $\Psi$ , then recovery of $x$ from $y$ can be formulated as the ${\ell }_0$ minimization

In principle, remarkably few incoherent measurements are required to recover a $K$ -sparse signal via ${\ell }_0$ minimization. Clearly, more than $K$ measurements must be taken to avoid ambiguity; the following theorem (which is proved in [link] ) establishes that $K+1$ random measurements will suffice. (Similar results were established by Venkataramani and Bresler  [link] .)

Let $\Psi$ be an orthonormal basis for ${\mathbb{R}}^N$ , and let $1\le K<N$ . Then the following statements hold:

1. Let $\Phi$ be an $M\times N$ measurement matrix with i.i.d. Gaussian entries with $M\ge 2K$ . Then with probability one the following statement holds: all signals $x=\Psi \alpha$ having expansion coefficients $\alpha \in {\mathbb{R}}^N$ that satisfy ${\parallel \alpha \parallel }_0=K$ can be recovered uniquely from the $M$ -dimensional measurement vector $y=\Phi x$ via the ${\ell }_0$ optimization [link] .
2. Let $x=\Psi \alpha$ such that ${\parallel \alpha \parallel }_0=K$ . Let $\Phi$ be an $M\times N$ measurement matrix with i.i.d. Gaussian entries (notably, independent of $x$ ) with $M\ge K+1$ . Then with probability one the following statement holds: $x$ can be recovered uniquely from the $M$ -dimensional measurement vector $y=\Phi x$ via the ${\ell }_0$ optimization [link] .
3. Let $\Phi$ be an $M\times N$ measurement matrix, where $M\le K$ . Then, aside from pathological cases (specified in the proof), no signal $x=\Psi \alpha$ with ${\parallel \alpha \parallel }_0=K$ can be uniquely recovered from the $M$ -dimensional measurement vector $y=\Phi x$ .