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.

## Examples

As 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

I’ve got an admittedly niggling question: as far as I know “FFT” stands for “Fast Fourier Transform”. Did you intentionally use that in the title?

My guess is that most software packages include the “fast” in name, because the algorithm used can be significant there, so we’ve all started referring to the “FFT”.

I just had to smile because in a class of 60 students I could see one of them get the idea from the title that a “slow” Fourier transform has a different support. Teaching has made me look for all the ways a statement could be misunderstood. :-)

Since DFT is almost always computed via the FFT, most people use the latter to refer to the former.

I did deliberately use “FFT” in the title rather than “DFT” because I suspect many readers would recognize the former and not the latter. Sometimes it’s helpful to make the distinction between the DFT transformation and the FFT algorithm for computing that transformation. I generally go into more detail when I have more room, i.e. I’ll be more explicit in the body of a post than in a headline, and more explicit in a blog post than on Twitter.

Uncertainty minimizers are found in:

Przebinda, Tomasz & DeBrunner, Victor & Ozaydin, Murad. (2001). The optimal transform for the discrete Hirschman uncertainty principle. Information Theory, IEEE Transactions on. 47. 2086 – 2090. 10.1109/18.930948.