토플리츠 행렬

1. 개요

토플리츠 행렬 Toeplitz Matrix
정의	Tij = ti−j (대각선마다 상수)
자유도	2n − 1 개 (대칭이면 n 개)
행렬-벡터 곱	FFT 로 O(n log n)
직접 풀이	레빈슨류 O(n2)
반복 풀이	순환 전처리 CG
등장처	정상 과정 공분산, 비주기 합성곱, 균일 격자 상수계수 이산화

대각선 하나에 숫자 하나. $n^2$ 칸을 $2n-1$ 개 숫자로 채운 행렬이니, 그 절약을 계산에서도 돌려받아야 한다.

토플리츠 행렬(Toeplitz matrix)은 각 대각선을 따라 성분이 일정한, 즉 $T_{ij} = t_{i-j}$ 꼴인 행렬이다. 독일 수학자 오토 퇴플리츠(Otto Toeplitz)의 이름을 땄다¹.

$$T_n = \begin{pmatrix} t_0 & t_{-1} & t_{-2} & \cdots & t_{-(n-1)} \\ t_1 & t_0 & t_{-1} & \ddots & \vdots \\ t_2 & t_1 & t_0 & \ddots & t_{-2} \\ \vdots & \ddots & \ddots & \ddots & t_{-1} \\ t_{n-1} & \cdots & t_2 & t_1 & t_0 \end{pmatrix}$$

이 구조가 나오는 이유는 하나로 요약된다 — 시프트 불변성. 성분이 위치 $i, j$ 가 아니라 그 차이 $i-j$ 에만 의존하는 모든 곳에 토플리츠가 생긴다.

• 정상 확률과정의 공분산. $\mathrm{Cov}(x_i, x_j) = r_{i-j}$ 이므로 공분산 행렬이 대칭 토플리츠다. 위너 필터의 정규방정식, 자기회귀 모형의 율-워커 방정식, 가우시안 프로세스 회귀를 등간격 격자에서 하면 다 이 꼴이다.
• 비주기 합성곱. 유한 길이 신호에 필터를 거는 것은 토플리츠 행렬 곱이다. 주기 경계로 감으면 순환 행렬이 된다.
• 균일 격자 위 상수계수 이산화. 1차원 디리클레 문제의 유한차분법 라플라시안 $\mathrm{tridiag}(-1, 2, -1)$ 이 대표적이다. 차분 커널이 위치와 무관하니 토플리츠다.
• 차 커널 적분방정식. $\int k(x-y)u(y)\,dy$ 를 등간격으로 이산화하면 토플리츠(2차원이면 블록 토플리츠)가 된다.

일반 조밀 행렬로 취급하면 저장 $O(n^2)$, 가우스 소거법 $O(n^3)$ 이다. 토플리츠 구조를 쓰면 저장 $O(n)$, 곱셈 $O(n\log n)$, 풀이 $O(n^2)$ 또는 그 이하로 떨어진다. 이 문서는 그 세 가지 절약이 어디서 나오는지와, 구조가 주는 스펙트럼 정보를 정리한다.

2. 심볼과 세게 정리 — 스펙트럼을 미리 안다

토플리츠 수열 $\{t_k\}$ 를 푸리에 계수로 갖는 $2\pi$-주기 함수

$$f(\theta) = \sum_{k=-\infty}^{\infty} t_k\, e^{ik\theta}$$

를 심볼(symbol) 또는 생성 함수라 하고, $T_n = T_n(f)$ 로 쓴다. $f$ 가 실수값이면 $T_n(f)$ 는 에르미트이고, 다음이 성립한다.

• $T_n(f)$ 의 모든 고유값은 $[\min f, \max f]$ 안에 있다. 특히 $f > 0$ 이면 모든 $n$ 에서 양정치다.
• 그레난더-세게 정리: $n \to \infty$ 에서 $T_n(f)$ 의 고유값은 $f(\theta)$ 의 값들과 같은 분포를 따른다. 즉 고유값 히스토그램이 $f$ 를 $[-\pi,\pi]$ 에서 균일하게 샘플한 값의 히스토그램으로 수렴한다.

$\mathrm{tridiag}(-1,2,-1)$ 의 심볼은 $f(\theta) = 2 - 2\cos\theta$ 이고, 고유값은 정확히 $\lambda_j = 2 - 2\cos\bigl(\tfrac{j\pi}{n+1}\bigr)$ 다. $n = 8$ 로 재면 작은 쪽 세 개가 $0.12061$, $0.46791$, $1.00000$ 으로 공식과 유효숫자 전부 일치한다. 심볼이 $\theta = 0$ 에서 0이 되므로 조건수는 $\kappa \approx 4(n+1)^2/\pi^2$ 로 $n^2$ 에 비례해 커진다. 반대로 $f$ 가 0에서 멀리 떨어져 있으면 $n$ 을 키워도 조건수가 유계다 — 위너 필터의 공분산은 파워 스펙트럼이 양수인 한 아무리 길게 잡아도 조건수가 $\max f/\min f$ 를 넘지 않는다.

이 정보는 공짜로 얻는 고유값 문제의 답이자, 아래 전처리기 설계의 근거다.

3. 빠른 곱셈 — 순환 임베딩

$n \times n$ 토플리츠를 $2n \times 2n$ 순환 행렬 안에 묻는다. 첫 열을 $(t_0, t_1, \dots, t_{n-1}, 0, t_{-(n-1)}, \dots, t_{-1})$ 로 잡고, 벡터 $\mathbf{x}$ 를 길이 $2n$ 으로 영채움해 순환 곱을 한 뒤 앞 $n$ 개를 취하면 $T\mathbf{x}$ 가 정확히 나온다. 순환 곱은 고속 푸리에 변환 세 번이므로 $O(n \log n)$ 이다. 원리는 합성곱 정리의 영채움과 같다.

실측: $n = 256, 1024, 4096$ 에서 조밀 곱 대비 상대오차가 각각 $3.3\times10^{-16}$, $4.8\times10^{-16}$, $5.6\times10^{-16}$ 이었다. 정확도를 잃지 않는다. 이 곱셈 하나로 켤레기울기법·GMRES 같은 반복법의 반복당 비용이 $O(n\log n)$ 이 된다.

4. 풀이 — 세 갈래

4.1. 레빈슨류 직접법

대칭 양정치 토플리츠 계는 레빈슨-더빈 알고리즘으로 $O(n^2)$ 에 푼다. 크기 $m$ 의 해에서 $m+1$ 의 해를 내적 하나와 벡터 갱신 하나로 만드는 점화식이다. 저장은 $O(n)$ 이고 구현이 짧다. 자세한 점화식과 안정성은 해당 문서로 넘긴다.

4.2. 초고속 직접법

분할 정복으로 $O(n \log^2 n)$ 에 푸는 이른바 초고속(superfast) 알고리즘도 있다(브렌트·거스타브슨·윤 1980, 아마르·그래그 1988 등). 점근 비용은 매력적이지만 상수가 크고 수치 안정성 보장이 약해서, 실무에서는 $n$ 이 아주 클 때가 아니면 아래 반복법이 더 자주 쓰인다.

4.3. 순환 전처리 켤레기울기법

토플리츠를 순환 행렬로 근사하면 그 근사의 역행렬은 FFT 로 $O(n\log n)$ 에 적용된다. 이걸 전처리기로 쓴다.

• 스트랭 전처리기(Strang, 1986): $T$ 의 가운데 대각선들을 그대로 복사하고 나머지를 주기적으로 감아 채운다. 첫 열이 $(t_0, t_1, \dots, t_{\lfloor n/2 \rfloor}, t_{-\lfloor (n-1)/2 \rfloor}, \dots, t_{-1})$.
• T. 챈 전처리기(T. Chan, 1988): 프로베니우스 노름으로 $T$ 에 가장 가까운 순환 행렬. 첫 열이 $c_k = \frac{(n-k)\,t_k + k\,t_{k-n}}{n}$.

R. 챈과 스트랭(1989)은 심볼이 양수이고 충분히 매끄러우면 전처리된 행렬 $C^{-1}T$ 의 고유값이 1 근처에 군집하고 몇 개만 바깥에 남는다는 것을 보였다. 군집된 스펙트럼에서 CG 는 초선형 수렴한다.

$t_k = 0.9^{\lvert k \rvert}$ (KMS 행렬², 조건수 약 360)에 무작위 우변, 상대잔차 $10^{-10}$ 까지의 CG 반복 수:

$n$	전처리 없음	스트랭	T. 챈
256	131	4	9
1024	198	3	7
4096	228	3	6

반복당 비용은 FFT 몇 번이므로 $n = 4096$ 계를 FFT 수십 번으로 푼 셈이다. 레빈슨의 $O(n^2)$ 보다도 싸다.³ 심볼이 0을 가지면(위의 라플라시안처럼) 순환 전처리기 자체가 특이해지거나 군집이 깨지므로, 그때는 0을 피하도록 보정한 변형이나 띠 토플리츠 전처리기를 쓴다.

5. 변위 구조 — 역행렬은 토플리츠가 아니다

토플리츠 행렬의 곱과 역행렬은 일반적으로 토플리츠가 아니다. KMS 행렬의 역행렬은 삼중대각이지만 대각선이 $(1, 1+\rho^2, \dots, 1+\rho^2, 1)/(1-\rho^2)$ 라 양 끝이 다르다.

그래도 구조가 사라지는 건 아니다. 아래로 한 칸 미는 시프트 행렬 $Z$ 로 변위(displacement) $\nabla T = T - ZTZ^\top$ 를 만들면, 토플리츠에서는 $(i,j)$ 와 $(i-1,j-1)$ 성분이 같으므로 첫 행과 첫 열만 남는다. 즉 $\mathrm{rank}(\nabla T) \le 2$ 다. 카일라스·쿵·모르프(1979)는 역행렬이 짝이 되는 변위 $T^{-1} - Z^\top T^{-1} Z$ 에 대해 같은 계수를 가진다는 것을 보였다(무작위 $10\times10$ 토플리츠로 재면 두 변위의 계수가 모두 2다). 그래서 $T^{-1}$ 은 생성자 벡터 두어 개로 완전히 정해지고, 이것이 첫 열과 마지막 열만으로 역행렬을 쓰는 고흐베르크-세메쿨 공식이다.

이 관점은 토플리츠를 넘어 변위 계수가 작은 행렬 전체(토플리츠의 곱·역·슈어 보수, 토플리츠+행켈 등)를 같은 빠른 알고리즘으로 다루게 해 준다. 일반화된 슈어 알고리즘이 그 대표다.

6. 친척들

• 순환 행렬 — 토플리츠의 주기판. DFT 로 정확히 대각화된다. 토플리츠는 순환에 “경계 결함”을 더한 것으로 볼 수 있다.
• 토플리츠+행켈 — 노이만 경계조건의 라플라시안처럼 대칭 반사가 끼면 나온다. 이산 코사인 변환이 이 부류를 대각화한다.
• 블록 토플리츠 / BTTB — 2차원 균일 격자의 합성곱·흐림(blur) 연산자. 블록 단위로 토플리츠이고 블록 자체도 토플리츠다. 순환 임베딩과 전처리가 2차원 FFT 로 그대로 확장된다.
• 띠 토플리츠 — 유한 길이 차분 스텐실. 띠 토머스 알고리즘으로 $O(n)$ 이라 오히려 위의 장치가 필요 없다.

7. 함정

• 구조는 생각보다 쉽게 깨진다. 비균일 격자, 변수 계수, 경계 행 한 줄의 수정만으로 토플리츠가 아니게 된다. “거의 토플리츠”면 토플리츠 부분을 전처리기로만 쓰는 게 정석이다.
• 양정치가 아닌 토플리츠에서 레빈슨은 깨질 수 있다. 행렬이 정칙이어도 선행 주소행렬식이 0이면 분모가 0이 된다. 피벗이 없는 점화식이라서다.
• 표본 자기공분산을 그대로 쓰면 양정치가 보장되지 않을 수 있다. 분모를 $N$ 으로 나눈 편향 추정량은 양반정치가 보장되지만, $N-k$ 로 나눈 불편 추정량은 그렇지 않다. 율-워커 추정에서 편향 추정량을 쓰는 이유다.
• 역행렬을 명시적으로 만들지 마라. 조밀 $n^2$ 이 되어 지금까지 아낀 걸 다 토한다. 필요하면 고흐베르크-세메쿨 생성자만 저장한다.

8. 관련 문서

• 순환 행렬 · 레빈슨-더빈 알고리즘 · 행켈 행렬 · 이산 코사인 변환
• 고속 푸리에 변환 · 합성곱 정리 · 블루스타인 알고리즘
• 켤레기울기법 · 전처리기 · GMRES · 슈어 보수
• 위너 필터 · 파워 스펙트럼 · 상관함수 · 가우시안 프로세스 · 자기회귀 모형

9. Footnotes

1. 독일어 발음은 「퇴플리츠」에 가깝지만 국내 문헌은 「토플리츠」·「퇴플리츠」·「테플리츠」를 섞어 쓴다. 검색할 땐 그냥 Toeplitz 로 치는 게 정신 건강에 좋다. ↩

2. 카츠-머독-세게(Kac–Murdock–Szegő) 행렬. 성분이 $\rho^{\lvert i-j \rvert}$ 로 AR(1) 과정의 상관행렬이다. 역행렬이 삼중대각이라는 사실이 알려져 있어 토플리츠 알고리즘의 단골 시험 문제로 끌려 나온다. 스트랭 전처리기가 3회 만에 끝내는 것도 이 삼중대각 역행렬 덕이 크다. ↩

3. 「$O(n^2)$ 이면 충분히 빠른 거 아냐?」 — $n = 10^6$ 짜리 위성 영상 흐림 연산자 앞에서는 아니다. $10^{12}$ 과 $2\times10^{7}$ 의 차이는 커피 한 잔과 지구 한 바퀴의 차이다. ↩