Approximate Sparse Recovery: Optimizing Time and Measurements

DOI10.1137/100816705zbMath1259.94024arXiv0912.0229OpenAlexW1994521750MaRDI QIDQ2903525

Yi Li, Ely Porat, Anna C. Gilbert, Martin J. Strauss

Publication date: 10 August 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

sparse approximationsublinear algorithmrandomized approximation schemeapproximate sparse recovery

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25) Randomized algorithms (68W20) Decoding (94B35)

Related Items (7)

Unnamed Item ⋮ Improved Algorithms for Adaptive Compressed Sensing ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Deterministic Heavy Hitters with Sublinear Query Time ⋮ On Low-Risk Heavy Hitters and Sparse Recovery Schemes ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ What's the frequency, Kenneth?: sublinear Fourier sampling off the grid

This page was built for publication: Approximate Sparse Recovery: Optimizing Time and Measurements