Преобразование Фурье относится к фундаментальным алгоритмам обработки данных и имеет приложения во многих инженерных областях. Алгоритм Кули и Тьюки для быстрого вычисления преобразования Фурье (БПФ; 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}.$