선형대수 note 29: Singular value decomposition

고유값 분해 A = Q\Lambda Q^{T} 가 가능하려면 A 는 대칭행렬이어야 한다. 특이값 분해 (Singular Value Decomposition) 는 A 가 임의의 직사각행렬이어도 적용할 수 있다.

    \[A = U\Sigma V^T\]

U 는 직교행렬, \Sigma 는 대각행렬, V 는 직교행렬이다. 행렬 A 가 대칭행렬이고, 양준정부호 행렬일 때 SVD 는 고유값 분해 Q \Lambda Q^T 와 같은 형태가 된다. 좀 더 자세히 알아보자.

직사각행렬 A\text{rank} = r 일 때 row space 의 차원은 r 이다. r 개의 직교하는 기저벡터를 찾을 수 있을 것이다. column space 도 마찬가지다. r 개의 기저벡터들을 찾을 수 있다. 아무 기저나 찾는 것이 아니라 특별히 A 를 곱해서 row space 기저에서 column space 기저로 변환이 되는 기저들을 찾을 것이다.
row space 에 존재하는 직교 벡터들 \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_rA 를 곱하면 A 의 column space 에 존재하는 직교 벡터 \sigma_1 \mathbf{u}_1, \sigma_2 \mathbf{u}_2, \dots, \sigma_r \mathbf{u}_r 으로 변환된다. 여기서 \sigma > 0 이다. A\mathbf{x}_i = \lambda_i \mathbf{x}_iAS = S\Lambda 였던 것 처럼, A\mathbf{v}_i = \sigma_i \mathbf{u}_iAV_r = \Sigma_r U_r 이 된다.

    \[\begin{aligned} A V_r &= U_r \Sigma_r \\  \underbrace{A}_{(m\times n)}  \underbrace{\begin{bmatrix}  \\ \mathbf{v}_1 & \dots & \mathbf{v}_r \\ \\ \end{bmatrix}}_{(n\times r)} &= \underbrace{\begin{bmatrix}  \\ \mathbf{u}_1 & \dots & \mathbf{u}_r \\ \\ \end{bmatrix}}_{(m\times r)} \underbrace{\begin{bmatrix} \sigma_1 \\ & \ddots \\ & & \sigma_r \\ \end{bmatrix}}_{(r\times r)} \end{aligned}\]

V_r 는 직교행렬이므로 양변의 오른쪽에 V_r^T 를 곱하면 A = U_r \Sigma_r V_r^T 가 되고, 이것을 reduced SVD 라고 한다.

\mathbf{v}_i 는 nullspace 와 직교하므로 추가적인 n - r 개의 직교벡터 \mathbf{v}_i 들을 nullspace 에서 찾을 수 있다. 마찬가지로 \mathbf{u}_i 는 left nullspace 와 직교하므로 추가적인 m - r 개의 직교벡터 \mathbf{u}_i 들을 left nullspace 에서 찾을 수 있다. n - r 개의 v_i 들은 A 에 의해서 \mathbf{0} 으로 맵핑된다. 따라서 이 벡터들을 포함하면,

    \[\begin{aligned} AV &= U\Sigma \\ \underbrace{A}_{(m\times n)}  \underbrace{\begin{bmatrix}  \\ \mathbf{v}_1 & \dots & \mathbf{v}_r & \dots & \mathbf{v}_n \\ \\ \end{bmatrix}}_{(n\times n)} &= \underbrace{\begin{bmatrix}  \\ \mathbf{u}_1 & \dots & \mathbf{u}_r & \dots & \mathbf{u}_m \\ \\ \end{bmatrix}}_{(m\times m)} \underbrace{\begin{bmatrix} \sigma_1 \\ & \ddots \\ & & \sigma_r \\ \\ \end{bmatrix}}_{(m\times n)} \end{aligned}\]

VU 는 정방행렬이고, \Sigma\Sigma_r 에서 m-r 만큼 0 행이 추가되고, n-r 만큼 0 열이 추가된다.
VU 는 직교 정방행렬이므로 V^{-1} = V^T,\ U^{-1} = U^T 이다. 그러므로 AV = U\SigmaA = U\Sigma V^T 로 쓸 수 있다.

그림으로 그려보면,

singular-vector-mapping

계산

정방행렬 A^TA 를 특이값 분해하면,

    \[\begin{aligned} A^T A &= (U\Sigma V^T)^T U\Sigma V^T \\ &= V\Sigma^T U^T U\Sigma V^T \\ &= V\Sigma^2 V^T \end{aligned}\]

위의 식은 Q\Lambda Q^T 와 같은 형태다. \mathbf{v}_i = \mathbf{q}_i 이고, \sigma_i^2 = \lambda_i 가 된다. A^TA 는 적어도 positive semi-definite 행렬이므로 \Lambda 의 성분들은 0 이상이고, 이것은 \sigma_i0 이상인 이유가 된다. A\mathbf{v}_i = \sigma_i \mathbf{u}_i 이므로 \mathbf{u}_i = \frac{A\mathbf{v}_i}{\sigma_i} 이다. 이로써 V, \Sigma, U 를 모두 구할 수 있다.

SVD 는 선형대수의 Key 가 되는 주제인 positive definite 행렬과 4 fundamental subspaces 를 모두 아우르는 중요한 주제라고 할 수 있다. 또 임의의 직사각 행렬에 적용가능하기 때문에 가장 유용한 분해 방법 중 하나다.

\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_r row space 의 orthonormal basis
\mathbf{v}_{r+1}, \mathbf{v}_{r+2}, \dots, \mathbf{v}_n nullspace 의 orthonormal basis
\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_r column space 의 orthonormal basis
\mathbf{u}_{r+1}, \mathbf{u}_{r+2}, \dots, \mathbf{u}_m left nullspace 의 orthonormal basis

활용

A 를 특이값 분해하면,

    \[A = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^T + \sigma_2 \mathbf{u}_2 \mathbf{v}_2^T + \dots + \sigma_r \mathbf{u}_r \mathbf{v}_r^T\]

\mathbf{u}_i \mathbf{v}_i^T\text{rank} = 1 행렬이다. 즉 A\text{rank} = 1 행렬의 합으로 나타낼 수 있다. \sigma_i 를 값이 큰 순서대로 정렬하면 A 를 표현하는데 있어서 뒷부분은 덜 중요한 행렬이 된다. 256 \times 512 이미지를 행렬로 나타내면 256\times 512 = 131072 개의 픽셀정보가 필요하다. 이 이미지를 특이값 분해하면 몇개의 \text{rank}=1 행렬로 근사할 수 있을 것이다. 예를 들어 16 개의 \sigma 를 사용한다면, 16 \times (256 + 512) = 12288 개의 값만 있으면 된다.


선형대수 note 목록

2 Comments

Leave a Reply to Lee Ju Hyung Cancel reply

Your email address will not be published. Required fields are marked *