Certifying the Restricted Isometry Property is Hard

By Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, W. Sawin. 2012

248 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Joey Tianyi Zhou
2. Xi Peng
3. Y. Liu
4. Rick Siow Mong Goh
5. Marc E. Pfetsch
6. Andreas M. Tillmann
7. Jiawei Du
8. Hongyuan Zhu

In Computational Mechanics

1. Joey Tianyi Zhou
2. Xi Peng
3. Y. Liu
4. Rick Siow Mong Goh
5. Marc E. Pfetsch
6. Andreas M. Tillmann
7. Jiawei Du
8. Hongyuan Zhu

In Computer Networks and Communications

1. Joey Tianyi Zhou
2. Y. Liu
3. Marc E. Pfetsch
4. Andreas M. Tillmann
5. Jiawei Du

Citations in the corpus

• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing (2012, methodology): “The main arguments used in the proofs of the following Lemma and Corollary have been independently derived by us and the authors of [20].”
• AnomalyNet: An Anomaly Detection Network for Video Surveillance (2019, background): “However, it is NP-hard to verify the RIP condition for a matrix [60].”