Complex gradient

[hermi...@gmail.com]

Hi,

I am trying to optimise a function like trace(X'*A*X), where A is hermitian and the matrix X is to be optimised.
I want to provide the euclidian gradient to manopt.
What is the expected format of a gradient of a function with complex arguments, where I would expect derivatives w.r.t. the real and imaginary parts to appear or some Wirtinger reformulation in variables and their complex conjugates.

Best,
Herm

[Nicolas Boumal]

Dear Herm,

Can you tell us more about the constraints you have on X? (Without constraints, trace(X'AX) might be unbounded.)

Constraints aside, the way most (all?) complex manifolds are implemented in Manopt is with a real inner product. So for example, we view C^n as essentially equivalent to R^(2n) where there is no strict distinction between real and complex parts., and the inner product is:

<A, B> = real(trace(A'*B))

Then you have the definition of a gradient: grad f(X) is the (unique) vector such that <grad f(X), U> = Df(X)[U] for all vectors U, where Df(X)[U] is the directional derivative of f at X along U.

Plugging these things together, we find that the gradient of f(X) = trace(X'AX) is 2AX (as you would expect; this is assuming A = A' (Hermitian)). There is no Wirtinger calculus to work out.

Please let us know of your experience, we'd be happy to get some feedback about uses of Manopt with complex manifolds (they get tested less often.)

Best,

Nicolas

[hermi...@gmail.com]

Hi Nicolas,

thank you very much for your reply. I wanted to rather optimise over a positive matrix M:=X* X', as in the symfixedrankYYcomplexfactory manifold, ideally also with unit trace as in spectrahedronfactory(n, k). Could this be modified for complex matrices?.

I suppose that <A, B> = real(trace(A'*B)) only makes sense for A and B Hermitian, resulting in a real-valued function to be optimised, right? I am just a bit curious since even when identifying Cˆn with Rˆ(2n), according e.g. to Kreutz, http://arxiv.org/abs/0906.4835, it is in general not clear that the gradient can be obtained by a "formal differentiation", treating the input variable as real-valued.

I'd be happy to provide more feedback on complex manifolds as soon as the optimisation is running.

Best,

Herm

[Nicolas Boumal]

Hello Herm,

You can optimize over the set of n-by-n complex matrices of unit Frobenius norm for example, using spherecomplexfactory.

If Y is a point on that manifold, then X = YY' is a complex positive semidefinite matrix with unit trace.

(The parameterization is redundant, but it's not a huge problem, at least not for a first round of experimentations.)

The real inner product <A, B> = real(trace(A'*B)) works for any complex matrices A and B of same size. They do not have to be Hermitian.

I'm aware of the Wirtinger calculus and other subtleties involved with differentiation with respect to complex variables. It's just that, for some functions at least, the formulas turn out to be rather easy to work out. My preferred way is to go back to the definitions. And then you can always use checkgradient and checkhessian to check your work.

Don't hesitate to post your cost function here; I'd be interested to see examples where the gradient is more intricate to get (or more examples where they are easy to get ;)).

Best,

Nicolas

[hermi...@gmail.com]

Hi Nicolas,
thanks! I'd be e.g. interested in a trace constraint. I suppose, spectrahedronfactory is not defined for complex matrices, right? At least, for the cost function
-trace(X'*A*X) and naively setting the egrad to -2*A*X, checkgradient says: "The slope should be 2. It appears to be: 1."

Alternatively, using an additional cost term instead, I would use e.g.:
n=5; r=2;
manifold=symfixedrankYYcomplexfactory(n,r);
A = randn(n)+1i*randn(n); A = (A*A')/sqrt(2); a=10;
problem.cost  = @(X) -real(trace(A*X*X'))+a*(trace(X*X')-1)^2;

For this, the egrad should look like

problem.egrad = @(X) -2*A*X+a*4*((trace(X*X')-1)*X);

... if I use the definition you mentioned: <A, B> = real(trace(A'*B)).
The result looks reasonable at first sight, i.e. it almost has unit trace and has smaller value -real(trace(A*X*X')) than iid sampled X matrices, however checkgradient also here says:
"The slope should be 2. It appears to be: 1."

I have the feeling this still relates to the problem of how to define the complex gradient. Namely, for the real problem:
manifold = symfixedrankYYfactory(n,r);
A = randn(n); A = (A*A')/sqrt(2); a=10;
problem.cost  = @(X) -trace(A*X*X')+a*(trace(X*X')-1)^2;
problem.egrad = @(X) -2*A*X+a*4*((trace(X*X')-1)*X);
... the gradient seems to be fine.

Best, Herm

[Nicolas Boumal]

Thank you for your message, Herm.

I see what is going on now. You derivation for the gradient is correct. But the metric for symfixedrankYYcomplexfactory is not Real(Trace(A'*B)) : it has an extra factor 2 in it, which I'm not sure why it is there.

You can simply remove the 2 one line 66 of symfixedrankYYcomplexfactory.m.

Thank you very much for bringing this to our attention!

Best,

Nicolas

[hermi...@gmail.com]

Perfect, thanks, it works now!
Best, Herm

[Nicolas Boumal]

By the way: in the upcoming update to Manopt, that change will be effective, so you can safely use the update when it comes out.

Best,

Nicolas