Fast algorithm for computing the similarity between two arrays

Question

Suppose there are two arrays (They have the same length), I want to give a quantitative description about the similarity between them. I define a formula like this, which means we can shuffle them arbitrarily. If we use the stupidest method, i.e. calculate every possible result, we need to keep array B unchanged and keep shuffling array A. There should be $n!$ kinds of $\sum (A_i-B_j)^2$ . (Because there are $n!$ different orders for array A.)

But is there any fast algorithm for it? $$ \min_{\text{$\sigma$ permutation of $\{1,\dots,n\}$}} \sum_{1\le i\le n}(A_i-B_{\sigma(i)})^2 $$

Answer 1

You can formulate this problem as an assignment problem of the form

$\min \sum_{i=1}^{n} \sum_{j=1}^{n} w_{i,j}x_{i,j}$

subject to

$\sum_{j=1}^{n} x_{i,j}=1,\; i=1, 2, \ldots, n$

$\sum_{i=1}^{n} x_{i,j}=1, \; j=1, 2, \ldots, n$

$x_{i,j}=\mbox{0 or 1} \; i=1, 2, \ldots, n, j=1, 2, \ldots, n.$

Basically, $x_{i,j}=1$ if column $i$ of $A$ is matched with column $j$ of $B$ and $0$ otherwise. The constraints ensure that each column of $A$ is matched with exactly one column of $B$.

Here, you would let

$w_{i,j}=\| A_{i} - B_{j} \|_{2}^{2}, i=1, 2, \ldots, n, j=1, 2, \ldots, n.$

Once you've precomputed the weights (which might well be the most time consuming step if the matrices have many more rows than columns), the well known Hungarian algorithm can solve this assignment problem in $O(n^{3})$ time. A number of more sophisticated algorithms are available that have even better asymptotic complexity. Depending on the size of your matrices, it might or might not be worthwhile to use one of these more sophisticated methods.

Answer 2

You have a $1D$ minimization problem and not an $argmin$-problem. Here, you could easily use a 1-Wasserstein distance (commonly known as the Earth mover's distance). For the 1-dimensional case, there is a closed form solution compute-able in linear time. I'll write more when I have the time.