sparse optimisation variables

[hermi...@gmail.com]

Hello,

is there a possibility to label the quantity to be optimised (say, a positive definite, fixed rank matrix) as explicitly sparse?

E.g. in order to vastly save memory.

Best,

Herm

[Nicolas Boumal]

Hello Herm,

The short answer is: no, not out of the box. You could modify the manifold factory you work with to force it to use sparse matrices though.

This being said, (low) fixed rank and sparse rarely go together, as far as I know. I'm not sure I see where you could gain anything. Something that is more common is playing with a matrix which is a sum of a low-rank one and a sparse one. Then you want to play on a product manifold. Note that sets matrices of a given sparsity do not form a manifold (not unless you fix the positions of the nonzero entries), so this would require some thinking.

Best,

Nicolas

[hermi...@gmail.com]

Hello Nicolas,

thanks! I would be optimising a function like trace(A*B) over a positive, rank-r, trace-constrained sparse B, and positive A fixed and sparse. 

So B could be written as the sum of r products x*x' of sparse column vectors x. However, the positions of the non-zero entries are indeed not known in advance and hence not fixed. The point of treating A sparse would be just to save memory and be able to handle very large A.

Best,

Herm

[Nicolas Boumal]

Hello Herm,

By positive, do you mean positive semidefinite? You say both A and B are positive; do you mean the same thing for both?

The sparsity of A is not fixed. That seems difficult to handle. You will need a special rule to decide when a zero entry is allowed to become nonzero, and likewise you will have to decide when to set a nonzero entry to zero.

I'm not sure this problem is phrased in its most useful way. For example, assuming you meant positive semidefinite, then the solution to min trace(AB) is simply A = B = 0. For maximization, the problem is unbounded. So I imagine there is something else in the constraints or the cost?

Best,

Nicolas