<p>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$?</p>

<p>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.</p>

<p>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$?</p>

<p>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.</p>

CC BY-SA 3.0
2015-04-23T14:52:59.890Z
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.
Tim
CC BY-SA 3.0
2015-04-24T00:04:51.127Z
Are the entries of your lists, matrices bounded? Integers? Reals?
kodlu
<permutations><minimization><norms>
Minimize L2 norm by circular permutation
user32856
# Minimize L2 norm by circular permutation

(Asked by: username_0 on 2015-04-23)

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.

**Tags:** permutations, minimization, norms

> **Comments:**
> **username_1**: 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.  
> **username_2**: Are the entries of your lists, matrices bounded? Integers? Reals?  

---

## 0 answers

