6 ms·

A funky thing is that you can replace the 'N' sin/cos functions used in Fourier analysis with any set of 'N' orthogonal functions (aka basis functions). In thi

by femto 4y ago

A funky thing is that you can replace the 'N' sin/cos functions used in Fourier analysis with any set of 'N' orthogonal functions (aka basis functions). In this context, a Fourier transform is just a bunch of correlations of the function to be analysed with each basis function. Two functions are orthogonal if their correlation is zero. PCM is "Fourier analysis" with impulse functions in place of sin/cos. CDMA replaces sin/cos with a set of (almost) orthogonal functions with a wide bandwidth. From an information perspective, orthogonality of the basis functions means each component/coefficient is giving you new information about the signal. In real life you can only compute a finite number of coefficients, meaning you must have a finite amount of information, so there is an inherent uncertainty in the relationship between the signal being analysed and the output of Fourier analysis. (Physical quantities that have an uncertainty principle, such as position and momentum, are related to each other by a Fourier transform.)

sfpotter 4y ago
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.
lupire 4y ago
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 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."
- sfpotter 4y ago
  Mathematically, the Fourier transform obeys an uncertainty principle. Here is a nice and simple writeup: https://www.johndcook.com/blog/2021/03/17/fourier-uncertainty-principle/ 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.
  - lupire 4y ago
    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.
    - sfpotter 4y ago
      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.
boxfire 4y ago
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...
enriquto 4y ago
> 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.
- Rayhem 4y ago
  Chebyshev polynomials are just sinusoids in disguise, but they also bring in some of the nice properties of polynomials and have helpful recurrence relations.
  - enriquto 4y ago
    sure, and they are the eigenfunctions of a Sturm-Liouville operator!
gmadsen 4y ago
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)
midjji 4y ago
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.
salty_biscuits 4y ago
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).
tasty_freeze 4y ago
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.
defrost 4y ago
.. 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.
djmips 4y ago
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.
- zardo 4y ago
  > 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?
ivansavz 4y ago
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#Modulation https://en.wikipedia.org/wiki/Pulse-code_modulation#Modulati... https://en.wikipedia.org/wiki/Code-division_multiple_access#Example 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_transformations.pdf#page=2 https://minireference.com/static/excerpts/fourier_transforma...

by femto 4y ago

sfpotter 4y ago

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.

lupire 4y ago

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

sfpotter 4y ago
Mathematically, the Fourier transform obeys an uncertainty principle. Here is a nice and simple writeup: https://www.johndcook.com/blog/2021/03/17/fourier-uncertainty-principle/ 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.
- lupire 4y ago
  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.
  - sfpotter 4y ago
    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.

boxfire 4y ago

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

enriquto 4y ago

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

Rayhem 4y ago
Chebyshev polynomials are just sinusoids in disguise, but they also bring in some of the nice properties of polynomials and have helpful recurrence relations.
- enriquto 4y ago
  sure, and they are the eigenfunctions of a Sturm-Liouville operator!

gmadsen 4y ago

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)

midjji 4y ago

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.

salty_biscuits 4y ago

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

tasty_freeze 4y ago

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.

defrost 4y ago

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

djmips 4y ago

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.

zardo 4y ago
> 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?

ivansavz 4y ago

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#Modulation https://en.wikipedia.org/wiki/Pulse-code_modulation#Modulati... https://en.wikipedia.org/wiki/Code-division_multiple_access#Example 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_transformations.pdf#page=2 https://minireference.com/static/excerpts/fourier_transforma...