랜드웨버 반복

1. 개요

랜드웨버 반복(Landweber iteration)은 불량조건 선형 문제 $Ax\approx b$ 에 대해 최소제곱 목적함수 $\tfrac12\|Ax-b\|^2$ 의 고정 보폭 경사하강법을 돌리고, 반복 횟수 자체를 정규화 매개변수로 써서 일찍 멈추는 방법이다. 루이스 랜드웨버가 1951년 제1종 프레드홀름 적분방정식을 풀기 위해 제안했다.¹ 수식만 보면 정규방정식 $A^{*}Ax=A^{*}b$ 에 적용한 리처드슨 반복이고, 리처드슨 반복 문서도 “다른 얼굴들” 의 하나로 짧게 다룬다. 이 문서는 그 짧은 문단이 미뤄 둔 이야기 — 왜 멈추는 게 정규화인지, 언제 멈추는지, 그리고 왜 느린지 — 를 다룬다.

역문제에서 $A$ 는 대개 콤팩트 연산자의 이산화라 특이값이 0 으로 빠르게 떨어지고, 잡음 낀 $b$ 로 $A^{-1}b$ 를 그대로 계산하면 잡음이 $1/\sigma_{\min}$ 배로 증폭된다. 정규화의 표준은 티호노프 정규화지만, $A$ 가 너무 커서 분해는커녕 저장도 못 하고 $A$ 와 $A^{*}$ 를 곱하는 서브루틴만 있는 경우(단층 촬영, 지진파 역산, 대기 원격 탐사)에는 반복법이 유일한 선택이다. 랜드웨버는 그중 가장 단순하고, 분석이 가장 깔끔해서 이론의 기준선 역할을 한다.

2. 필터 인자 — 반복 횟수가 정규화가 되는 이유

$A$ 의 특이값 분해 $A=\sum_i\sigma_iu_iv_i^{*}$ 를 쓰면, $x_0=0$ 에서 출발한 $k$ 번째 반복은

$$x_k=\sum_i \varphi_i^{(k)}\,\frac{u_i^{*}b}{\sigma_i}\,v_i,\qquad \varphi_i^{(k)}=1-(1-\omega\sigma_i^2)^k$$

로 닫힌꼴이 나온다. $\varphi_i^{(k)}$ 가 필터 인자다. 보폭 조건 $0<\omega\sigma_1^2<2$ 아래서 $|1-\omega\sigma_i^2|<1$ 이므로

• 큰 특이값 ($\omega\sigma_i^2$ 가 1 근처): 몇 번 만에 $\varphi_i\approx1$ — 신호 성분이 빨리 들어온다.
• 작은 특이값 ($\omega\sigma_i^2\ll1$): $\varphi_i^{(k)}\approx k\,\omega\sigma_i^2$ — 잡음 증폭 성분은 반복 수에 비례해 천천히 들어온다.

경계는 대략 $\sigma_i^2\approx1/(\omega k)$ 근처다. 티호노프의 필터 인자 $\sigma_i^2/(\sigma_i^2+\alpha)$ 와 비교하면 $\alpha\approx1/(\omega k)$ 의 대응이 보인다. 반복을 $k$ 번 하는 것은 정규화 매개변수 $\alpha=1/(\omega k)$ 로 티호노프를 푸는 것과 질적으로 같다. 그래서 반복을 무한히 하면 $\alpha\to0$, 즉 정규화 없는 해로 가서 잡음이 폭발한다. 이 “처음엔 좋아지다가 나중에 나빠지는” 현상을 준수렴(semi-convergence)이라 부른다.

3. 검산 — 가우스 흐림 풀기

$[0,1]$ 위의 가우스 흐림 핵($\sigma=0.05$)을 100 점 중점 규칙으로 이산화한 $A$(조건수 $\approx1.4\times10^{18}$, 사실상 특이)에 두 봉우리짜리 참값 $x$ 를 넣고, $b=Ax+e$ 에 상대 1% 의 가우스 잡음을 섞었다. $\omega=1/\sigma_1^2$.

반복 $k$	상대 오차 $\lVert x_k-x\rVert/\lVert x\rVert$
1	0.405
10	0.151
100	0.063
1 000	0.038
10 000	0.077
100 000	0.277
200 000	0.383

최적은 $k=776$ 에서 오차 0.0377 이었다. 그 뒤로는 반복할수록 해가 나빠지고, 정규화 없이 solve(A, b) 를 하면 상대 오차가 $5\times10^{15}$ 다 — 숫자가 아니라 잡음이다. 같은 문제에서 매개변수를 사후 최적으로 고른 티호노프는 0.040, 아래에서 다룰 CGLS 는 15 반복에 0.035 였다.

3.1. 언제 멈추나 — 불일치 원리

참값을 모르니 실제로는 최적 $k$ 를 알 수 없다. 표준 규칙은 모로조프 불일치 원리다. 잡음 수준 $\delta=\|e\|$ 를 안다면

$$\|b-Ax_k\|\le\tau\delta\qquad(\tau>1)$$

을 처음 만족하는 $k$ 에서 멈춘다. 잔차를 잡음보다 작게 만드는 것은 잡음을 적합하는 것이기 때문이다. 위 예에서 $\tau=1.01$ 로 하면 $k=76$ 에서 멈추고 오차는 0.069 — 최적(0.038)의 두 배 가까이지만, 참값 없이 얻은 결과로는 충분히 좋다. 랜드웨버에 대해서는 이 규칙이 잡음 $\delta\to0$ 일 때 차수 최적의 수렴 속도를 준다는 것이 증명돼 있다(엥글·한케·노이바우어 교과서 6장). $\delta$ 를 모르면 L-곡선이나 일반화 교차검증 같은 휴리스틱을 쓰는데, 이들은 반례가 알려져 있어 보장이 없다.

4. 느리다 — 그리고 그게 왜 문제인가

위 예에서 랜드웨버는 최적까지 776 반복, CGLS 는 15 반복이었다. 우연이 아니다. 매끄러움 가정(소스 조건)의 지수를 $\nu$ 라 하면 랜드웨버의 최적 정지 반복 수는 대략 $\delta^{-2/(2\nu+1)}$ 로 크는데, 크리로프 방법은 그 제곱근 정도에서 같은 정확도에 도달한다.² 이유는 필터 다항식에 있다. 랜드웨버의 $k$ 번째 해는 $A^{*}A$ 의 고정된 다항식 $1-(1-\omega t)^k$ 로 필터링한 것인데, 크리로프 부분공간법은 같은 차수의 다항식 중 데이터에 맞춰 최적인 것을 고른다. 고정 보폭 경사하강이 켤레기울기법보다 느린 것과 정확히 같은 이야기다.

그래서 선형 문제의 실무 표준은 랜드웨버가 아니라 정규방정식의 CG 인 CGLS, 또는 수치적으로 동치이면서 더 안정한 LSQR이다. 둘 다 준수렴하므로 같은 불일치 원리로 멈춘다. 체비쇼프 가속을 얹은 $\nu$-방법(브라케이지)도 랜드웨버를 제곱근 수준으로 빠르게 만든다.

5. 그런데도 랜드웨버를 쓰는 곳

• 제약이 있는 문제 — 사영 랜드웨버. 매 걸음 뒤에 볼록 집합 $C$ 로 사영하면 $x_{k+1}=P_C\!\left(x_k+\omega A^{*}(b-Ax_k)\right)$ 이다. 음수가 될 수 없는 밀도·농도·영상 밝기에 $C=\{x\ge0\}$ 를 거는 것은 한 줄로 끝나지만, CG 계열에는 이렇게 단순히 끼워 넣을 수 없다. 이 걸음을 일반 근접 연산자로 바꾸면 근접 경사법(ISTA)이고, $\ell_1$ 근접 연산자(소프트 임계)를 쓰면 희소 복원이 된다. 결국 현대 압축 센싱 알고리즘들의 조상이 랜드웨버다.
• 단층 촬영의 SIRT. 전산 단층촬영의 SIRT·심미노(Cimmino) 방법은 행·열 가중치를 붙인 랜드웨버, 즉 전처리된 랜드웨버다. 모든 투영 데이터를 한 번에 써서 병렬화가 쉽고 잡음에 둔감해, 행 하나씩 쓰는 카치마르츠 방법(ART)과 짝을 이룬다.
• 비선형 역문제. $F(x)=y$ 에 대해 $x_{k+1}=x_k+\omega F'(x_k)^{*}(y-F(x_k))$ 로 그대로 확장된다. 한케·노이바우어·셰르처(1995)가 “접선 원뿔 조건” 아래서 불일치 원리와 함께 수렴·정규화 성질을 증명했다. 비선형에서는 CG 의 깔끔한 이론이 깨지므로, 분석 가능한 단순함이 다시 장점이 된다.
• 딥러닝의 조기 종료. 신경망을 경사하강으로 학습하다 검증 오차가 오르기 시작할 때 멈추는 관행은, 선형화하면 정확히 랜드웨버의 준수렴이다. “조기 종료는 정규화다” 라는 말의 수학적 근거가 여기 있다.³

6. 관련 문서

• 리처드슨 반복 · 경사하강법 · 티호노프 정규화 · 절단 특이값 분해
• 역문제 · 프레드홀름 적분방정식 · LSQR · 켤레기울기법
• 근접 경사법 · 전산 단층촬영 · 모로조프 불일치 원리 · 카치마르츠 방법 · CGLS

7. Footnotes

1. 원 논문 제목이 그대로 An iteration formula for Fredholm integral equations of the first kind 다. 랜드웨버는 아이오와 대학 수리연구소에서 선박 유체역학을 연구하던 사람이다. 정규화 이론이라는 말이 생기기(티호노프, 1963) 10여 년 전이라 “일찍 멈추면 정규화” 라는 해석은 나중에 붙었다. ↩

2. 정확한 지수는 소스 조건의 형태와 잡음 모형에 따라 달라지지만, “랜드웨버 $k$ 번 ≈ CG $\sqrt k$ 번” 이라는 경험칙은 문헌과 실험에서 꾸준히 확인된다. 위 예의 776 대 15 는 그보다도 더 벌어졌다. 경사하강을 고정 보폭으로 돌리면 현생이 갈려 나간다는 것을 숫자로 보여 주는 장면. ↩

3. 그러니까 2010년대 딥러닝 논문들이 “암묵적 정규화” 라는 이름으로 재발견한 현상의 선형판 증명은 1951년에 이미 있었다. 랜드웨버 본인은 적분방정식을 손으로 풀던 시대의 사람이니, 자기 공식이 수십억 매개변수 모델의 학습 곡선을 설명하게 될 줄은 몰랐을 것이다. ↩