푸리에 행렬 \(F_n\) 은 시간 도메인 신호를 주파수 도메인으로 옮기는 unitary 행렬이다. 직접 곱셈 \(F_n \mathbf{c}\) 는 \(n^2\) 연산이지만, Cooley-Tukey의 FFT는 \(F_n\) 을 두 개의 \(F_{n/2}\) 로 재귀 분해하여 \(\frac{n}{2}\log_2 n\) 연산에 끝낸다. 이 포스트는 Strang §10.3 을 뼈대로 1의 \(n\) 제곱근과 푸리에 행렬 \(F_n\) 의 구조, \(F_n F_n^H = nI\) 증명, 한 단계 재귀 분해 (\(F_n\) 에서 \(F_{n/2}\) 둘로), butterfly 다이어그램, bit-reversal 순서, 전체 연산량 \(\frac{1}{2}n\log n\) 유도를 정리한다. 실무 응용(JPEG, 오디오, CNN, Multigrid)까지 폭을 넓힌다.
Mathematics
Machine Learning
Deep Learning
저자
Kwangmin Kim
공개
2026년 04월 13일
1 개요
Strang은 §10.3 서두에서 이 알고리즘을 “지난 세기 가장 중요한 수치 알고리즘”이라 부른다. 과장이 아니다. FFT 이전의 푸리에 변환은 \(O(n^2)\) 연산이었고, \(n = 10^6\) 짜리 신호 한 번 변환에 \(10^{12}\) 연산이 들었다. 1965년 Cooley와 Tukey가 발표한 Fast Fourier Transform 은 이를 \(O(n \log n)\) 으로 단축시켜 같은 \(n = 10^6\) 에서 \(2 \times 10^7\) 연산만을 필요로 한다. 5만 배 차이다.
이 단축은 JPEG 이미지 압축, MP3·AAC 오디오 코덱, 5G·Wi-Fi의 OFDM 변조, MRI 영상 재구성, 딥러닝의 convolution 가속, 천문학의 전파 간섭계, 금융의 시계열 분석까지 20세기 정보 기술 전반의 실제 구현 가능성을 결정했다. FFT가 없었다면 많은 기술이 존재 자체가 불가능했거나 수십 년 늦어졌을 것이다.
알고리즘 자체는 간단하다 — “길이 \(n\) 신호의 푸리에 변환을 길이 \(n/2\) 신호 두 개의 변환으로 쪼갠다”는 재귀 한 줄이다. 이 한 줄이 작동하는 이유는 1의 \(n\) 제곱근 \(\omega_n = e^{2\pi i/n}\) 이 갖는 대수적 대칭이다. 이 포스트는 그 대칭이 어떻게 재귀를 만들어 내는지를 수식과 그림으로 단계별로 추적한다.
즉 \(U_n = F_n/\sqrt{n}\) 이 unitary. Strang은 계산 편의상 \(\sqrt{n}\) 을 넣지 않고 \(F_n^{-1} = \frac{1}{n} F_n^H\) 로 쓴다.
직관: 왜 unitary 인가
\(F_n\) 의 각 열은 “특정 주파수의 샘플 벡터”다. 0번째 열은 상수(주파수 0, DC), 1번째 열은 기본 주파수, 2번째 열은 2배 주파수, … 이다. 서로 다른 주파수의 샘플은 직교하며(내적 0), 각 벡터의 길이는 \(\sqrt{n}\) 이다. 정규화하면 orthonormal 기저가 되고 unitary 조건이 성립한다.
이는 Parseval 정리 \(\|\mathbf{c}\|^2 = \frac{1}{n}\|F_n \mathbf{c}\|^2\) 의 근거다 — 주파수 도메인의 에너지와 시간 도메인의 에너지가 (정규화 상수를 제외하면) 같다. 불확정성 원리·신호처리 필터 설계의 근본 바탕이다.
Vandermonde 구조: \(F_n\) 은 점 \(1, w, w^2, \dots, w^{n-1}\) 에서의 Vandermonde 행렬이다. 따라서 \(\mathbf{y} = F_n \mathbf{c}\) 는 다항식 \(p(z) = \sum c_k z^k\) 를 이 점들에서 평가하는 것과 동일. 역으로 \(F_n^{-1} \mathbf{y} = \mathbf{c}\) 는 n개 단위원 점에서의 보간 문제를 푸는 것이다.
3 왜 직접 곱셈은 \(O(n^2)\) 인가
\(\mathbf{y} = F_n \mathbf{c}\) 를 성분별로 쓰면
\[
y_j = \sum_{k=0}^{n-1} w^{jk} c_k
\]
각 \(y_j\) 는 \(n\) 번의 곱셈 + \((n-1)\) 번의 합. 총 \(n\) 개의 \(y_j\) 가 있으므로 \(n^2\) 곱셈. 행렬은 0이 전혀 없으므로 절약할 수 없어 보인다.
\(n = 1024\) 이면 \(\approx 10^6\) 곱셈. 한 번은 빠르지만 실시간 오디오(초당 44100 샘플, 50ms 윈도우마다 변환)에서는 초당 수천만~수억 번이 필요해 부담이 된다. 실시간 FIR 필터, 영상·비디오 처리, 과학 계산에서도 마찬가지다.
그런데 \(F_n\) 의 원소가 특정 패턴 \(w^{jk}\) 를 따른다는 사실을 이용하면 \(O(n \log n)\) 로 줄일 수 있다. 이것이 FFT다.
4 FFT의 핵심 아이디어: \(F_n \to 2 \times F_{n/2}\)
4.1 짝수·홀수 분리
\(n\) 이 짝수라 하자 (\(n = 2m\)). \(y_j = \sum_k w^{jk} c_k\) 를 짝수 인덱스 (\(k = 0, 2, 4, \dots\)) 와 홀수 인덱스 (\(k = 1, 3, 5, \dots\)) 로 쪼갠다.
즉 길이 \(n\) 의 FFT 한 번이 길이 \(n/2\) 의 FFT 두 번 + 보조 연산으로 쪼개졌다.
4.3 위·아래 절반의 결합
\(j\) 가 \(0, 1, \dots, m-1\) 에만 정의되어 있어 보이지만, \(y_j\) 는 \(0, 1, \dots, n-1\) 까지 모두 필요하다. 핵심 관찰은 \(w_n^{m+j} = w_n^m \cdot w_n^j = -w_n^j\) (\(w_n^m = e^{i\pi} = -1\)).
\(j \to j + m\) 로 치환하면 \(y'_{j+m} = y'_j\) (주기 \(m\)), \(y''_{j+m} = y''_j\), 그리고 \(w_n^{j+m} = -w_n^j\). 따라서
FFT: \(\frac{n}{2}\log_2 n = 512 \times 10 = 5{,}120\)
단축률: 약 200배
\(n = 10^6\) 에서는 약 5만 배, \(n = 10^9\) 에서는 약 3천만 배. \(n\) 이 커질수록 단축률이 기하급수로 증가한다.
직관: 분할정복의 교과서 사례
분할정복 알고리즘의 비용은 항상 (레벨 수) × (레벨당 작업량) 으로 분해된다. FFT의 레벨 수는 \(\log_2 n\), 레벨당 작업량은 \(O(n)\). 두 곱이 \(O(n \log n)\).
다른 분할정복 알고리즘(병합 정렬, 퀵 정렬)도 같은 구조이지만, FFT만의 특별함 은 분할이 “수학적으로 자연”하다는 점이다. \(w_n^2 = w_m\) 이라는 한 줄짜리 대수 관계가 입력이 어떻든 정확한 반분을 보장한다. 정렬은 입력 분포에 따라 최악의 경우 불균형이 생길 수 있지만 (퀵 정렬의 \(O(n^2)\) 최악), FFT는 항상 \(O(n\log n)\) 이다.
이 “대수 구조가 알고리즘 복잡도를 결정한다” 는 깊은 관찰이 FFT를 단순한 트릭이 아니라 근본 원리로 만든다.
7 Bit-Reversal 순서
재귀 분할을 \(\ell\) 번 적용하면 입력 \(c_0, c_1, \dots, c_{n-1}\) 이 특이한 순서로 재배열된다.
놀라운 패턴: 이 최종 순서 \((0, 4, 2, 6, 1, 5, 3, 7)\) 을 3비트 이진수로 쓰고 비트를 뒤집으면 원래 순서가 복원된다.
십진
이진
비트 뒤집기
십진
0
000
000
0
4
100
001
1
2
010
010
2
6
110
011
3
1
001
100
4
5
101
101
5
3
011
110
6
7
111
111
7
이를 bit-reversal 순서라 한다. 실제 FFT 구현은 재귀 호출 대신 “입력을 bit-reversal 순서로 한 번에 재배열” → “\(\log n\) 단계의 in-place butterfly” 로 반복문 형태(iterative FFT)가 표준이다. 메모리 할당·재귀 호출 오버헤드가 없어 훨씬 빠르다.
직관: 비트 뒤집기는 왜 재귀 순서를 표현하는가
재귀 분할의 각 단계에서 인덱스 \(k\) 가 “짝수 쪽(\(k\) 의 최하위 비트가 0)” 인지 “홀수 쪽(\(k\) 의 최하위 비트가 1)” 인지가 결정된다. 다음 단계는 남은 비트 중 다음 최하위 비트를 본다. 이렇게 \(\ell\) 단계 동안 \(\ell\) 비트를 “최하위 → 최상위” 순서로 훑는다.
원래 인덱스 “MSB → LSB” 순서 → 훑어진 “LSB → MSB” 순서 → 정확히 비트 뒤집기. 재귀 분할 트리의 리프 순서가 bit-reversal 이라는 사실은 우연이 아니라 분할 규칙의 구조적 결과다.
8 코드 예시
8.1 Step 1: 푸리에 행렬과 직접 곱셈
코드
import numpy as npdef fourier_matrix(n):"""F_n: (F_n)_{jk} = w^{jk}, w = e^(2πi/n)""" w = np.exp(2j* np.pi / n) j, k = np.meshgrid(np.arange(n), np.arange(n), indexing='ij')return w ** (j * k)n =8F = fourier_matrix(n)# Unitary 성질: F^H F = n Iprint(f"F^H F / n = I ? {np.allclose(F.conj().T @ F / n, np.eye(n))}")# 대칭 (전치): F = F^Tprint(f"F = F^T ? {np.allclose(F, F.T)}")# Hermitian은 아님print(f"F = F^H ? {np.allclose(F, F.conj().T)}")# 직접 곱셈c = np.random.randn(n).astype(complex)y_direct = F @ c# NumPy FFT와 비교 (규약 주의: np.fft.fft 는 e^{-2πi/n} 사용)y_fft_numpy = np.fft.fft(c)print(f"직접 곱(e^{{+2πi/n}})과 np.fft.fft 는 규약 차이: "f"{np.allclose(y_direct, y_fft_numpy.conj())}")
8.2 Step 2: 재귀 FFT 구현 (Cooley-Tukey)
코드
import numpy as npdef fft_recursive(c):"""교과서 재귀 FFT, 규약 y_j = Σ w^{jk} c_k with w = e^{2πi/n}.""" n =len(c)if n ==1:return c.astype(complex).copy()assert n %2==0, "길이는 2의 거듭제곱"# 짝수·홀수 분리 y_even = fft_recursive(c[0::2]) # F_{n/2} c' y_odd = fft_recursive(c[1::2]) # F_{n/2} c''# Butterfly: y_j = y'_j + w^j y''_j, y_{j+m} = y'_j - w^j y''_j m = n //2 w = np.exp(2j* np.pi / n) w_j = w ** np.arange(m) t = w_j * y_oddreturn np.concatenate([y_even + t, y_even - t])# 검증n =16c = np.random.randn(n) +1j* np.random.randn(n)y_rec = fft_recursive(c)y_ref = fourier_matrix(n) @ cprint(f"재귀 FFT vs 직접 곱: 오차 = {np.linalg.norm(y_rec - y_ref):.2e}")
8.3 Step 3: 연산량 비교 (실측)
코드
import numpy as npimport timens = [2**k for k in [8, 10, 12, 14, 16, 18, 20]]print(f"{'n':>8}{'Direct (ms)':>14}{'FFT (ms)':>12}{'Speedup':>10}")for n in ns: c = np.random.randn(n) +1j*np.random.randn(n) t0 = time.time() y_fft = np.fft.fft(c) t_fft = (time.time() - t0) *1000if n <=2**12: # 직접 곱은 n=4096까지만 F = np.exp(-2j* np.pi * np.outer(np.arange(n), np.arange(n)) / n) t0 = time.time() y_dir = F @ c t_dir = (time.time() - t0) *1000print(f"{n:>8}{t_dir:>14.2f}{t_fft:>12.3f}{t_dir/t_fft:>9.0f}x")else:print(f"{n:>8}{'(too slow)':>14}{t_fft:>12.3f}{'>1000x':>10}")
8.4 Step 4: 응용 — 신호 주파수 분석
코드
import numpy as npimport matplotlib.pyplot as plt# 합성 신호: 50Hz + 120Hz + 노이즈fs =1000# 샘플링 주파수T =1.0# 길이 1초n =int(fs * T)t = np.arange(n) / fssignal =1.0*np.sin(2*np.pi*50*t) +0.5*np.sin(2*np.pi*120*t) \+0.3*np.random.randn(n)# FFTC = np.fft.fft(signal)freqs = np.fft.fftfreq(n, 1/fs)# 양의 주파수만 시각화pos = freqs >=0fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(10, 5))ax1.plot(t[:200], signal[:200]); ax1.set_title("시간 도메인 (앞 200 샘플)")ax1.set_xlabel("time (s)")ax2.stem(freqs[pos], np.abs(C[pos]), markerfmt=' ', basefmt=' ')ax2.set_xlim(0, 200); ax2.set_title("주파수 도메인 |C(f)|")ax2.set_xlabel("frequency (Hz)")plt.tight_layout(); plt.show()
이 코드의 핵심: 시간 도메인에서 얽힌 세 성분(50Hz, 120Hz, 노이즈)이 주파수 도메인에서는 명확한 두 피크(50, 120)와 전 주파수 대역에 흩어진 노이즈로 분리된다. FFT가 없으면 실시간으로 이런 스펙트럼을 얻는 것이 불가능하다.
9 응용
9.1 전통 분야
분야
역할
JPEG 영상 압축
8×8 DCT (FFT 친척)로 공간 주파수 분해 후 고주파 폐기
MP3/AAC 오디오
MDCT 로 시간-주파수 분석, 지각적 모델로 비트 할당
5G/Wi-Fi (OFDM)
부반송파 간 직교성이 DFT로 실현 — FFT 없으면 복조 불가능
MRI
k-공간(주파수 도메인) 측정 → 공간 영상으로 역 FFT
SAR (합성개구레이더)
도플러 주파수 분석으로 영상 재구성
천문학 전파 간섭계
간섭 패턴 → 영상 재구성 (역 FFT)
숫자 곱셈
두 큰 정수의 곱 = 계수의 convolution = FFT로 \(O(n\log n)\)
9.2 ML/DL
FFT 기반 convolution: 큰 커널(예: \(k \geq 11\)) 의 CNN 에서 \(\mathcal{F}(\text{signal}) \cdot \mathcal{F}(\text{kernel})\) 후 역 FFT 가 공간 도메인 convolution 보다 빠르다. PyTorch의 conv2d 가 커널 크기에 따라 자동 선택.
Fourier Neural Operator (FNO, Li et al. 2021): PDE 해를 학습할 때 \(\mathcal{F}\) → 학습 가능한 주파수 도메인 선형 변환 → \(\mathcal{F}^{-1}\) 구조로 메시 독립적 \(O(n\log n)\) 추론.
FNet (Lee-Thorp et al. 2021): Transformer의 self-attention 을 FFT로 대체. Attention의 \(O(n^2)\) 을 \(O(n\log n)\) 으로 낮추며 성능은 약간만 떨어진다.
Spectral Methods for RL: 주기 구조가 있는 환경(오디오, 진동)에서 관측을 주파수로 전처리.
9.3 수치 해석
스펙트럼 방법 PDE: 주기 경계 조건의 푸리에 기저 위에서 편도함수는 대각 행렬이 되어 풀이가 \(O(n \log n)\) 로 줄어든다.
Multigrid 고속화: 거친 격자에서의 잔차 보정에 FFT 기반 직접법을 사용.
convolution 전반: \((f * g)[n] = \sum_k f[k] g[n-k]\) 는 \(O(n^2)\) 이지만 \(\mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g)\) 를 이용해 \(O(n \log n)\) 으로 계산.
10 변형과 확장
실무에서 만나는 FFT 변형들을 짧게 정리한다.
변형
상황
방법
실수 입력 FFT
실제 신호는 실수
\(F_n\) 의 켤레 대칭 \(y_{n-j} = \bar{y}_j\) 이용 → 연산 절반 (np.fft.rfft)
다차원 FFT
2D/3D 이미지·영상
각 축 따라 1D FFT 반복 → 총 \(O(n \log n)\), \(n\) = 전체 원소 수