Sparse approximation is provably hard under coherent dictionaries

DOI10.1016/J.JCSS.2016.07.001zbMATH Open1354.65085arXiv1702.02885OpenAlexW2491631217MaRDI QIDQ340554FDOQ340554

Ali Çivril

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: It is well known that sparse approximation problem is extsf{NP}-hard under general dictionaries. Several algorithms have been devised and analyzed in the past decade under various assumptions on the emph{coherence} $mu$ of the dictionary represented by an $MimesN$ matrix from which a subset of $k$ column vectors is selected. All these results assume $mu=O(k^{-1})$. This article is an attempt to bridge the big gap between the negative result of extsf{NP}-hardness under general dictionaries and the positive results under this restrictive assumption. In particular, it suggests that the aforementioned assumption might be asymptotically the best one can make to arrive at any efficient algorithmic result under well-known conjectures of complexity theory. In establishing the results, we make use of a new simple multilayered PCP which is tailored to give a matrix with small coherence combined with our reduction.

Full work available at URL: https://arxiv.org/abs/1702.02885

zbMATH Keywords

sparse approximationcomplexityPCPunique games

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• A threshold of ln n for approximating set cover
• Greed is Good: Algorithmic Results for Sparse Approximation
• Adaptive greedy approximations
• Weak greedy algorithms
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Sparse Approximate Solutions to Linear Systems
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Greedy algorithms and \(M\)-term approximation with regard to redundant dictionaries
• On the power of unique 2-prover 1-round games
• On the hardness of approximating minimization problems
• A Parallel Repetition Theorem
• Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property
• Compressed sensing with coherent and redundant dictionaries
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Exponential inapproximability of selecting a maximum volume sub-matrix
• Column subset selection problem is UG-hard
• On Lebesgue-type inequalities for greedy approximation
• On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
• Title not available (Why is that?)
• The Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing
• On performance of greedy algorithms

Cited In (3)

• On some deterministic dictionaries supporting sparsity
• Title not available (Why is that?)
• Average Performance of the Sparsest Approximation Using a General Dictionary

   Recommendations

• A note on the hardness of sparse approximation
• NP-hardness and inapproximability of sparse PCA
• [[:Publication:4633050|Title not available (Why is that?)]]
• [[:Publication:4471300|Title not available (Why is that?)]]
• Sparse Approximate Solutions to Linear Systems

This page was built for publication: Sparse approximation is provably hard under coherent dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340554)