Быстрое преобразование Фурье

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск

Nikita Elкhin (Обсуждение | вклад)
(Новая: == Быстрое преобразование Фурье == '''Быстрое преобразование Фурье''' (БПФ, {{lang-en|Fast Fourier Transform, FFT}}) — клас...)
К следующему изменению →

Версия 05:08, 18 июля 2026

Содержание

Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ, Шаблон:Lang-en) — класс алгоритмов, позволяющих вычислить дискретное преобразование Фурье (ДПФ) и обратное к нему за время O(N \log N). Прямое вычисление ДПФ по определению требует O(N^2) арифметических операций, что делает БПФ незаменимым инструментом в задачах цифровой обработки сигналов, спектрального анализа, вычисления свёрток и умножения многочленов.

Определение и вычислительная сложность

Пусть задана последовательность комплексных чисел x_0, x_1, \dots, x_{N-1}. Её дискретное преобразование Фурье определяется как

X_k = \sum_{n=0}^{N-1} x_n W_N^{nk}, \qquad k = 0, 1, \dots, N-1,

где W_N = e^{-i 2\pi / N} — комплексный корень из единицы, называемый поворачивающим множителем. Обратное дискретное преобразование Фурье (ОДПФ) задаётся аналогично с заменой W_N на W_N^{-1} и нормировкой 1/N.

Непосредственное вычисление всех N коэффициентов X_k требует N^2 комплексных умножений и N(N-1) сложений, т. е. имеет временную сложность O(N^2). При больших N (порядка 10^5–10^6, типичных в приложениях) такое количество операций неприемлемо.

Быстрым преобразованием Фурье называют любой алгоритм, понижающий сложность до O(N \log N). Наиболее распространённым является алгоритм Кули — Тьюки, основанный на методе «разделяй и властвуй». Далее основное внимание уделяется случаю N = 2^m как наиболее простому и эффективному для изложения, хотя современные библиотеки (FFTW, Intel MKL) активно используют смешанные основания для достижения максимальной производительности.

Алгоритм Кули — Тьюки

Алгоритм Кули — Тьюки[1] был опубликован в 1965 г., хотя его идеи восходят к Гауссу. Ключевая идея состоит в рекурсивном сведении вычисления ДПФ длины N к двум ДПФ длины N/2 и последующем объединении результатов с помощью N/2 комплексных умножений и N сложений. Алгоритм эксплуатирует алгебраические свойства корней из единицы, в частности периодичность и симметрию. Для случая N = 2^m это приводит к временной сложности O(N \log N).

Существуют две симметричные формы алгоритма — с прореживанием по времени и по частоте. Ниже подробно разбирается вариант с прореживанием по времени, который наиболее наглядно демонстрирует принцип «разделяй и властвуй».

Прореживание по времени (Decimation in Time, DIT)

Пусть N чётно. Разобьём исходную последовательность x_n на две подпоследовательности половинной длины, выбирая отсчёты с чётными и нечётными индексами:

x_n^{(e)} = x_{2n}, \quad x_n^{(o)} = x_{2n+1}, \qquad n = 0, \dots, N/2 - 1.

Обозначим через E_k и O_k их N/2-точечные ДПФ:

E_k = \sum_{n=0}^{N/2-1} x_{2n} W_{N/2}^{nk}, \quad O_k = \sum_{n=0}^{N/2-1} x_{2n+1} W_{N/2}^{nk}.

Теперь выразим искомое ДПФ X_k через E_k и O_k. Для любого k = 0, \dots, N-1 справедливо:

X_k = \sum_{n=0}^{N-1} x_n W_N^{nk} </p> <pre> = \sum_{n=0}^{N/2-1} x_{2n} W_N^{2nk} + \sum_{n=0}^{N/2-1} x_{2n+1} W_N^{(2n+1)k} = \sum_{n=0}^{N/2-1} x_n^{(e)} W_{N/2}^{nk} + W_N^k \sum_{n=0}^{N/2-1} x_n^{(o)} W_{N/2}^{nk}. </pre> <p>

В последнем переходе использовалось тождество W_N^{2nk} = W_{N/2}^{nk}, которое следует из определения поворачивающего множителя: W_N^{2nk} = e^{-i 2\pi \cdot 2nk / N} = e^{-i 2\pi nk / (N/2)} = W_{N/2}^{nk}.

Таким образом, для первой половины выходных индексов (k = 0, \dots, N/2 - 1) получаем:

X_k = E_k + W_N^k O_k.

Для второй половины (k = N/2, \dots, N-1) воспользуемся периодичностью ДПФ половинной длины: E_{k+N/2} = E_k, O_{k+N/2} = O_k, и тем, что W_N^{k+N/2} = -W_N^k. Подстановка даёт:

X_{k+N/2} = E_k - W_N^k O_k, \qquad k = 0, \dots, N/2 - 1.

Два последних соотношения

X_k = E_k + W_N^k O_k, \qquad X_{k+N/2} = E_k - W_N^k O_k

называются базовой операцией «бабочка». Она составляет элементарный шаг алгоритма и за один раз вычисляет по одному элементу из каждой половины выходного массива, используя одно комплексное умножение и два сложения.

Рекурсивно применяя ту же процедуру к подзадачам длины N/2, а затем к N/4 и так далее, мы в конечном итоге дойдём до ДПФ длины 1, которое является просто тождественным отображением (X_0 = x_0). Глубина рекурсии составляет \log_2 N. На каждом уровне рекурсии выполняется N/2 бабочек, каждая из которых содержит одно комплексное умножение и два сложения.

Формально время работы удовлетворяет рекуррентному соотношению T(N) = 2T(N/2) + \Theta(N), T(1) = 0. По основной теореме о рекуррентности это даёт T(N) = \Theta(N \log N), то есть общее число комплексных умножений — (N/2) \log_2 N, сложений — N \log_2 N.

Прореживание по частоте (Decimation in Frequency, DIF)

В альтернативном подходе исходная последовательность x_n делится на две половины: x_n и x_{n+N/2} для n = 0,\dots,N/2-1. Вместо рекурсивного вычисления ДПФ чётных и нечётных индексов здесь сначала с помощью бабочек формируются две промежуточные последовательности, после чего вычисляются N/2-точечные ДПФ для получения чётных и нечётных частот. Вычислительная сложность остаётся такой же — O(N \log N).

Итеративная реализация и бит-реверсивная перестановка

Прямая рекурсивная реализация требует дополнительной памяти порядка O(N \log N) для хранения промежуточных массивов. На практике используют итеративный алгоритм, работающий «на месте» (in\text{-}place) с O(1) дополнительной памяти (не считая массива входных данных). Алгоритм состоит из двух фаз.

  1. Бит-реверсивная перестановка. Входной массив переупорядочивается так, что элемент с индексом j переносится в позицию, двоичное представление которой является обратным к двоичному представлению j (длина двоичных слов равна m = \log_2 N). Например, для N=8 индекс 1 \; (001_2) переходит в 4 \; (100_2). После этой перестановки рекурсивные подзадачи оказываются расположенными в памяти последовательно, что позволяет выполнять слияние снизу вверх.
  2. Послойное вычисление бабочек. Пусть номер слоя s пробегает значения от 1 до m = \log_2 N. На слое s размер блока ДПФ равен B = 2^s, а полублока — H = B/2. Для каждого блока с индексом j = 0, \dots, N/B - 1 и для каждого элемента внутри полублока k = 0, \dots, H-1 выполняется бабочка над парой элементов с индексами p = jB + k и q = jB + k + H:

u = x_p, \quad v = W_B^k \cdot x_q, \quad x_p = u + v, \quad x_q = u - v.

Здесь W_B^k = e^{-i 2\pi k / B} — предвычисленный поворачивающий множитель. Внешний цикл идёт по слоям s, затем по блокам, и наконец по позициям внутри полублока. После завершения последнего слоя массив x содержит коэффициенты ДПФ в естественном порядке.

Итеративная схема лежит в основе большинства высокопроизводительных библиотек, включая FFTW и Intel MKL.

Другие алгоритмы БПФ

Помимо алгоритма Кули — Тьюки для степеней двойки, существует ряд методов, ориентированных на произвольные длины N.

  • Составное N и гнездовые алгоритмы — обобщение Кули — Тьюки на случай N = N_1 N_2, в том числе для смешанного основания. Рекурсивно сводят ДПФ к ДПФ меньших длин, возможно, разных. Пример — алгоритм Синглтона[1].
  • Алгоритм Гуда — Томаса (алгоритм простых множителей) — применяется, когда N = N_1 N_2 со взаимно простыми N_1, N_2. Использует китайскую теорему об остатках для переиндексации, сводя ДПФ к двумерному без дополнительных поворачивающих множителей.
  • Алгоритм Винограда (WFTA) — использует свёрточную структуру ДПФ для простых длин и тензорное произведение для составных. Минимизирует число умножений ценой усложнения адресации[1].
  • Алгоритм Блюстейна (Chirp Z-Transform) — позволяет вычислить ДПФ произвольной длины N, сводя его к вычислению линейной свёртки, которая затем эффективно вычисляется с помощью БПФ. Для этого используется БПФ длины L, где L — наименьшая степень двойки, не меньшая 2N-1[1].
  • БПФ для действительных данных — использует симметрию спектра действительного сигнала (X_{N-k} = \overline{X_k}), что позволяет вдвое сократить память и вычисления. Широко распространены упакованные форматы хранения (Hermitian-symmetric).

Выбор конкретного алгоритма зависит от длины N, архитектуры вычислителя и допустимой задержки.

Приложения в анализе данных

Быстрое преобразование Фурье занимает важное место в современном анализе данных и машинном обучении. Его способность эффективно переводить временные и пространственные зависимости в частотную область открывает возможности для извлечения признаков, быстрой обработки и построения масштабируемых моделей.

Анализ временных рядов и спектральные признаки

В задачах прогнозирования и классификации временных рядов часто бывает полезно представить сигнал через его частотные компоненты. БПФ позволяет:

  • Выделять периодические тренды. Амплитудный спектр |X_k| мгновенно выявляет доминирующие частоты, что используется для обнаружения сезонностей, циклических паттернов в финансовых, метеорологических и сенсорных данных.
  • Формировать спектральные признаки. На основе БПФ строятся такие признаки, как энергия в заданных частотных полосах, спектральный центроид, спад спектра, коэффициенты кепстра. Они широко применяются в задачах распознавания активности по акселерометру, мониторинга состояния промышленного оборудования и анализа биомедицинских сигналов (ЭЭГ, ЭКГ).
  • Детекция аномалий с помощью спектральных остатков. Метод Spectral Residual[1] использует БПФ для выделения «неожиданных» компонент во временном ряде, что позволяет эффективно находить выбросы и аномалии в потоковых данных без обучения.

Быстрая свёртка в машинном обучении

Свёрточные операции — основа архитектур свёрточных нейронных сетей (CNN). Для больших ядер свёртки или при работе с одномерными сигналами высокой размерности прямые вычисления становятся затратными. БПФ даёт альтернативный путь: дополнив последовательности нулями до длины N \ge L+M-1 (где L,\;M — длины исходных векторов), линейную свёртку можно вычислить как

y = \text{IFFT}\left( \text{FFT}(x_{zp}) \odot \text{FFT}(h_{zp}) \right),

где x_{zp},\;h_{zp} — дополненные нулями сигналы, а \odot — поэлементное умножение. Это не только ускоряет вычисления на CPU и GPU (особенно с помощью таких библиотек, как cuFFT), но и позволяет реализовать свёртку с очень большим рецептивным полем, что полезно в задачах обработки аудио и длинных последовательностей. Аналогично, взаимная корреляция через БПФ используется для быстрого сопоставления шаблонов, например, при поиске объекта на изображении.

Признаки для аудио- и речевой аналитики

Практически все стандартные признаки в обработке речи и музыки опираются на БПФ:

  • Мел-частотные кепстральные коэффициенты (MFCC). Вычисление мел-спектрограммы и последующего дискретного косинусного преобразования начинается с БПФ коротких кадров сигнала. Эти коэффициенты служат входом для систем распознавания речи, идентификации диктора и музыкальных рекомендательных систем.
  • Спектрограммы как изображения. Во многих нейросетевых подходах (например, SoundNet, VGGish) аудиосигнал преобразуется в логарифмическую мел-спектрограмму, которая затем подаётся на вход CNN. Сама спектрограмма строится с помощью БПФ, и её качество напрямую влияет на точность классификации.

Обработка изображений и компьютерное зрение

Двумерное БПФ, получаемое последовательным одномерным БПФ по строкам и столбцам, — мощный инструмент в арсенале дата-сайентиста:

  • Фильтрация и улучшение изображений. Частотная фильтрация (низкочастотная для подавления шума, высокочастотная для выделения контуров) выполняется элементарным умножением спектра на маску, после чего применяется обратное БПФ. Это стандартный этап предобработки в задачах распознавания.
  • Ускорение глубоких сетей. Некоторые исследовательские работы предлагают переносить свёртки внутрь нейросетей в частотную область, что может снизить вычислительную сложность для слоёв с большими фильтрами[1].
  • Поиск по образцу и регистрация. Фазовая корреляция, основанная на БПФ, позволяет находить сдвиг между двумя изображениями с субпиксельной точностью, что используется при совмещении снимков, отслеживании объектов и в задачах оптического потока.

Другие направления

  • Умножение многочленов и больших чисел. Умножение многочленов степени d эквивалентно свёртке коэффициентов и выполняется за O(d \log d) с помощью БПФ. Это находит применение в алгоритмах длинной арифметики и криптографии, а также при вычислении ядерных методов (полиномиальные ядра).
  • Решение уравнений в частных производных. Спектральные методы на основе БПФ являются основным инструментом для моделирования турбулентности, прогноза погоды и физических симуляций, где требуется быстрое решение периодических задач.
  • Беспроводная связь. OFDM-модуляция в Wi-Fi, LTE, 5G реализуется с помощью БПФ/ОБПФ, что обеспечивает эффективную передачу данных, однако это скорее область передачи данных, чем их анализа.

БПФ продолжает оставаться активной областью исследований: появляются разреженные БПФ (sparse FFT) для сигналов с небольшим числом ненулевых частот, квантовые алгоритмы БПФ и высокоэффективные реализации для графических процессоров.

Смотрите также

Примечания

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5»
Личные инструменты