Прореженный FFT

Прореженный FFT вошел в десятку "развивающихся технологий".
В MIT разработали и опубликовали результаты второй версии Sparce FFT. Если число ненулевых (точнее весомых) коэффициентов преобразования известно и равно k, то время выполнения преобразования оценивается как O(k log n), то есть в разы быстрее обычного полного FFT.
В действительности длина входного сигнала (степень двух) должна быть большой, чтобы получить выигрыш в скорости. Например, только при длине 2^18 sFFT быстрее FFTW:
Total sFFT time: 0.005048
Time to run FFTW : 0.010581
А это ограничивает возможности метода, в частности, в медиа обработке. Зато быстрее, чем FFTW, который, как мы знаем, самый быстрый FFT в мире :)

Алгоритм не использует оптимизацию в том смысле, как это делает FFTW, то есть не адаптирует код под архитектуру. Главная операция - многократная фильтрация, которая выполняется в частотной области с использованием FFTW. С помощью фильтрации ищутся (локализуются и оцениваются изолированные пики) значимые коэффициенты преобразования.
Не уверен, что прореженный FFT должен быть в первой десятке технологий. Разве что в пределах самого MIT.