Information Processing & Algorithm Laboratory

Spike and Slab priors have been of much recent interest in signal processing as a means of inducing sparsity in Bayesian inference. Applications domains that benefit from the use of these priors include sparse recovery, regression and classification. It is well-known that solving for the sparse coefficient vector to maximize these priors results in a hard non-convex and mixed integer programming problem. Most existing solutions to this optimization problem either involve simplifying assumptions/relaxations or are computationally expensive. We propose a new greedy and adaptive matching pursuit (AMP) algorithm to directly solve this hard problem. Essentially, in each step of the algorithm, the set of active elements would be updated by either adding or removing one index, whichever results in better improvement. In addition, the intermediate steps of the algorithm are calculated via an inexpensive Cholesky decomposition which makes the algorithm much faster. Results on simulated data sets as well as real-world image recovery challenges confirm the benefits of the proposed AMP, particularly in providing a superior cost-quality trade-off over existing alternatives.

This toolbox has been uploaded online for easy access to implementation of the following paper.

Please contact me for question regarding this toolbox.

The MATLAB code corresponding to our proposed algorithm can be downloaded here.

We perform one experiment with sparse data that is naturally non-negative and vary the sparsity level of $\mathbf{x}_0$ from 10 to 120 and compare the running time, MSE, optimal cost function and SM of different methods. Results are shown in Figure below. Similar trends can be seen in this figure where AMP requires less running time than ICR does while it consistently outperforms others in the remaining aspects. It is worth to mention that AMP and ICR obtain almost the identical cost which is better than what SpaRSA achieves.

We apply the different sparse recovery algorithms to real data for image reconstruction. We work with the well-known handwritten digit images MNIST. Since most of pixels in each image are inactive (0), each image is naturally sparse. The experiment is set up such that a vectorized sparse signal is to be reconstructed from a smaller set of random measurements. We randomly generate a Gaussian matrix. For each signal, we add a Gaussian noise. Clearly, AMP and ICR outperform other methods with slightly better but much faster results provided by AMP:

Tiep H. Vu, Hojjat S. Mousavi, Vishal Monga, "Adaptive matcing pursuit for sparse signal recovery." IEEE on International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2017. [pdf]. Finalist for the Best Student Paper Award.

Adaptive matching pursuit
for sparse signal recovery

AMP

Finalist for the Best Student Paper Award ICASSP 2017

ABSTRACT

AMP Toolbox

Software

Experimental Results

Image Recovery

Visualization of AMP

Related Publications

Adaptive matching pursuitfor sparse signal recovery

AMP