The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

By Andreas M. Tillmann, Marc E. Pfetsch. IEEE Transactions on Information Theory, 2012

403 citations recorded by the source corpus.

This paper deals with the computational complexity of conditions which guarantee that the NP-hard problem of finding the sparsest solution to an underdetermined linear system can be solved by efficient algorithms. In the literature, several such conditions have been introduced. The most well-known ones are the mutual coherence, the restricted isometry property (RIP), and the nullspace property (NSP). While evaluating the mutual coherence of a given matrix is easy, it has been suspected for some time that evaluating RIP and NSP is computationally intractable in general. We confirm these conjectures by showing that for a given matrix A and positive integer k, computing the best constants for which the RIP or NSP hold is, in general, NP-hard. These results are based on the fact that determining the spark of a matrix is NP-hard, which is also established in this paper. Furthermore, we also give several complexity statements about problems related to the above concepts.

Subfields: Computational Mechanics, Radiology, Nuclear Medicine and Imaging, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e4e2717f7c244d7ae119c66467f1bd77633d68eb

How researchers see this paper

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

In Computational Mechanics

In Radiology, Nuclear Medicine and Imaging

In Signal Processing

Citations in the corpus

Computationally Efficient Robust Sparse Estimation in High Dimensions (2017, background): “This is the sparse PCA problem and is known to be NP-hard in a strong sense (Tillmann and Pfetsch, 2014).”
Spectrum sensing in cognitive radio (2016, background): “The reason for this is that verifying that a matrix satisfies any of these properties is generally NPhard [60].”
Compressed Sensing (2014, neutral): “Si bien la propiedad RIP y el spark permiten garantizar la unicidad de soluciones de CS, el cálculo de estos es dif́ıcil en general, encontrándose dentro de los problemas NP-dif́ıcil [67].”
Signal representations with minimum ℓ∞-norm (2012, background): “Verifying the UP for a given frame D requires, in general, a combinatorial search over all δN -sparse vectors [22].”
Certifying the Restricted Isometry Property is Hard (2012, methodology): “Recently, Tillmann and Pfetsch [10] used ideas similar to McCormick’s to reduce Problem 3 from the clique problem, thereby demonstrating strong -hardness.”