1
$\begingroup$

Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that $\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$?

Of course one can take all the indices $j\in\{1, \dots, n\}$ and compute all the sums, but the goal is to find something faster.

The same question hold for matrices: If $A$, $B$ are two square matrices, how to minimize $f(a,b)=\sum_{i=1}^n\sum_{j=1}^n (A[i][j]-B[i+a][j+b])^2$ for $a,b\in\{1,\dots,n\}$, where indices are again taken modulo $n$?

Thanks a lot. I would like to apologize, if my question is a classic one, but I searched and I didn't find an answer.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Your problem combines the cross-correlation with the sum of squared differences. If you are able to map the values of $L$ and $M$ into the complex plane, such that the correlation between $l\in L$ and $m\in M$ is $(l-m)^2$, then the cross-correlation (for all $n$ values of $j$) takes $O(n\log n)$ time to compute using the Fast Fourier Transform. $\endgroup$
    – Tim
    Apr 23, 2015 at 14:52
  • $\begingroup$ Are the entries of your lists, matrices bounded? Integers? Reals? $\endgroup$
    – kodlu
    Apr 24, 2015 at 0:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.