Sparse approximation is provably hard under coherent dictionaries
Author:
- 1 March 2017
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 84, 32-43
Abstract
No abstract availableKeywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Column Subset Selection Problem is UG-hardJournal of Computer and System Sciences, 2014
- Exponential Inapproximability of Selecting a Maximum Volume Sub-matrixAlgorithmica, 2011
- Compressed sensing with coherent and redundant dictionariesApplied and Computational Harmonic Analysis, 2011
- Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry PropertyIEEE Transactions on Information Theory, 2010
- On Lebesgue-type inequalities for greedy approximationJournal of Approximation Theory, 2007
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear EquationsJournal of Computer and System Sciences, 1997
- Adaptive greedy approximationsConstructive Approximation, 1997