Lower Bounds for Adaptive Sparse Recovery

DOI10.1137/1.9781611973105.47zbMath1423.94023arXiv1205.3518OpenAlexW2952501021MaRDI QIDQ5741755

David P. Woodruff, Eric Price

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (4)

Improved Algorithms for Adaptive Compressed Sensing ⋮ Performance Guarantees for Adaptive Estimation of Sparse Signals ⋮ Randomized approximation of summable sequences -- adaptive and non-adaptive ⋮ Querying a Matrix Through Matrix-Vector Products.

This page was built for publication: Lower Bounds for Adaptive Sparse Recovery