SODA Conference 2012 Conference Paper
Sublinear time, measurement-optimal, sparse recovery for all
- Ely Porat
- Martin J. Strauss
An approximate sparse recovery system in ℓ 1 norm makes a small number of measurements of a noisy vector with at most k large entries and recovers those heavy hitters approximately. Formally, it consists of parameters N, k, ∊, an m -by- N measurement matrix, Φ, and a decoding algorithm, D. Given a vector, x, where x k denotes the optimal k -term approximation to x, the system approximates x by, which must satisfy Among the goals in designing such systems are minimizing the number m of measurements and the runtime of the decoding algorithm, D. We consider the “forall” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x. Many previous papers have provided algorithms for this problem. But all such algorithms that use the optimal number m = O ( k log( N/k )) of measurements require superlinear time Ω ( N log( N/k )). In this paper, we give the first algorithm for this problem that uses the optimum number of measurements (up to constant factors) and runs in sublinear time o ( N ) when k is sufficiently less than N. Specifically, for any positive integer ℓ, our approach uses time O (ℓ 5 ∊ −3 k ( N/k ) 1/ℓ ) and uses m = O (ℓ 8 ∊ −3 k log ( N/k )) measurements, with access to a data structure requiring space and preprocessing time O (ℓ Nk 0. 2 /∊).