RTRMC : A Riemannian Trust-Region method for low-rank Matrix Completion
RTRMC is an algorithm developed by Nicolas
Boumal (contact person) and Pierre-Antoine
Absil at UCLouvain to solve low-rank matrix completion problems.
The associated paper is available here:
N. Boumal and P.-A. Absil, RTRMC : A Riemannian trust-region method for
low-rank matrix completion, NIPS 2011,
with a corresponding BibTex entry.
An extended version of the paper, with more detailed mathematical
developments and numerical experiments, is available too:
N. Boumal and P.-A. Absil, Low-rank matrix completion via trust-regions
on the Grassmann manifold.
Since then, we developed a preconditioner for RTRMC and added
Riemannian conjugate gradients support, thanks to the Manopt toolbox.
As a consequence, the code changed significantly: please see below to
download version 2.0 of RTRMC and RCGMC.
This version of the algorithms is described in Nicolas Boumal's PhD
thesis. See his web page for a copy (soon to be available).
The abstract of the extended paper
|We consider large matrices of low
rank. We address the mathematical problem of recovering such
matrices when most of the entries are unknown. We follow an approach
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. The proposed methods, RTRMC 1 and 2,
outperform state-of-the-art algorithms on a wide range of problem
instances. In particular, RTRMC
performs very well on rectangular matrices and we note that
second-order methods such as RTRMC 2 are well
suited to solve badly conditioned or nonuniformly sampled matrix
Here is a plot of one of the experiments, where different matrix completion
algorithms compete on rectangular matrices of size 1000-by-30000:
|Figure 2: Evolution of the Root
Mean Square Error for six matrix completion methods under Scenario
2 of the RTRMC paper (m = 1000, n = 30000, rank = 5, sampling
ratio = 2.6%). For rectangular matrices, RTRMC is especially
efficient owing to the linear growth of the dimension of the
search space in min(m,n),
whereas for most methods the growth is linear in m+n.
Here is the Matlab code for RTRMC v2.0
under BSD licence.
This version of the code was put online on Nov. 18, 2013. It changed
significantly since version 1.1 and now uses Manopt.
To install and use the software:
- Unzip the archive on your disk and launch the script main.m.
- If this works, you're done.
- If this fails, then the C-Mex codes probably need to be compiled for
- Edit the script installrtrmc.m
and set the flag I_launched_main_and_it_failed
- Launch the script installrtrmc.m.
- Launch the script main.m
- Use the functions in buildproblem.m,
initialguess.m and rtrmc.m
as shown in main.m to apply
RTRMC to your problem instances.
|If this procedure
fails (quite probably somewhere in the installrtrmc.m
script), then either there is trouble with the C compiler Matlab
tries to use, which you can check by typing 'mex -setup' at the
Matlab prompt, or the installation script is incompatible with your
OS (it was written for Windows users, but has been found to work as
is on a MacOS and a Linux computer). If you need help, please feel
free to contact us. If you successfully ran installrtrmc.m
on your computer, we'd love to know about any, if any, difficulties
you may have resolved.
If you get this error:
??? Error using ==> spbuildmatrix
then try to raise the value of lambda (the regularisation parameter). This
error triggers when the least-squares problem (the computation of WU)
does not have a unique solution, so that one of the diagonal blocks of the
large matrix A does not have a proper Cholesky factorization.
dpotrf (in spbuildmatrix): a leading minor is not positive definite.
Error in ==> lsqfit>buildmatrix at 132
Achol = spbuildmatrix(problem.mask, U, lambda^2);
Error in ==> lsqfit at 65
Error in ==> rtrmcobjective at 66
[W compumem] = lsqfit(problem,
Raghunandan Keshavan, co-author of OptSpace, maintains an interesting web
page listing matrix
papers and software.
The blog Nuit-Blanche
featured a post about RTRMC on Sept. 12, 2011. The Matrix
Factorization Jungle is another list of related software.
Last update: November 18, 2013