You are currently at the new webpage of the Club. The list of all courses of the Club is available at the old page: old.compsciclub.ru
City: Saint-Petersburg Kazan Language: Русский English

Algorithms for sparse Fourier transform
Autumn 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

02 February 2016

Видео

Выложены видеозаписи лекций.