Преобразование Фурье – одно из основных понятий в информационных науках. Это метод представления автомобильные сигнала, такого как напряжение в сети, в виде комбинаций чистых частот. Алгоритм широко применяется для преобразования сигналов, сжатия изображений и аудио файлов, решения дифференциальных уравнений, оценок стоимости акций и т.п.. Даже при постановки задачи браузеру: скачать демон тулс , данный алгоритм успешно применяется.
Причина, почему преобразование Фурье стало таким популярным – разработка в середине 60-х годов прошлого века алгоритма быстрого преобразования Фурье (FFT), который позволил проводить преобразования Фурье в реальном времени. С тех пор, как FFT был предложен, люди не прекращали поиск еще более быстрого алгоритма.
На Симпозиуме по дискретных алгоритмов (SODA) на прошлой неделе группа исследователей из Массачусетского технологического института предложила новый алгоритм, который для широкого круга важных приложений является быстрее FFT. При определенных обстоятельствах можно получить десятикратное увеличение скорости. Новый алгоритм может оказаться особенно полезным для сжатия изображений, например, это может позволить портативным устройствам быстро обмениваться большими файлами через беспроводную сеть с меньшими затратами энергии и сетевого трафика.
Как и FFT, новый алгоритм работает с цифровым сигналом, он раскладывает его в взвешенную сумму набора частот. Частотами, которые имеют низкий вес, пренебрегают без существенной потери точности. Вот почему преобразование Фурье такое полезное в сжатии информации. Изображение 8х8 точек можно считать выборке из 64 измерений, т.е. суммой 64 различных частот. Но, как отмечают исследователи, эмпирические данные показывают, что в среднем 57 частот можно отбросить с минимальной потерей качества изображения.
Сигналы, преобразование Фурье включает в относительно малое количество частот с большим весом, называются «рассеянными». Новый алгоритм определяет вес наиболее важных частот. Чем больше рассеянный сигнал, тем больше ускорение достигает новый алгоритм. Действительно, если сигнал достаточно рассеянный, алгоритм может сделать небольшую выборку из него вместо полной обработки.
«Большинство нормальных сигналов в природе рассеяны», – утверждает Дина Катаби, одна из разработчиков нового алгоритма. Рассмотрим, для примера, запись камерной музыки. Совокупный сигнал в каждый момент времени состоит только из звуков нескольких инструментов, каждый играет по одной ноте. С другой стороны, запись всех возможных инструментов, которые играют все возможные ноты одновременно, не будет рассеянным, но этот сигнал никому не интересен.
Новый алгоритм, разработанный профессорами Катаби и Петром индюком из МТИ, основанный на двух ключевых идеях. Первая – разделение сигнала на узкие куски так, чтобы каждый кусок в общем случае содержал лишь одну частоту с большим весом.
В обработке сигналов основным инструментом для изоляции определенных частот является фильтр. Но у фильтров могут быть размыты границы. Одни частоты будут проходить почти невредимыми, частоты у границ диапазона будут немного ослаблены, и так далее до полного исчезновения сигнала.
Если так случится, что одна из частот с большим весом находится на краю фильтра, может возникнуть ситуация, что после ослабления ее невозможно распознать. Поэтому первой задачей исследователей стал поиск эффективного вычислительного способа соединения фильтров так, чтобы они могли налагаться, гарантируя, что ни одна из частот в целевом диапазоне не будет чрезмерно слабеть, но при этом границы между кусками спектра остаются довольно четкими.
После отделения кусочков спектра необходимо определить наиболее важную частоту. Сначала предлагался способ повторного разделения спектра на все меньшие куски, оставляя лишь те, у которых максимальная концентрация сигнала. Позже было найдено значительно более эффективную методику, которая похожа на способ обработки сигналов в сотовых сетях формата 4G.
Похожий алгоритм для улучшения FFT для разреженных сигналов уже предлагался двумя учеными из Мичиганского университета, профессорами Анной Гильберт и Мартином Штраусс. «Некоторые предварительные работы, включая мою Анной Гильберт, улучшающие преобразования FFT для случаев, когда коэффициент разрежения (количество частот с большим весом) значительно меньше размер выборки», – признает Штраусс. — «Вместо этого алгоритм, предложенный в МТИ имеет значительно более широкий круг случаев, в которых он может победить обычный FFT по скорости обработки. Даже если коэффициент разрежения приближается к размеру выборки, новый алгоритм дает небольшое ускорение по сравнению с FFT »
Источник:
