A question about the Symmetric positive semidefinite, fixed-rank (complex) manifold

[Fan Liu]

Dear sir,

Recently I was using the manifold of complex symmetric positive semidefinite matrices with fixed-rank. 

In my optimization sometimes I obtained the solution with a rank that less than the rank I set, namely rank-K. I have noticed that in the description of this manifold, you mentioned that:

"Notice that this manifold is not complete: if optimization leads Y to be rank-deficient, the geometry will break down. Hence, this geometry should only be used if it is expected that the points of interest will have rank exactly k. Reduce k if that is not the case."

Does this mean that this manifold is in fact  the manifold of complex symmetric positive semidefinite matrices, but with a rank<=K?

I have also read the paper you mentioned, which is "Radio interferometric calibration using a Riemannian manifold". In this paper, the matrix J is not to be assumed as full-rank matrix. So the resultant solution might be rank-deficient. 

Is this a reasonable interpretation for the rank-deficient solution? 

Looking forward to hearing from you soon!

Best,

Fan

[Nicolas Boumal]

Dear Fan,

In principle, the manifold only includes matrices of rank exactly k, represented as YY^T, where Y has full rank.

However, on the boundary of that manifold, we find matrices of rank < k, represented as YY^T with Y rank deficient.

These rank-deficient matrices are not part of the manifold, but it is numerically difficult to prevent convergence to them. One way to think about it is: with the representation YY^T, the set of matrices of rank exactly k is an open set. As long as we remain in the open set, we enjoy a nice Riemannian geometry, which is what allows theory and algorithms to work. But if we ever "step out" and get to a rank-deficient matrix, we lose the Riemannian geometry, and theory breaks down, and algorithms may fail (getting NaN's, inf's, not converging...).

I tend to think is like this: if the interior of the unit square in the plane is a manifold, then as long as I remain in the square, I see a nice two-dimensional manifold. But if I converge to an edge of the square, that geometry will break down (and likewise if I converge to a vertex.)

So, what now? In practice, if the optimal solution to your optimization problem has rank < k, then the optimization algorithm is likely to converge to that -- and hence to step out of the manifold. There can be two scenarios: either that's actually what you want (this happens in certain problems), and so you may implement a stopping criterion that will stop the algorithm if rank deficiency is encountered (with options.stopfun for example, see documentation in https://manopt.org/tutorial.html) ; or you do not want that, and in that case you could examine your cost function again and investigate why it is that optimizers tend to be rank deficient. Either that's a good thing, in which case you may want to work with a smaller k, or it's a bad thing, in which case you may want to add a penalty/regularizer in your cost function to promote solutions of full rank (e.g., something with det(Y'*Y)).

I hope this makes sense.

Best,

Nicolas

[pierr...@gmail.com]

For information, the paper
http://sites.uclouvain.be/absil/2015.05
proposes a rank-adaptive mechanism that addresses the issue of convergence to lower-rank matrices. The concept is not straightforward, but the algorithm is described in detail, there is a convergence analysis, and code is available from the same page. Regarding the code, Wen Huang (http://www.math.fsu.edu/~whuang2/) may have a more user-friendly implementation. -PA

[Fan Liu]

Thanks a lot Nicolas,

I have noticed that in the paper "Radio interferometric calibration using a Riemannian manifold", which you referred as the geometry of this manifold, a quotient manifold has been used, which is \bar M = M/~, where \bar M is the set of all the 2N*2 complex matrices (include rank-deficient matrices), ~ is a equivalence relation regarding the unitary matrices. In this paper no full-rank assumption has been made. So if you used the same geometry, as per my understanding about this paper, the manifold will be a rank<=K manifold. Is this a reasonable understanding for the manifold?

Actually I want to do optimization on the manifold of symmetric complex semidefinite matrices with rank<=K, and I do obtain rank-deficient results. So can I assume that I have chosen the correct manifold in manopt?

Best,

Fan

[Fan Liu]

Thanks a lot Pierre, I will read the paper to see if I can use the algorithm.

[Nicolas Boumal]

Hello Fan,

You are raising a good point.

In the paper you reference, equation (14) is a Sylvester equation useful for orthogonal projection to the horizontal space at a point J. That equation involves the term J^H J, where J^H is the Hermitian conjugate of J.

If J is rank deficient, then J^H J is not invertible, and this should lead to trouble when solving the Sylvester equation. My interpretation (without running tests) is that this simply reveals the fact that the horizontal space at rank-deficient J's has a different dimension from the horizontal space at a full-rank J, which, if that is the correct interpretation, shows that the geometry "breaks" at rank-deficient J's.

If you run Manopt with that geometry from a rank deficient J, do you get warnings or NaN's / Inf's ? I expect that should happen.

Best,

Nicolas

[Fan Liu]

Hi Nicolas,

Thanks for your kind reply.

Sometimes the error occurs in MATLAB saying that the solution of the Sylvester equation is not unique or doesn't exist. In this case I can not get any results.

However when the rank-deficient results are obtained, there is no warnings or errors. And the algorithms (I use RTR in the problem) convergent normally.

Since I do want to obtain a solution of rank<=K. Maybe we can say that the rank-deficient results are 'not-bad' feasible solutions for my problem. 

Anyway, thanks a lot for your patience. You guys are really doing the great job! I have seen a lot of engineering papers using your toolbox.

Best,

Fan