2012/05/09 by Andreas M. Tillmann, Tillmann, Andreas M., Marc E. Pfetsch +1 · 4 citations
Computer Science · Engineering · 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
paper · pdf · doi:10.48550/arxiv.1205.2081
openalex publication_date 2012/05/09 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
This paper deals with the computational complexity of conditions which\nguarantee that the NP-hard problem of finding the sparsest solution to an\nunderdetermined linear system can be solved by efficient algorithms. In the\nliterature, several such conditions have been introduced. The most well-known\nones are the mutual coherence, the restricted isometry property (RIP), and the\nnullspace property (NSP). While evaluating the mutual coherence of a given\nmatrix is easy, it has been suspected for some time that evaluating RIP and NSP\nis computationally intractable in general. We confirm these conjectures by\nshowing that for a given matrix A and positive integer k, computing the best\nconstants for which the RIP or NSP hold is, in general, NP-hard. These results\nare based on the fact that determining the spark of a matrix is NP-hard, which\nis also established in this paper. Furthermore, we also give several complexity\nstatements about problems related to the above concepts.\n