0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$
  • 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.

$\endgroup$
  • $\begingroup$ @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). $\endgroup$ – jomobro Mar 2 '17 at 16:22
  • $\begingroup$ @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)? $\endgroup$ – Maximilian Matthé Mar 3 '17 at 3:18
  • $\begingroup$ Your answer is clear, thank you. I've ammended the description and accepted your answer. $\endgroup$ – jomobro Mar 3 '17 at 10:50

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.