In an L-1 approximate sparse recovery system, given a vector, x, the system approximates x by R(Phi.x), which must satisfy ||R(Phi.x) - x|| <= (1 + epsilon)||x-opt - x||, in L-1 norm, where x-opt is the best possible k-term approximation to x.  In our "forall" model, a single matrix Phi is used for all signals x.  The best existing sublinear algorithm by Porat and Strauss (SODA’12) uses k*log(N/k)/epsilon^3 measurements and runs in time a little better than sqrt(kN).

In this paper, we improve the number of measurements to k*log(N/k)/epsilon^2, matching the best existing upper bound (attained by super-linear algorithms), and the runtime to poly(k, log(N), 1/epsilon), under the restriction that epsilon < log(k)/log(N).  (The full result, available in the paper, is slightly stronger.)