Warning info in Manopt with fixedrankfactory_2factors_preconditioned factory

[lineya...@gmail.com]

Hi all,

I found a strange warning infos when I use the fixedrankfactory_2factors_preconditioned factory on Windows 10 workstation. Here are the warning info:

The cost function returned NaN (perhaps the retraction returned a bad point?) rho is NaN! Forcing a radius decrease. This should not happen.

I'm using trustregion algorithm, and this info keeps printing on my command window (in some settings) and makes my program very slow.  Would you please tell me what I can do for this problem? Thanks very much.

Kai

[Nicolas Boumal]

Hello,

This error message indicates the cost function returned NaN, which Manopt doesn't know how to handle.

This typically comes from one of two sources:

 1) The cost function itself has issues (division by zero? inverting singular matrices?)

 2) The cost function received as input an improper point x. This can happen if the retraction produced such a bad point.

The latter shouldn't happen of course, but in the case of fixed-rank geometries (here, fixedrankfactory_2factors_preconditioned), a common cause is this: if the manifold is setup to work with matrices of rank k (exactly), and the solver converges to a matrix of rank < k (strictly), then singular matrices may come up in retractions, resulting in NaN's.

Two easy fixes:

 a) Reduce k so that the solver will converge to a matrix of rank exactly k and not lower. (In certain applications, this is never an issue because the actual target matrix is close to low rank but actually full rank.)

 b) Work with matrices of rank <= k instead of = k. This can be done, for example, by working with a productmanifold of euclideanfactory such that X = U*V', with U and V both living in a euclidean space. This simple minded approach can pose issues of its own though. Another possibility is to fix U in stiefelfactory and allow V to be free in euclideanfactory.

I hope this makes sense (the last part is admittedly a bit more technical.)

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Thanks very much for your fime. However in my problem, the solution is exactly rank k (I generate it with the product of two gaussian random matrices of size M×k and k× M) without adding any noise. That's very strange.  I guessed it may be because of the preconditioning, then I replace it with "fixedrankfactory_2factors" factory. However, another error in matlab says 

Error using lyap (line 35)

The input arguments of the "lyap" command cannot have Inf or NaN entries.

Error in fixedrankfactory_2factors/projection (line 125)

        Omega = lyap(SS, SS,-AS);

Error in fixedrankfactory_2factors/ehess2rhess (line 115)

        Hess = M.proj(X, Hess);

Error in getHessian (line 84)

        hess = problem.M.ehess2rhess(x, egrad, ehess, d);

Error in tCG (line 145)

    Hdelta = getHessian(problem, x, delta, storedb, key);

Error in trustregions (line 470)

                tCG(problem, x, fgradx, eta, Delta, options, storedb, key);

Error in ranking_fixedrankTR_nonreg (line 98)

       [Xcg, xcost, info, options] = trustregions(problem, X0, options);

How can it happen just out of sudden in some iteration of trust region? Thanks very much.

Kai

[Nicolas Boumal]

Hello Kai,

Can you please add this line of code at the end of your cost function, your gradient function and your hessian function:

assert(~any(isnan(Z(:))), 'assert #');

assert(~any(isinf(Z(:))), 'assert #');

where Z is the output and replace # with something so you can identify which assert failed (although Matlab's debugger will tell you.)

This should help identify where NaN's or Inf's appear. From the looks of it, the issue is in problem.ehess.

If not, then please go into the factory file and place similar tests in the projection and retraction functions, to see where things go wrong. Apparently, lyap in M.projection receives ill-formed inputs.

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Thanks a lot!   And I found that it was caused by my hessian matrix, which in some cases return nan because of numerical problems. Very appreciate for your kindness and your time!  And I'd like to ask a question about the fixed_rank_2factors (or _preconditioned). In your paper and tutorial and what your refers to, it says they are used for "fixed rank", i.e. rank(X) is exactly k. Since matrix X=UV^T where U and V are M×k and N×k matrix, why wouldn't it be rank(X)<=k?  Could you please give me some details or references?  Thanks

Kai

[Nicolas Boumal]

Hello Kai,

I'm glad this worked out.

About your question: "Since matrix X=UV^T where U and V are M×k and N×k matrix, why wouldn't it be rank(X)<=k?"

UV^T could indeed have rank < k, no doubt about it. But the Riemannian geometry relies on both U and V being full rank, so that UV^T has maximal rank, equal to k here.

What does it mean that the Riemannian geometry relies on that? Two views:

 * A practical view: if you take a look at the inner product in the fixed-rank 2 factors manifold, it involves solving a linear system with U'U and V'V (which there are called L'L and R'R) : if either is rank deficient, we get in trouble immediately.

 * A more geometric view: the geometry is a quotient geometry, where we take into account the fact that UV' = (UQ) (VQ)' for any Q orthogonal. So pairs (U, V) are deemed equivalent to (UQ, VQ) and they are all "lumped" together in a set, called an equivalence class. The set of all equivalence classes (which is then one-to-one with fixed rank matrices) is called the quotient space. Now, as long as U and V have full rank, all these equivalence classes have the same dimension. But think about what happens if, say, the last column of U and V is all zeros; then we can still pick any orthogonal Q of size kxk we want, but a lot of them will have no effect (or the same effect) when computing UQ and VQ; so in practice the equivalence class will have lower dimension. The set of equivalence classes doesn't have a nice geometry if the equivalence classes do not have the same dimension. This is what I mean by: the Riemannian geometry relies on U, V being full rank.

Now what is the fix if you really want to work with rank <= k? Simple: don't quotient out the equivalence. That may require a different kind of care, but an easy start is with a product manifold as I hinted above.

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Thanks very much. You did help me a lot. Would you mind give me some references about how to develop a algorithm on product manifold?  And I found that log function cannot be handled by manopt, are there any solutions to it?

It's like  y = f(X) + log(AX-B).  If I use checkgradient it says that 

"Warning: Exponential for fixed rank manifold not implemented yet. Used retraction instead. "

Best,

Kai

[Nicolas Boumal]

Hello,

About using productmanifold, I recommend you check out the Truncated SVD example.

About the warning: no worries. It's not important for checking gradients. This should not be related to your use of the log (but I am unsure where that log you mentioned is used.)

Best,

Nicolas

[lineya...@gmail.com]

Hi,

Actually I use log function in the objective function, which is used to replace (represent) the infinite norm (largest element). In my original problem there is a infinite norm constraint, so I try to add it into the objective function as a regularization term. Since infinite norm is non-smooth which can't be used directly for manifold optimization, I thought about using the log barrier function as the surrogate for infinite norm,  i.e.  -sum(log(t-X)) - sum(log(t+X)).  I'm very sorry that I'm not familiar with this kind of smoothing approach. do you have any better idea than this?  Or if there are any problems for my surrogate?  I'll appreciate it very much if you have any references or suggestions for smoothing L infinite norm.

Best,

Kai Yang

[Nicolas Boumal]

Hello,

The classical smoothing for the infinity norm is the log-sum-exp approximation. You can read more about it here:

https://hips.seas.harvard.edu/blog/2013/01/09/computing-log-sum-exp/

Note that there may be some confusion in terms here: what Manopt calls log and exp are geometric notions of log and exp; they have (in this case at least) little to do with the fact that you may use Matlab's log/exp in your cost function.

Best of luck,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Thanks very much! I also notice that some may use log_sum_exp(X^2) for approximation (but I didn't find the original sources or related analysis). What do you mean by that Manopt's have little to do with matlab log/exp?  Did you mean if I use directly  log(sum(exp(X))) it wouldn't output what I expect in the Matlab?  Would you please give me more hints?

Best,

Kai

[Nicolas Boumal]

Hello,

I simply mean that, while they are the same words, log and exp used internally in Manopt are very different from log and exp in their common meaning (and as meant in Matlab's built-in functions). You can use log and exp (and logm and expm) in cost functions and their derivatives in the usual meaning of the term without issues.

Best,

Nicolas

[Behnam M]

Hi There, 

I am using specialeuclideanfactory(3) as the manifold and trustregion as the solver, I have the similar warning, could you please tell me I can fix it?!

Cheers

[Nicolas Boumal]

Hello,

Did you consider the suggestions from my two posts from Sep 27, 2016, on this thread?

Mainly, I would recommend you add code to check whether the point x that problem.cost receives has any NaN's in it, using assert(~any(isnan([x.R(:), x.t ])) and also checking that the value you return is ~isnan(value) and ~isinf(value).

If that doesn't work, could you please also show the code for your cost function (and possibly gradient and Hessian)?

Best,

Nicolas