Но с момента его разработки в 1960-х годах компьютерные ученые искали алгоритм, который улучшил бы его.
В прошлом году исследователи Массачусетского технологического института Петр Индик и Дина Катаби сделали именно это, представив алгоритм, который в некоторых случаях может выполнять преобразования Фурье в сотни раз быстрее, чем быстрое преобразование Фурье (БПФ).
Теперь Индик, профессор информатики и инженерии и член группы теории вычислений в Лаборатории компьютерных наук и искусственного интеллекта (CSAIL), и его команда пошли еще дальше, значительно сократив количество образцов, которые необходимо брать. из заданного сигнала, чтобы выполнить операцию преобразования Фурье.
Близко к теоретическому минимуму
В статье, которая будет представлена на симпозиуме ACM-SIAM по дискретным алгоритмам в январе, Индик, постдок Майкл Капралов и бывший студент Эрик Прайс представят алгоритм, который может выполнять преобразования Фурье с использованием близкого к теоретическому минимальному количеству выборок. Они также улучшили даже это, разработав алгоритм, который использует минимально возможное количество выборок сигнала.
По словам Индика, это может значительно сократить время, необходимое медицинским устройствам, таким как аппараты магнитно-резонансной томографии (МРТ) и ядерно-магнитного резонанса (ЯМР), для сканирования пациентов или позволить астрономам делать более подробные изображения Вселенной.
Преобразование Фурье — это фундаментальное математическое понятие, которое позволяет разбивать сигналы на их составные части. Например, когда вы слушаете чью-то речь, вы можете услышать доминирующий тон, который является основной частотой в его голосе. «Но есть много других основных частот, поэтому человеческий голос не является однотонным, он намного богаче», — говорит Индик. "Итак, чтобы понять, как выглядит спектр, нам нужно разложить звуки на их основные частоты, и это именно то, что делает преобразование Фурье."
Разработка БПФ впервые автоматизировала этот процесс, что позволило компьютерам быстро манипулировать цифровыми сигналами и сжимать их в более управляемую форму.
Это возможно, потому что не все частоты в цифровом сигнале равны. Действительно, в природе многие сигналы содержат всего несколько доминирующих частот и ряд гораздо менее важных, которые можно безопасно игнорировать. Это так называемые разреженные сигналы.
«В реальной жизни, когда вы часто смотрите на сигнал, в спектре доминирует лишь небольшое количество частот», — говорит Индик. "Таким образом, мы можем сжать [сигнал], оставив только первые 10 процентов этих."
Предыдущая работа Индика и Катаби была сосредоточена на продолжительности времени, необходимом их алгоритму для выполнения операции разреженного преобразования Фурье. Однако во многих приложениях количество выборок, которые алгоритм должен взять для сигнала, может быть столь же важным, как и время его работы.
Приложения в медицинской визуализации, астрономии
Индик говорит, что один из таких примеров — сканирование МРТ. «Устройство собирает образцы Фурье, в основном снимки тела, лежащего внутри устройства, которые оно использует для восстановления внутренней структуры тела», — говорит он. «В этой ситуации количество взятых образцов прямо пропорционально количеству времени, которое пациент должен провести в аппарате."
Таким образом, позволяя сканеру МРТ создавать изображение тела с использованием части образцов, необходимых для существующих устройств, он может значительно сократить время, которое пациенты должны проводить, лежа в узких, шумных аппаратах.
Команда также изучает идею использования нового алгоритма разреженного преобразования Фурье в астрономии.
Они работают с исследователями из обсерватории Хейстэк Массачусетского технологического института, которые специализируются на радиоастрономии, над использованием системы в интерферометрии, в которой сигналы от множества телескопов объединяются для создания единого изображения космоса с высоким разрешением. По словам Индика, применение алгоритма разреженного преобразования Фурье к сигналам телескопа уменьшит количество наблюдений, необходимых для получения изображения такого же качества.
«Это важно, — говорит он, — потому что это действительно массивные наборы данных, и, что еще хуже, большая часть этих данных распределена, потому что существует несколько разных, разделенных телескопов, и каждый из них получает некоторую информацию, а затем все это должно быть отправлено в одно и то же место для обработки."
Более того, создание радиотелескопов чрезвычайно дорогое, поэтому алгоритм, который позволяет астрономам использовать меньшее их количество или получать изображения лучшего качества с того же количества датчиков, может быть чрезвычайно важным, говорит он.
Мартин Штраус, профессор математики, электротехники и информатики в Мичиганском университете, который разрабатывает фундаментальные алгоритмы для таких приложений, как обработка сигналов и массивы данных, говорит, что работа Индика и других делает алгоритмы разреженного преобразования Фурье более выгодными, чем знаменитые. БПФ по большему классу задач, чем раньше. «Текущая статья выжимает почти все [характеристики], которые возможны с помощью этих методов», — говорит он.