Manifold defined by eigenvalues & eigenvectors& Laplacian. Is defining the following manifold possible with MANOPTS?

[keoxkeox]

Greetings,
I am completely new to optimization on manifolds so please forgive me if I am asking either something trivial or something stupid. I am currently unable to assess what is feasible by using MANOPT or not.

I am involved with SSL using graphs. In that context I am trying to tackle some optimization problems using the eigenvalues and eigenvectors of the graph Laplacian as the optimization arguments. Simply

L graph Laplacian satisfies,
L_i_j <= 0 if i \neq j
L = L'
L * ones = zeros (centered)

its eigendecomposition L = U*W*U' satisfies,
W_i_i >= 0
U*U' = eye (Stiefel)

My question: Is it possible to define the following manifold to optimize on using MANOPT?
Given matrix U and diagonal matrix W as optimization arguments

(1) U*U' = eye
(2) W_i_i >= 0
(3) (U*W*U') * ones = zeros
(4) [U*W*U']_i_j <= 0

I have a feeling that (3) and (4) can cause problems.

Anyway, so sorry for such a sloppy question

Best Regards,

[Nicolas Boumal]

Hello,

This is a perfectly fine question.

At a higher level, do I understand it right that you would like to optimize over the set of Laplacians, and be allowed to express your cost function in terms of U and W for that Laplacian?

I'm assuming you want connected graphs.

I suppose a direct approach would be to optimize over the set of graph adjacency matrices (let's call them A): that's a linear space, consisting of symmetric matrices with a zero diagonal. Very easy to handle with Manopt (we can discuss details if that's useful.) Then, eigenvalues of L = D-A (where D is the degree matrix of A: D = diag(A1)); are continuous (but not smooth) functions of A. They are almost everywhere differentiable though, so this could work out (issues arise when eigenvalues are not distinct). Same for the eigenvectors. This makes the search space easy (just a linear space), but the cost function might be tough to handle, depending on what you have at hand.

An alternative would go along these lines perhaps:

 - U could live in the set of orthogonal matrices of size n whose last column is constant (code would be inspired from stiefelfactory; it may be more convient to force the first column to be constant if we use QR--technical detail).

 - W could be a diagonal matrix of size n with first diagonal entry equal to 0, and the remaining n-1 diagonal entries positive (similar to the positivefactory).

This would lead to some invariances, in that graphs can be represented with more than one pair (U, W), but that's not necessarily an issue.

From experience with other problems, it might be better to let W be any positive definite matrix (fixing a zero row and column), but to figure this out would require testing.

Out of curiosity, could you detail what kind of problems and cost functions you have in mind, and any relevant references?

Also: what is SSL? (I presume it has nothing to do with the encryption protocol?)

Best,

Nicolas

[mgrid...@gmail.com]

Greetings,

Thanks for your accommodating response,

(1) "At a higher level, do I understand it right that you would like to optimize over the set of Laplacians, and be allowed to express your cost function in terms of U and W for that Laplacian?" : Exactly correct, my cost function contains graph Wavelet-like terms U*g((W-a)/k)*U'.

(2) "I'm assuming you want connected graphs." : Not really but as a first step I am completely fine with having only one 0 valued eigenvalue. (In practice, I may have more than one)

(3) Dealing with adjacency matrix is not very desirable as I will be dealing with spectral terms.

(4) "An alternative would go along these lines perhaps:

U could live in the set of orthogonal matrices of size n whose last column is constant (code would be inspired from stiefelfactory; it may be more convient to force the first column to be constant if we use QR--technical detail).

W could be a diagonal matrix of size n with first diagonal entry equal to 0, and the remaining n-1 diagonal entries positive (similar to the positivefactory)." : This is definitely more like what I am looking for but I cannot follow two points
(4.i) Do given U and W imply centrality(L*1=0)?
(4.ii) Do given U and W imply non-diagonal terms of L being non-positive?
(A valid Laplacian implies given U and W, but I am not sure about the otherway around)

(5) "This would lead to some invariances, in that graphs can be represented with more than one pair (U, W), but that's not necessarily an issue.": Yup, as long as I end up with a valid graph, I do not care about unique representations

(6) SSL, is semisupervised learning. We are estimating a function defined on the nodes of the graph, using very few measurements on a handful nodes and graph topology itself. I am hoping to devise a method to estimate desired functions while learning a compatible graph topology at the same time.

(7) "Out of curiosity, could you detail what kind of problems and cost functions you have in mind, and any relevant references?": Basically something like this:
min_{U_2, W_2}{L2norm((U_1*g(W_1)*U_1')*S1 - (U_2*g(W_2)*U_2')*S2)}
g is a function defined on the vector of N eigenvalues to (Real numbers ^ N)
S1 and S2 are selection matrices

Thank you very much for reply and kindness,

[keoxkeox]

(4.i) Is obviously satisfied due to "a" 0 eigenvalue corresponding to all 1's eigenvector.
I will continue to think about (4.ii) :)

[Nicolas Boumal]

Hello,

I believe you are right regarding (4.ii): I do not expect that, with what I described, the nonpositivity constraints would be automatically satisfied. It is possible, however, that upon optimizing over that set you would 'by chance' get valid answers most of the time..? This is mostly wishful thinking, not based on any insight.

About steps forward: this is a rather non-trivial use of Manopt. To gauge whether it is worth exploring, here is my question: for (3), you indicated that working with adjacency matrices is not practical since you want access to spectral information. What is this assessment based on? Is the issue that computing spectral information cost O(n^3) flops? Because if so, the approach we consider here is not going to help: the matrix U is nx(n-1), and to keep it orthonormal requires QR factorizations of it, which also cost O(n^3) at each iteration---with a smaller constant admittedly, but still.

Best,

Nicolas

[keoxkeox]

Greetings,

Rather than small complexity gains, optimizing using U and V is easier to interpret in some extremely vague ( :) ) regards.

Let me take a step back, if I were to use adjacency matrix directly, symmetricfactory(n) would be enough as the Laplacian removes self loops, however, as a learning example how can I add 0 diagonal to this setting, as you have previously mentioned before?

Best Regards,

[Nicolas Boumal]

You can use the (rather recent) factory to work on linear subspaces: euclideansubspacefactory

https://github.com/NicolasBoumal/manopt/blob/master/manopt/manifolds/euclidean/euclideansubspacefactory.m

Your base space would be euclideanfactory(n, n); your projector would extract the symmetric part of its input, and zero out the diagonal. Check the help of that factory, it's rather explicit.

There's still an issue though: this doesn't enforce nonnegativity of the entries.. You could conceivably add penalties in your cost function for this (nonsmooth, or a smoothed version), and/or you could try an augmented Lagrangian approach. Since your base space is now linear, there are no manifold-specific things to worry about.