Iterative Estimation of Constrained Rank-One Matrices in Noise (implementation)

So the Approximate Message Passing algorithm is taking over the world, slowly but surely (thank you Emtiyaz for the tutorial report of Arian Maleki's thesis) . Here is an implementation for Low Rank factorization using the GAMP package, hence this is a paper with an implementation: Iterative Estimation of Constrained Rank-One Matrices in Noise by Sundeep Rangan, Alyson Fletcher. The abstract reads:

We consider the problem of estimating a rank-one matrix in Gaussian noise under a probabilistic model for the left and right factors of the matrix. The probabilistic model can impose constraints on the factors including sparsity and positivity that arise commonly in learning problems. We propose a simple iterative procedure that reduces the problem to a sequence of scalar estimation computations. The method is similar to approximate message passing techniques based on Gaussian approximations of loopy belief propagation that have been used recently in compressed sensing. Leveraging analysis methods by Bayati and Montanari, we show that the asymptotic behavior of the estimates from the proposed iterative procedure is described by a simple scalar equivalent model, where the distribution of the estimates is identical to certain scalar estimates of the variables in Gaussian noise. Moreover, the effective Gaussian noise level is described by a set of state evolution equations. The proposed method thus provides a computationally simple and general method for rank-one estimation problems with a precise analysis in certain high-dimensional settings.

Let us not forget that while rank-1 matrices seem to be a small problem it is at the heart of some optics problems with quadratic compressed sensing. (pdf is here)From the GAMP Package site:

Uses the GAMP package for rank one matrix factorization. The paper shows that you can obtain an exact state evolution analysis for predicting the GAMP performance. In the future, we hope to extend this to higher ranks.

Code is in the directory gampmatlab\trunk\code\matrixFactor. 

Image Credit: NASA/JPL/Space Science Institute
W00074018.jpg was taken on April 23, 2012 and received on Earth April 24, 2012. The camera was pointing toward SATURN-ERING at approximately 2,837,370 kilometers away, and the image was taken using the CL1 and CL2 filters. 

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.