Additional structures for sparse recovery

Question

The problem of sparse recovery using $l_1$ minimization is well known. Using random Gaussian matrices, we are able to achieve recovery with high probability in $O(k\log(d/k)$ measurements. It is pretty natural to conjecture that with additional information about the sparsity pattern, one might be able to produce recovery with even lower number of measurements. Group sparsity, for instance, can be used to derive better bounds.

My question is, what are some common structures that people often impose on sparse signals? For instance, the support of some signals may tend to cluster at certain locations, or that the sparsity might follow a certain probability distribution.

Answer 1

Here is my 2cts (this is in no particular order):

1. L1 analysis -- That's a pretty straightforward thing, but interesting nonetheless
2. Tree sparse signals (see some work of Bubacarr Bah for instance) which might be required for certain wavelet decompositions for instance
3. Sparsity in fusion frames: only a small number of subspaces are activated
4. Non-negativity constraint: used for instance in metagenomic reconstruction
5. Sparse and low rank matrices: used typically in Netflix-like problems (note that it is not clear how to embed both information as part of the regularizer, even though one would expect better results)
6. Joint sparsity: similar to group sparsity in a sense. It improves only on the average case analysis, as the worst case scenario is just as bad as the single vector case. This is used, for instance, in generalized polynomial approximations of parametric PDEs in which the polynomial coefficients have similar sparsity patterns
7. Sparsity within fusion frames: allows to have local information which might be redundant in some other locations. This is important for distributed systems in which only partial information is available (think SAR images for instance)

You do not necessarily gain in the (theoretical) guarantees by adding information. In the case of sparsity within fusion frames, you may prove that the number of measurements per sensor decreases linearly with the number of sensors for instance.