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