SVD(Singular Value Decomposition)

Diagonal matrix(주대각 행렬)은 diagonal element를 제외한 element들이 모두 0인 행렬을 의미한다. 

\(D = \begin{pmatrix}d_1 & 0 & 0 \\0 & d_2 & 0 \\0 & 0 & d_3\end{pmatrix}\)

위의 형식을 봐보면 일반적인 행렬보다 간단하고 계산이 용이해보인다(실제로도 맞음). 그렇다면 일반적인 행렬들을 주대각행렬로 바꿀 수 있는 방식을 알게 된다면 좋지 않을까? 이러한 의문은 decomposition(분해)를 통해서 해결할 수 있는데, 기존 matrix를 분해하여 다른 방식으로 풀고자 하는 시도는 매우 많았지만 대부분이 일반화의 한계를 가지고 있었다. 

...

우선 이전에 소개한 EVG를 보면 크게 2가지의 단점이 있었다. 우선 Square Matrix(n*n)만 가능하고, Symmetric이어야 한다는 점이다. 이러한 한계로 다양한 상황을 커버할 수 없게되는데, 이러한 단점을 커버한 SVD(Singular Value Decomposition)는 EVD(고윳값 분해) 등 여러 Decomposition 이론의 한계를 해결한다. 우선 SVD는 간단히 정리하면 아래와 같다.

SVD : \(A = U \sum V^T \) (U, V : orthogonal / ∑  : main diagonal / rank(A) = k)

위의 식은 비로소 main diagonal(정사각행렬이 아니더라도 주대각 행렬의 형태를 갖춘 행렬) 아니더라도 다양한 상황에서 decomposition을 사용할 수 있는 것을 의미한다. 이때 ∑는 main diagonal로 아래와 같은 형태인데, 이를 이용하면 U,V는 쉽게 계산을 할 수가 있다. 우선 \(A^TA와 AA^T\)는 symmetrix 하므로 각각 eigendecomposition이 가능한다는 전제 하에 아래을 봐보자.

 

따라서 V = [\(v_1, v_2, ... , v_n\)]는 \(A^TA\)의 orthogonally diagonalizes이며, U = [\(u_1, u_2, ... , u_m\)]는 \(AA^T\)의 orthogonally diagonalizes이다. 

또한 V의 column vector에 대응되는  \(A^TA\)의 nonzero eigenvalues인 \(\lambda_1, \lambda_2, ... , \lambda_k\)는 ∑의 nonzero diagonal entries인 \(\sigma_1, \sigma_2, ... , \sigma_k\)와 \(\sigma_1 = \sqrt\lambda_1\), \(\sigma_2 = \sqrt\lambda_2\), \(\sigma_3 = \sqrt\lambda_3\), .... ,  \(\sigma_k = \sqrt\lambda_k\)라는 관계가 있다. 

U를 left sigular vactor, V를 right sigular vactor라고도 하는데 left sigular vactor의 entries 중 k까지의 diagonal entries를 모은 {\(u_1, u_2, ... , u_k\)}는 col(A)의 orthonormal basis이다. 

---

기본적으로 일반 행렬을 한번 계산하는 것보다 쉬운 행렬을 3번 연산하는 것이 더 쉽고 효율적이기에 사용을 많이 하게된다. SVD를 만족하기 위한 조건과 성질들은 많지만 기본적으로 받아드리기 쉽도록 정리를 해보았다. 다음에는 SVD를 더욱 효율적으로 사용하는 방식에 대하여 정리해보고자 한다.