2012/05/09 by Andreas M. Tillmann, Tillmann, Andreas M., Marc E. Pfetsch +1 · 5 citations
Computer Science · Engineering · Mathematics · Medicine · #Advanced MRI Techniques and Applications #Blind Source Separation Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1205.2081
13 pages; accepted for publication in IEEE Trans. Inf. Theory
openalex publication_date 2012/05/09 · arxiv created 2013/11/04 · arxiv updated 2013/11/05 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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.