This is an announcement for the paper "Certifying the restricted isometry property is hard" by Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, and William F. Sawin.

Abstract: This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is hard for NP under randomized polynomial-time reductions. Our reduction is from the NP-complete clique decision problem, and it uses ideas from matroid theory. As a consequence of our result, it is impossible to efficiently test for RIP provided NP \not\subseteq BPP, an assumption which is slightly stronger than P \neq NP.

Archive classification: math.FA cs.IT math.IT

Remarks: 7 pages

Submitted from: dmixon@princeton.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1204.1580

or

http://arXiv.org/abs/1204.1580