Алгоритмы быстрого вычисления разреженного преобразования Фурье Опции

[andyp]

Наброшу пожалуй

Наткнулся тут недавно на описание очень быстрых алгоритмов, вычисляющих в некотором смысле (по 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