절단 특이값 분해

1. 개요[편집]

절단 특이값 분해 Truncated Singular Value Decomposition
약칭	TSVD
정의	xk = Σi≤k (uiTb / σi) vi
필터인자	fi = 1 (i ≤ k), 0 (i > k) — 브릭월
손잡이	절단 지표 k (정수 하나)
최적성	에카르트-영-미르스키 정리
부작용	하드 컷이 만드는 링잉

절단 특이값 분해(truncated SVD, TSVD)는 특이값 분해 $A = U\Sigma V^{T}$ 에서 상위 $k$ 개 특이값만 남기고 나머지를 통째로 버려, 저계수 근사를 만들거나 역문제의 해를 안정화하는 기법이다.

$$A_k = \sum_{i=1}^{k}\sigma_i u_i v_i^{T}, \qquad x_k = A_k^{+}b = \sum_{i=1}^{k}\frac{u_i^{T}b}{\sigma_i}\,v_i$$

정규화 없는 최소자승해 $x_{\mathrm{LS}} = \sum_i (u_i^{T}b/\sigma_i)v_i$ 가 왜 폭발하는지를 보면 TSVD의 동기는 자명하다. 분모 $\sigma_i$ 가 0으로 붕괴하는데 분자 $u_i^{T}b$ 는 잡음 바닥에서 멈추므로, 뒤쪽 항들이 잡음을 $1/\sigma_i$ 배로 증폭해 해에 쏟아붓는다. TSVD는 그 항들을 그냥 안 더한다. 손잡이가 실수 $\alpha$ 하나인 티호노프 정규화와 달리 정수 $k$ 하나라는 점이 다르다.

2. 필터인자 — 브릭월 대 소프트 필터[편집]

정규화 기법을 통일적으로 비교하는 언어가 필터인자 $f_i$ 다. 어떤 방법이든 해를 $x = \sum_i f_i (u_i^{T}b/\sigma_i)v_i$ 로 쓸 수 있고, 방법의 차이는 오직 $f_i$ 의 모양이다.

• TSVD: $f_i = 1\ (i\le k)$, $0\ (i>k)$. 이상적 저역통과 필터, 즉 브릭월.
• 티호노프: $f_i = \sigma_i^2/(\sigma_i^2+\alpha^2)$. 매끄럽게 감쇠하는 1차 필터.

두 방법은 $\alpha \approx \sigma_k$ 로 맞추면 대체로 비슷한 해를 준다. 실제로 실무 코드에서 둘을 바꿔 끼워도 그림이 크게 달라지지 않는 경우가 많고, 그래서 “어차피 같은 거 아니냐”는 인상을 받기 쉽다. 그런데 결정적으로 다른 상황이 두 가지 있다.

첫째, 특이값이 뭉쳐 있을 때. $\sigma_k \approx \sigma_{k+1}$ 이면 TSVD는 사실상 구분 불가능한 두 성분 사이에 칼을 대라고 강요한다. $k$ 를 1만 바꿔도 해가 눈에 띄게 튀고, 특이값이 거의 겹칠 때 개별 특이벡터 자체가 수치적으로 불안정하다는 문제까지 겹친다. 티호노프는 그 구간을 부드럽게 넘어가므로 이런 민감성이 없다.

둘째, 링잉. 전형적인 부적절 문제(디컨볼루션, 열전도 역추적, 단층촬영)에서 특이벡터 $v_i$ 는 지표가 커질수록 부호 변화가 늘어나는 점점 더 진동하는 함수다. 즉 SVD 전개는 사실상 문제에 맞춰진 푸리에 전개이고, TSVD는 그것을 특정 항에서 뚝 자르는 부분합이다. 결과는 예측 가능하다 — 참해에 불연속이나 급한 기울기가 있으면 그 근처에서 깁스 현상에 해당하는 과도한 진동(ringing, 오버슈트)이 남는다. 티호노프의 매끄러운 필터는 고차 항을 죽이되 급격히 끊지 않으므로 이 링잉이 훨씬 약하다. “둘이 비슷하다”는 말은 해를 노름으로 잴 때 맞고, 해를 눈으로 볼 때는 틀리는 경우가 있다.¹

3. k는 어떻게 고르나 — 이산 피카르 조건[편집]

$k$ 선택의 1차 도구는 이산 피카르 조건이다. 무잡음 데이터라면 $u_i^{T}b_{\text{exact}} = \sigma_i(v_i^{T}x_{\text{true}})$ 이므로 분자가 $\sigma_i$ 보다 빨리 떨어져야 정상이다. 관측에 섞인 잡음은 $u_i^{T}e$ 를 지표와 무관한 상수 수준(백색이면 정확히 그렇다)으로 만들어 놓기 때문에, 로그 축에 $\sigma_i$ 와 $|u_i^{T}b|$ 를 겹쳐 그리면 항상 같은 그림이 나온다. 앞쪽에서 나란히 내려가던 $|u_i^{T}b|$ 가 어느 지표에서 평평한 잡음 바닥에 착지하고 더는 안 내려간다. 그 착지 지표가 곧 유효 랭크이고 $k$ 의 자연스러운 후보다. 그 뒤 항들은 신호 대 잡음비가 1 미만이므로 더해 봐야 잡음만 는다.

보조 도구로 교차검증의 회전불변 판본인 GCV, 잡음 크기 $\delta$ 를 알 때의 불일치 원리($\|Ax_k-b\|_2 \le \tau\delta$ 를 만족하는 최소 $k$), 잔차 노름 대 해 노름의 L-곡선이 그대로 쓰인다. 다만 $k$ 가 정수라 L-곡선이 연속 곡선이 아니라 점들의 열이 되므로 곡률 최대점을 찾는 알고리즘을 그대로 쓸 수 없고, 스플라인으로 매끄럽게 잇는 등의 손질이 필요하다. 손잡이가 정수라는 게 편할 것 같지만 실제로는 이런 데서 불편하다.²

4. 에카르트-영-미르스키 정리 — 그리고 그것이 말하지 않는 것[편집]

TSVD의 명성은 에카르트-영-미르스키 정리에서 온다. 랭크 $k$ 이하의 모든 행렬 중에서 $A_k$ 가 $A$ 에 가장 가깝고, 그 오차가 정확히 잘라낸 특이값으로 결정된다.

$$\min_{\mathrm{rank}(B)\le k}\|A-B\|_2 = \|A-A_k\|_2 = \sigma_{k+1}, \qquad \|A-A_k\|_F = \sqrt{\textstyle\sum_{i>k}\sigma_i^2}$$

에카르트와 영(1936)이 프로베니우스 노름에 대해 증명했고 미르스키(1960)가 임의의 유니터리 불변 노름으로 일반화했다. $\sigma_k > \sigma_{k+1}$ 이면 최적해는 유일하다. 데이터 압축·주성분 분석·축소차수모델이 TSVD 위에 세워진 근거가 이 정리다.

그런데 여기서 아주 흔한 논리 비약이 하나 일어난다. “최적 저계수 근사”와 “좋은 정규화”는 서로 다른 주장이다. 정리는 $\|A - B\|$ 를 최소화한다고 말할 뿐, $\|x_k - x_{\text{true}}\|$ 를 최소화한다고는 한마디도 하지 않는다. 정규화가 원하는 것은 연산자를 잘 흉내 내는 것이 아니라 해를 잘 복원하는 것이고, 이 둘은 목적함수부터 다르다. 실제로 위에서 본 링잉은 EYM 최적성과 아무 모순 없이 발생한다 — $A_k$ 가 $A$ 의 최선의 랭크-$k$ 근사인 것과, $A_k^{+}b$ 가 $x_{\text{true}}$ 의 좋은 추정인 것은 별개다. 티호노프 해는 어떤 랭크-$k$ 근사에도 대응하지 않지만 복원 오차는 종종 더 작다. 정리는 강력하지만, 정리가 보장하지 않는 것을 정리 덕분이라고 말하면 안 된다.³

5. PCA·POD와의 관계[편집]

TSVD는 이름만 다르게 여러 분야에 이미 들어와 있다.

• 주성분 분석: 열 평균을 뺀 데이터 행렬의 TSVD가 곧 PCA다. $V$ 의 열이 주성분 방향, $\sigma_i^2/(n-1)$ 이 그 방향의 분산.
• POD / 모드 분해: 유동장 스냅숏 행렬에 같은 짓을 하면 적합직교분해가 되고, 상위 몇 모드가 축소차수모델의 기저가 된다. 에너지의 99%를 담는 $k$ 를 고르는 관행이 바로 EYM 오차식의 프로베니우스 판본이다.
• 잠재의미분석(LSA): 문서-단어 행렬의 TSVD. “잡음을 잘라 내면 의미가 남는다”는 신념의 원조 격.
• 잡음 제거: 데이터가 저차원 부분공간 근처에 있고 잡음이 등방적이면, 신호는 상위 특이값에 잡음은 전 스펙트럼에 고루 퍼지므로 절단이 곧 잡음 제거가 된다.

여기서 자주 새는 곳이 “에너지 99%” 관행이다. $\sum_{i\le k}\sigma_i^2 / \sum_i \sigma_i^2 \ge 0.99$ 는 스냅숏 행렬을 얼마나 잘 재현하는가의 기준일 뿐, 그 기저 위에서 갈레르킨 사영한 축소 모형이 정확하다거나 안정적이라는 보장이 아니다. 특히 이류가 지배하는 유동처럼 해 다양체의 콜모고로프 $n$-폭이 천천히 줄어드는 문제에서는 특이값이 거의 안 떨어져서, 99%를 채우려면 $k$ 가 수백을 넘고 그쯤 되면 축소한 보람이 없다. 특이값 스펙트럼이 뚝 떨어지느냐 아니냐는 알고리즘이 아니라 물리가 정하는 것이고, TSVD는 그 사실을 정직하게 보고할 뿐이다.

6. 대규모 문제 — 랜덤화와 크리로프[편집]

$m\times n$ 전체 SVD는 $O(mn\min(m,n))$ 이라, 상위 20개가 필요한데 100만 차원 행렬을 통째로 분해하는 것은 낭비를 넘어 불가능이다. 실무 표준은 둘이다.

랜덤화 SVD (Halko-Martinsson-Tropp 2011). 랜덤 가우시안 행렬 $\Omega \in \mathbb{R}^{n\times(k+p)}$ 로 $Y = A\Omega$ 를 만들고 QR로 정규직교기저 $Q$ 를 얻은 뒤, 작은 행렬 $B = Q^{T}A$ 를 정직하게 SVD한다. 여유차원 $p$(보통 5~10)만 조금 주면 기대오차가

$$\mathbb{E}\,\|A - QQ^{T}A\|_F \le \left(1+\frac{k}{p-1}\right)^{1/2}\Big(\textstyle\sum_{i>k}\sigma_i^2\Big)^{1/2}$$

로, EYM 최적값의 상수배 안에 들어온다. 행렬을 곱셈 연산자로만 접근하면 되므로 FFT나 희소행렬 곱으로 정의된 $A$ 에도 그대로 쓴다. 스펙트럼이 천천히 감쇠하면 $(AA^{T})^qA\Omega$ 형태의 멱반복을 한두 번 끼워 넣어 감쇠를 인위적으로 가파르게 만드는 것이 정석이다.

부분 SVD / 골룹-칸 이중대각화. 란초스 알고리즘 계열로 상위 특이쌍만 반복적으로 뽑는다(svds, PROPACK). 정확도가 필요하고 특이값이 잘 분리돼 있으면 이쪽이 유리하며, 반복 자체가 큰 특이값부터 복원하므로 일찍 멈추는 것이 곧 절단이라는 성질까지 딸려 온다. 이 성질을 정규화로 이용하는 것이 크리로프 부분공간법의 반복 정규화(semi-convergence)다.

7. 관련 문서[편집]

• 특이값 분해 · 티호노프 정규화 · 역문제
• 능형회귀 · 교차검증 · 조건수
• 주성분 분석 · 축소차수모델 · 적합직교분해
• 랜덤화 SVD · 란초스 알고리즘 · 크리로프 부분공간법
• 최소자승법 · 깁스 현상 · 희소행렬
• 전변분 잡음제거 · 기저 추구 · 압축센싱

8. Footnotes[편집]

1. 그래서 논문 그림에서 복원 결과 옆에 상대오차 숫자만 달랑 적혀 있으면 일단 의심해 볼 만하다. 링잉은 $\ell_2$ 오차에 잘 안 잡힌다 — 진동의 평균이 0에 가깝기 때문이다. 사람 눈에는 제일 먼저 보이는데 노름에는 제일 안 보이는 오차가 링잉이다. ↩

2. 정수 손잡이의 또 다른 불편함. $k$ 를 CV로 고르면 후보가 $n$ 개뿐이라 격자 탐색이 쉬워 보이지만, 정작 최적 $k$ 근처에서 CV 곡선이 계단처럼 울퉁불퉁해 최소점이 잡음에 흔들린다. 티호노프의 연속 $\alpha$ 는 곡선이 매끄러워 최소점 찾기가 오히려 편하다. 이산이 항상 쉬운 게 아니다. ↩

3. 같은 함정이 머신러닝 쪽에도 있다. “이 임베딩은 EYM 최적입니다”는 재구성 오차 이야기일 뿐, 다운스트림 과제 성능과는 논리적 연결이 없다. 최적성 정리가 붙어 있는 방법을 볼 때는 무엇에 대해 최적인지를 먼저 확인하는 습관이 수명을 늘려 준다. ↩