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.

  • 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


Your Answer

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

Browse other questions tagged or ask your own question.