Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
    
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... –  Suvrit Nov 1 '13 at 23:16
    
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! –  Norouzi Nov 2 '13 at 2:19
add comment

3 Answers

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$.

share|improve this answer
    
It should be possible to solve for the optimal permutation by using the Hungarian algorithm. –  Norouzi Nov 5 '13 at 23:46
    
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.... –  Suvrit Nov 6 '13 at 0:19
add comment

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.

share|improve this answer
    
Could you provide me with a pointer to this bound? What is it called or where can I find the proof? –  Norouzi Nov 4 '13 at 20:46
    
@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, –  Suvrit Nov 5 '13 at 15:41
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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