A note on reductions between compressed sensing guarantees

Tom Morgan, Jelani Nelson

In compressed sensing, one wishes to acquire an approximately sparse high-dimensional signal $x\in {\mathbb{R}}^n$ via $m\ll n$ noisy linear measurements, then later approximately rec…