Compressed Sensing: Better Reweighted L1 with Hidden Markov Trees when using Wavelets and Choosing a wavelet should be an afterthought

We covered the release of Wavelet-Domain Compressive Signal Reconstruction Using a Hidden Markov Tree Model by Marco Duarte, Michael Wakin and Richard Baraniuk before. We now also have the slides presented at ICASSP. To recall the abstract:

Compressive sensing aims to recover a sparse or compressible signal froma small set of projections onto random vectors; conventional solutions involve linear programming or greedy algorithms that can be computationally expensive. Moreover, these recovery techniques are generic and assume no particular structure in the signal aside from sparsity. In this paper, we propose a new algorithm that enables fast recovery of piecewise smooth signals, a large and useful class of signals whose sparse wavelet expansions feature a distinct “connected tree” structure. Our algorithm fuses recent results on iterative reweighted ℓ1-norm minimization with the wavelet Hidden Markov Tree model. The resulting optimization-based solver outperforms the standard compressive recovery algorithms as well as previously proposed wavelet-based recovery algorithms. As a bonus, the algorithm reduces the number of measurements necessary to achieve low-distortion reconstruction.

We have already seen that tree-based techniques were likely to yield improvements in reconstruction methods dealing with wavelet coefficients. In visual term this technique allows the coefficients being used in the reweighted L1 algorithm

to be modified so that it would weigh contingent on belonging to the right part of the tree.


Obviously, the reweighted lp algorithm could use a similar argument to speed things up.

A long presentation that parallels the tutorial presentation at ITA'08 was presented at ICASSP as well. It is entitled Compressive sensing - Theory and applications by Petros Boufounos, Justin Romberg and Richard Baraniuk. It is a nice tutorial that goes a little deeper than the ITA presentation if I recall. I think this is first time I see in not so many words that choosing a wavelet basis (out of many) should be an afterthought i.e. it should not be the driver for the requirements on designing hardware. This is new as the main worry in the wavelet community has always been to be extremely cautious on the type of wavelet family to choose because "a better one might still be around" especially with the lifting schemes. Compressed Sensing settles that argument.