고윳값
\(8,\;2\)
24차시 · 정의와 표기
특잇값 분해의 정의
실수 행렬 \(A\in\mathbb R^{m\times n}\)에 대해 다음 분해를 특잇값 분해(SVD)라고 한다. 직사각행렬에도 정의된다.
\[A=U\Sigma V^T,\qquad U^TU=I_m,\quad V^TV=I_n\]
\(U\)는 \(m\times m\), \(V\)는 \(n\times n\) 직교행렬이다. \(\Sigma\)는 \(m\times n\) 대각형 행렬이며 대각성분 \(\sigma_1\ge\cdots\ge\sigma_p\ge0\), \(p=\min(m,n)\)을 특잇값이라고 한다.
\(V\)의 열 \(v_i\)는 오른쪽 특이벡터(입력 방향), \(U\)의 열 \(u_i\)는 왼쪽 특이벡터(출력 방향)이다. \(1\le i\le p\)에서 \(Av_i=\sigma_i u_i\)가 성립한다.
24차시 · 설명과 유도
특잇값을 구하는 대칭 고윳값 문제
\(A^TA\)는 대칭이고 \(v^TA^TAv=\|Av\|^2\ge0\)이다. 따라서 직교 고유기저를 고를 수 있고 고윳값은 음이 아니다.
\[A^TAv_i=\sigma_i^2v_i,\qquad u_i=\frac{Av_i}{\sigma_i}\quad(\sigma_i>0)\]
정규화한 두 출력은 \(u_i^Tu_j=v_i^TA^TAv_j/(\sigma_i\sigma_j)=0\ (i\ne j)\)이므로 서로 직교한다. \(\sigma_i=0\)이면 나누지 않고 출력의 직교기저를 보충한다.
24차시 · 특잇값 분해
계산할 행렬과 두 특잇값
\[A=\begin{bmatrix}2&2\\1&-1\end{bmatrix}\]
입력 방향은 서로 직교하게 고른다. 그 방향을 변환한 출력의 길이가 각각 특잇값이다.
\(2\sqrt2\)첫째 특이벡터 방향
\(\sqrt2\)둘째 특이벡터 방향
이 예에서는 두 배율을 직접 계산한 뒤, 단위원의 상에서 확인한다.
오른쪽 특이벡터
오른쪽 특이벡터는 어떻게 구할까?
\[A^\mathsf TA=\begin{bmatrix}2&1\\2&-1\end{bmatrix}\begin{bmatrix}2&2\\1&-1\end{bmatrix}=\begin{bmatrix}5&3\\3&5\end{bmatrix}\]
단위 고유벡터
\(\mathbf{v}_1=(1,1)/\sqrt2\)
\(\mathbf{v}_2=(1,-1)/\sqrt2\)
오른쪽 특이벡터는 \(A^\mathsf TA\)의 단위 고유벡터입니다. 특잇값은 그 고윳값의 음이 아닌 제곱근이므로, 여기서는 \(\sigma_1=2\sqrt2\), \(\sigma_2=\sqrt2\)입니다.
오른쪽 특이벡터 · 특잇값 · 왼쪽 특이벡터
두 고유벡터를 \(A\)에 넣어 출력 방향을 구해 봅시다
1. 첫 방향
\[A\mathbf{v}_1=\begin{bmatrix}2\sqrt2\\0\end{bmatrix}=(2\sqrt2)\mathbf{u}_1\]
\(\mathbf{u}_1=(1,0)\)
2. 둘째 방향
\[A\mathbf{v}_2=\begin{bmatrix}0\\\sqrt2\end{bmatrix}=(\sqrt2)\mathbf{u}_2\]
\(\mathbf{u}_2=(0,1)\)
3. 분해
\[A=U\Sigma V^\mathsf T\]
\(U=I\), \(\Sigma=\operatorname{diag}(2\sqrt2,\sqrt2)\)
\[V=\frac1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix},\qquad A=\sum_{i=1}^{2}\sigma_i\mathbf{u}_i\mathbf{v}_i^\mathsf T\]
24차시 · 정의와 표기
랭크와 근사오차의 기준
외적 \(u_iv_i^T\)는 입력 \(x\)에서 스칼라 \(v_i^Tx\)를 읽어 \(u_i\) 방향으로 보내는 행렬이다. 각 항의 랭크는 1이다.
\[Ax=\sum_{i=1}^{p}\sigma_i u_i(v_i^Tx),\qquad A_k=\sum_{i=1}^{k}\sigma_i u_iv_i^T\]
랭크는 열공간의 차원이며 0이 아닌 특잇값의 개수이다. 근사가 좋다는 말에는 오차의 기준이 필요하다.
\[\|E\|_F=\sqrt{\sum_{i,j}E_{ij}^2},\qquad \|E\|_2=\max_{\|x\|=1}\|Ex\|\]
단위원의 상
입력점을 움직여 두 특이벡터 방향의 배율을 확인해 봅시다
입력 \(\mathbf{x}\): 단위원과 \(\mathbf{v}_1,\mathbf{v}_2\)
출력 \(A\mathbf{x}\): 타원과 \(\mathbf{u}_1,\mathbf{u}_2\)
\[\mathbf{x}=(0.71,0.71)\]
\[A\mathbf{x}=(2.83,0.00)\]
\(\mathbf{x}=\mathbf{v}_1\)이다. 배율은 \(\sigma_1=2\sqrt2\)이다.
특잇값 절단
남길 랭크를 바꾸면 오차는 어떻게 달라질까?
행렬의 랭크는 서로 독립인 열벡터의 최대 개수이며 0이 아닌 특잇값의 개수와 같습니다. 특잇값이 큰 랭크 1 성분부터 \(k\)개 남겨 봅시다.
1보존 성분
√2성분별 오차 제곱합의 제곱근
(프로베니우스)
(프로베니우스)
\[A_1=\sigma_1\mathbf{u}_1\mathbf{v}_1^\mathsf T=\begin{bmatrix}2&2\\0&0\end{bmatrix}\]
\[A-A_1=\begin{bmatrix}0&0\\1&-1\end{bmatrix},\qquad \lVert A-A_1\rVert_F=\sqrt2\]
최적의 낮은 랭크 근사
특잇값이 큰 랭크 1 성분부터 남기는 최적 근사
가정: \(A\in\mathbb R^{m\times n}\), \(p=\min(m,n)\), \(0\le k<p\)
\(\sigma_1\ge\cdots\ge\sigma_p\ge0\), \(A_k=\sum_{i=1}^k\sigma_i\mathbf{u}_i\mathbf{v}_i^\mathsf T\)
\(\lVert\cdot\rVert_F\): 성분별 오차 제곱합의 제곱근 · \(\lVert\cdot\rVert_2\): 단위벡터에서 생기는 가장 큰 출력 오차
\[\min_{\operatorname{rank}(B)\le k}\lVert A-B\rVert_F=\lVert A-A_k\rVert_F=\sqrt{\sum_{i>k}\sigma_i^2}\]
\[\min_{\operatorname{rank}(B)\le k}\lVert A-B\rVert_2=\lVert A-A_k\rVert_2=\sigma_{k+1}\]
비교 대상은 랭크가 \(k\) 이하인 모든 행렬이다. 같은 오차를 얻는 행렬이 여러 개일 수 있으므로 '최적'이 곧 '유일'을 뜻하지는 않는다.
24차시 · 계산과 논증
최적 근사는 언제 여러 개일까?
\[D=\operatorname{diag}(3,3,1),\qquad k=1\]
① 최소 프로베니우스 오차를 구하라. ② 서로 다른 최적 랭크 1 근사행렬 두 개를 제시하라. ③ '항상 첫 번째 열을 남기면 최적이다'라는 주장을 반박하라.
풀이와 판단 근거
\[\min_{\operatorname{rank}B\le1}\|D-B\|_F=\sqrt{3^2+1^2}=\sqrt{10}\]
\(B_1=\operatorname{diag}(3,0,0)\), \(B_2=\operatorname{diag}(0,3,0)\)은 모두 오차가 \(\sqrt{10}\)이다. 가장 큰 특잇값이 중복되어 최적 방향이 유일하지 않다.
열 선택은 좌표에 의존한다. \(\operatorname{diag}(1,3)\)에서 첫 열만 남기면 오차는 3이지만 둘째 열을 남기면 1이다. SVD는 열 번호가 아니라 특잇값의 크기로 성분을 고른다.
데이터의 저차원 표현
영상과 시공간 데이터의 절단 SVD
픽셀 행렬
작은 \(k\)로 원래 영상을 잘 나타낼 때의 저장량 감소
절단 SVD
\[A_k=\sum_{i=1}^k\sigma_i\mathbf{u}_i\mathbf{v}_i^\mathsf T\]
버린 특잇값으로 계산하는 오차의 크기
시간별 공간 자료
\[X_k=U_k\Sigma_kV_k^\mathsf T\]
대표 공간 모양 \(U_k\)와 시간에 따른 크기 \(\Sigma_kV_k^\mathsf T\)로 분리
24차시 · 계산과 논증
근사오차와 저장량을 함께 비교하기
\(100\times80\) 행렬의 특잇값은 \(10,4,1\)이고 나머지는 0이다. 절단 SVD를 \(U_k,\sigma_1,\ldots,\sigma_k,V_k\)로 저장한다.
오차 \(\|A-A_k\|_F\le1.1\)을 만족하는 최소 \(k\)와 저장할 실수의 개수를 구하라. 작은 랭크만 택하면 언제나 좋은 압축인지 설명하라.
풀이와 판단 근거
\(k=1\)이면 오차가 \(\sqrt{17}>1.1\), \(k=2\)이면 1이므로 최소 \(k=2\)이다. 저장량은 \(k(100+80+1)=362\)개로 원래 8000개보다 작다.
오차 허용범위와 저장량을 둘 다 확인해야 한다. \(k(m+n+1)\ge mn\)이면 이 저장 방식은 압축이 아니며, 작은 \(k\)라도 버린 특잇값이 크면 오차가 크다.