Compressive Sensing: What Class of Signals Are Exactly Model Sparse?

Question

In traditional compressed sensing, one would require $ m = O ( K.logN)$ measurements to recover a signal of size $N$, and sparsity $K$.

The paper, Richard Baraniuk - Model Based Compressive Sensing, shows that it is actually possible to get rid of the $log N$ factor in the number of sampled measurements, provided the $K$-sparse signals follow some additional characteristics. In traditional CS, in general, a $K$-sparse signal ( or a $K$-compressible one) lives on (or near) one of the canonical $K$-dimensional subspace of the basis of measurement. In model sparse signals, the additional requirement is that only a subset of these subspaces are allowed. These subspaces are such that they obey some well-formed characteristic. For instance, a Tree-sparse signal is one for which the top wavelet coefficients are to form a connected and rooted subtree in a wavelet tree decomposition.

I have to admit that I am still trying to understand their paper, so it may be a bit naive to ask it, but here is the question.

What sort of signals can one represent with these tree-sparse forms? The above paper gives a few sample signals to that effect. But is there a general characterization of these signals? For example, consider a signal comprising of, say $O(N/d)$ gaussians, with peaks randomly located among the N points ( $d < N$ is a constant in this case). Can this be represented/approximated by one of these Tree-sparse models?

Any general pointer to literature that studied these objects?

Answer 1

In the case of general Compressed Sensing, we assume that we have no prior information about the location of the sparse support of a given signal. If we knew the support exactly, that is, if an oracle told us where the non-zero coefficients are located, we would only need $K$ measurements to recover our signal accurately. Since we do not generally have such a genie, we require more measurements to both determine both the support and the signal values on that support, hence $M$ on the order of $O(K \operatorname{log}N)$.

The authors in the Model-Based Compressed Sensing technique make the observation that if an a priori assumption can be made about the location of signal support, fewer measurements are required (since we know more about the support, statistically, we need to deduce less information from our measurements).

When a signal obeys a tree-structured, or hierarchical, model for its support, we have an easy way of predicting the support. This knowledge allows us to lower the number of required measurements for accurate reconstruction. This kind of model is very common since many classes of interesting natural signals can be represented compactly using Wavelets. The multiresolution nature of wavelet analysis groups significant (i.e. non-zero) coefficients into a tree-structure: significant coefficients at one resolution scale are highly correlated with spatially co-located coefficients in neighboring resolution scales.

(from: http://www.dominikdeak.com/coding/wavelet-compression/figure_17.png)

In the example you give about a mixture of Gaussians, it is not immediately clear that Model-Based CS can be used, since, as you say, the parameters (the peaks) of these Gaussians are randomly distributed within the signal. This kind of signal can be sparsely-represented (pretty much ideally) with some redundant dictionary of Gaussians of different parameters. The sparse support when represented within this dictionary would not necessarily obey any kind of model, the measurements alone would be needed to determine the support (Gaussian parameters).

On the topic of Compressed Sensing recovery of Gaussian Mixture Models, I ran a quick google search and came up with the following on arXiv:

Yu and Sapiro, "Statistical Compressed Sensing of Gaussian Mixture Models."