0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ What are the bounds on your summation? $\endgroup$ – Mehrdad Nov 5 '14 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. Nov 5 '14 at 12:36
  • $\begingroup$ @Mehrdad: I added a little Matlab/Octave script for clarity. $\endgroup$ – Matt L. Nov 5 '14 at 16:40
  • $\begingroup$ Why are you going through all elements, though? The question is about elements at n >= 0, not all n. $\endgroup$ – Mehrdad Nov 5 '14 at 19:25
  • $\begingroup$ @Mehrdad: Why would there be any elements for $n<0$? $\endgroup$ – Matt L. Nov 5 '14 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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