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 aﬃne 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 ﬁnd 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 eﬃcient 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 deﬁning 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 eﬃcient 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.