Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a matrix $A$ and matrix $B$ of same dimension. We generally use $||A-B||_F^2$ (Forbenius norm) to compare these two matrix how close they are to each other. Here we assume the $col_i$ of matrix $A$ corresponds to $col_i$ of matrix $B$ and so on and hence the subtraction make sense. If the matrix $A$ and $B$ are equal we have the Forbenius norm as zero. When the matrix $A$ and $B$ deviates, the Forbenius norm increases.

But in my case $col_i$ of matrix $A$ may corresponds to $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 its gets problematic when the number of columns increases (we need to evaluate for $n!$ permutation).

Is there any other measure (not necessarily Forbenius norm) to evaluate the closeness of matrix $A$ and $B$ where the correspondence is from $col_i$ of $A$ to $col_j$ of B

share|improve this question

2 Answers 2

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.