The restricted isometry property and its implications for compressed sensing (Q927127)

Conditions on a \textit{sensing matrix} \(\Phi\) are given such that the solution \(x^\star\) of \[ \min_{\tilde{x}\in \mathbb{R}^n}\| \tilde{x}\| _{\ell^1} \quad{\text{ subject\,\, to}}\quad \Phi x =y \leqno{(\star)} \] recovers \(x\) exactly provided \(x\) is {\textit{sparse}} and the sensing matrix satisfies a {\textit{restricted isometry property}}. A vector \(x\in \mathbb{R}^N\) is \(s\)-sparse if at most \(s\) of its coordinates are nonzero. For each \(s=1,2,\dots\) the \(s\)-isometry constant of a matrix \(\Phi\) is the smallest number \(\delta_s\) such that \[ (1-\delta_s)\| x\| _{\ell^2}^2\leq \| \Phi x\| _{\ell^2}^2\leq (1+\delta_s) \| x\| _{\ell^2}^2 \] whenever \(x\) is \(s\)-sparse. The first result applies to noiseless recovery, and states that if \(\delta_{2s}<\sqrt{2}-1\) then there is a constant \(C\) such that the solution \(x^\star\) of (\(\star\)) satisfies \(\| x^\star -x\| _{\ell^1}\leq C\| x-x_s\| _{\ell^1}\) and \(\| x^\star -x\| _{\ell^2}\leq C s^{-1/2}\| x-x_s\| _{\ell^1}\). In particular, the recovery is exact if \(x\) is \(s\)-sparse. The second result applies to the minimizer of \[ \min_{\tilde{x}\in \mathbb{R}^n}\| \tilde{x}\| _{\ell^1} \quad{\text{subject\,\, to}}\quad y=\Phi x =z \leqno{(\star\star)} \] where \(\| z\| _{\ell^2}\leq \varepsilon\). Assuming again that \(\delta_{2s}<\sqrt{2}-1\) it is shown that the solution of (\(\star\star\)) satisfies \(\| x^\star-x\| _{\ell^2} \leq C s^{-1/2}\| x\| _{\ell^1}+ K\varepsilon\) for a second constant \(K\). How \(C\) and \(K\) depend on \(\delta_s\) can be inferred from the proofs. The bounds here improve those first established by the author and \textit{T.~Tao} in [``Decoding by linear programming'', IEEE Trans. Inform. Theory 51 (12), 4203--4215 (2005)] where it was first shown that the \(\ell^1\) minimizer of \(\Phi \tilde x=y\) recovers \(x\) when \(x\) is sufficiently sparse.