The restricted isometry property and its implications for compressed sensing. (English) Zbl 1153.94002

Conditions on a 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 {(\star)} \] recovers \(x\) exactly provided \(x\) is {sparse} and the sensing matrix satisfies a {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 {(\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 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.


94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A20 Sampling theory in information and communication theory
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
42C15 General harmonic expansions, frames
Full Text: DOI


[1] Candès, E.J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. pure appl. math., 59, 8, 1207-1223, (August 2006)
[2] Candès, E.J.; Tao, T., Decoding by linear programming, IEEE trans. inform. theory, 51, 12, 4203-4215, (December 2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.