English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This paper deals with the computational complexity of conditions whichguarantee that the NP-hard problem of finding the sparsest solution to anunderdetermined linear system can be solved by efficient algorithms. In theliterature, several such conditions have been introduced. The most well-knownones are the mutual coherence, the restricted isometry property (RIP), and thenullspace property (NSP). While evaluating the mutual coherence of a givenmatrix is easy, it has been suspected for some time that evaluating RIP and NSPis computationally intractable in general. We confirm these conjectures byshowing that for a given matrix A and positive integer k, computing the bestconstants for which the RIP or NSP hold is, in general, NP-hard. These resultsare based on the fact that determining the spark of a matrix is NP-hard, whichis also established in this paper. Furthermore, we also give several complexitystatements about problems related to the above concepts.

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