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

In this paper Richard Baraniuk and his co-authors show 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? – MimSaad May 5 '17 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)$.