[HN Gopher] Demystifying Fourier analysis
___________________________________________________________________
Demystifying Fourier analysis
Author : dsego
Score : 225 points
Date : 2022-11-17 09:20 UTC (13 hours ago)
(HTM) web link (dsego.github.io)
(TXT) w3m dump (dsego.github.io)
| johndoe0815 wrote:
| Nice! I used this website by Jack Schaedler as an intro in my
| signal processing course, also highly recommended:
|
| https://jackschaedler.github.io/circles-sines-signals/index....
| marmetio wrote:
| Nice. I used All Signal Processing to get an intuitive feel
| through visualization.
|
| There's a website, but the videos are more easily accessible
| through YouTube. Still worth checking out for the table of
| contents and quizzes.
|
| https://youtube.com/user/allsignalprocessing
| raxxorraxor wrote:
| I only really understood it while looking at imaging. How the
| base frequencies overlap to form an image and how the phase
| information is much more important for signal reconstruction than
| the amplitude.
|
| While images have an additional dimension it still helped me to
| really figure out what was going on.
|
| Since it is so well documented I recommend looking at DCT that is
| employed in JPG. The principle is the same, just the frequency
| disection works a bit different.
| geokon wrote:
| I thought this was really well done without any misleading
| oversimplifications. I do think the author missed the central
| trick of the Fourier Transform though. He's right in pointing out
| the sounds aren't a bunch of sine waves (typically), but the
| trick is that Fourier frequencies are cleverly chosen so they're
| all orthogonal (ie. you can't represent any of them in terms of
| the other). The complex number form turns out to give you one of
| the simplest representations of this set of frequencies.
|
| I was wondering if anyone has a more rigorous explanation of the
| in-between frequencies part. I tried to follow this explanation
| from a great concise but rigorous book hosted online
|
| https://ccrma.stanford.edu/~jos//dft/Frequencies_Cracks.html
| https://ccrma.stanford.edu/~jos//proj/Bessel_Functions.html
|
| but unfortunately in this section it seems to gloss over the
| proof (or maybe I don't get it). It just sorta tells you "Bessel
| functions"! Which isn't very satisfying - especially when you
| have no idea what a Bessel function is..
|
| I have a problem where my signal (which has a bit of noise) has
| maybe one (or several) strong non-multiple frequency (I likely
| know their approximately values a-priori). There may be other
| frequencies but they shouldn't be close in the frequency space.
| What I expect to see is a similar spectrogram with this same
| ringing. But what I'd like to do next is work backwards and
| estimate the original frequency and most importantly the phase!
| Everyone talks about the frequency ringing but everyone skips
| explaining what happens to the phase.
|
| And since I haven't been able to find a nice proof of the
| ringing, I haven't been able to work it out for myself either
|
| Does anyone happen to have any good pointers for me? Thank you :)
| HelloNurse wrote:
| Citing from that page
|
| > In other words, $ J_k(\beta)$ is the amplitude of the $ k$ th
| harmonic in the Fourier-series expansion of the periodic signal
| $ x_m(t)$ .
|
| Or from the parent page about FM
|
| > It is well known that sinusoidal frequency-modulation of a
| sinusoid creates sinusoidal components that are uniformly
| spaced in frequency by multiples of the modulation frequency,
| with amplitudes given by the Bessel functions of the first kind
| [15]. As a special case, frequency-modulation of a sinusoid by
| itself generates a harmonic spectrum in which the $ k$ th
| harmonic amplitude is proportional to $ J_k(\beta)$ , where $
| k$ is the order of the Bessel function and $ \beta $ is the FM
| index.
|
| In other words, Bessel functions come up in Fourier transforms
| of frequency modulation signals, because integrals. The
| calculations have been figured out centuries ago.
|
| Regarding phase and arbitrary frequencies, it's easier to
| understand in the discrete time case: a vector of N complex
| numbers (time domain samples) goes in, it's multiplied by a
| matrix, and a vector of N complex numbers (Fourier
| coefficients) comes out.
|
| Regardless of the input signal, such a transform can be
| inverted (up to rounding errors and the like) by multiplication
| with the inverse of the forward matrix: the difference between
| signals of different frequencies is that if periods are a whole
| fraction of N samples the projections fall on one Fourier
| coefficient instead of spreading around all of them. Aligning
| the signal's period with the window length M allows reproducing
| the whole infinite duration signal from a N coefficient slice
| because all slices are identical.
| wankle wrote:
| I did sound analysis in the submarine service and always
| appreciated how the FFT worked though I lacked/lack the math
| background to fully understand it. The article was great, got
| through the first part, bookmarked for later.
| abstrakraft wrote:
| There are a couple of incorrect assertions near the beginning
| that should be addressed:
|
| 1. "That is, sound waves are not made out of sines as real-word
| phenomena."
|
| Sinusoids are the solutions to the harmonic oscillator
| differential equation (\ddot{x} = -w^2 x). The harmonic
| oscillator is an excellent model, or a component of excellent
| models, for many natural phenomena, including vibrating strings
| and columns of air, pressure waves in fluids, the list goes on.
| The utility of sinusoids is not due simply to their convenient
| mathematical properties, it's because many natural signals are
| sparse in the frequency domain, precisely because sinusoids _do_
| describe real world phenomena.
|
| 2. "A piston on a crankshaft produces "pure" sinusoidal up-and-
| down motion when operating at constant angular velocity."
|
| Uh, no. The motion of a piston is approximately sinusoidal as you
| decrease the radius of the crank, but in no case is it a "pure"
| sinusoid.
| [deleted]
| kevlened wrote:
| The 2-minute brute-force explanation of Fourier transforms in a
| recent Veritasium video was my "aha!" moment.
|
| https://www.youtube.com/watch?v=nmgFG7PUHfo&t=464s
| SJSque wrote:
| I can also highly recommend 3Blue1Brown's treatment of the
| topic: https://www.youtube.com/watch?v=spUNpyF58BY (...which I
| see now is cited in the video that you link to!)
| SnooSux wrote:
| I have a Bachelors and Master's in Electrical Engineering and
| do some signal and image processing as part of my job. I've
| been working with FFTs since undergrad and I thought a good
| understanding of what it does and how it works. But that
| Veritasium video helped me put all the pieces together in a way
| that made things click.
|
| The famous 3Blue1Brown video is also very strong and maybe
| explains why complex numbers are used better.
|
| Of course both videos leave stuff out in the interest of time
| but they should both be part of a signal processing curriculum.
| djmips wrote:
| You might also enjoy this Engineering Guy video playlist on how
| a mechanical harmonic analyzer works.
|
| https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqG...
| photochemsyn wrote:
| For an additional video exposition, I also like Eugene
| Khutoryansky's "Fourier Transform, Fourier Series, and
| frequency spectrum"
|
| https://www.youtube.com/watch?v=r18Gi8lSkfM
|
| In particular, the visualization of the addition of sine waves
| of different frequencies in three dimensions is pretty
| spectacular. It's similar to Mathologer's "Epicycles, complex
| Fourier series and Homer Simpson's orbit":
|
| https://www.youtube.com/watch?v=qS4H6PEcCCA
| TuringTest wrote:
| To expand the insight, you may see this video about Wavelets
| which relates them to the Fourier transform.
|
| It explains wavelets as an intermediate point between pure waves
| (all time, no frequency representation) and the Fourier transform
| (all frequencies, no time representation), with wavelets having
| part of both.
|
| https://www.youtube.com/watch?v=jnxqHcObNK4
| lupire wrote:
| "time" is present in both frequency and position. The
| difference is how time is sampled. Fourier Transform maps
| between global frequency space sampling and (repeating wave for
| all time) and local positional/point space sampling (perfect
| impulse).
|
| Wavelets map to an intermediate space,as you say, with smeared
| points/impulses and damped waves.
| dsego wrote:
| In this aspect, are wavelets similar to how stft is done with
| a hann window or the like?
| femto wrote:
| 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.)
| gmadsen wrote:
| 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 wrote:
| 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 wrote:
| 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).
| defrost wrote:
| .. 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 wrote:
| 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.
| ivan_ah wrote:
| 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...
| boxfire wrote:
| 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...
| lupire wrote:
| 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."
| sfpotter wrote:
| 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.
| midjji wrote:
| 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.
| lupire wrote:
| 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 wrote:
| 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.
| [deleted]
| enriquto wrote:
| > 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.
| sfpotter wrote:
| 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.
| enriquto wrote:
| 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...
| enriquto wrote:
| > 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 wrote:
| 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 wrote:
| sure, and they are the eigenfunctions of a Sturm-Liouville
| operator!
| sfpotter wrote:
| 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.
| Phenomenit wrote:
| I get the math and the explanations and all that but what I don't
| get is how do you express a complex sound signal as a function of
| f? Is it a long array with t and the amplitude?
| sizzzzlerz wrote:
| In reality, you can't. Since the fourier transform was designed
| for a continuous signal, it needs some modifications to tailor
| it to work in a digital world where, instead of a continuous
| signal, you periodically sample the waveform at regular
| intervals and use the discrete fourier transform (DFT) or its
| more efficient little brother, the fast fourier transform
| (FFT). Both these work off N samples of the waveform at a time.
| sfpotter wrote:
| Yes.
| dsego wrote:
| Afaik, in digital sound recordings it's basically an array of
| sampled amplitudes. And you need to know the sampling rate in
| advance, eg 44100 samples in a second. This is I think called
| PCM https://en.wikipedia.org/wiki/Pulse-code_modulation
| dinobones wrote:
| Really great explanation, but one thing is missing that plagues
| every other explanation of Fourier analysis: signals are not
| infinite.
|
| The time window you use for analysis matters just as much as the
| number of frequency bins, but everyone always ignores the time
| window for some reason.
| dsego wrote:
| Is there something missing in the two sections near the end
| about the sinc function and limited time intervals?
|
| https://dsego.github.io/demystifying-fourier/#sinc-function-...
| euroderf wrote:
| It's not for nothing that at college, the course in Fourier
| Series & Boundary Value Problems was better known as Mystery
| Math. There was a single key insight that made the entire course
| suddenly clear as a bell, and if you were lucky, that insight
| came _before_ the final exam.
| jqgatsby wrote:
| so, uh, you gonna tell us the insight?
| msla wrote:
| Maybe that it's "just" a change of basis, onto a basis made
| of orthogonal periodic functions.
___________________________________________________________________
(page generated 2022-11-17 23:01 UTC)