Наткнулся тут недавно на описание очень быстрых алгоритмов, вычисляющих в некотором смысле (по l2-норме) приближенную оценку коэффициентов преобразования Фурье для случая с небольшим количеством тонов на входе.
Алгоритмов очень быстрых - с вычислительной сложностью O(k*log(n) * log log(n)) для количества значимых компонент сигнала k и длиной буфера во временной области n.
Т.е. он выигрывает у FFT в n/(k * log log (n)) раз!
Источники:
http://groups.csail.mit.edu/netmit/sFFT/
https://groups.csail.mit.edu/netmit/sFFT/paper.html
Видеокурс на русском:
https://www.youtube.com/playlist?list=PL-_c...A_-xmSv1bDQLmqD
