3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ As a cheap observation, we can equivalently maximize $\|Q_1^T P Q_2 \|_F$ over doubly stochastic matrices. $\endgroup$
    – Mahdi - Free Palestine
    Commented Nov 22, 2018 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 - Free Palestine
    Commented Nov 22, 2018 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
    Commented Nov 23, 2018 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 - Free Palestine
    Commented Nov 23, 2018 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
    Commented Nov 23, 2018 at 21:59

1 Answer 1

Reset to default
5
$\begingroup$

It is a graph-matching problem, which is NP-hard. But some solutions available if relaxing the perturbation matrix assumption. See example at https://doi.org/10.1016/j.patcog.2016.07.015

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .