5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ You might get better answers on signal processing. $\endgroup$
    – Pål GD
    Sep 19 at 10:19
  • $\begingroup$ I was considering it. But this question is about an algorithm for signal processing, and not signal processing in itself. $\endgroup$
    – Andrea Nardi
    Sep 19 at 10:54
  • 5
    $\begingroup$ I have never seen this mentioned in any textbook, which is a bad sign. $\endgroup$
    – user16034
    Sep 19 at 10:58

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Indeed, the FFT can be seen as the brute-force evaluation of the transformation at... $\log(n)$ points, which is typical of a dichotomic search or Fibonacci search for an extremum (I mean in terms of complexity). It would be a little miracle if we could find the maximum with so little points and a sublinear cost of evaluation at those frequencies. $\endgroup$
    – user16034
    Sep 19 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.