Consider $N$ discrete signals $x_1(n), x_2(n), \ldots,x_N(n)$ each a bounded support of size $M$.

To convolve them, we can zero-pad each of them, multiply their FFTs, and take the result's inverse FFT.
I believe this requires taking $N$ FFTs of length $N(M-1)+1$ each, taking $O(MN\,\log(MN))$ time.

However, what I need isn't the full convolution. I only need the area under the convolution above zero: $$\sum_{k=0}^\infty y(n)$$ assuming $y$ is the convolution of our signals: $$y = x_1 * x_2 * \ldots * x_N$$

Is there any algorithm that allows me to compute this value with a better time complexity than that required for computing the full convolution, or are the problems equally difficult?


1 Answer 1


Note that


where $Y[k]$ is the DFT of $y[n]$. Since


with $X_i[k]$ the DFT of $x_i[n]$ (appropriately zero-padded), you have


And since

$$X_i[0]=\sum_nx_i[n]$$ you get the final result


the computation of which requires $N-1$ multiplications and $N(M-1)$ additions.

This little Matlab script illustrates how it works:

M=100;          % length of each signal
N=10;           % number of different signals
X=randn(M,N);   % each column of X contains a signal
Xs=sum(X);      % sums over each signal
Xsp=prod(Xs);   % product of the sums = desired result

% compute convolution of N signals
for i=2:N, y=conv(y,X(:,i)); end
ys=sum(y);      % this should equal Xsp

[Xsp, ys]       % .. and it does
  • $\begingroup$ What are the bounds on your summation? $\endgroup$
    – user541686
    Commented Nov 5, 2014 at 12:20
  • $\begingroup$ @Mehrdad: Well, the product is over all $N$ signals, and the sums simply go over all elements of the respective signals. $\endgroup$
    – Matt L.
    Commented Nov 5, 2014 at 12:36
  • $\begingroup$ @Mehrdad: I added a little Matlab/Octave script for clarity. $\endgroup$
    – Matt L.
    Commented Nov 5, 2014 at 16:40
  • $\begingroup$ Why are you going through all elements, though? The question is about elements at n >= 0, not all n. $\endgroup$
    – user541686
    Commented Nov 5, 2014 at 19:25
  • $\begingroup$ @Mehrdad: Why would there be any elements for $n<0$? $\endgroup$
    – Matt L.
    Commented Nov 5, 2014 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.