Max Home IndustryИсследовательская группа из Массачусетского технологического института разработала улучшенный алгоритм, который может сделать больше с аудио- и графическими данными с помощью менее мощного оборудования.
Преобразование Фурье является фундаментальным для алгоритмов обработки сигналов, и с практической точки зрения оно лежит в основе сжатия изображений, звука и видео, а также большинства методов фильтрации и восстановления. Проще говоря, это важно. Однако был день, когда вычисление преобразования Фурье было проблемой, требующей много времени — настолько, что наивный алгоритм сделал практически невозможным использование этой техники на реальных данных.
В цифровой области преобразование Фурье — это матричное умножение, фактически вращение, которое переводит вас из пространственной области в частотную. То есть вы даете ему амплитуду одиночного сигнала в различные моменты времени, и он возвращает вектор частотных амплитуд и фазы в различных частотных точках. Поскольку это умножение матриц, прямой алгоритм выполняет n2 операций для входного вектора размера n, что означает, что вы не можете работать с большими наборами данных.
Изобретение быстрого преобразования Фурье Дж. У. Кули и Джон Тьюки в 1965 году, известный в то время просто как алгоритм Кули-Тьюки, стал огромным прорывом. Самое безумное было то, что он был изобретен раньше, вероятно, в 1805 году Гауссом, но его проигнорировали! Влияние БПФ было огромным. Это открыло всевозможные возможности в обработке сигналов, обработке изображений и искусственном интеллекте. Его назвали важнейшим численным алгоритмом, и это не преувеличение.
Основная идея БПФ — просто использовать стратегию «разделяй и властвуй». Если размер вектора данных n факторизуемый, скажем, n = n1n2, то вы можете вычислить преобразование Фурье на n1 элементах, а затем на n2 элементах и сложить результат, чтобы получить полный результат. Если n очень факторизуем, вы можете повторить деление до наборов из двух точек данных. Это БПФ, и вы можете показать, что для него требуется время, пропорциональное nlogn, что является большим улучшением по сравнению с n2 для больших n. Вы также можете построить аналогичные алгоритмы, даже если n не является сильно составным и существуют алгоритмы БПФ, даже если n простое.
До недавнего времени БПФ было лучшим, что вы могли сделать в целом, но до сих пор неизвестно, является ли это оптимальным алгоритмом. Очевидно, что теоретическая нижняя граница сложности равна n, поскольку вам нужно вычислить n коэффициентов Фурье. Однако, если частотный спектр разреженный, т.е. есть только k ненулевых частот, то вы можете надеяться на алгоритм, сложность которого пропорциональна k.
Теперь исследовательская группа из Массачусетского технологического института продемонстрировала алгоритм, который требует времени на блокировку. Алгоритм принимает вектор данных с n элементами и возвращает k наибольших компонентов Фурье — это именно то, что вам нужно в случае большинства алгоритмов сжатия и приблизительной обработки сигналов.
Если вы надеетесь на элегантный алгоритм, который использует симметрию ситуации, скажем, с использованием модифицированной бабочки, это не так. Идеи и реализация основаны на использовании фильтров для разделения полосы пропускания на интервалы так, чтобы каждый интервал содержал не более одной из значимых частот. Фильтры (Гаусса и Дельфа-Чебышева) сконструированы таким умным образом, что они перекрываются именно так, чтобы гарантировать, что вы не пропустите важный компонент. После этого используется разделительный поиск для выделения областей, содержащих значимые коэффициенты Фурье. Результирующее преобразование является лишь приближением к истинному преобразованию, но точность может быть определена количественно.
Многие сигналы являются разреженными, и, если это не так, алгоритмы сжатия, которые ими управляют, предполагают, что это так. Другими словами, k-разреженный приближенный алгоритм достаточно хорош для многих практических приложений.
Это означает, что при использовании такого подхода. вы можете реализовать более быстрое сжатие в стиле MP3 или MP4 или использовать гораздо менее мощный процессор.
Важным моментом в этом новом алгоритме является то, что даже если k приближается к n, можно показать, что алгоритм примерно так же хорош, как и обычное БПФ.
На этом графике FFTW — это обычное БПФ, SFFT 3.0 — новый алгоритм, а AAFFT — предыдущий самый быстрый разреженный алгоритм.
Так что это прорыв. В результате своего изобретения этот алгоритм позволит обрабатывать звук, изображение и другие данные быстрее, чем когда-либо прежде. Что еще вы можете спросить — но было бы неплохо, если бы алгоритм был таким же красивым, как исходное БПФ.
Дополнительная информация:
Ранее самый быстрый алгоритм — хороший способ понять идеи, лежащие в основе новейшего метода:
Простой и практичный алгоритм разреженного преобразования Фурье Хайтам Хассани, Петр Индик, Дина Катаби и Эрик Прайс. PDF
Описанный здесь алгоритм является предметом статьи: Почти оптимальное разреженное преобразование Фурье Хайтам Хассани, Петр Индик, Дина Катаби и Эрик Прайс. PDF на ArXiv.
sFFT: страница группы разреженных быстрых преобразований Фурье