Cómo encontrar el cambio que minimiza la diferencia entre dos vectores?

Question

Estoy buscando una forma eficaz de encontrar el valor de k que minimiza

$\sum(s_t - b_{t+k})^2$

donde $s$ $b$ N-dimensional de los vectores y de los valores que se envuelven alrededor de como esta:

$b_{t+k} := b_{(t+k)-N}$ si $(t+k) > N$

$b_{t+k} := b_{(t+k)+N}$ si $(t+k) < 1$

Necesito esto para algunos algoritmo y por el momento no tengo mejor idea que probar todos los posibles valores de $k$. Si $s$ o $b$ son conocidos de antemano, uno puede hacer algunos trucos, sin embargo no he podido encontrar una forma inteligente para el caso general.

Actualmente mi idea es considerar el cambio como una rotación alrededor de un eje fijo y, a continuación, buscar el ángulo que minimiza la diferencia entre los dos vectores. Sin embargo, después de buscar un poco, tengo la impresión de que esto hace que el problema más complicado que sea más fácil. Algunas preguntas están en este, y este.

Todas las ideas son bienvenidas. Atm yo realmente no tienen nada mejor que probar todos los posibles cambios.

EDIT: quiero aclarar lo que yo tenía en mente con rotaciones...

Si N=3, el cambio puede ser realizado por una rotación $R$ alrededor del eje $(1,1,1)$ por un ángulo de $0$,$2/3 \pi $, o $4/3\pi$. Es un poco engorroso, pero no imposible, para maximizar $<s|R(\theta)|b>$ con respecto al $\theta$ (y como este es en realidad el único término en la expresión anterior, que depende de $k$, de esta manera se minimiza la diferencia entre los dos vectores). Sin embargo, no sé cómo funcionaría en dimensiones superiores.

EDIT2: Al escribir esta pregunta, yo estaba buscando el principio general, pero ahora, ya más o menos sé qué camino seguir (transformada de Fourier y, a continuación, buscar en las fases, o de convolución a través de la DFT) tengo algunas dudas acerca de los detalles y no quiero abrir una nueva pregunta sobre el mismo tema:

• En realidad no quiero envolver alrededor de los vectores, pero en lugar de buscar el mínimo de $k \in (k_{min},k_{max})$ (porque ya sé más o menos donde buscar) y en lugar de considerar el (cuadrado) a distancia es más significativo a considerar

  $\sum_{t = t_{min}}^{t_{max}} (s_t - b_{t+k})^2$ $t_{min}$ $t_{max}$ elegido tal que $0<t+k<=N$.

  No estoy seguro, si en este caso es sencillo el uso de la transformada de Fourier discreta.

• Una vez que lo tengo funcionando con el entero turnos de $k$, me gustaría perfeccionar el cambio por interpolación lineal. I. e. con

  $b_{t} := b_{n} + (t-n)(b_{n+1}-b_{n}) $ si $n<t<(n+1)$ $n \in \mathbb N$

  Tal vez la más sencilla sería la primera búsqueda de las mejores entero de turno, luego interpolar los vectores con un número suficiente de puntos intermedios y, a continuación, de nuevo de la búsqueda por entero turnos (los vectores son bastante suave, por lo que este debe encontrar la correcta mínimo). Sin embargo, tal vez hay una forma más inteligente manera de hacer esto.

PS: yo no quiero abrir una nueva pregunta en el mismo (o por lo menos estrechamente relacionado con el tema. Por otro lado, ya la tengo muy útil respuestas y no quiero invalidarlos. Si resulta que mis ediciones hecho la pregunta demasiado amplia, voy a considerar la posibilidad de dividirla en preguntas separadas.

Answer 1

En primer lugar, tenga en cuenta que si se multiplica el cuadrado, la suma de dos de los cuadrados de los términos que no dependen de $k$, por lo que efectivamente está maximizando $\sum_ts_tb_{t+k}$. Si lees un poco en las circunvoluciones y discreta de Fourier, usted encontrará que ellos le permiten encontrar el máximo en $N\log N$ tiempo en lugar de la $N^2$ tiempo que le lleva a tratar todos los valores de $k$.

Editar con un esbozo de lo que debe hacer: Realizar una transformada de Fourier en ambas secuencias, multiplicar la transformación con el complejo conjugado de la otra (la conjugación de la transformación corresponde a la inversión de la secuencia original con el fin de escribir su suma como una convolución), a continuación, realizar una inversa de la transformada de Fourier en el producto. Que le da su correlación cruzada suma como una función de la $k$, y se puede leer en el óptimo $k$ desde el valor con mayor magnitud.

Answer 2

Otro método es utilizar la traducción o el paso del tiempo en el teorema en el análisis de Fourier:

$$h(x) = f(x-x_0) \Leftrightarrow \mathcal{F}\{h\}(\omega) = e^{i2\pi x_0 \omega} \mathcal{F}\{f\}(\omega)$$ Vemos que la fase de aumento es una función lineal de la $\omega$.

1. Hacer una forma de FFT para cada señal,
2. Calcular las fases.
3. Calcular la derivada de w.r.t. $\omega$ de la diferencia de las fases.
4. Calcular la certeza de la medida a partir de los valores absolutos.
5. Calcular la media ponderada del paso 3 con la certeza de la medida anterior.

La certeza de medida es evitar el ruido o error numérico para influir en la solución. Partes del dominio de Fourier que tienen un bajo valor absoluto son mucho más sensibles al ruido, por lo tanto, la necesidad de tener una certeza de la medida.

Aquí está un ejemplo de 3er orden polinomio de ser desplazados, divulgó y luego corrigió: Aquí es la fase de estimación en azul y la certeza de la medida en rojo. Eje Y se estima que el desplazamiento de azul y x es la frecuencia con la DC está en el medio.