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

Candès, Emmanuel J.

C. R., Math., Acad. Sci. Paris 346, No. 9-10, 589-592 (2008).

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.

Reviewer: Joseph Lakey (Las Cruces)

MSC:

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

Keywords:

compressed sensing; restricted isometry property

References:

[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)