<< Chapter < Page | Chapter >> Page > |
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.
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.
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] .)
TheoremLet $\Psi $ be an orthonormal basis for ${\mathbb{R}}^{N}$ , and let $1\le K<N$ . Then the following statements hold:
Notification Switch
Would you like to follow the 'Concise signal models' conversation and receive update notifications?