我需要计算以下卷积:
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)。谢谢!
最佳答案
使用 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) 并且有趣的是独立于过滤器尺寸。
关于python - python中具有有限滤波器和狄拉克增量之和的快速一维卷积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26121770/