Lower Bounds for Adaptive Sparse Recovery

Eric Price, David P. Woodruff

We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector $x\in {\mathbb{R}}^n$ from $m$ linea…