Fourier convolution of a histogram

Notation:

• $\mathcal F\left\{a\right\}$ denotes applying the discrete forward Fourier transform to the histogram $a$. Similarly for $\mathcal F^{-1}\left\{a\right\}$ and the discrete inverse Fourier transform.

• Capitals represent the discrete fast Fourier transform of the lower-case counterpart, e.g. $A = \mathcal F\left\{a\right\}$.

• The convolution of two histograms $f$ and $g$ is denoted $f\star g$.

Say I have histograms $a$ and $b$ with $a=[1,2,3]$ and $b=[4,5,6]$ (the heights) and the edges given by $e=[0,1,2,3]$. I.e. For the histogram $a$, there is one entry in the interval $[0,1)$, two entries in the interval $[1,2)$, and three entries in the interval $[2,3]$.

In order to perform a linear convolution as opposed to circular, $a$ must be padded such that len($a$) = len($a$) $+$ len($b$) $-1$. Similarly for $b$.

The convolution theorem states: $$\mathcal F\left\{a\star b\right\} = \mathcal F\left\{a\right\} \cdot \mathcal F\left\{b\right\}$$

So if $c = a\star b$ and $d = \mathcal F^{-1}\left\{A\cdot B\right\}$, then $c = d$.

On performing the Fourier convolution of the $a$ and $b$ mentioned above, I obtain a result if $d = [4,13,28,27,18]$.

My questions:

• Where does $c$ sit in terms of bins?
• Do I need to expand the bin edges, $e$, in some way?
• In which direction should I expand them?
• Should the extra bins have the same width as the originals (in this case, $1$)?

Intuition tells me that there should be an extra bin on either side of $e$, of the same width.

Furthermore, if I was to crop $c$ such that it has the same length as the unpadded kernel or the signal, where would I make the cut? Is this even possible?

• Actually, it does not really matter, if a or b are histograms or time domain sequences. However, I suppose you want to convolve to histograms to get the probability distribution of a random variable that is the sum of two variables. Then, its PDF is the convolution of the PDF of the original variables. But, considering the convolution of two time-domain sequences might make it easier to understand.

• The convolution theorem states fft(ab)=fft(a)*fft(b), where * denotes the N-point circular convolution and a and b are of length N points. Your statement of the convolution theorem fft(ab) = fft(a) . fft(b) is not correct.

• As I said, the convolution theorem in discrete domain corresponds to circular convolution. Most probably, you want to have a linear convolution. Then, you need to zero-pad a and b before applying the convolution theorem.

• If the original bins range from 0-3 (left-side of the interval), then the bin edges after convolution would range from 0-6, because the (linear) convolution has a length of (N+N-1) samples, where N is the length of the sequence (which is 4 in your case). You can also understand this from the fact that the convolution of the histogram is the PDF of the sum of both random variables: The minimum sum would be 0, the maximum sum would be 3+3=6.

For more information on circular convolution, you might have a look at an article I wrote or the Wikipedia entry.

• @Maximillian thanks for the reply. I have edited (with the help of another) my original question. Apologies for being unspecific, but does the convolution theorem I have now written apply to the non-circular discrete convolution? I also forgot to mention that I do zero-pad a before applying the fourier transform, such that its length is equal to len(a) + len(b) - 1, is that correct? I apply no such corrections to matrix b, but on conducting the fft, I force the method (in my case, numpy.fft.fft) to an output of length = len(A). – jomobro Mar 2 '17 at 16:22
• @jomobro Zero-Padding is still not mentioned in your original question. Your description in the comment sounds correct (forcing the fft output to a given length is equal to zero-padding (if the length is greater than the signal length). So then, what is still unclear from my answer (it also describes the case of using zero-padding/linear convolution)? – Maximilian Matthé Mar 3 '17 at 3:18