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
The associated paper is available here:
N. Boumal and P.-A. Absil, RTRMC : A Riemannian
trust-region method for low-rank matrix completion,
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, submitted.
The abstract of the extended paper
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 that exploits
geometry of the low-rank constraint to recast the problem as an
unconstrained optimization problem on the Grassmann manifold.
then apply first- and second-order Riemannian trust-region methods
solve it. The cost of each iteration is linear in the number of
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
|Figure 2: Evolution
of the Root Mean Square Error for
six matrix completion methods under Scenario 2 of the RTRMC paper
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
space in min(m,n),
whereas for most methods the growth is linear in m+n.
Here is the Matlab code
for RTRMC v1.1 under BSD
To install and use the
- Unzip the archive on your disk and launch the script TestRTRMC.m.
- If this works, you're done.
- If this fails, then the C-Mex codes probably need to be
compiled for your platform:
- Edit the script installrtrmc.m
and set the flag I_launched_TestRTRMC_and_it_failed
- Launch the script installrtrmc.m.
- Launch the script TestRTRMC.m
- Use the functions in buildproblem.m,
as shown in TestRTRMC.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
written for Windows users, but has been found to work as is on a
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: April 15, 2013