CS: ALPS, Reconstructions from Compressive Random Projections of Hyperspectral Imagery

If you have been wondering about the effect of multiplicative noise on the Donoho-Tanner transition, you might be interested in the following installments: Part 1, 2, 3, 4, 5.

Volkan Cevher just sent me the following:

Hi Igor,
Hope you are doing fine.... It took a while but my lab page is online. We are now posting our codes:

http://lions.epfl.ch/software

In particular, simple sparse recovery based on algebraic pursuits are here

http://lions.epfl.ch/ALPS

There will be more to come (e.g., the game theoretic CS recovery codes, structured sparsity recovery ...)
best,
Volkan

Thanks Volkan !

ALPS: accerelated IHT methods for sparse recovery

ALPS (ALgebraic PursuitS) is a software package that implements the accelerated Iterative Hard Thresholding schemes presented in ''On Accelerated Hard Thresholding Methods for Sparse Approximation'', Technical Report, by Volkan Cevher. ALPS can be used as a computational efficient tool to solve underdetermined linear regression problems.

Description
ALPS (ALgebraic PursuitS) is a MATLABimplementation of a series of accelerated Iterative Hard Thresholding (IHT) methods for sparse signal reconstruction from dimensionality reducing, linear measurements.
ALPS includes three accelerated IHT methods designed to solve the following sparse linear regression problem:

where u is the M-tupled real valued observation vector, A is the MxN real measurement matrix (M < N) and x is a K-sparse N-tuple vector signal.

Hard thresholding methods for sparse recovery

• 0-IHT(#) is a memoryless IHT algorithm that uses an adaptive step size selection rule.

• 1-IHT(#) employs memory for acceleration in addition to the adaptive step size selection. The algorithm uses a linear combination of past estimates during each iteration with a momentum term, which is automatically computed.

• infinity-IHT(#) uses a weighted sum of all the previously computed gradients during each iteration. The gradient weights are automatically calculated.

For all these schemes, we follow the naming convention [0,1,infinity]-IHT(#), as described in "On Accelerated Hard Thresholding Methods for Sparse Approximation", where (#) is the binary number generated by the following options: SolveNewtonb, GradientDescentx, and SolveNewtonx. Please see the paper for their description.

I'll add shortly to the compressive sensing reconstruction page. In the meantime, Jim Fowler sent me the following:

Hi Igor,

Just wanted to drop you a line and let you know of a book chapter that will be appearing in print shortly (it's already available in SpringerLink). The citation is:

J. E. Fowler and Q. Du, "Reconstructions from Compressive Random Projections of Hyperspectral Imagery," in Optical Remote Sensing: Advances in Signal Processing and Exploitation Techniques, S. Prasad, L. M. Bruce, and J. Chanussot, Eds. Springer, 2011, ch. 3, pp. 31-48.

Abstract:

High-dimensional data such as hyperspectral imagery is traditionally acquired in full dimensionality before being reduced in dimension prior to processing. Conventional dimensionality reduction on-board remote devices is often prohibitive due to limited computational resources; on the other hand, integrating random projections directly into signal acquisition offers an alternative to explicit dimensionality reduction without incurring sender-side computational cost. Receiver-side reconstruction of hyperspectral data from such random projections in the form of compressive-projection principal component analysis (CPPCA) as well as compressed sensing (CS) is investigated. Specifically considered are single-task CS algorithms which reconstruct each hyperspectral pixel vector of a dataset independently as well as multi-task CS in which the multiple, possibly correlated hyperspectral pixel vectors are reconstructed simultaneously. These CS strategies are compared to CPPCA reconstruction which also exploits cross-vector correlations. Experimental results on popular AVIRIS datasets reveal that CPPCA outperforms various CS algorithms in terms of both squared-error as well as spectral-angle quality measures while requiring only a fraction of the computational cost.

PDF at: http://www.ece.msstate.edu/~fowler/Publications/FD2011.html

Best Regards,

-Jim

Thanks Jim!

Credit photo:  NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, Two weeks ago, on January 14, 2008, MESSENGER became the first spacecraft to see the side of Mercury shown in this image. The first image transmitted back to Earth following the flyby of Mercury, and then released to the web within hours, shows the historic first look at the previously unseen side. This image, taken by the Wide Angle Camera (WAC) of the Mercury Dual Imaging System (MDIS), shows a closer view of much of that territory.