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 isNP-hard. As a consequence of our result, it is impossible to efficiently test for RIP providedP≠NP.