Tuesday, May 28, 2013

qGeomMC: A Quotient Geometric approach to low-rank Matrix Completion - implementation -

While searching for something else, I stumbled upon Bamdev Mishra's page and found this implementation featured in A Riemannian geometry for low-rank matrix completion by Bamdev Mishra, K. Adithya Apuroop, Rodolphe Sepulchre
We propose a new Riemannian geometry for fixed-rank matrices that is specifically tailored to the low-rank matrix completion problem. Exploiting the degree of freedom of a quotient space, we tune the metric on our search space to the particular least square cost function. At one level, it illustrates in a novel way how to exploit the versatile framework of optimization on quotient manifold. At another level, our algorithm can be considered as an improved version of LMaFit, the state-of-the-art Gauss-Seidel algorithm. We develop necessary tools needed to perform both first-order and second-order optimization. In particular, we propose gradient descent schemes (steepest descent and conjugate gradient) and trust-region algorithms. We also show that, thanks to the simplicity of the cost function, it is numerically cheap to perform an exact linesearch given a search direction, which makes our algorithms competitive with the state-of-the-art on standard low-rank matrix completion instances.

That implementation is available from this page:  qGeomMC: A Quotient Geometric approach to low-rank Matrix Completion

This package contains a MATLAB implementation of algorithms for the low-rank matrix completion problem. The present version includes gradient descent and conjugate gradient algorithms based on the fixed-rank geometry proposed in the techreport [arXiv:1211.1550]......

Bamdev Mishra also mentions the release of two other implementations:

Manopt comes with a large library of manifolds and ready-to-use Riemannian optimization algorithms. It is well documented and includes diagnostics tools to help you get started quickly and make sure you make no mistakes along the way. It is designed to provide great flexibility in describing your cost function and incorporates an optional caching system for more efficiency.
 Updated TraceNorm code to handle large scale matrices

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

No comments: