Преобразование Фурье: визуальное и математическое введение

Преобразование Фурье — один из тех редких математических инструментов, которые кажутся слишком хорошими, чтобы быть правдой. Тем не менее оно работает с поразительной точностью в областях, таких непохожих, как квантовая механика, сжатие изображений и аудиотехника.

Какую задачу оно решает?

Предположим, вы записываете музыкальный аккорд. Микрофон улавливает одну волну — зубчатую, сложную функцию времени. Внутри этой волны скрыты отдельные ноты: чистые синусоиды на определённых частотах. Преобразование Фурье — это операция, разлагающая составной сигнал на его частотные составляющие.

Формально, для функции $f(t)$ её преобразование Фурье $\hat{f}(\xi )$ равно:

$$\hat{f}(\xi )={\int }_{-\infty }^{\infty }f(t)e^{-2\pi i\xi t}dt$$

Обратное преобразование восстанавливает $f$ из $\hat{f}$:

$$f(t)={\int }_{-\infty }^{\infty }\hat{f}(\xi )e^{2\pi i\xi t}d\xi$$

Ключевое прозрение: любую достаточно хорошо ведущую себя функцию можно записать как (возможно, бесконечную) сумму синусов и косинусов.

Сравнение сложности алгоритмов

Алгоритм	Временна́я сложность	При $N=10^6$
Наивное ДПФ	$O(N^2)$	$10^{12}$ операций
БПФ	$O(N\log N)$	$2\times 10^7$ операций
Ускорение	—	$\approx 50000\times$

Теорема о свёртке

Одно из самых мощных применений преобразования Фурье — его связь со свёрткой. Если $\star$ обозначает свёртку:

$$\mathcal{F}\{f\star g\}=\hat{f}\cdot \hat{g}$$

Это означает, что свёртка во временной области становится поточечным умножением в частотной области.

«Глубокое изучение природы — самый плодотворный источник математических открытий.» — Жозеф Фурье, Аналитическая теория теплоты, 1822

Это справедливо спустя два столетия.