Projection matrices with prescribed diagonal

[Vincent Loonis]

Hello,

I am a survey sampling statistician who faces a specific problem.  I would like to optimize a matrix function on the set of projection matrices with a prescribed diagonal.

I am not an expert in the field of optimization.

Could someone help me to start
with the good reference, the first step, the right way to do it?

Thank you in advance,
Sincerely,
Vincent Loonis

[Nicolas Boumal]

Dear Vincent,

Could you tell us more about the set you need to optimize over, and the real-valued function you wish to minimize or maximize over that set?

Specifically, when you say projection matrices, do you mean orthogonal projection matrices, or any square matrix such that P² = P ? And how about the rank of the projector (that is, the dimension of the subspace it is projecting to): is that known and fixed, or is it just bounded above? (I imagine it is known, since trace(P) = "sum of the known diagonal entries" must be equal to the rank, as P² = P implies all eigenvalues of P are either 1 or 0).

Best,

Nicolas

[Bamdev Mishra]

Hello, Vincent,

Hello, Nicolas,

It would certainly be helpful to get more insights on the problem as Nicolas mentioned.

However, if have to take a stab randomly, I believe you might be 

looking for constraint P'P = D, where P is d by r (r<=d) and D is a r by r diagonal matrix.

If that is so, then we can

convert P'P = D to Q'Q = I with Q = P Dinvhalf.

Problem1: Min f(P) where P'P = D

Problem2: Min f(Q Dhalf) where Q'Q = I.

Dhalf is sqrt(D).

Dinvhalf is pinv(sqrt(D)).

Both the problems are equivalent. We can solve Problem2 with the Stiefel manifold using Manopt.

Regards,

Bamdev

--
http://www.manopt.org
---
You received this message because you are subscribed to the Google Groups "Manopt" group.
To unsubscribe from this group and stop receiving emails from it, send an email to manopttoolbo...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/manopttoolbox/37db36c2-85b1-49e9-af5a-c12638cad63en%40googlegroups.com.

[Vincent Loonis]

Hi thank you for your help.

I want to minimise something like    -trace(X"K*\overline(K)X) where X is given, * is the Hadamard product and  K is an orthognal  projection matrix whose diagonal and rank are given as well. \overline(K) is the conjuguate of K and of course K*\overline(K) provides a matrix whose entries are the modulus of all K entries.

There is no reason for K to be real, but if it helps I can restrict the search to real matrices.

Best regards,

Vincent

[Nicolas Boumal]

Hello again,

I cannot think of a clean way to force K both to be a projection matrix and to have a prescribed diagonal exactly.

My suggestion then would be to go as follows: every projection K can be written as K = VV', where V is an orthonormal matrix, that is, V'V = Identity --- V' is the conjugate-transpose of V, and V has size n x k with k < n corresponding to the rank of the projector.

We want to minimize

f(V) = -trace(X' ( (VV') .* conj(VV') ) X)

with V on grassmanncomplexfactory(n, k).

(Matlab 2021b or more recent with the Deep Learning toolbox can figure out the gradient for you automatically with problem = manoptAD(problem); and otherwise you can also figure out the gradient with some calculus on paper; see also Sec. 4.7 in my book on my webpage if need be).

But we would also like to force the norms of the rows of V to be equal to certain given values (as they correspond to the diagonal entries of VV', which is our projector).

Something to try here is to add a penalty term in the cost function to favor the correct diagonal entries. One possibility is to use a type of augmented Lagrangian approach on manifolds, as described here for example:

https://arxiv.org/abs/1901.10000

A simpler approach would be to add the following to the cost function: sum_i (V(i, :)'*V(i, :) - u(i))^2   where u(i) is the desired value for the diagonal entry K(i, i). That penalty (the whole sum) should be multiplied with some penalty weight that needs to be tuned.

I hope this helps.

Best,

Nicolas

[Vincent Loonis]

Hi Nicolas,

Thank you for your help. To tell you the truth, I am a little bit afraid of what it means since I am not expert in Mathlab, nor in gradient calculus...

I have two remaining questions :
my criteria is concave, and the solution is an extreme point. Does this feature have some impact on the validity of the process ?
What about the size of the problem on the efficiency of the algorithms ? N can be large  and k as well.
Best regards,
Vincent

[Nicolas Boumal]

Hello Vincent,

> my criteria is concave, and the solution is an extreme point. Does this feature have some impact on the validity of the process ?

For maximization problems, it is normally a good thing to have a concave function, indeed. That said, if the search space (that is, the set over which you optimize) is not convex, then it does not, in general, offer any particular advantage. There are particular cases where one can say more, but it gets technical.

> What about the size of the problem on the efficiency of the algorithms ? N can be large  and k as well.

Unless N and k are well beyond the 1000's, I wouldn't worry too much, unless you need to solve such problems in real time at high frequency.

Best,

Nicolas

[Vincent Loonis]

For maximization, yes but for minimisation ?

[Nicolas Boumal]

For minimization, having a concave cost function only tells you that there will be solutions on the boundary of the domain (even at extreme points of the domain).

That's part of why linear programming is so nice: they have a convex search space, and linear cost functions are convex (hence local minima are global minima) and concave (hence if there are optimal solutions, some of them are at the vertices of the domain).