6
$\begingroup$

Given two $n \times n$ symmetric positive definite matrices $A$ and $B$, I am interested in solving the following optimization problem over $n \times n$ unitary matrices $R$: $$ \mathrm{arg}\max_R \,\mathrm{trace}(RAR^TB)~~~\text{s.t.}~~~RR^T = I_n~. $$ More generally, given two sets of $m$ positive definite matrices $\{A_i\}_{i=1}^m$ and $\{B_i\}_{i=1}^m$ I would like to solve: $$ \mathrm{arg}\max_R \,\sum_i\mathrm{trace}(RA_iR^TB_i)~~~\text{s.t.}~~~RR^T = I_n~. $$

If I recall correctly, I have seen the following inequality $$ \mathrm{trace}(R\,\mathrm{diag}({\bf c})\,R^T\,\mathrm{diag}({\bf d})) \le {\bf c}^T{\bf d} $$ for positive vectors ${\bf c}$ and ${\bf d}$. If this inequality is correct, then $R=I_n$ provides the optimal solution for diagonal matrices and using spectral decomposition of non-diagonal $A$ and $B$ we can solve the problem in the case of $m = 1$. Can somebody please show me how to prove this inequality? More importantly, Is there a way to solve the problem in the more general case of $m > 1$?

$\endgroup$
2
  • $\begingroup$ For two posdef matrices, it is known that $\text{trace}(AB) \ge \langle \lambda^\downarrow(A), \lambda^\uparrow(B) \rangle$, which yields the inequality that you mention (because $RAR^T$ is also positive definite), though you must be careful that $c$ and $d$ are sorted in opposite order as the $\downarrow$ and $\uparrow$ above indicate... $\endgroup$
    – Suvrit
    Nov 1, 2013 at 23:16
  • $\begingroup$ Your comment made me realize that I had a typo in the direction of my inequality which is related to $\mathrm{trace}(AB) \le \langle \lambda^\downarrow(A), \lambda^\downarrow(B) \rangle$. Also, my problem is $\mathrm{argmax}$ not $\mathrm{argmin}$ which is corrected now. Thanks! $\endgroup$
    – Norouzi
    Nov 2, 2013 at 2:19

3 Answers 3

3
$\begingroup$

If your $B_i$ commute among themselves, and the $A_i$ commute among themselves, then the $m=1$ solution extends somewhat. Indeed, in that case write $A_i=V C_i V^T$, $B_i=UD_iU^T$ where $U,V$ are unitary and $C_i,D_i$ diagonal. Now, optimizing over $R$ becomes the same (after the right and left multiplication by $V^T$ and $U$) as optimizing over $W$ orthogonal in the expression $$tr \sum_i WD_iW^TC_i=\sum_{j} \sum_{i,k} w_{jk}^2D_i(k)C_i(j)= \sum_{j,k} s_{jk} \sum_i D_i(k)C_i(j)=: \sum_{j,k} s_{jk} T(k,j),$$ where $T(k,j)=\sum_i D_i(k)C_i(j)\geq 0 $. Here, the $s_{jk}$ form a doubly stochastic matrix. By Birkhoff's theorem, the extreme points of the set of doubly stochastic matrices are permutations, so the optimal solution for the above convex problem is a permutation matrix $\{s_{j,k}\}$ ; unlike the case where $\sum_i$ is trivial, I am not sure there is a simple description of the optimizing permutation.

Remark: when $m=1$, the argument above shows the inequality you wanted: the optimal permutation in that case is the one that orders the eigenvalues of $B$ in the same order as those of $A$.

$\endgroup$
2
  • $\begingroup$ It should be possible to solve for the optimal permutation by using the Hungarian algorithm. $\endgroup$
    – Norouzi
    Nov 5, 2013 at 23:46
  • $\begingroup$ This case with commuting matrices indeed reduces to solving the "linear assignment problem" en.wikipedia.org/wiki/Assignment_problem --- also, if the $A_i$ don't commute, but $B_i=B$, it is just $m=1$; maybe something non trivial can be said about the general case too.... $\endgroup$
    – Suvrit
    Nov 6, 2013 at 0:19
2
$\begingroup$

To expand on my comment (and given the update by the OP), it is clear that $R=UP^T$ (where $A=PDP^T$ and $B=ULU^T$) maximizes the trace. This follows because $\text{tr}(RAR^TB) \le \langle\lambda^\downarrow(A),\lambda^\downarrow(B)\rangle$, [Problem III.6.14, R1] and equality can be achieved by setting $R=UP^T$.

The case with $m > 1$ is a different story. A partial observation is that if $B_i=B$ for all $i$, then the problem reduces to the $m=1$ case. Otherwise, it seems to not admit a closed form solution. If I get more time, I'll try to update this answer with further thoughts.

[R1] R. Bhatia, Matrix Analysis. Springer, 1997.

$\endgroup$
2
  • $\begingroup$ Could you provide me with a pointer to this bound? What is it called or where can I find the proof? $\endgroup$
    – Norouzi
    Nov 4, 2013 at 20:46
  • $\begingroup$ @Norouzi: I added a citation to this result, you can find that result, and much more related useful material in the chapter of the cited book. Best, $\endgroup$
    – Suvrit
    Nov 5, 2013 at 15:41
1
$\begingroup$

You could apply Newton's method on the manifold of orthonormal matrices, using the remannian structure to define derivatives and geodesic steps. This is developed in the following paper,

Edelman, Alan, Tomás A. Arias, and Steven T. Smith. "The geometry of algorithms with orthogonality constraints." SIAM journal on Matrix Analysis and Applications 20.2 (1998): 303-353. http://web.mit.edu/~wingated/www/introductions/stiefel-mfld.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.