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.

A preliminary version of this work won the Best Student Paper Award at SPARS'13.

@article{TillmannPfetsch2014,

author = {A. M. Tillmann and M. E. Pfetsch},

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

journal = {{IEEE Transactions on Information Theory}},

volume = {60},

number = {2},

pages = {1248--1259},

year = {2014},

note = {DOI: 10.1109/TIT.2013.2290112}

}