Re:Understanding DFT and FFT
by programjames on Thursday March 07, 2024 @11:01AM
(#39630652)
Here's a much better explanation of the Fourier transform:
When you took calculus, you learned that functions can be written in a kind of "Taylor series":
f(x) = a0 + a1 x + a2 x^2 + ...
However, the functions {1, x, x^2, ...} aren't unique. You can use any basis functions. Let's replace them with {Φ0, Φ1, Φ2, ...}. To find your "Taylor series" you need some way to measure how far off your approximation is. We call this an "inner product", and one common one is the integral, i.e.
<f, g> = integral of f̅g dx
If we can change our coefficients {ai} and get a better approximation, it means there is some basis function where
So, to get the best approximation, we just set the left and right sides of the equation equal. This is really easy to calculate if most of the <Φi, Φj> = 0 (and cancel out). We call a basis orthogonal if <Φi, Φj> = 0 except when i=j. For an orthogonal basis, we're left with
<Φi, f> = ai<Φi, Φi> --> ai = <Φi, Φi> / <Φi, f>.
One common orthogonal basis are the Legendre polynomials, which are the same as {1, x, x^2, ...} with the Gram-Schmidt process applied to them. We're not really going to discuss those here. Another common one are sines and cosines. In trigonometry you learned that
e^{ix} = cos(x) + i sin(x),
so we can instead use the basis
{..., e^{-2ix}, e^{-ix}, 1, e^{ix}, e^{2ix}, ...}
Plugging this in gives the Fourier transform:
a_k = 1/2pi * integral from -pi to pi of e^{-kix}f(x) dx.
Re:Understanding DFT and FFT
by jcgrillo on Thursday March 07, 2024 @11:23AM
(#39630928)
Why don't we use the frequency domain for o11y stuff? Intuitively it seems like being aware of periodic phenomena, and being able to identify them, would be useful. But nobody does it. Is that because it's actually useless or some other reason?
Re:Understanding DFT and FFT
by jmwilson on Thursday March 07, 2024 @12:10PM
(#39631451)
Frequency domain analysis is useful when you have a physical quantity (which normally comes down to energy or power, in joules or watts) that you want to understand in terms of frequency. Mere periodicity of events doesn't imply that is the case. Statistical techniques, on the other hand, are widely applicable to time series data.
Re:Understanding DFT and FFT
by jcgrillo on Thursday March 07, 2024 @01:00PM
(#39632276)
I guess I'm thinking along the lines of analyzing processes for which I have some intuition what the frequency distribution should look like. Say I have a scheduled task running once per second which does some work, and I expect to see a corresponding cpu spike every second. But I notice that sometimes when the task runs it takes longer. Looking at the cpu spectrum I see a frequency spike at 1Hz corresponding to my 1/s task, but I also see a spike at 0.2Hz, confirming my suspicion that something is contending for cpu resources on every fifth task, slowing it down. Now I know to look for something that's happening every 5s.
In this contrived example I could have probably intuited that I was looking for something with a period of 5s without looking at the spectrum but maybe there are cases where it could be useful? I guess I'll just have to play around with data and find out :p.
When you took calculus, you learned that functions can be written in a kind of "Taylor series":
f(x) = a0 + a1 x + a2 x^2 + ...
However, the functions {1, x, x^2, ...} aren't unique. You can use any basis functions. Let's replace them with {Φ0, Φ1, Φ2, ...}. To find your "Taylor series" you need some way to measure how far off your approximation is. We call this an "inner product", and one common one is the integral, i.e.
<f, g> = integral of f̅g dx
If we can change our coefficients {ai} and get a better approximation, it means there is some basis function where
<Φi, f> =/= <Φi, a0Φ0 + a1Φ1 + a2Φ2 + ...> = a0<Φi, Φ0> + a1<Φi, Φ1> + a2<Φi, Φ2> + ...
So, to get the best approximation, we just set the left and right sides of the equation equal. This is really easy to calculate if most of the <Φi, Φj> = 0 (and cancel out). We call a basis orthogonal if <Φi, Φj> = 0 except when i=j. For an orthogonal basis, we're left with
<Φi, f> = ai<Φi, Φi> --> ai = <Φi, Φi> / <Φi, f>.
One common orthogonal basis are the Legendre polynomials, which are the same as {1, x, x^2, ...} with the Gram-Schmidt process applied to them. We're not really going to discuss those here. Another common one are sines and cosines. In trigonometry you learned that
e^{ix} = cos(x) + i sin(x),
so we can instead use the basis
{..., e^{-2ix}, e^{-ix}, 1, e^{ix}, e^{2ix}, ...}
Plugging this in gives the Fourier transform:
a_k = 1/2pi * integral from -pi to pi of e^{-kix}f(x) dx.
Fourier series is a discrete sum over integer multiple of frequencies, while Fourier transform is a continuous integral over all frequencies.
The former works for periodic functions, the latter for an arbitrary function. Because you need all frequencies to bound a function.
In this contrived example I could have probably intuited that I was looking for something with a period of 5s without looking at the spectrum but maybe there are cases where it could be useful? I guess I'll just have to play around with data and find out :p.