permutation_2sided not performing well for me

[OnDraganov]

I tried using procrustes.permutation.permutation_2sided with single=True, and the results are much worse than a naive "local-flips optimization", which surprised me. It might be because my setting is particularly degenerate, but I am not sure. I have the following questions:
-- Is permutation_2sided supposed to work well or is it more experimental and sometimes gives ok results?
-- Can the parameters be tweaked in my case so that the results get better?
-- Is this generally a difficult problem or is my setting particularly degenerate?

Details

The problem

For two matrices, $A$, $B$, I want to find the permutation matrix $P$ minimizing $||P^TAP - B||^2_F$. The matrix $P^TAP$ is the matrix $A$ with both columns and row permuted by a permutation $\pi$.

My naive approach: Start with a random permutation $\pi_0$. Then randomly choose two elements $i,j$ and flip them, i.e. $\pi_{n+1}=(i\ j)\pi_n$. Check the norm---if it improves, keep the flip, otherwise revert the flip. This improves a lot at first, and then gets stuck in various local optima (no single flip improves the norm).

Using procrustes as an alternative: I tried running permutation_2sided with method in ['approx-normal1', 'approx-normal2', 'approx-umeyama', 'approx-umeyama-svd', 'nmf'] and also softassign. The results they yield are not always local optima with respect to the single flips (I checked for approx-normal2 and softasign), and the errors are as follows:

Method     approx-normal1, error: 1.401
Method     approx-normal2, error: 1.401
Method     approx-umeyama, error: 1.801
Method approx-umeyama-svd, error: 1.916
Method                nmf, error: 1.778
Method         softassign, error: 0.580

Compare this to 0.528 that I got from a few (~10) runs of the flip-optimization, with less than 20'000 tried flips each.

The matrices

The results above are for $50\times 50$ matrices. I got them with the following procedure.
-- Start with $\tilde{A}$, $\tilde{B}$ two distance matrices.
-- For each, take the lower triangular part, rank the values, and replace the values in the whole matrix with those ranks (ranks as used in Spearman's correlation rank computation).
-- For each matrix, compute the mean value, and remove it from all non-diagonal elements.

The resulting matrices are, in particular, symmetric, have zeros on diagonals, and contain mostly integers or small fractions (as in small denominator) between ~ $-1000$ and $1000$.

For the errors above I used scale=True so that the numbers are readable, but this does not seem to influence the optimization results (I tried both scale=True and scale=False).

!!! One thing that might be important: my matrix $\tilde{B}$ has only a few distinct values (13 including 0), so $B$ only contains values [-598.0, -566.5, -517.5, -418.5, -286.5, -145.5, 0.0, 26.5, 203.0, 335.0, 448.5, 551.5, 602.5].

[PaulWAyers]

As you know, 2-sided permutation Procrustes is NP, so one doesn't expect a reliable solution. I view our heuristics as useful, but they were customized for certain cases related to chemistry, and may not be useful in your cases. I also view them as primarily useful as initial guesses for softassign (which is a semi-experimental feature, but which is guaranteed to work with enough fiddling with parameters, albeit at very high cost) or k-opt, which is basically a greedy algorithm that does what you are describing. The approx-normal# cases would be ill-suited to cases with many repeated numbers; they were intended for charge-bond-order matrices (and similar objects) in chemistry, though I think they will often work for weighted graphs and matrices that can be interpreted as adjacency matrices for weighted graphs.

The approximate methods are not (at all) guaranteed to give a local optimum. k-opt will give a local optimum (relative to k-fold permutations).

In general, then, I recommend running an "approx-" method and then using it as a guess for k-opt with the highest value of $k$ you can afford.

[OnDraganov]

Thank you very much for the quick response! This is a useful summary to me. I will try to experiment a bit with k-opt and see how that goes.
To the first statement -- it is clearly NP, but is it NP-complete? As opposed to the 1-sided permutation Procrustes which is in P due to the relaxation to linear programming, as described in the documentation? I am not very familiar with the broad context of the Procrustes problem, so this is a valuable information for me too.

[PaulWAyers]

It is NP-hard as it is equivalent to the quadratic assignment problem, which NP-hard as there is no polynomial algorithm for checking or solving the problem. (Some special cases are merely NP, e.g., where one knows that $A$ and $B$ are exactly related by permutations.)

[OnDraganov]

I see, thank you for the clarification!

[PaulWAyers]

I'm going to close this discussion for now, but feel free to reopen it after you try k-opt. @FanwangM and @FarnazH , most especially, should feel to comment if they have additional remarks.