(1 + eps)-Approximate Sparse Recovery

DOI10.1109/FOCS.2011.92MaRDI QIDQ5495019zbMATH OpenOpenAlexFDO

Authors Eric Price, David P. Woodruff

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.92

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sampling theory in information and communication theory (94A20)

Cited in

(9)

• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Sparse recovery with partial support knowledge
• Fast sketch-based recovery of correlation outliers
• Taylor polynomial estimator for estimating frequency moments
• Improved algorithms for adaptive compressed sensing
• On low-risk heavy hitters and sparse recovery schemes
• Deterministic sparse Fourier transform with an _ guarantee
• A combinatorial approach to robust PCA
• Fixed-sparsity matrix approximation from matrix-vector products

This page was built for publication: (1 + eps)-Approximate Sparse Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495019)