RTRMC: Exploiting manifolds' smoothness in Low Rank problems

Not all low rank approaches rely on an L_1 or L_0 regularization, here is a new and competitive example relying on smooth manifolds by Nicolas Boumal and Pierre-Antoine Absil that will be presented at NIPS (see yesterday's  entry for the workshop on Sparse Representation and Low-rank Approximation): RTRMC : A Riemannian trust-region method for low-rank matrix completion by Nicolas Boumal and Pierre-Antoine Absil. The abstract reads:

We consider large matrices of low rank. We address the problem of recovering such matrices when most of the entries are unknown. Matrix completion finds applications in recommender systems. In this setting, the rows of the matrix may correspond to items and the columns may correspond to users. The known entries are the ratings given by users to some items. The aim is to predict the unobserved ratings. This problem is commonly stated in a constrained optimization framework. We follow an approach that exploits the geometry of the low-rank constraint to recast the problem as an unconstrained optimization problem on the Grassmann manifold. We then apply first- and second-order Riemannian trust-region methods to solve it. The cost of each iteration is linear in the number of known entries. Our methods, RTRMC 1 and 2, outperform state-of-the-art algorithms on a wide range of problem instances.

The matlab implementation of this code is here.It is obviously also listed in the Matrix Factorization Jungle page. 

Several presentations relevant to this way of using Grassmanian manifold smoothness to perform this rank minimization:

• Low-rank matrix completion: optimization on manifolds at work,
• A Riemannian trust-region method for low-rank matrix completion,
• Low-rank matrix completion: optimization on manifolds at work,
• Low-rank matrix completion for recommender systems: optimization on manifolds at work, 
• Discrete curve fitting on manifolds,

I note a connection to BSS in images, refining Sparse PCA and a book and the use of another software package GenRTR, from its webpage:

GenRTR is the Generic Riemannian Trust-Region package. GenRTR is a MATLAB package for the optimization of functions defined on Riemannian manifolds. GenRTR currently provides two Riemannian trust-region methods:

• the Riemannian Trust-Region (RTR) method (more info)

• the Implicit Riemannian Trust-Region (IRTR) method (more info)

While the current emphasis concerns trust-region methods, the framework is suitable for the implementation of any retraction-based optimization method. Future plans involve the expansion of the framework to other optimization methods.

Finally, let us recall that one of the goals of compressive sensing is to perform signal processing on manifolds without performing reconstruction. 

Thank you Laurent for the heads-up.



Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from