Fast 1D convolution with finite filter and sum of dirac deltas in python
Question: I need to compute the following convolution:

![enter image description here](http://i.stack.imgur.com/0bDzy.gif)

And K is a very simple filter, that is simply a rectangular box with finite
(!) size. My data is a list of the times t_i of the Dirac deltas.

The straightforward solution would be to bin the data and use one of numpy or
scipys convolution functions. Yet, is there a quicker way? Can I avoid the
binning of the data and take advantage of the fact that a) my filter is finite
in size (just a box) and b) I have a list of time points. Thus, I just have to
check whether my time points are currently part of the sliding box, or not.

So, I am looking for a solution that has complexity O(d*n) with d the size of
the resolution of the convolution. Thus, I want to be much faster than O(b**2)
with b the number of bins. Moreover, since n << b, it still holds that O(d*n)
is much less than O(b * log b) for fft based convolution. Thanks!


Answer: Convolutions with large box filters can be speed up using a [cumulative sum of
the signal](http://en.wikipedia.org/wiki/Summed_area_table):

**Example signal:**

    
    
    import numpy as np
    
    a = np.random.rand(10)
    print a
    

Output:

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

**Convolution using the[default convolution
function](http://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html):**

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

Output:

    
    
    [ 0.45489469  0.67420116  0.55520466  0.49698454  0.35836086  0.39715857
      0.55124917  0.54373314]
    

**Convolution using the cumulative sum:**

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

Output:

    
    
    [ 0.45489469  0.67420116  0.55520466  0.49698454  0.35836086  0.39715857
      0.55124917  0.54373314]
    

* * *

Both the `cumsum` computation as well as the list subtraction are O(n) with n
being the number of list elements, so the overall computing time is O(n) and -
interestingly - independent of the filter size.

