Sublinear Time, Approximate Model-based Sparse Recovery For All
arXiv:1203.4746
Abstract
We describe a probabilistic, {\it sublinear} runtime, measurement-optimal system for model-based sparse recovery problems through dimensionality reducing, {\em dense} random matrices. Specifically, we obtain a linear sketch of a vector $\bestsignal\in \R^N$ in high-dimensions through a matrix . We assume this vector can be well approximated by non-zero coefficients (i.e., it is -sparse). In addition, the nonzero coefficients of $\bestsignal$ can obey additional structure constraints such as matroid, totally unimodular, or knapsack constraints, which dub as model-based sparsity. We construct the dense measurement matrix using a probabilistic method so that it satisfies the so-called restricted isometry property in the -norm. While recovery using such matrices is measurement-optimal as they require the smallest sketch sizes $\numsam= O(\sparsity \log(\dimension/\sparsity))$, the existing algorithms require superlinear runtime with the exception of Porat and Strauss, which requires but provides an approximation guarantee. In contrast, our approach features $ O\big(\max \lbrace \sketch \sparsity \log^{O(1)} \dimension, ~\sketch \sparsity^2 \log^2 (\dimension/\sparsity) \rbrace\big) $ complexity where is a design parameter, independent of $\dimension$, requires a smaller sketch size, can accommodate model sparsity, and provides a stronger guarantee. Our system applies to "for all" sparse signals, is robust against bounded perturbations in as well as perturbations on $\bestsignal$ itself.
This paper has been drawn by the author due to a error in the derivation