python - python中具有有限滤波器和狄拉克增量之和的快速一维卷积

Question

我需要计算以下卷积:

K 是一个非常简单的过滤器，它只是一个具有有限(!)大小的矩形框。我的数据是狄拉克三角洲的时间 t_i 的列表。

最简单的解决方案是将数据分箱并使用 numpy 或 scipys 卷积函数之一。然而，有没有更快的方法呢？我可以避免数据分箱并利用以下事实:a)我的过滤器大小有限(只是一个盒子)和b)我有一个时间点列表。因此，我只需检查我的时间点当前是否是滑动框的一部分。

因此，我正在寻找一种复杂度为 O(d*n) 且 d 为卷积分辨率大小的解决方案。因此，我希望比 O(b**2) 快得多，其中 b 是 bin 的数量。此外，由于 n << b，对于基于 fft 的卷积，仍然认为 O(d*n) 远小于 O(b * log b)。谢谢!

Answer 1

使用 cumulative sum of the signal 可以加速大型盒式过滤器的卷积速度:

信号示例:

import numpy as np

a = np.random.rand(10)
print a

输出:

[ 0.22501645  0.46078123  0.6788864   0.88293584  0.10379173  0.50422604
  0.4670648   0.22018486  0.96649785  0.44451671]

使用 default convolution function 进行卷积:

print np.convolve(a, np.ones(3) / 3, mode='valid')

输出:

[ 0.45489469  0.67420116  0.55520466  0.49698454  0.35836086  0.39715857
  0.55124917  0.54373314]

使用累积和进行卷积:

s = np.cumsum(np.concatenate(([0], a)))
print (s[3:] - s[:-3]) / 3

输出:

[ 0.45489469  0.67420116  0.55520466  0.49698454  0.35836086  0.39715857
  0.55124917  0.54373314]

<小时/>

cumsum 计算以及列表减法都是 O(n)，其中 n 是列表元素的数量，因此总计算时间是 O(n) 并且有趣的是独立于过滤器尺寸。