# For-all Sparse Recovery in Near-Optimal Time

arXiv: https://arxiv.org/abs/1402.1726 · HTML: https://mlsanity.com/paper/1402.1726/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2014.

## Built on by (most cited first, 1 of 1)

- [Fast White-Box Adversarial Streaming Without a Random Oracle](https://mlsanity.com/paper/2406.06808/) (2024)

## Abstract (arXiv)

An approximate sparse recovery system in ℓ1 norm consists of parameters k, ε, N, an m-by-N measurement Phi, and a recovery algorithm, R. Given a vector, x, the system approximates x by widehatx = R(Phix), which must satisfy |widehatx-x|1 ≤ (1+ε)|x-xk|1. We consider the 'for all' model, in which a single matrix Phi, possibly 'constructed' non-explicitly using the probabilistic method, is used for all signals x. The best existing sublinear algorithm by Porat and Strauss (SODA'12) uses O(ε-3 klog(N/k)) measurements and runs in time O(k1-αNα) for any constant α > 0. In this paper, we improve the number of measurements to O(ε-2 k log(N/k)), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O(k1+βtextrmpoly(log N,1/ε)), with a modest restriction that ε ≤ (log k/log N)γ, for any constants β,γ > 0. When k≤ logc N for some c>0, the runtime is reduced to O(ktextrmpoly(N,1/ε)). With no restrictions on ε, we have an approximation recovery system with m = O(k/ε log(N/k)((log N/log k)γ + 1/ε)) measurements.