patternMinor
Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?
Viewed 0 times
themaximumfftfrequencythanamplitudefasteralgorithminterestedthere
Problem
Given an $n$ input array, is there an algorithm that is faster than Fast Fourier Transform if we are only interested in obtaining the maximum amplitude frequency?
Looking at the Cooley–Tukey algorithm it seems there would be a way to "prune" frequencies that are guaranteed to not be of maximum amplitude.
The application seems common enough that some other people might have already worked on a similar problem.
I am both interested in algorithms that are time-complexity-wise faster and practically faster through small "shortcuts" arising from this particular problem.
Is there such an algorithm?
Looking at the Cooley–Tukey algorithm it seems there would be a way to "prune" frequencies that are guaranteed to not be of maximum amplitude.
The application seems common enough that some other people might have already worked on a similar problem.
I am both interested in algorithms that are time-complexity-wise faster and practically faster through small "shortcuts" arising from this particular problem.
Is there such an algorithm?
Solution
Partial FFT and Sparse FFT can exploit an expected range of said maximum.
Practically, the range of frequencies over which the maximum may occur is often known. There are also approaches to estimate said location. These are signals, not algorithms questions.
Generally, the maximum can occur anywhere. That is also a signals question. The FFT is merely a fast computation of the Discrete Fourier Transform, so the place to look is Fourier theory.
Cooley–Tukey ... seems there would be a way to "prune" [non-maximum] frequencies
FFT devotes equal compute to all bins, and bin amplitude isn't known before computation is complete. If there's a way to conditionally "intercept" the computation, it'll likely add way more compute than it saves - even when the interval is known ahead of time (as in the two linked algos), the savings are marginal. Put simply, the FFT is brutally fast for what it computes - it's not just math, but hardware optimizations.
Practically, the range of frequencies over which the maximum may occur is often known. There are also approaches to estimate said location. These are signals, not algorithms questions.
Generally, the maximum can occur anywhere. That is also a signals question. The FFT is merely a fast computation of the Discrete Fourier Transform, so the place to look is Fourier theory.
Cooley–Tukey ... seems there would be a way to "prune" [non-maximum] frequencies
FFT devotes equal compute to all bins, and bin amplitude isn't known before computation is complete. If there's a way to conditionally "intercept" the computation, it'll likely add way more compute than it saves - even when the interval is known ahead of time (as in the two linked algos), the savings are marginal. Put simply, the FFT is brutally fast for what it computes - it's not just math, but hardware optimizations.
Context
StackExchange Computer Science Q#162126, answer score: 5
Revisions (0)
No revisions yet.