2
$\begingroup$

We have matrices $A$ and $B$ of the same dimension. Generally, we use the Frobenius norm of the difference, $\|A-B\|_F^2$, to compare these two matrices and measure how close they are to each other.

Here we assume the $\mbox{col}_i$ of matrix $A$ corresponds to $\mbox{col}_i$ of matrix $B$ and so on and, hence, the subtraction makes sense. If matrices $A$ and $B$ are equal, the Frobenius norm is zero. When matrices $A$ and $B$ deviate, the Frobenius norm is positive.

In our case, $\mbox{col}_i$ of matrix $A$ may corresponds to $\mbox{col}_j$ of matrix $B$. Is there any measure to compare these two matrices where the columns are permuted in one matrix?

One can say that, we can find all the permuted matrix $B$ and evaluate $\|A -\operatorname{perm}(B)\|_F^2$ and choose the best $B$. However, this gets problematic when the number of columns increases, as we need to evaluate $n!$ permutations.

Is there any other measure (not necessarily using the Frobenius norm) to evaluate the closeness of matrices $A$ and $B$ where $B$ is a version of $A$ in which the columns have been permuted?

2 Answers 2

4

Define the cost of matching the $i$th column of $A$ (which I'll call $a_i$) with the $j$th column of $B$ (i.e. $b_j$) as $c(i,j) = \| a_i - b_i \|^2$. A permutation of the columns of $B$ can be viewed as a bijection $f\colon \{1,\ldots,n\}\to\{1,\ldots,n\}$ such that the $i$th column of the permuted matrix is $b_{f(i)}$. Then you want to minimize the norm $\|A-\operatorname{perm}(B)\|^2_F = \sum_{i=1}^n\|a_i-b_{f(i)}\|^2 = \sum_{i=1}^n c(i,f(i)).$ This is nothing but the assignment problem, which can be solved in polynomial time using, for example, the Hungarian algorithm.

0

I would post a comment, but this is turning out to be too long. Unless you a are completely satisfied with the following, don't regard it as an answer.

From what I gather from your question, according to what you want, $m(A, B) = \min_{\sigma\in S_n}\|A - \sigma(B)\|_F^2$ is the best you can do, where $S_n$ is the group of permutations on $n$ letters and $\sigma(B)$ is a permutation of columns of $B$. Why? Because embedded in your problem is the following decision problem: given two $n\times m$ matrices $A$, $B$, decide whether $A = \sigma(B)$ for some $\sigma\in S_n$. Indeed, if $A = \sigma(B)$ for some $\sigma \in S_n$, then $m(A, B) = 0$; otherwise, $m(A, B)\neq 0$.