  We consider the extensively studied problem of $\ell_2/\ell_2$ compressed
sensing. The main contribution of our work is an improvement over [Gilbert, Li,
Porat and Strauss, STOC 2010] with faster decoding time and significantly
smaller column sparsity, answering two open questions of the aforementioned
work.
  Previous work on sublinear-time compressed sensing employed an iterative
procedure, recovering the heavy coordinates in phases. We completely depart
from that framework, and give the first sublinear-time $\ell_2/\ell_2$ scheme
which achieves the optimal number of measurements without iterating; this new
approach is the key step to our progress. Towards that, we satisfy the
$\ell_2/\ell_2$ guarantee by exploiting the heaviness of coordinates in a way
that was not exploited in previous work. Via our techniques we obtain improved
results for various sparse recovery tasks, and indicate possible further
applications to problems in the field, to which the aforementioned iterative
procedure creates significant obstructions.
