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

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?

• It is a good question. Have you read and understand the papers? Can you answer your own question? May 5, 2017 at 16:13

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)$.