Nearly linear-time model-based compressive sensing

Compressive sensing is a method for recording a k-sparse signal x ∈ Rⁿ with (possibly noisy) linear measurements of the form y = Ax, where A ∈ R^{m × n} describes the measurement process. Seminal results in compressive sensing show that it is possible to recover the signal x from m = O(log n/k) measurements and that this is tight. The model-based compressive sensing framework overcomes this lower bound and reduces the number of measurements further to m = O(k). This improvement is achieved by limiting the supports of x to a structured sparsity model, which is a subset of all (_kⁿ) possible k-sparse supports. This approach has led to measurement-efficient recovery schemes for a variety of signal models, including tree-sparsity and block-sparsity. While model-based compressive sensing succeeds in reducing the number of measurements, the framework entails a computationally expensive recovery process. In particular, two main barriers arise: (i) Existing recovery algorithms involve several projections into the structured sparsity model. For several sparsity models (such as tree-sparsity), the best known model-projection algorithms run in time Ω(kn), which can be too slow for large k. (ii) Existing recovery algorithms involve several matrix-vector multiplications with the measurement matrix A. Unfortunately, the only known measurement matrices suitable for model-based compressive sensing require O(nk) time for a single multiplication, which can be (again) too slow for large k. In this paper, we remove both aforementioned barriers for two popular sparsity models and reduce the complexity of recovery to nearly linear time. Our main algorithmic result concerns the tree-sparsity model, for which we solve the model-projection problem in O(n logn + k log² n) time. We also construct a measurement matrix for model-based compressive sensing with matrix-vector multiplication in O(n logn) time for k ≤ n^1/2-μ, μ > 0. As an added bonus, the same matrix construction can also be used to give a fast recovery scheme for the block-sparsity model.