5
$\begingroup$

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

$\endgroup$
9
  • 3
    $\begingroup$ You could sort the arrays and only take the difference of the corresponding elements. $\endgroup$
    – Tyberius
    Mar 25, 2020 at 15:02
  • 1
    $\begingroup$ As far as I understand you have $\mathbf{A}$ and $\mathbf{B}$ as two same length vectors with $n$ elements, and you want to know how close are these two vectors right? So, instead of doing this strange calculation by shuffling, I recommend to use $L^{2}$ norm defined as: $$\epsilon_{2} = \sqrt{(\mathbf{A}-\mathbf{B})(\mathbf{A}-\mathbf{B})^{T}}$$ $\endgroup$ Mar 25, 2020 at 16:19
  • $\begingroup$ @Tyberius What if they contain complex numbers? (Granted, you may argue that they are not complex because OP did not put a modulus around that square, but the problem makes sense also for complex numbers.) $\endgroup$ Mar 25, 2020 at 18:39
  • 1
    $\begingroup$ @AloneProgrammer OP wants to find the distance up to permutations, if I understand correctly. Assume the array contains pairs of close numbers, but they are shuffled randomly, for instance. $\endgroup$ Mar 25, 2020 at 18:41
  • 3
    $\begingroup$ @Tyberius Now that you put it that way, it sounds a lot like an instance of the assignment problem, which is solvable in $O(n^3)$. Maybe though one can do better than that, since here essentially the number of degrees of freedom of the problem is $O(n)$, not $O(n^2)$. $\endgroup$ Mar 26, 2020 at 20:23

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks. I believe it is feasible. Another question is just like what I commented above, suppose there are two ordered arrays $A$ and $B$. We can shuffle them arbitrarily and turn them into $A′$ and $B′$. Is there any possibility that $(A−B)(A−B)^T>(A′−B′)(A′−B′)^T$? I tried some instances, but I didn't find any arrays that could meet the requirements above. $\endgroup$
    – DingDong
    Mar 28, 2020 at 1:21
  • $\begingroup$ I’m sorry, but your notation is unclear. Our A and B matrices or vectors? What do you mean by X > Y when X and Y are matrices? $\endgroup$ Mar 28, 2020 at 4:29
  • $\begingroup$ I mean A and B are arrays, which can also be taken as row vectors. For example, $A=[a_1\ a_2 \cdots a_n], B=[b_1\ b_2\cdots b_n]$. $\endgroup$
    – DingDong
    Mar 28, 2020 at 13:49
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Are you saying that the Wasserstein distance gives the solution of that minimum problem, or that it can be used to formulate another (different) similarity measure that could suit OP's needs? It is not clear from your answer. $\endgroup$ Mar 28, 2020 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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