5 ms·

Fractional Fourier transform

32 points by dustingetz 3y ago

fallingfrog 3y ago
If you were to set this up as a Schrödingers classical wave equation with a periodic boundary condition, (real and imagined parts) in one dimension, it would evolve exactly in this way into its own Fourier transform and then back. (Referring to the image of the square wave evolving into a sinc function halfway down the page). I only know this because I simulated it, I don’t know why that is the case. Perhaps someone better at the math can fill in the details.
deleted 3y ago
[deleted]
dustingetz 3y ago
fractional FT is the uncertainty principle then? you can know position locally, or momentum locally, or you can know them both blurrily with a rotated basis in between
- adonovan 3y ago
  _Ordinary_ FT is the uncertainty principle. Fourier analysis of waves can tell you the frequency or the phase, but not both to arbitrary precision: the more precisely you can tell when the signal occurred (phase), the less precisely you can tell its pitch. (The spectrum of a sharp square wave is smeared across all the frequencies.) The QM wavefunction is a wave, and so the same applies. Phase is position and frequency is energy is velocity. So you can't know the position and the speed.
  - ur-whale 3y ago
    > _Ordinary_ FT is the uncertainty principle. Yeah, I was about to jump in and say the same thing. More precisely, in Fourier theory (_regular_ Fourier Theory, not fractional), there is an inequality that can be proven independently of any physical interpretation and which directly implies the uncertainty principle as it's called in physics and QM. In other words, Heisenberg's uncertainty principle has basically nothing to do with physics or quantum mechanics, it's a basic property of the Fourier transform: As soon as two physical quantities are the FT of one another (the FT being almost an involution, i.e. the FT and the inverse FT are almost the same thing), they have to obey the uncertainty principle. Stated simply: the more localized a function (e.g. a small hump and almost zero everywhere else), the more spread-out its FT. And conversely: the more spread-out, regular and slow moving a function, the more localized its FT will be (all energy concentrated in a small region of the freq domain). Which, if you think about it for 5mn is quite intuitive: a function that is almost zero everywhere and suddenly exhibits a hump has to have a sudden rate of change. Which - very visually - implies high frequency components (high rate of change = high freq components).
    - wiml 3y ago
      The thing that quantum mechanics introduces here is the idea that there are conjugate variables (things which are the FT of each other), and that position and momentum is just one such pair.
      - ur-whale 3y ago
        > is the idea that there are conjugate variables (things which are the FT of each other) God forbid that physicists would use the existing lingo instead of inventing their own and create more confusion.
bigmattystyles 3y ago
meta I love the fascination with the Fourier transform on this site even though I would venture most of us haven't thought of it since college if even exposed to it at all then. My hunch is that it's the first math concept many of us encountered that's not straightforward. Even integrating and taking derivatives is mostly procedural and intuitive. Plus it's so insanely cool when you understand the power of changing domains. I'm no expert, I'm a failed EE turned mediocre programmer, but I'm equally always in awe of it. Its history is so fascinating, especially how the FFT came up - I saw a great Veritasium video on it.
- dustingetz 3y ago
  afaict fourier theory is basically the heart of physics. What is energy? frequency! Why do things oscillate? Force fields and energy conservation.
- ur-whale 3y ago
  > I would venture most of us haven't thought of it since college Not sure what kind of engineering work you are doing, but I can vouch that your assessment is incorrect in general for any kind of engineering work, be it CS related or not. I've (n=1) had to think about the FT a very large number of times in my engineering career, be it for image processing, computer graphics, or any time there is some sort of time-based signal to deal with and understand. A bunch of colleagues working on radar tech, FT and related concepts are their daily bread. Anyone doing actual EE - same thing, it's always there lurking in the background Now sure, if what you do all day is react-type stuff, then yeah, maybe. Physicists - same thing, how can you possibly look at any kind of physical process and not at the very least think how the thing looks like in the frequency domain?
  - bigmattystyles 3y ago
    I should say I'm also n=1 :-)
- sudosysgen 3y ago
  The DFT/FFR is actually very much useful and transformative to computer science. It is, along with Karatsuba's algorithm, the basis for a lot of the triumphs of computer science. Want to do polynomial interpolation? FFT. Want to do convolutions on large-ish images? FFT. Want to compress audio/images/video? FFT, or FFT-ish. Want to break RSA on a quantum computer? FFT also (well, QFT). Any algorithms class that left over the Fourier transform is, in my opinion, a small tragedy. That said, I personally think that integration is less straightforward than the Fourier transforms. It's the first task you're given that requires creativity, as there is no practical algorithm for it (sometimes, there isn't even really a way to do it). If you try to approach the Fourier transform as a piece of linear algebra, seeing it as an orthonormal transformation to periodic vectors/functions, it's a lot more intuitive.
mikewarot 3y ago
I don't understand the math, but the ability to rotate the time/frequency of a sample of data to filter out chirps and things like that via DSP sounds damned handy in some cases. I started learning DSP playing around with audio signals in GNU Radio. Filtering gets a lot easier if you have IQ signals, so you can shift the frequencies up or down below zero, and back up. There are types of filtering you can do that way, that just won't work with only REAL signals. This is another powerful tool for that toolbox. Thanks! This looks like an interesting read: FRFT based Method of Modulation Techniques for SDR https://inpressco.com/wp-content/uploads/2013/09/Paper59304-307.pdf https://inpressco.com/wp-content/uploads/2013/09/Paper59304-...
- akomtu 3y ago
  It looks like this FRFT is the good old DFT spectrogram rotated by an arbitrary angle.
dsign 3y ago
Slightly off-topic, unpopular opinion: the coolest area of software development today, as in "look-at-us-babe-we-are-still-rocking-it," is audio plugins for music producers. And I say this because, despite attempts to the contrary, most plugins are sold for a fixed amount of cash in a pay-once use-forever fashion. Audio-plugin developers not only get to treat their customers as something else other than subscribers, they also get to play with cool mathematical toys like Fourier Transforms, Wavelets, Short-time-fourier-transform, and a zillion others. It's the only industry where geeks get to be rockstars to the rockstars.
- monetus 3y ago
  It really is a unique environment, and a lot of fun for everyone involved. I'm trying to think of another niche like it, and I can't exactly. Very feel-good, look-at-this-secret-sauce, vibes all the way through from the musicians to the sdk developers.
jesuslop 3y ago
A bare-bones case of Fourier transform would be the discrete finite FT, that is just multiplying by a well crafted matrix W as in [1]. So here it looks to me that the fractional transform would be a rational exponent of W, W^r, r rational. For instance W^(2/3)=(W^(1/3))^2, with W^(1/3)=X and X^3=W hopefully a well-defined X. [1] https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix
- jesuslop 3y ago
  A bit more techy thing to said is that Plancherel theorem here simply means that W in parent comment is unitary, so we can understand fractional FTs applying Stone's theorem for uniparametric unitary groups (the parameter here the order of the fractional, a scalar). The theorem guarantees that there is an infinitesimal generator H (a matrix) such that W^t = e^(tH).

32 points by dustingetz 3y ago

If you were to set this up as a Schrödingers classical wave equation with a periodic boundary condition, (real and imagined parts) in one dimension, it would evolve exactly in this way into its own Fourier transform and then back. (Referring to the image of the square wave evolving into a sinc function halfway down the page). I only know this because I simulated it, I don’t know why that is the case. Perhaps someone better at the math can fill in the details.

deleted 3y ago

[deleted]

dustingetz 3y ago

fractional FT is the uncertainty principle then? you can know position locally, or momentum locally, or you can know them both blurrily with a rotated basis in between

adonovan 3y ago
_Ordinary_ FT is the uncertainty principle. Fourier analysis of waves can tell you the frequency or the phase, but not both to arbitrary precision: the more precisely you can tell when the signal occurred (phase), the less precisely you can tell its pitch. (The spectrum of a sharp square wave is smeared across all the frequencies.) The QM wavefunction is a wave, and so the same applies. Phase is position and frequency is energy is velocity. So you can't know the position and the speed.
- ur-whale 3y ago
  > _Ordinary_ FT is the uncertainty principle. Yeah, I was about to jump in and say the same thing. More precisely, in Fourier theory (_regular_ Fourier Theory, not fractional), there is an inequality that can be proven independently of any physical interpretation and which directly implies the uncertainty principle as it's called in physics and QM. In other words, Heisenberg's uncertainty principle has basically nothing to do with physics or quantum mechanics, it's a basic property of the Fourier transform: As soon as two physical quantities are the FT of one another (the FT being almost an involution, i.e. the FT and the inverse FT are almost the same thing), they have to obey the uncertainty principle. Stated simply: the more localized a function (e.g. a small hump and almost zero everywhere else), the more spread-out its FT. And conversely: the more spread-out, regular and slow moving a function, the more localized its FT will be (all energy concentrated in a small region of the freq domain). Which, if you think about it for 5mn is quite intuitive: a function that is almost zero everywhere and suddenly exhibits a hump has to have a sudden rate of change. Which - very visually - implies high frequency components (high rate of change = high freq components).
  - wiml 3y ago
    The thing that quantum mechanics introduces here is the idea that there are conjugate variables (things which are the FT of each other), and that position and momentum is just one such pair.
    - ur-whale 3y ago
      > is the idea that there are conjugate variables (things which are the FT of each other) God forbid that physicists would use the existing lingo instead of inventing their own and create more confusion.

bigmattystyles 3y ago

meta I love the fascination with the Fourier transform on this site even though I would venture most of us haven't thought of it since college if even exposed to it at all then. My hunch is that it's the first math concept many of us encountered that's not straightforward. Even integrating and taking derivatives is mostly procedural and intuitive. Plus it's so insanely cool when you understand the power of changing domains. I'm no expert, I'm a failed EE turned mediocre programmer, but I'm equally always in awe of it. Its history is so fascinating, especially how the FFT came up - I saw a great Veritasium video on it.

dustingetz 3y ago
afaict fourier theory is basically the heart of physics. What is energy? frequency! Why do things oscillate? Force fields and energy conservation.
ur-whale 3y ago
> I would venture most of us haven't thought of it since college Not sure what kind of engineering work you are doing, but I can vouch that your assessment is incorrect in general for any kind of engineering work, be it CS related or not. I've (n=1) had to think about the FT a very large number of times in my engineering career, be it for image processing, computer graphics, or any time there is some sort of time-based signal to deal with and understand. A bunch of colleagues working on radar tech, FT and related concepts are their daily bread. Anyone doing actual EE - same thing, it's always there lurking in the background Now sure, if what you do all day is react-type stuff, then yeah, maybe. Physicists - same thing, how can you possibly look at any kind of physical process and not at the very least think how the thing looks like in the frequency domain?
- bigmattystyles 3y ago
  I should say I'm also n=1 :-)
sudosysgen 3y ago
The DFT/FFR is actually very much useful and transformative to computer science. It is, along with Karatsuba's algorithm, the basis for a lot of the triumphs of computer science. Want to do polynomial interpolation? FFT. Want to do convolutions on large-ish images? FFT. Want to compress audio/images/video? FFT, or FFT-ish. Want to break RSA on a quantum computer? FFT also (well, QFT). Any algorithms class that left over the Fourier transform is, in my opinion, a small tragedy. That said, I personally think that integration is less straightforward than the Fourier transforms. It's the first task you're given that requires creativity, as there is no practical algorithm for it (sometimes, there isn't even really a way to do it). If you try to approach the Fourier transform as a piece of linear algebra, seeing it as an orthonormal transformation to periodic vectors/functions, it's a lot more intuitive.

mikewarot 3y ago

I don't understand the math, but the ability to rotate the time/frequency of a sample of data to filter out chirps and things like that via DSP sounds damned handy in some cases. I started learning DSP playing around with audio signals in GNU Radio. Filtering gets a lot easier if you have IQ signals, so you can shift the frequencies up or down below zero, and back up. There are types of filtering you can do that way, that just won't work with only REAL signals. This is another powerful tool for that toolbox. Thanks! This looks like an interesting read: FRFT based Method of Modulation Techniques for SDR https://inpressco.com/wp-content/uploads/2013/09/Paper59304-307.pdf https://inpressco.com/wp-content/uploads/2013/09/Paper59304-...

akomtu 3y ago
It looks like this FRFT is the good old DFT spectrogram rotated by an arbitrary angle.

dsign 3y ago

Slightly off-topic, unpopular opinion: the coolest area of software development today, as in "look-at-us-babe-we-are-still-rocking-it," is audio plugins for music producers. And I say this because, despite attempts to the contrary, most plugins are sold for a fixed amount of cash in a pay-once use-forever fashion. Audio-plugin developers not only get to treat their customers as something else other than subscribers, they also get to play with cool mathematical toys like Fourier Transforms, Wavelets, Short-time-fourier-transform, and a zillion others. It's the only industry where geeks get to be rockstars to the rockstars.

monetus 3y ago
It really is a unique environment, and a lot of fun for everyone involved. I'm trying to think of another niche like it, and I can't exactly. Very feel-good, look-at-this-secret-sauce, vibes all the way through from the musicians to the sdk developers.

jesuslop 3y ago

A bare-bones case of Fourier transform would be the discrete finite FT, that is just multiplying by a well crafted matrix W as in [1]. So here it looks to me that the fractional transform would be a rational exponent of W, W^r, r rational. For instance W^(2/3)=(W^(1/3))^2, with W^(1/3)=X and X^3=W hopefully a well-defined X. [1] https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix

jesuslop 3y ago
A bit more techy thing to said is that Plancherel theorem here simply means that W in parent comment is unitary, so we can understand fractional FTs applying Stone's theorem for uniparametric unitary groups (the parameter here the order of the fractional, a scalar). The theorem guarantees that there is an infinitesimal generator H (a matrix) such that W^t = e^(tH).