Efficient algorithm for computing area under convolution?

Question

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?

Answer 1

Note that

$$\sum_ny[n]=Y[0]$$

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

$$Y[k]=\prod_iX_i[k]$$

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

$$\sum_ny[n]=Y[0]=\prod_iX_i[0]$$

And since

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

$$\sum_ny[n]=\prod_i\sum_nx_i[n]$$

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
y=X(:,1);
for i=2:N, y=conv(y,X(:,i)); end
ys=sum(y);      % this should equal Xsp

[Xsp, ys]       % .. and it does