0
$\begingroup$

If you have a discrete signal, say

[1,0,0,1]

and you convolve it linearly with itself, you will quickly get a Gaussian distribution.

Why does it not hold for circular convolution?

$\endgroup$
2
  • $\begingroup$ For circular convolution you will always stay with 4 samples. That's not enough to do any meaningful of statistics on and a Gaussian is a statistical phenomenon. $\endgroup$
    – Hilmar
    Jul 24, 2022 at 12:15
  • $\begingroup$ The premise of this question is wrong. Convolving any signal with itself many times does not create something that is converging to a Gaussian distribution. $\endgroup$ Jul 25, 2022 at 21:08

2 Answers 2

3
$\begingroup$

Convolving $x = [1,0,0,1]$ with itself repeatedly will not generate a "Gaussian distribution".

\begin{align} x \star x &= [1,0,0,2,0,0,1]\\ x \star x \star x &= [1,0,0,3,0,0,3,0,0,1] \end{align}

and so on.

Convolving $y = [1,1]$ with itself will, eventually, generate something that looks like the Gaussian shape.

import numpy as np
import matplotlib.pyplot as plt

x = [1,1]
N = 20
xx = x.copy()

for idx in np.arange(N):
    xx = np.convolve(xx,x)
    
plt.plot(xx)

Convolving 20 times

The support (length) of the output of all those convolutions grows and grows with each new convolution.

When circular convolution is done, the support cannot grow to be longer than the chosen length of the convolution (in my code below, the length of the FFT used to implement the convolution).

import numpy as np
import matplotlib.pyplot as plt

def my_convolve(x,y,Nfft):
    X = np.fft.fft(x,Nfft)
    Y = np.fft.fft(y,Nfft)
    Z = X*Y
    return np.fft.ifft(Z,Nfft)

x = [1,1]

N = 20

xx = x.copy()

for idx in np.arange(N):
    xx = np.real(my_convolve(xx,x, 16))
    
plt.plot(xx)

Circularly convolved shape

As a result, the "tails" (ends) of the output will overlap due to the circularity.

$\endgroup$
1
$\begingroup$

Circular convolution is simply linear convolution that "wraps around"

As we know, convolving $A$ and $B$ with supports $S_A$ and $S_B$ yields something with support $S_A + S_B - 1$, worst case. So our pal above gets wider and wider, arms and legs overlap, and realization strikes it's time to diet.

The two convolutions can be forced into agreement by placing the "portals" farther apart: zero-padding. The phenomenon can then be understood in frequency domain:

See the deal? Step by step:

  1. Get signal
  2. Center-pad. Per how DFT works, with out = conv(x, h), out[i] is with h centered at x[i] if h itself is centered at index 0, this way we guarantee our convolution doesn't "drift" over successive iterations.
  3. Center padding in frequency $\Leftrightarrow$ interpolating in time. And vice versa, from duality. So, by padding, we're upsampling the spectrum.
  4. Circular convolution in time $\Leftrightarrow$ multiplication in frequency. So, the spectrum squares itself.

Summarized, $1)$ interpolate, $2)$ square, $3)$ repeat. The key is in step 2: note, where is the final peak in frequency? If we zoom on orange plot of first frame, we'll notice it's where the original peaked. Put differently, we're really just doing a fancified $[1, 2, 3, 1]^\text{large}$, attenuating everything but the most dominant bin.

However, this "fancifying" (interpolation) makes all the difference. Without it, we can predict - and confirm - we converge to a pure sine:

If we are indeed correct, then it should be possible to construct a signal whose linear convolution fails to converge to a Gaussian, by making an x whose pad+squaring always produces at least two equal frequency peaks. An easy example is unit impulse.

This provides an intuition on why it's bell-shaped, not why it's specifically Gaussian. Latter is explained in the Central Limit Theorem, that exploits the $n$-th power of the Fourier transform ... or so it's said (incidentally agreeing with my reasoning), I never studied the CLT in detail.

$\endgroup$
1
  • $\begingroup$ PS, rfft should say |rfft| $\endgroup$ Jul 23, 2022 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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