Преобразование Фурье относится к фундаментальным алгоритмам обработки данных и имеет приложения во многих инженерных областях. Алгоритм Кули и Тьюки для быстрого вычисления преобразования Фурье (БПФ; Fast Fourier Transform) считается одним из десяти важнейших алгоритмов двадцатого века — его открытие в 1965 г. привело к революции в алгоритмах обработки сигналов, и этот алгоритм используется повсеместно на сегодняшний день. БПФ позволяет вычислить преобразование Фурье сигнала длины \(N\) за время \(N\log N\), и получение более быстрого метода для произвольных сигналов является одним из важнейших вопросов теоретической информатики.

Алгоритм БПФ применим к произвольным сигналам, но сигналы, встречающиеся на практике, часто обладают дополнительными свойствами, позволяющими ускорить вычисление. Одним из таких свойств является разреженность спектра (Fourier sparsity): спектр Фурье сигналов, встречающихся на практике, часто хорошо приближается малым количеством коэффициентов (например, это свойство лежит в основе нескольких схем сжатия изображений и видео). В этом мини-курсе будут рассмотрены алгоритмы приближенного вычисления преобразования Фурье с разреженным спектром. Мы покажем, что если спектр сигнала длины \(N\) хорошо приближается \(k\) коэффициентами (\(k\)-разреженный сигнал; \(k\)-sparse signal), то хорошее приближение спектра можно получить за время \(O(k\log^2 N)\). Если количество доминирующих коэффициентов \(k\) существенно меньше, чем \(N\), это улучшает время работы БПФ. Более того, в этом случае время работы алгоритма сублинейно по \(N\), т.е. алгоритм даже не считывает все \(N\) элементов сигнала во временной области. Для некоторых приложений (таких как магнитно-резонансная томография) количество элементов сигнала, считываемых алгоритмом во временной области, является не менее важным параметром эффективности алгоритмов разреженного БПФ, чем временная сложность. Мы покажем, как получить приближение преобразования Фурье \(k\)-разреженного сигнала, считав всего \(O(k\log N)\) его значений во временной области, что оптимально для всех значений \(k<N^{0.99}.\)