different behevaviors with and without Euclidean Hessian on rotationsfactory

[Ju Sun]

Dear Nicolas,

We're trying to minimize a quadratic function over the rotation group:

min <C, X.^2>

s.t. X is a rotation.

When implementing this with Manopt, we observed a curious thing: if the Euclidean Hessian is not provided, the iterate sequence converges to a critical point pretty rapidly. But if the analytic form of the Euclidean Hessian is provided, the sequence stagnates around certain noncritical points.

Are the very different behaviors normal? Besides possible inappropriate settings of Delta_0 and Delta_bar, are there other fundamental factors that account for this?  

Our code is attached.

Thanks,
Ju

[Nicolas Boumal]

Hello Ju,

Thanks for your question.

Sorry about the time you lost on this: it's the result of a poor design choice made years ago at the time of implementing rotationsfactory.

The short answer is: no, the behavior you observe is not normal; the issue is that the Hessian is incorrect.

The catch is as follows: when you define the Euclidean Hessian, you receive two inputs: X is the point on the manifold (an orthogonal matrix), and U is the representation of a tangent vector at X: here, U is a skew-symmetric matrix (representation in the Lie algebra), and the actual tangent vector is X*U.

In general, the transformation from the representation of a tangent vector to the corresponding vector in the ambient space is coded in problem.M.tangent2ambient(X, U); --- In this case, it's just X*U.

I'd like to embed a warning for this in the toolbox, but I haven't figured out a good way to produce that warning without undue warnings.

Concretely, you need only change one line (full code below for easier reference):

problem.ehess = @(X, U) 2*(C.*(X*U));   % X*U instead of U

You can verify it with checkhessian(problem), which will now pass all tests. Trust-regions is even a bit faster now.

As a side note: I'm sure you know this, but for your cost function, it's more efficient to replace

problem.cost  = @(X) trace(C'*(X.*X));

by

inner = @(A, B) A(:)'*B(:);

problem.cost  = @(X) inner(C, X.*X);

Best wishes,

Nicolas

====

n = 20;
C = randn(n);
 
% Create the problem structure.
manifold = rotationsfactory(n);
problem.M = manifold;
 
% Define the problem cost function and its Euclidean gradient.
C = sign(det(C))*C;
problem.cost  = @(X) trace(C'*(X.*X));
problem.egrad = @(X) 2*(C.*X);
problem.ehess = @(X, U) 2*(C.*(X*U));

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

====

[Ju Sun]

Hi Nicolas,

Thank you for the clarification!

I think I possibly have overlooked things, but it seems to me the online documentation on ehess doesn't emphasize the u should be the tangent space vector represented in the tangent space:

https://www.manopt.org/tutorial.html#costdescription

So do I only need to worry about this specifically for the rotation group, or for other manifolds as well?

I also experimented with the orthogonal group, with

manifold = stiefelfactory(n, n);

In this case, my naive implementation 
problem.ehess = @(X, U) 2*(C.*U)

seemed to do the right thing: the convergence behaviors are similar with or without the analytic Hessian and the hessian check is passed. 

PS: The latex codes on the rotation group page are not rendered 

https://www.manopt.org/manifold_documentation_rotations.html 


Best, 
Ju

--
http://www.manopt.org
---
You received this message because you are subscribed to a topic in the Google Groups "Manopt" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/manopttoolbox/jS65DgovYxg/unsubscribe.
To unsubscribe from this group and all its topics, send an email to manopttoolbo...@googlegroups.com.
Visit this group at https://groups.google.com/group/manopttoolbox.
To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/f0c0fc42-0486-4456-a42f-fa2d2244185f%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Nicolas Boumal]

Hello Ju,

Thanks for your further input on this.

You are right about the description of ehess on the tutorial page, it gave no heads up about this; I changed the description now. Thanks!

Of the top of my head, it is only rotationsfactory and its derivatives such as specialeuclideanfactory that have this peculiarity. The reason for this choice, originally, was that when you work with rotations, often times, the first thing you do to a tangent vector is to slide it back to the Lie algebra, so this felt a tad wasteful. Changing things now would unfortunately break older code, which is something we try to avoid.

Stiefel should work indeed, as you described: tangent2ambient is the identity map in this case.

Thanks for the PS: fixed now.

Best,

Nicolas

To unsubscribe from this group and all its topics, send an email to manopttoolbox+unsubscribe@googlegroups.com.

[Nicolas Boumal]

(Documentation on https://www.manopt.org/manifold_documentation_rotations.html was also edited further following this thread.)

[Nicolas Boumal]

Actually, fixedrankembeddedfactory also has this property.

I added a message in the call to checkhessian() that will appear every time one of those manifolds is used, to warn of the possible necessity to call M.tangent2ambient.

Thanks again for bringing this up!

Nicolas