A note on the hardness of sparse approximation
From MaRDI portal
Publication:2444766
DOI10.1016/j.ipl.2013.04.014zbMath1284.68278MaRDI 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
complexity; computational complexity; subset selection; sparse approximation; approximation algorithms; inapproximability
68T05: Learning and adaptive systems in artificial intelligence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
65Y20: Complexity and performance of numerical algorithms
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