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.

As a consequence, the code changed significantly: please see below to download version 3.0 of RTRMC and RCGMC (released March 7, 2014).

The abstract of the extended paper reads:

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 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. 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 completion tasks. |

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 v3.0 under BSD licence.

This version of the code was put online on March 7, 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 order.

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 your platform:
- Edit the script installrtrmc.m and set the flag I_launched_main_and_it_failed to true.
- Launch the script installrtrmc.m.
- Launch the script main.m once again.
- 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:

then try to raise the value of lambda (the regularisation parameter). This error triggers when the least-squares problem (the computation of W??? Error using ==> spbuildmatrix

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

compumem.Achol = buildmatrix(problem, U);

Error in ==> rtrmcobjective at 66

[W compumem] = lsqfit(problem, U, compumem);

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 7, 2014