Lower bounds for sparse recovery problems

Sparse recovery or compressed sensing is the problem of estimating a signal from noisy linear measurements of that signal. Sparse recovery has traditionally been used in areas like image acquisition, streaming algorithms, genetic testing, and, more recently, for image recovery tasks.

Over the last decade many techniques have been developed for sparse recovery under various guarantees. We develop new lower bound techniques and show the tightness of existing results for the following variants of the sparse recovery problem: (i) adaptive sparse recovery, (ii) sparse recovery under high SNR, (iii) deterministic L2 heavy hitters, and, (iv) compressed sensing with generative models.