Hacker News Reader

Comment by sfpotter | Hacker News Reader

Mathematically, the Fourier transform obeys an uncertainty principle. Here is a nice and simple writeup:

https://www.johndcook.com/blog/2021/03/17/fourier-uncertaint...

The discrete Fourier transform (which is what OP is talking about) doesn't satisfy an uncertainty principle as far as I know. The concept doesn't really make sense.

You can talk about these concepts without bringing information or precision into the picture.

View on HN

Discrete FT is just an approximate of the the continuous FT, so it follows the same uncertainty principle. It doesn't have an additional uncertainty feature, jt just has the same approximation error that any finite model of an infinite phenomenon would have. That's not "uncertainty" because you can get arbitrarily precision by adding more samples. But Uncertainty means that it it impossible to get below the Uncertainty threshold, just like how if you squeeze a (theoretical) balloon full of incompressible fluid, you can never reduce its global volume to zero, even though you can reduce any local part of it to zero volume.

I'm happy to be wrong and learn about an uncertainty principle for the DFT. I'm just not aware of one. Your comment isn't very helpful for illuminating, absence any mathematical detail.

I've never heard of one either. The first time I was introduced to an uncertainty principle for the DFT was in time-frequency analysis which exists due to not being able to know both time domain and frequency domain information simultaneously. There is some shared concepts from QM, but they are not the same thing.

That a non periodic signal eg something which is nonzero only in a short span, requires a infinite number of periodic functions i.e fourier series/transform to represent is better considered as a limitation of the basis, it simply cannot represent such, only approximate it by a signal with a infinite period, which is not the same as non-periodic to mathematicians.

The definition of the signal implies its expression both in fourier and spatial basis exactly, with no uncertainty.

For this to have an interpretation as uncertainty requires that the functions themselves have that interpretation.

> The discrete Fourier transform doesn't satisfy an uncertainty principle as far as I know. The concept doesn't really make sense.

It certainly does. There are different formulations of it (by Donoho-Stark and by Tao, that I know of). They work when the domain is a finite abelian group.

I guess I'm not totally surprised. Could you give a reference? I'm not sure what this would mean exactly or what the utility would be.

I guess the original article [0] is a good starting reference. A post [1] in Tao's blog gives a nice overview.

If you just want a short statement of the discrete uncertainty principle: If you define the discrete Fourier transform F(u) for functions u defined on a finite abelian group G, and you denote by |S(u)| the cardinal of the support of u, then you have the inequalities:

  |S(u)| · |S(F(u))| >= |G|

and (as consequence)

  |S(u)| + |S(F(u))| >= 2 sqrt(|G|)

Notice that this contains as a particular case the discrete Fourier transform, where the abelian group in question is the integers modulo N.

This has a very practical and intutive interpretation: if the signal u is very localized, then its spectrum F(u) cannot be very localized at the same time, for their supports must be large enough (with respect to the total size of the domain).

[0] Donoho D. L. and Stark P. B., Uncertainty Principles and Signal Recovery, SIAM Journal of Applied Mathematics, 49 (1989), 906–931

[1] https://terrytao.wordpress.com/2010/06/25/the-uncertainty-pr...

Ah, very cool! Yeah, that makes sense. Appreciate you taking the time to write up a quick explanation and send a reference. I'll check it out.

Reply on news.ycombinator.com