Источник: MIT
Источник: MIT

ДПФ — один из столпов цифровой обработки сигналов: например, он применяется в алгоритмах компрессии изображений JPEG и звука MP3. Попытки дополнительно ускорить ДПФ предпринимались со времени разработки первоначального алгоритма, но пока существенных результатов добиться не удавалось.

Принцип действия ДПФ — преобразование цифрового сигнала, как набора дискретных значений частот, во взвешенную сумму этих значений. При этом часть частот считаются незначимыми и отбрасываются. Сигналы, содержащие относительно малое число значимых частот, исследователи называют «разреженными» (sparse). Именно на выявлении таких сигналов основан принцип действия нового алгоритма. Чем разреженнее сигнал, тем быстрее работает новый алгоритм. По мнению авторов, большинство встречающихся на практике сигналов — разреженные, поэтому существует масса случаев, когда их алгоритм будет быстрее традиционного.