Let $A$ and $B$ be $n \times n$ real matrices. I'm interested in knowing something about the quantity \begin{align*} L = \min_{\pi_1, \pi_2} \Vert \pi_1 A \pi_2^T - B \Vert_F \end{align*} where $\pi_1$ and $\pi_2$ represent row-wise permutation matrices. $L$ represents the sum of squared residuals between the elements of $B$ and the elements of the 'closest' row/column permutation of $A$.
How should I think about this problem? Is there an efficient algorithm for finding the optimal permutation? As a side problem, I'm also interested in the statistics of $L$ when $A_{ij}$ and $B_{ij}$ are sampled i.i.d. from different distributions $p_A$ and $p_B$. Is there a way to compute the expectation value of $L$ under this model?
As written now, this will be non-linear. Use the properties of permutation matrices, for example $P^{-1} = P^{T}$ and assuming a $0$-minimizing solution exists:
$$\pi_1 A \pi_2^T - B = 0 \Leftrightarrow\\\pi_1 A\pi_2^T\pi_2 = B\pi_2 \Leftrightarrow\\ \pi_1 A = B \pi_2 \Leftrightarrow\\\min_{\pi_1,\pi_2}\|\pi_1 A - B \pi_2\|_F^2$$
Now what remains is some constraint or regularization to enforce row-permutationness.
I am sure you can come up with some way.