Talks
Fall 2018
Adaptive Sparse Recovery with Limited Adaptivity
Tuesday, November 27th, 2018, 10:20 am–11:00 am
Speaker:
Eric Price (University of Texas at Austin)
In sparse recovery/compressed sensing, one can estimate a k-sparse vector in n dimensions with only Theta(k log n) nonadaptive linear measurements. With adaptivity -- if each measurement can be based on the previous ones -- this reduces to O(k log log n). But what happens if the measurement matrices can only be chosen in a few rounds, as seen (for example) in constant-pass streaming algorithms? This talk will give upper and lower bounds, showing (up to a log^* k factor) that R rounds of adaptivity require Theta(k log^{1/R} n) measurements.
Attachment | Size |
---|---|
Adaptive Sparse Recovery with Limited Adaptivity | 1.31 MB |