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$
  • 3
    $\begingroup$ You could sort the arrays and only take the difference of the corresponding elements. $\endgroup$ – Tyberius Mar 25 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$ – Alone Programmer Mar 25 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$ – Federico Poloni Mar 25 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$ – Federico Poloni Mar 25 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$ – Federico Poloni Mar 26 at 20:23
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 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$ – Brian Borchers Mar 28 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 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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Federico Poloni Mar 28 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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