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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$
8
  • $\begingroup$ What are the bounds on your summation? $\endgroup$ 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$ Commented Nov 5, 2014 at 12:36
  • $\begingroup$ @Mehrdad: I added a little Matlab/Octave script for clarity. $\endgroup$ 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$ Commented Nov 5, 2014 at 19:25
  • $\begingroup$ @Mehrdad: Why would there be any elements for $n<0$? $\endgroup$ Commented Nov 5, 2014 at 21:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.