Let $M_1$ and $M_2$ be two real positive-semidefinite matrices. Is there any algorithm to compute a permutation matrix $P$ to minimize $\| M_1-PM_2P^T \|_F^2$ or equivalently to maximize $trace(M_1PM_2P^T)$?

To be simple, for $i=1,2$, further assume $M_i=Q_iQ_i^T$, where $Q_i$ has orthonormal columns.

  • $\begingroup$ As a cheap observation, we can equivalently maximize $\|Q_1^T P Q_2 \|_F$ over doubly stochastic matrices. $\endgroup$ – Mahdi Nov 22 '18 at 18:17
  • $\begingroup$ Also, we have $\|Q_1^T P Q_2 \|_F^2 = \sum_{1\leq i,j\leq k}(a_i^TPb_j)^2 = \sum_{1\leq i,j\leq k} \tr(PQ_{ij})^2 $, where $a_i$'s and $b_i$'s are respectively columns of $Q_1$ and $Q_2$ and $Q_{ij}=a_ib_j^T$. $\endgroup$ – Mahdi Nov 22 '18 at 18:17
  • $\begingroup$ @Mahdi, I think you meant $Q_{ij}=b_ja_i^T$. So, we need to maximize $\sum_{1\le i,j,\le k}tr(PQ_{ij})^2$. Could you explain a little bit more to maximize it? Here, $P$ is a permutation matrix. $\endgroup$ – John Nov 23 '18 at 21:31
  • $\begingroup$ Yes, that was a typo. Since $\|Q_1^T P Q_2 \|_F$ is a convex function, the optimum value didn't change if we get optimum over the convex hull of all permutation matrices, which is equal to doubly stochastic matrices. I am not sure, is there any exact algorithm, for maximizing that quadratic function over some linear constraints. $\endgroup$ – Mahdi Nov 23 '18 at 21:54
  • $\begingroup$ @Mahdi, did you mean to get a continuous $P$ first via optimization, then make it discrete with {0,1} elements? $\endgroup$ – John Nov 23 '18 at 21:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.