Sparse approximation is provably hard under coherent dictionaries
From MaRDI portal
Publication:340554
DOI10.1016/j.jcss.2016.07.001zbMath1354.65085arXiv1702.02885OpenAlexW2491631217MaRDI QIDQ340554
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.02885
Computational methods for sparse matrices (65F50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)
Cites Work
- Unnamed Item
- On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries
- Compressed sensing with coherent and redundant dictionaries
- On performance of greedy algorithms
- Greedy algorithms and \(M\)-term approximation with regard to redundant dictionaries
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Weak greedy algorithms
- Column subset selection problem is UG-hard
- On Lebesgue-type inequalities for greedy approximation
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Greed is Good: Algorithmic Results for Sparse Approximation
- On the power of unique 2-prover 1-round games
- Probabilistic checking of proofs
- On the hardness of approximating minimization problems
- A Parallel Repetition Theorem
- Sparse Approximate Solutions to Linear Systems
- The Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing
- Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Adaptive greedy approximations
This page was built for publication: Sparse approximation is provably hard under coherent dictionaries
