Implementation: Iterative Reweighted Algorithms for Matrix Rank Minimization

Slowly but surely some of the vectorial examples that used to fit the compressed sensing framework are bound to cross over to rank minimization. Today, we have an example of that in Iterative Reweighted Algorithms for Matrix Rank Minimization by Karthik Mohan, Maryam Fazel. The abstract reads:

The problem of minimizing the rank of a matrix subject to affine constraints has many applications in machine learning, and is known to be NP-hard. One of the tractable relaxations proposed for this problem is nuclear norm (or trace norm) minimization of the matrix, which is guaranteed to find the minimum rank matrix under suitable assumptions. In this paper, we propose a family of Iterative Reweighted Least Squares algorithms IRLS-p (with 0 ≤ p ≤ 1), as a computationally efficient way to improve over the performance of nuclear norm minimization. The algorithms can be viewed as (locally) minimizing certain smooth approximations to the rank function. When p = 1, we give theoretical guarantees similar to those for nuclear norm minimization, i.e., recovery of low-rank matrices under certain assumptions on the operator defining the constraints. For p < 1, IRLS-p shows better empirical performance in terms of recovering low-rank matrices than nuclear norm minimization. We provide an efficient implementation for IRLS-p, and also present a related family of algorithms, sIRLS-p. These algorithms exhibit competitive run times and improved recovery when compared to existing algorithms for random instances of the matrix completion problem, as well as on the MovieLens movie recommendation data set

The attendant code implementing thie IRLS approach to rank minimization is here.


Image Credit: NASA/JPL-Caltech/Malin Space Science Systems 

This image was taken by Mastcam: Left (MAST_LEFT) onboard NASA's Mars rover Curiosity on Sol 39 (2012-09-15 03:26:04 UTC) . 

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.