Warning: Matrix is close to singular or badly scaled.

[lineya...@gmail.com]

Hi,
recently when I try to use this powerful tool to solve fixed rank matrix completion problems, a strange problem comes to me. If the matrix to be completed (denoted by X) and some fixed rank r is input, I expect it to output a local optimum. If this problem is feasible (cost is low enough) under the first rank r0, I find there are chances that it becomes infeasible under another larger rank r>r0, which can be explained by the nonconvexity of this problem.

However, in this case a warning named "Matrix is close to singular or badly scaled. Results may be inaccurate" shows up and the result may be badly inaccurate (cost becomes much larger while I expect it to be very low). I'm not sure it's a bug or I have missed something. Do you know how to solve it? A lot of thanks.

[BM]

Hello, 

Thanks for the interest in the toolbox. 

By the way, which manifold factory are you using? This will allow us understand the problem better.

Regards,

Bamdev

[lineya...@gmail.com]

Hi BM,
I'm using the fixed rank factory. The function is named as `fixedrankfactory_2factors_preconditioned'. Thanks a lot.

Best,
KY

[BM]

Thanks. 

In this case, it seems that L'L and R'R are becoming rank deficient. What is the gradient norm when this happens?

Have you tried regularization? 

Regards,

Bamdev

[Nicolas Boumal]

The issue is that the set of fixed rank matrices (be they psd or not) is an open set.

Say M is the set of matrices of rank exactly r.

If you optimize f over M but the true optimum of f actually has rank strictly less than r, then the sequence of iterates will tend to that lower rank matrix, which means it "wants to leave the manifold" and things break down.

Practically, what happens is that you represent the rank r matrix as LR', with L and R having r columns. If LR' get closer and closer (as you iterate) to a matrix of rank less than r, then either L or R (or both) must become close to rank deficient. This will translate into L'L and/or R'R being close to singular.

So how do you fix it?

One way is to pick r such that the optimum has rank r (or more): then, there is no incentive to get close to the open boundary and we stay away from singularity.

Another way is to regularize f, to favor rank r matrices. One way to do this is explained here:

http://www.unige.ch/math/vandereycken/bibtexbrowser.php?key=Vandereycken_2013&bib=my_pubs.bib

Low-rank matrix completion by Riemannian optimization

by B. Vandereycken

See section 4.

This paper is built with the geometry here: fixedrankembeddedfactory

but it can be adapted to other geometries as well: it's just an extra term in the cost function.

Best,

Nicolas

[lineya...@gmail.com]

Great, BM and Nicolas! Since I'm still not very familiar with the toolbox, I'll need some time to check if it is the case that you said. I'll let you know as soon as possible if I have some new results of this. A lot of thanks for both of you!