RTRMC : Low-rank matrix completion via preconditioned optimization on
the Grassmann manifold
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 preconditioned optimization on the Grassmann
manifold, in Linear Algebra and its Applications, 2015.
This version includes a preconditioner for RTRMC and adds Riemannian
conjugate gradients support, thanks to the Manopt
As a consequence, the code changed significantly: please see below to
download version 3.1 of RTRMC and RCGMC (released Oct. 15, 2014).
This version of the algorithms is also described in Nicolas
Boumal's PhD thesis.
The abstract of the extended paper
|We address the numerical problem of recovering large matrices of low rank
when most of the entries are unknown. We exploit the geometry of the low-rank constraint
to recast the problem as an unconstrained optimization problem on a
single Grassmann manifold. We then apply second-order Riemannian
trust-region methods (RTRMC 2) and Riemannian conjugate gradient
methods (RCGMC) to solve it. A preconditioner
for the Hessian is introduced that helps control the
conditioning of the problem and we detail preconditioned versions of
algorithms. The cost of each iteration is linear in the number of
known entries. The proposed methods are competitive with
state-of-the-art algorithms on a wide range of problem instances. In
particular, they perform well on
rectangular matrices. We further note that second-order and
preconditioned methods are well
suited to solve badly conditioned matrix completion tasks.
Here is the Matlab code for RTRMC v3.1
under BSD licence.
This version of the code was put online on October 15, 2014. It changed
significantly since version 1.1 and now uses Manopt.
Changes since version 2: now bundled with Manopt 1.0.5 instead of 1.0.4, and
the buildproblem function now allows the data I, J, X, C to be given in any
Changes since version 3: a bug prevented the code from working when
the weights Cij were not all the same. This
was corrected by patching spbuildmatrix.c.
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.
- Ideally, download the latest version of Manopt,
to be used instead of the version bundled in the zip-file above.
|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 regularization 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
completion-related 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: March 6, 2015