  It is known that certain structures of the signal in addition to the standard
notion of sparsity (called structured sparsity) can improve the sample
complexity in several compressive sensing applications. Recently, Hegde et al.
proposed a framework, called approximation-tolerant model-based compressive
sensing, for recovering signals with structured sparsity. Their framework
requires two oracles, the head- and the tail-approximation projection oracles.
The two oracles should return approximate solutions in the model which is
closest to the query signal. In this paper, we consider two structured sparsity
models and obtain improved projection algorithms. The first one is the tree
sparsity model, which captures the support structure in the wavelet
decomposition of piecewise-smooth signals. We propose a linear time
$(1-\epsilon)$-approximation algorithm for head-approximation projection and a
linear time $(1+\epsilon)$-approximation algorithm for tail-approximation
projection. The best previous result is an $\tilde{O}(n\log n)$ time
bicriterion approximation algorithm (meaning that their algorithm may return a
solution of sparsity larger than $k$) by Hegde et al. Our result provides an
affirmative answer to the open problem mentioned in the survey of Hegde and
Indyk. As a corollary, we can recover a constant approximate $k$-sparse signal.
The other is the Constrained Earth Mover Distance (CEMD) model, which is useful
to model the situation where the positions of the nonzero coefficients of a
signal do not change significantly as a function of spatial (or temporal)
locations. We obtain the first single criterion constant factor approximation
algorithm for the head-approximation projection. The previous best known
algorithm is a bicriterion approximation. Using this result, we can get a
faster constant approximation algorithm with fewer measurements for the
recovery problem in CEMD model.
