Optimization over Stiefel manifold

[Keyvan Aslansefat]

Hi all,

I am facing an optimization challenge concerning a problem defined on the Stiefel manifold. The objective function is represented as follows:

∥HTXdiag(d)XTG∥2

where X is a K×K optimization matrix, H and d are complex vectors, and G is a complex matrix.

Despite attempting to optimize this problem using conjugate gradient descent, I have encountered significant computational challenges. As the dimensionality K increases, such as K=100, the computation time becomes excessively long, rendering the problem practically unsolvable.

I am reaching out to inquire if anyone has encountered similar difficulties or has insights into more efficient optimization strategies for this problem.

Thank you for any assistance or advice you can provide.

[Nicolas Boumal]

Hello Keyvan,

Is that a Frobenius norm? (norm(X, 'fro') in Matlab)

Is H also a matrix?

That cost function doesn't look too bad in terms of computations. However, the actual computation time may depend largely on how you implement it and its gradient (and possibly Hessian). Moreover, the optimization algorithm may run but be very slow if the gradient / Hessian are incorrect.

Could you post your code for computing the cost and gradient here, and also post here the text produced by the command "checkgradient(problem)" (and also checkhessian(problem) if you defined the Hessian)?

Best,

Nicolas

[Keyvan Aslansefat]

Actually H is a complex vector, and internal expression of the norm is a vector. SO the norm is l2 norm.

The code is as follows:

clear

clc

close all

K = 4;

P = 25;

H = -(1+1i)*rand(K, 1) + (1+1i)*rand(K, 1);

G = -(1+1i)*rand(K, P) + (1+1i)*rand(K, P);

d = complexcirclefactory(K, 1).rand();

D = diag(d);

manifold = stiefelfactory(K, K);

problem.M = manifold;

problem.cost = @(X) -norm(H.'*(X*D*X.')*G, 2)^2;

problem.egrad = @(X) -(2*G*G.'*X*D.'*X.'*H*(H.'*X*D) + 2*H*((H.'*X*D)*X.'*G*G.'*X*D.'));

[U, ~] = conjugategradient(problem, [], []);

Theta = U*diag(d)*U.';

checkgradient(problem)

The slope should be 2. It appears to be: 1.
If it is far from 2, then directional derivatives might be erroneous.
The residual should be 0, or very close. Residual: 1.56579e-14.
If it is far from 0, then the gradient is not in the tangent space.
In certain cases (e.g., hyperbolicfactory), the tangency test is inconclusive.

Thank you for your kind cosideration. 

[Nicolas Boumal]

"The slope should be 2. It appears to be: 1."

The gradient appears to be incorrect. You can try to fix it, and let us know if things are still slow once it passes the test.

--
http://www.manopt.org
---
You received this message because you are subscribed to the Google Groups "Manopt" group.
To unsubscribe from this group and stop receiving emails from it, send an email to manopttoolbo...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/94374f10-cb72-43ab-9061-c83a2362ba6fn%40googlegroups.com.

[Keyvan Aslansefat]

Thank you very much. I calculated the derivative with the tool provided in https://www.matrixcalculus.org/. I will appriciate any resources about the complex matrices derivation.

[Nicolas Boumal]

Sure, you can find some on this forum with the search bar, perhaps with keywords "complex cost" or "complex gradient". 

To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/9037e355-1547-472d-8094-db2e664f6213n%40googlegroups.com.