A note on the hardness of sparse approximation
From MaRDI portal
Publication:2444766
DOI10.1016/j.ipl.2013.04.014zbMath1284.68278OpenAlexW2007457286MaRDI QIDQ2444766
Publication date: 11 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2013.04.014
complexitycomputational complexitysubset selectionsparse approximationapproximation algorithmsinapproximability
Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Greedy algorithms and \(M\)-term approximation with regard to redundant dictionaries
- Weak greedy algorithms
- On Lebesgue-type inequalities for greedy approximation
- A threshold of ln n for approximating set cover
- Greed is Good: Algorithmic Results for Sparse Approximation
- Sparse Approximate Solutions to Linear Systems
- Compressed sensing
- Adaptive greedy approximations