Overall this statement is rubbish. There is fundamentally no difference in accuracy. The domains are precise duals of one another and nothing is more accurate than the other.
The devil as usual resides in the details. Mostly in how much noise there is in amplitude, frequency and phase. Noise gets you into all manner of interesting nasties. This then leads into the next question. What are the requirements of the measurement? “As accurate as possible” isn’t a requirement. One needs to know what the constraints on the system are and what is actually being measured. Is the system noisy? How much does the phase vary? What is the spectrum of the phase noise?
We forget that working in the digital domain is a pretty recent thing. Phase measuring was done in the analog domain for ages, and still is. And can be done very very well. In the time domain it isn’t hard to measure phase very accurately, whether digital or not. They are all the same thing, but sometimes one is easier or better suited to the task than another.
The inherent equivalence of the different domains is frequently overlooked. If I was handed a PhD dissertation claiming “phase is most accurately measured in the frequency domain” it would go back with a “please explain” to the author. “More easily measured” perhaps, but that depends on the domain. “Most accurately” is just plain wrong.
I’m a theorist. I did occasionally do LIGO-related work, and several of my colleagues did a lot more than I, but I’m at one remove from the folks who did the lab work (though we did see them a lot at conferences and such).
And yeah, they probably meant that phase is easier to measure in the frequency domain, because it’s right there as a component of the complex number. It can’t be more accurate, because frequency and time domain both have the exact same information.
I’m more than willing to believe that for the reasons you, Chronos and others have presented.
Yes; all of that tracks for me. And thanks for the peek at your professional life. I’ve worked on a lot of metrology projects, and LIGO is sort of the ultimate in metrology…
O my goodness me, this is mind boggling. So, how much of this do software users need to know? Do all the major software packages and libraries that offer any Fourier transforms do it this way, or is this a differentiating feature between software products? How does this inform a quantitatively engaged Doper choosing their software?
I use SAS, but not for long (retiring soon). I hope to learn R. Somebody mentioned LabVIEW, somebody mentioned Matlab. Do we want to look into these details before we choose (or invest in) a tool?
Every data analysis package will have some pre-built Fourier transform function that comes with it (and likewise for all of the other standard data-analysis operations), and the vast majority of the time, a user doesn’t need to think about it any further than knowing what format to use for calling it. Usually, the built-in function will be based on the most efficient algorithm known at the time the package was released, and usually, even if it’s not the most efficient, the difference in time won’t matter. Occasionally, when someone is doing a really big batch job, they’ll discover that the package isn’t using the most efficient algorithm, and it’s enough to make a significant difference, and at that point, they’ll go looking for a plug-in for the more efficient algorithm (which they still probably won’t need to understand in detail).
Most if not all commercially available tools use some implementation of LAPACK for FFT, as do standard open source tools like SciPy and Octave. I do not know specifically about R and while a cursory look at the documentation says “Compute the inverse Fast Fourier Transform compatible with ‘Matlab’ and ‘Octave’” but doesn’t cite a specific library, I would assume that it uses OpenBLAS. These differences between implementations are negligible and are all validated against a standard benchmark so you really shouldn’t have to weigh that in consideration for which language and toolset you select, and if you needed something superfast or capable of massive parallelization you’d look for or build a custom algorithm as @Chronos notes. Since you mention R I assume that you are not looking as really high performance computing and whatever FFT library it uses should be sufficient.
If you’re a student in a relevant field, you may be tasked with coding the FFT (for a power of 2 anyway) as an assignment, just to see how it works. That can definitely be illuminating.
But most software packages have built-in FFTs, and it’s generally more important to understand what it is and why you use one than being able to efficiently reproduce one. Efficiency can and does make a difference but using the FFT at all is the major improvement over time domain implementations and other people have done the leg work on the efficiency end.
At work, we had to take some developers to task for coding a signal filter in the time domain, i.e. convolution which is O(n^2), vs coding it in the frequency domain with FFTs which is O(n*log(n)). Huge difference in compute times and efficiency. I’d trade some inefficiency every day using non-optimal FFTs over that mess.
And even if you do, when it comes time to actually use a FFT for real data analysis, you’ll probably still use the standard pre-written one. Writing your own FFT or the like is just for practice, to prepare you for when you have a task sufficiently novel that you really will need to write your own algorithm for it (which will happen sooner or later, probably sooner, if you continue in research).
Some of my gravitational-wave colleagues joked about having accidentally invented the “White dwarf transform”, because it turns out that absolutely any gravitational wave signal, real or noise, can be represented as an appropriate combination of white dwarf binaries (and so, if you hope to ever detect anything other than white dwarf binaries, you need some sort of heuristics to rule out the white dwarf possibility).
I found one of the best ways to learn how Fourier transforms work is to play around with FFTs. Look at a signal in both domains, change it in one, see the effect in the other.
You’ll see how position changes in one domain become phase changes in the other. This makes it easy to take either position or phase measurements.
You’ll see how the information is spread among the samples. A subinterval in one domain reduces the resolution in the other. Or, zero-padding in one domain increases the sampling in the other. (And drives home the difference between resolution and sampling.)
Yep. For the work I do, our FFT packages handle multiples of 2, 3, 5, and 7 without measurable difference. Larger primes have a measurable effect, but usually not enough to matter unless the number of samples is large. But a careless coworker once let slip in a five-digit prime factor–many Shuvs and Zuuls knew what it was to be roasted in the depths of the Slor that day!
I did this about 20 years ago when I built a measurement system whose data get used in a variety of ways, just one of which is to search for and measure periodicities. So, in the user interface of the system, I put a button that calls up another program I wrote that lets people pretend there will be periodic variability in their result, and specify its fundamental frequency, and choose square or triangle waves or white or pink noise, or describe what one fundamental cycle looks like as a time series by sliding 20 sliders to create effectively a coarse graph of that cycle. They can then view the resulting pretend data set in either the time or frequency domain, linear or logged, and with or without lines joining the discrete points. The thing is, they have to set how many points the system will measure, how far apart they will be, and how long the whole data set will be (so that’s 2 degrees of freedom but with three different linked options for how to define them). This other program understands how they have set the measurement system and shows them the frequency domain version based on their settings. They can play with their settings here, and when they exit back to the main program, their last played-with settings propagate back into it. This is how people without experience in Fourier transforms can set up a run on the system (which can go for as long as a couple weeks) and wind up with measurements that are good for testing their hypotheses.
It’s much less of a issue now but back in my student days, the professors all told us one of the cheapest things you could do was simply zero pad your signal up front - power of 2 was the best of course but to some other convenient length was better than a bad number of samples - and cut them out at the end. Unsurprisingly, they were correct and it’s something I sometimes wish some of our devs had beaten into their heads.
I do those beatings (or feedings of the Slor). We have multitudes of FFT wrappers that do all sorts of massaging, but kids less experienced engineers will do all sorts of crazy stuff. The defaults, if you don’t know what you’re doing, is pad up to the nearest number that only has factors of 2, 3, 5, and 7. Or, similar, with the added condition of even-only, double-even-only, or odd.-only.
Another vote for just getting your hands dirty and doing stuff with FFTs. There are a lot of interesting gotyas and deep truths to be found. Understanding the implications of noise, windowing, sampling, aliasing, ringing and more is best done by doing.
Keeping in mind the fundamental assumptions and duality of time and frequency spaces makes it much easier.
I tend to mostly use Python and Numpy. That plus matplotlib gets you a very powerful numerical playground that is very close in use to Matlab. The Scipy package gets you a one stop very useful start with pretty much everything you need. That it is free is a significant thing as well.
If you need to tune something for best performance it is hard to avoid the underlying implementation. Libraries like FFTW or the Intel math library are well documented and pretty easy to use. But you will be talking to them in C, or a simple wrapper.
Python and NumPy with SciPy is great for both learning and using FFTs and other signal processing, filtering, and optimization methods. Unless you are processing a massive amount of signals, it is plenty fast, easy to use, and well documented. The Anaconda Python distribution is free, easy to install with all of the necessary libraries by default, and Conda makes it easy to maintain and install a wide variety of common libraries without requiring admin privileges. There are a broad selection of IDEs but I’ve just gone to using Jupyter Lab, which just runs a web server feeding an interactive browser page where you can run a notebook interface, console window, edit text files, or display graphics and interactive components.