Hacker News Reader

No! This is a huge misconception that misses the essence of quantum mechanics. The Uncertainty is not due to finite information. It is an inherent property!

Uncertainty is due to (or better, "modeled by", because FT is math, not physics, and you could use wavelets or something instead), Fourier (and similar transforms) is a (bidirectional) function that maps (local) points to (dispersed) waves, and vice versa. This holds true even with infinite precision/information.

http://math.uchicago.edu/~may/REU2021/REUPapers/Dubey.pdf

"Qualitatively, this means a narrow function has a wide Fourier transform, and a wide function has a narrow Fourier transform. In either domain, a wider function means there is literally a wide distribution of data, so there always exists uncertainty in one domain."

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.

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.

> 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.

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 Uncertainty is not due to finite information. It is an inherent property!

That's what they said, though? Although I suppose it could stand to be emphasized more:

Physical quantities that have an uncertainty principle, such as position and momentum, are inherently related to each other by a Fourier transform. At a quantum-mechanical level, position is the Fourier transform of momentum, and vice versa - anything that constrains the position to a narrow interval (including but not limited to measuring it very precisely) inherently also smears momentum over a wide range of possibilities, even it was itself previously tighly constained (and, again, vice versa).

Apologies if you consider this pedantic, but I prefer to phrase it in terms of the wavefunctions in position and momentum, rather than position and momentum, unadorned:

At a quantum-mechanical level, the wavefunction in the position domain is the Fourier transform of the wavefunction in the momentum domain, and vice versa - anything that constrains the position wavefunction to a narrow interval inherently also smears the momentum wavefunction...

Again, apologies if this seems pedantic. I know enough about quantum mechanics to be dangerous, but am no expert, so pedantic wording helps me keep things straight.

> Apologies if you consider this pedantic

Honestly, if anything I'd say the pedatry goes the other way: pedantically, the wavefunction in the position domain is what a particle's position is (and respectively for momentum); it's making a distiction between the two (or pretending that there's anything in the position domain other than wave functions) that's insufficiently pedantic.

Need to be careful about the difference between the discrete Fourier transform and the Fourier series here.

It sounds like you're talking about the discrete Fourier transform, but making some statements which apply to Fourier series.

For the DFT, your N orthogonal "functions" are really just orthogonal vectors in C^N. In this case, if they're normalized appropriately, they certainly provide an orthonormal basis for C^N. But this is just linear algebra. The same is true of other orthogonal matrices which are discretized versions of systems of orthogonal functions. Like the discrete Wavelet transform, for example.

On the other hand, with the Fourier series, to represent any 2pi-periodic square integrable function, you need an expansion over an infinite sequence of orthogonal basis functions. In this case, the complex exponentials with integer frequency.

But you can't just take N arbitrary orthogonal functions and expect them to be meaningful when it comes to analyzing 2pi-periodic square integrable functions. Generating a system of orthogonal functions which truly spans L^2 for some set is more involved than what you do in linear algebra. You can read about Sturm-Liouville eigenvalue problems for one way. If you want a system of orthogonal polynomials, it's possible to use Gram-Schmidt, but notice that this doesn't make any sense for a periodic interval (and simply running Gram-Schmidt doesn't actually prove that the resulting sequence of polynomials actually spans L^2...). Also, note that the construction of the continuous wavelets is very different.

From this perspective you can look at it as comparable to the dot product concept of 'how much' of this thing is in that thing. You can also think of it as a 'rotation' operation - a change of basis into the frequency domain. That insight I garnered from graphics pioneer James Blinn.

A related funky thing is that if you choose the right functions you can engineer the analysis to require only shifts and adds which was a boon for making bespoke compression schemes on limited hardware. An example is the Slant transform used in an early Intel video codec. IIRC the Hadamard transform was also similarly useful where the coefficients were all 1s and -1s. I also seem to recall that some modern codecs have modes that use transforms that avoid the traditional DCT.

One last thing, I might have dreamt this but I recall reading a NASA tech report from the 70s or 80s outlining a video compression scheme that used a non DCT approach that could be calculated with simpler hardware without multiplication. I remember thinking, wow they were out front but never commercialized that.

> You can also think of it as a 'rotation' operation - a change of basis into the frequency domain.

Is this only a rotation between two discrete states, or do intermediate angles exist?

Nice, I never thought of PCM and CDMA in terms of basis functions, but you're totally right. Here are some links for anyone interested: https://en.wikipedia.org/wiki/Pulse-code_modulation#Modulati... https://en.wikipedia.org/wiki/Code-division_multiple_access#...

For further reading on orthogonal functions, here is a quick table that shows the bases used for the Fourier series (FS), Fourier transform (FT), and Discrete Fourier transform (DFT) from my linear algebra book: https://minireference.com/static/excerpts/fourier_transforma...

.. and wavelets replace the sin|cos functions that echo out to infinity with tapered funclets that have 'better' (for some value of) local modelling properties with fewer edge effects.

As noted by femto a key insight is there can be many types of basis functions.

I'm late and I only skimmed the other replies to see if someone else mentioned it, but being orthogonal is not sufficient. They must also form a complete basis. For instance, a set of sin functions with the same phase at 0 would not be complete because all of them would be 0 at x=0, and thus any function that is non-zero at x=0 could not be represented.

The second point to make is that the fourier transform can be exactly correct if the bandwidth of the signal being analyzed is finite. Or stated another way, signals with non-finite bandwidth require an infinite number of terms to represent. The famous case of the overshoot of reconstructed square waves is because square waves have an infinite bandwidth. Adding more terms can reduce the energy of the area under the overshoot to an arbitrarily small limit, but it can never be zero with a finite number of terms.

Yeah I chuckle every time people keep rediscovering Hilbert's functional analysis and the idea of orthogonal basis for functional spaces (goes well beyond Hilbert's widest dreams too!!).

Also Re the person who said no to you... Wave mechanics is written in Hilbert's language directly...

> you can replace the 'N' sin/cos functions used in Fourier analysis with any set of 'N' orthogonal functions

But why? It rarely makes sense to use such arbitrary functions that don't satisfy further properties! Typically you'd also want your functions to be the eigenfunctions of a symmetric linear operator which is naturally associated to your problem. Most often, the Laplacian (second derivative operator) of your domain. Thus the natural linear PDE on your space (diffusion, potential, wave equations and their variations) can be readily solved in the Fourier domain. The sequence of eigenvalues provides a lot of geometrical information about the shape of the domain.

Chebyshev polynomials are just sinusoids in disguise, but they also bring in some of the nice properties of polynomials and have helpful recurrence relations.

sure, and they are the eigenfunctions of a Sturm-Liouville operator!

Yes, you can think of so many methods of signal analysis as searching of the right set of overcomplete basis functions that give you a nice sparse representation for your problem (machine learning included).

The functions as a group must also be a basis for the function, them being orthogonal is insufficient for that. Any finite set is also often insufficient.

i never took functional analysis, but is orthogonal strictly required in a function space? in finite dim vector spaces, you don't need orthogonal to have a complete basis, it is just cleaner. You only need linear independence. (1,2), (0,1) is just as much a basis set of R^2 as (0,1) (1,0)