Lower Bounds for Sparse Recovery

zbMath1288.94015arXiv1106.0365MaRDI QIDQ5417699

Khanh do Ba, Eric Price, David P. Woodruff, Piotr Indyk

Publication date: 22 May 2014

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Fundamental barriers to high-dimensional regression with convex penalties, Tensor Regression Using Low-Rank and Sparse Tucker Decompositions, Taylor Polynomial Estimator for Estimating Frequency Moments, Sample Complexity Bounds on Differentially Private Learning via Communication Complexity, Improved Algorithms for Adaptive Compressed Sensing, On exact recovery of sparse vectors from linear measurements, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Bessel sequences of exponentials on fractal measures, Lower Bounds for Testing Computability by Small Width OBDDs, The nonnegative zero-norm minimization under generalized \(Z\)-matrix measurement, Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time, Sparse Recovery with Partial Support Knowledge, Everywhere-Tight Information Cost Tradeoffs for Augmented Index, Querying a Matrix Through Matrix-Vector Products., Unnamed Item