Manifold? of low-rank Hankel matrices

[Jesus Briales]

Hi everyone,

I've a question which is closely related to this previous thread although much more concrete,

regarding if optimization on low-rank Hankel matrices could be addressed through Riemannian geometry (and thus Manopt).

The interest in this question arises because I'm solving a (convex relaxation) SDP problem of the type:

  min <C,M>, s.t. M is Hankel and Positive Semidefinite

So here C is a symmetric nxn data matrix and M is a Positive Semidefinite Hankel matrix.

The global solutions of interest turn to be low-rank and, because of this, I was considering to use

a Burer-Monteiro low-rank reformulation approach for scalability and the possible viability of doing this

through smooth optimization in a manifold, following the trend in Nicolas' work in the Riemannian Staircase

or the recent NIPS16 paper.

A quick characterization of a rank<p PSD Hankel matrix which comes to my mind is

  M = YY', Y\in Re^{nxp},

with the constraints of the Hankel matrix written as

  <B_i Y, Y> = 0,

and also considering this is a quotient space regarding orthogonal transformations Y~YO.

I've been trying to figure out if this is actually a smooth manifold following the indications in the previous post,

but this seems not to be trivial at all, so before putting more time into this I would like to know

your opinion (from previous knowledge or intuition) about the viability of this.

Actually, my main question is:

I can work towards checking the dimensionality of the tangent space derived

from the quadratic constraints (B_i matrices) arising above,

BUT then even if I am able to prove this is a smooth manifold (maybe not!)

I assume I still would need to find a retraction to perform the optimization in the Riemannian manifold.

That doesn't seem easy as well. A idea which comes to my mind to project ambient points

into the *manifold* (but I'm not sure if this is a retraction, so correct me if necessary!) would be solving:

  min_M ||M - M0||, s.t. rank(M)<=p and M is Hankel

and then using the SVD decomposition of M to recover the appropriate Y point.

But, as I said, I don't know if this is promising at all as a possible retraction and,

most important, I've checking on some literature and this *structured low-rank approximation* problem

seems quite difficult per se, so I'm not sure if this is promising at all.

Well, as I said, this is a much more particular stuff but I would appreciate to hear

the opinion of those who have more experience on this before proceeding further :)

Best regards,

Jesus Briales

[Nicolas Boumal]

Hello Jesus,

I don't have a useful answer to this unfortunately,though I wanted to address a couple points:

1) I actually encourage you to /not/ quotient out the equivalent relation Y ~ YO, because the geometry breaks down at matrices Y which are column rank deficient --- which is exactly what we hope to converge to. Bonus: it's easier not to quotient, so .. :).

2) 

I can work towards checking the dimensionality of the tangent space derived

from the quadratic constraints (B_i matrices) arising above,

BUT then even if I am able to prove this is a smooth manifold (maybe not!)

I assume I still would need to find a retraction to perform the optimization in the Riemannian manifold.

Indeed..

3) If the Hankel constraints on X do not reduce to a manifold constraint on Y (which I would deem plausible, though I have nothing to back it up), then you could still try an augmented Lagrangian approach (ALM, much close to the original work of Burer and Monteiro, SDPLR). if a subset of the Hankel constraints reduce to a nice manifold (for example, if the trace of X is fixed, then Y lives on a sphere), you can handle those constraints via the manifold, and handle the rest of the constraints via ALM. or you handle everything via ALM (manopt can also optimize over matrices without constraints via euclideanfactory). I would actually be very interested in hearing about your experience with this if you try it.

Best,

Nicolas

[Jesus Briales]

Thanks for your directions Nicolas!

I will tell you if something comes up regarding this :)

Best,

Jesus

[Jesus Briales]

By the way, I'm not fully sure if you meant that you *deem plausible* (I'm aware that only in a intuitive basis)

- Hankel constraints on X *reducing* to a manifold constraint on Y, or

- Hankel constraints on X *NOT reducing* to a manifold constraint on Y.

It makes quite a difference in the statement! ;)

Regards,

Jesus

[Nicolas Boumal]

I figured this might be unclear :). So, to clarify: I do not expect that the set is a manifold. This is not based on anything concrete, it's just baseline pessimism I suppose. I hope I'm wrong!

Best,

Nicolas