python - 如何使用 Numpy 更快地最小化这个距离？ (找到两个信号彼此接近的移位索引)

Question

给定一个长度为 1000 的数组 x 和长度为 500k 的 y，我们可以计算 索引 k ，其中 x 最接近“y-按 k 索引移动”:

mindistance = np.inf  # infinity
for k in range(len(y)-1000):
    t = np.sum(np.power(x-y[k:k+1000],2))
    if t < mindistance:
        mindistance = t
        index = k
 print index
 # x is close to y[index:index+N]

根据我的测试，这似乎在数字上成本很高。 是否有一种聪明的numpy方法可以更快地计算它？

<小时/>

注意:似乎如果我将 x 的长度从 1000 替换为 100，计算所需的时间不会有太大变化。缓慢似乎主要来自 for k in range(...) 循环。如何加快速度？

Answer 1

这可以通过 np.correlate 来完成它计算的不是相关系数(正如人们可能猜测的那样)，而是简单地计算乘积之和，例如 x[n]*y[m](这里 m 是 n 加上一些偏移)。自从

(x[n] - y[m])**2  = x[n]**2 - 2*x[n]*y[m] + y[m]**2

通过将 x 的平方和与 y 的一部分相加，我们可以得到差平方和。 (实际上，x[n]**2 的总和不依赖于移位，因为我们总是得到 np.sum(x**2) ，但我还是将其全部包含在内。)y**2 的一部分的总和也可以通过这种方式找到，通过将 x 替换为 all -ones 大小相同的数组，以及 y 和 y**2。 这是一个例子。

import numpy as np
x = np.array([3.1, 1.2, 4.2])
y = np.array([8, 5, 3, -2, 3, 1, 4, 5, 7])
diff_sq = np.sum(x**2) - 2*np.correlate(y, x) + np.correlate(y**2, np.ones_like(x))
print(diff_sq)

这会打印出[39.89 45.29 11.69 39.49 0.09 12.89 23.09]，这确实是从x到y的各个部分所需的距离。使用argmin选择最小的。