Certifying the Restricted Isometry Property is Hard.

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 \ssr NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided \ssr P\ne\ssr NP. [ABSTRACT FROM PUBLISHER]