Support of a signal and its FFT
The previous post looked at the Fourier uncertainty principle. This post looks at an analogous result for the discrete Fourier transform.
The uncertainty principle for the (continuous) Fourier transform says a signal cannot be localized in both the time domain and the frequency domain. The more bunched up a function is, the more spread out its transform is.
The discrete analog of the Fourier uncertainty principle given in [1] says something similar, that a signal and its discrete Fourier transform cannot both be concentrated. The difference is in how concentration is measured.
In the previous post, concentration was measured in terms of variance, very similar to how variance is defined for random variables. But in the discrete case, we do something simpler: we count how many terms are non-zero.
The support of a function is the set of points where the function is not zero. A highly concentrated function is one with small support. The discrete Fourier uncertainty principle says that a non-zero signal and its Fourier transform cannot both have small support.
Specifically, let f be a sequence of length N and let F be its discrete Fourier transform. Then
| support of f | * | support of F | >= N.
where | S | is the number of elements in a set S.
As with the continuous case, we have a lower bound on the product of the uncertainty of something and its Fourier transform. The discrete form is simpler in that the lower bound does not depend on one's convention for defining the Fourier transform. As with the continuous case, there are many conventions for defining the DFT. But these variations in convention don't effect counting zeros.
ExamplesAs pointed out in [1], you can construct examples where the inequality above holds exactly. These sequences are evenly spaced constants. If N = pq then the FFT of a sequence of 1s every p places will have non-zero elements every q places.
For example,
>>> import numpy as np >>> np.fft.fft([1,0,0,1,0,0]) array([2, 0, 2, 0, 2, 0])
In this instance, the original sequence has support of size 2, its transform has support of size 3, and the product of the support sizes is their length 6.
Note that multiplying a Python list (not a NumPy array) by an integer concatenates the list to itself that many times. The example above could be read as saying the FFT of
[1, 0, 0]*2
is
[2, 0]*3
.
As another example, we can show that the FFT of
[1, 0, 0, 0, 0]*3
is
[3, 0, 0]*5
.
The code below is complicated a bit by NumPy bookkeeping, but essentially it shows that the FFT of [1,0,0,0,0]*3 is [3,0,0]*5.
>>> x = np.fft.fft([1, 0, 0, 0, 0]*3) >>> y = 3*np.array([1, 0, 0]*5, dtype=complex) >>> np.all(x == y) True
The lower bound on the product of support sizes is tight for multiples and rotations of sequences like those above.
For example,
>>> np.fft.fft([0, 7, 0, 0, 7, 0]) array([14. +0.j , 0. +0.j , -7.-12.12435565j, 0. +0.j , -7.+12.12435565j, 0. +0.j ])
Here we took the first example, changed the 1s to 7s, and rotated everything one position. The FFT is a little more complicated in this case, but it's still the case that the input has support of size 2 and the output has support of size 3.
The only sequences for which the discrete uncertainty principle lower bound is tight are those like we've seen above: multiples and rotations of evenly spaced 1s. For any other sequences the inequality above is strict. For example, here's what happens if our 1's are not evenly spaced.
>>> np.fft.fft([1, 0, 0, 0, 1, 0]) array([2. +0.00000000e+00j, 0.5+8.66025404e-01j, 0.5-8.66025404e-01j, 2. -5.55111512e-17j, 0.5+8.66025404e-01j, 0.5-8.66025404e-01j])
Now the input has support 2, the output has support 6.
Related posts[1] David L. Donoho and Philip B. Stark. Uncertainty Principles and Signal Recovery. SIAM Journal on Applied Mathematics, June 1989, Vol. 49, No. 3, pp. 906-931
The post Support of a signal and its FFT first appeared on John D. Cook.