Теорема Кули-Тьюки: линейная алгебра Быстрого преобразования Фурье

Дискретное преобразование Фурье (ДПФ) — это абсолютный фундамент всей современной цифровой эры. Оно позволяет разложить любой сигнал (звук, изображение, радиоволну) на гармонические составляющие (спектр). С точки зрения линейной алгебры, ДПФ является не чем иным, как умножением вектора сигнала на квадратную матрицу Вандермонда, заполненную комплексными корнями из единицы. Однако прямое умножение вектора на плотную матрицу размера n на n требует O(n^2) арифметических операций. Для обработки аудиосигнала с частотой 44100 Гц компьютеру потребовались бы миллиарды вычислений в секунду, что сделало бы MP3 и стриминг невозможными. Изящное решение — алгоритм Быстрого преобразования Фурье (БПФ), алгебраическая структура которого основана на факторизации матриц.

Матрица ДПФ и комплексные корни из единицы

Матрица Дискретного преобразования Фурье F_n размера n на n обладает уникальной геометрией. Ее элементы генерируются одним единственным числом — главным (первообразным) комплексным корнем n-й степени из единицы: omega = e^(-2 * pi * i / n). Элемент матрицы на пересечении j-й строки и k-го столбца равен (omega)^(j*k). Эта матрица является симметричной (но не эрмитовой) и обладает феноменальным свойством: ее столбцы ортогональны друг другу в комплексном смысле. Таким образом, нормализованная матрица (F_n / sqrt(n)) является унитарной. Унитарность означает, что обратное преобразование Фурье (восстановление сигнала из спектра) вычисляется простым умножением на эрмитово сопряженную матрицу, заменяя экспоненты на комплексно сопряженные.

Разделяй и властвуй: факторизация Кули-Тьюки

В 1965 году Джеймс Кули и Джон Тьюки опубликовали алгоритм (БПФ), который перевернул мир. В терминах линейной алгебры алгоритм Кули-Тьюки доказывает, что плотную матрицу F_n (если n является степенью двойки) можно алгебраически разложить (факторизовать) в произведение логарифмического числа (log2 n) крайне разреженных матриц. Вместо одной тяжелой операции мы выполняем цепочку легких. Суть факторизации заключается в разделении исходного вектора на элементы с четными и нечетными индексами. Выясняется, что преобразование Фурье размера n можно математически точно собрать из двух преобразований Фурье размера n/2, сложив их результаты со специальными фазовыми множителями, называемыми «поворачивающими коэффициентами» (twiddle factors).

Кронекерово произведение и перестановка битов

Алгебраическая структура факторизации Кули-Тьюки изящно описывается через тензорное (Кронекерово) произведение матриц. Рекурсивное разделение ДПФ на половины порождает формулу, в которой участвуют единичные матрицы, умноженные кронекерово на матрицы бабочек F_2 (базовых операций сложения и вычитания). Однако этот процесс «четные/нечетные» перемешивает элементы исходного вектора. Чтобы правильно подать данные в матричный конвейер, порядок элементов вектора должен быть изменен с помощью специальной матрицы перестановки P. Эта матрица выполняет инверсию битов (bit-reversal permutation): элемент с индексом, чье двоичное представление равно 110 (6), перемещается на позицию 011 (3). Эта матрица идеально симметрична и совпадает со своей обратной.

Сложность O(n log n) и свертка полиномов

Умножение вектора на каждую разреженную матрицу в факторизации Кули-Тьюки требует всего O(n) операций, так как в каждой строке матрицы находится ровно два ненулевых элемента (коэффициенты бабочки). Поскольку таких разреженных матриц ровно log2(n), общая вычислительная сложность алгоритма БПФ составляет O(n log n). Это снижение сложности с квадратичной до логарифмической линейной имеет астрономические последствия. Кроме обработки сигналов, БПФ используется для сверхбыстрого умножения гигантских чисел и полиномов. Обычное умножение двух многочленов степени n требует O(n^2) операций. Но если применить к коэффициентам БПФ, перемножить их попарно за O(n) и сделать обратное БПФ, мы получим коэффициенты результирующего многочлена в сотни раз быстрее.

Оценить