7.3 Singular Value Decomposition

이번 포스트에서는 Singular Value Decomposition에 대해 다루어보겠습니다.

1) Singular Value Decomposition

이전 포스트에서 Diagonalization에 대해 배웠습니다. 하나의 행렬을 여러 행렬의 곱으로 분해할 수 있는 지의 여부는 행렬의 중요한 성질 중 하나입니다. Diagonalization의 경우, square matrix에 한정해서 가능하였고, 모든 square matrix가 diagonalization이 가능하지는 않았습니다.

이번 포스트에서 다루는 Singular Value Decomposition(SVD)는 임의의 행렬 모두에 대해서 적용이 가능합니다! 즉 square matrix가 아니더라도 적용이 가능합니다! 어떠한 방법을 이용하여 다루는지 알아보도록 하겠습니다.

(1) Singular Value

Definition : Singular Value

Let $A$ be $m\times n$ matrix. The singular values of $A$ are the square root of the eigenvalues of $A^TA$, denoted by $\sigma_1, ..., \sigma_n$, and they are arranged in decreasing order

where $\lambda_i$ is the $i$th eigenvalue of $A^TA$.

$A$의 singular value는 $A^TA$의 eigenvalue를 이용하여 구할 수 있습니다. $A^TA$의 eigenvalue에 root를 씌운 값이 $A$의 singular value가 됩니다. 또한 singular value의 경우 일반적으로 크기순으로 순서를 나열합니다.

해당 정의에서 확인해야 할 점은 다음과 같습니다.

• $A$의 singular value는 중복을 포함하여 $n$개 존재한다.
• $A^TA$의 eigenvalue는 항상 0보다 크거나 같다. 즉 positive semidefinite이다.

이는

• $A^TA$는 $n\times n$ matrix이므로, 해당 square matrix의 eigenvalue는 중복도(multiplicity)를 고려하여 최대 $n$개 존재하는 것을 알 수 있습니다. 또한 $A^TA$는 symmetric matrix이므로, $n$개의 eigenvalue 모두 실숫값을 가집니다.

• 모든 $\mathbb R^n$에 속하는 $\boldsymbol x$에 대해서 $\boldsymbol x^T A^TA \boldsymbol x = \|A\boldsymbol x\|^2 \geq 0$를 만족하므로, $A^TA$는 positive semidefinite입니다. 즉 $A^TA$의 eigenvalue가 모두 0보다 크거나 같다는 것을 의미하고, 따라서 eigenvalue에 root를 씌운 singular value가 정의될 수 있습니다.

다음 정리는 singular value decomposition의 기본 개념이 되는 정리입니다.

Theorem

Suppose $\{\boldsymbol v_1, ..., \boldsymbol v_n\}$ is an orthonormal basis of $\mathbb R^n$ consisting of eigenvectors fo $A^TA$, arranged so that the corresponding eigenvalues of $A^TA$ satisfy $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_n$, and suppose $A$ has $r$ nonzero singular values. Then $\{A\boldsymbol v_1, ..., A\boldsymbol v_r\}$ is an orthogonal basis for $ColA$, and $rankA = r$

$A^TA$의 eigenvector를 이용하여 $ColA$의 basis를 구할 수 있고, non-zero singular value의 수가 $A$의 rank가 됩니다. 이 때, $C olA$의 orthogonal basis가 $\{A\boldsymbol v_1, ..., A\boldsymbol v_r\}$인 점은 singular value decomposition 과정에서 중요하게 사용됩니다. (증명은 appendix에 남겨두겠습니다.)

(2) Singular Value Decomposition

그럼 어떠한 방법으로 singular value decomposition을 하게 되는지 확인해봅시다.

Theorem : Singular Value Decomposition

Let $A$ be $m\times n$ matrix with rank $r$. Then there exists an $m \times n$ matrix $\Sigma$ such that

where diagonal entries of $D$ are the first $r$ singular values of $A$, i.e.

, and there exists $m\times m$ orthogonal matrix $U$ and $n\times n$ orthogonal matrix $V$ such that

$U$ and $V$ are not uniquely determined by $A$, but diagonal entries of $\Sigma$ are necessarily the singular values of $A$.

The columns of $U$ are called left singular vectors of $A$, the columns of $V$ are called right singular vectors of $A$.

임의의 $m\times n$ matrix $A$는 세 개의 matrix $U, \Sigma, V$로 분해가 가능합니다. $\Sigma$는 $m\times n$ matrix인데, $D$와 zero matrix로 partition된 matrix입니다. 이 때, diagonal matrix $D$의 diagonla entry는 $A$의 singular value로 구성됩니다. 따라서 $\Sigma$는 unique하게 결정되구요.

$U$의 column을 $A$의 left singular vector, $V$의 column을 $A$의 right singular vector라고 합니다.

실제 임의의 matrix에 singular value decomposition을 적용하기 위해서는 $A$가 $U, \Sigma, V$로 어떻게 분해되는지 알아야 됩니다. 따라서 위의 정리를 증명해보겠습니다.

Proof

$A$의 rank는 $r$이므로, $A^TA$의 rank는 $r$입니다. 따라서, $A^TA$의 eigenvalue는 중복을 포함하여 총 $n$개가 나오는데, 이 때, $r$의 eigenvalue가 0이 아닌 값을 가지고, $n-r$개의 eigenvalue는 0이 됩니다. 즉 $A^TA$의 eigenvalue는

인 것을 알 수 있습니다. $\lambda_1, ..., \lambda_r, 0$에 해당하는 orthonormal한 eigenvector를 각각 $\boldsymbol v_1, ..., \boldsymbol v_n$이라고 하면

은 $ColA$의 orthogonal basis가 됩니다. 해당 basis에 속한 벡터를 normalize 시킨

은 $ColA$의 orthonormal basis가 됩니다.

을 만족하므로,

이 됩니다. 즉

를 만족합니다. 위 식을 이용하여 $U, \Sigma, V$를 만들 예정입니다.

먼저 $U$에 대해서 살펴봅시다. 정리에서 $U$는 $m \times m$ orthogonal matrix입니다. $\boldsymbol u_1, ..., \boldsymbol u_r$끼리는 모두 orthonormal하므로, 추가적으로 $m-r$개의 orthonormal한 vector를 찾아주면 됩니다. $\mathbb R^m$에 속하는 vector이기 때문에, $m-r$개의 orthonormal한 vector를 무조건 찾을 수 있습니다. 그리하여 얻은 $\boldsymbol u_1, ..., \boldsymbol u_m$으로 이루어진 집합

은 $\mathbb R^m$의 orthonormal basis가 됩니다.

두 번째는 $\Sigma$입니다. $\Sigma$는 $m\times n$ matrix이고

다음의 partition된 matrix로 이루어져 있습니다. 이 때 $D = diag(\sigma_1, ..., \sigma_r)$이구요.

마지막으로 $V$입니다. $V$는

으로 만들어집니다. $\boldsymbol v_1, ..., \boldsymbol v_n$은 $A^TA$의 $\lambda_1, ..., \lambda_r, 0$에 해당하는 크기가 1인 eigenvector입니다. $A^TA$는 symmetric이므로, $V$는 orthogonal matrix입니다.

다음과 같이 $U, \Sigma, V$를 만들면,

를 만족합니다.

$U\Sigma$를 살펴보면

이고, ($\Sigma$의 (1,1), (2, 2), ..., (r, r) entry를 제외하곤 모두 0이기 때문에 $i\geq r+1$부터 $U\Sigma$값은 0입니다.)

$AV$를 살펴보면

이고,

이므로($i>r$인 경우, $\boldsymbol v_i$에 해당하는 eigenvalue가 0이므로, $A^TA\boldsymbol v_i = 0$이고, $\boldsymbol v_i^TA^TA\boldsymbol v_i = \|A\boldsymbol v_i\|^2 = 0$이므로, $A\boldsymbol v_i=0$입니다.),

가 됩니다. 이 때,

이므로,

가 성립합니다. 여기에, $V$는 orthogonal matrix이므로

를 만족합니다.

위 정리를 통해서 임의의 $m\times n$ matrix $A$의 singular value decomposition은 다음의 과정을 통해 구할 수 있습니다.

1. $A^TA$의 eigenvalue를 구하고, $A$의 singular value를 구한다. ($\sigma_1\geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0$)
2. Singular value를 이용하여 $\Sigma$를 구한다.
3. $A^TA$의 각각 eigenvalue에 대응하는 크기 1의 eigenvector를 구한다.(eigenvalue의 중복도와 같은 수의 linearly independent한 eigenvector를 구합니다. 해당 eigenvector를 column으로 가지는 matrix가 $V$가 됩니다.)
4. $\boldsymbol v_1, ..., \boldsymbol v_r$를 이용하여 $\boldsymbol u_1, ..., \boldsymbol u_r$을 구한다. ($A\boldsymbol v_i = \sigma_i\boldsymbol u_i,$ 이므로, $\boldsymbol u_i = \frac{1}{\sigma_i}A\boldsymbol v_i$가 됩니다.)
5. 만약 $r=m$이면 $U = \begin{bmatrix} \boldsymbol u_1 & \cdots & \boldsymbol u_r \end{bmatrix}$이 되고, $r<m$이면, 추가적인 orthonormal한 벡터 $\boldsymbol u_{r+1}, ...,\boldsymbol u_{m}$을 구해 $U$를 만든다. ($\mathbb R^m$에 속한 벡터이므로 반드시 존재합니다. 이 때 Gram-Schmidt process를 이용합니다.)

Example

다음 $A$ matrix를 분해해보겠습니다.

• $A$의 singular value 구하기

를 이용하여 $A^TA$의 eigenvalue를 구하면

인 것을 알 수 있습니다. 따라서 $A$의 singular value는

가 됩니다.

• $\Sigma$ 구하기

$A$의 singular value를 이용하여 $\Sigma$를 구할 수 있습니다.

• $A^TA$의 eigenvector 구하기

$\lambda_1=360$일 때

를 만족하는 크기 1의 eigenvector $\boldsymbol v_1$는

가 되고,

$\lambda_2=90, \ \lambda_3=0$일 때 eigenvector $\boldsymbol v_2, \boldsymbol v_3$는

이 됩니다. 이를 이용하여

$V$를 구할 수 있습니다.

• $\boldsymbol u_1, ..., \boldsymbol u_r$ 구하기

$\boldsymbol u_i = \frac{1}{\sigma_i}A\boldsymbol v_i$임을 이용하여 $\boldsymbol u_1, \boldsymbol u_2$를 구합니다.

• $U$ 만들기

지금 $U$는 $2\times 2$ matrix여야 하는데, $\boldsymbol u_1, \boldsymbol u_2$만으로 충분히 $U$를 만들 수 있습니다. (만약 이전 단계에서 구한 $\boldsymbol u$의 개수가 부족하다면, Gram-Schmidt process를 통해 orthonormal한 $\boldsymbol u$벡터를 찾아주면 됩니다.)

정리하면

가 됩니다.

Example

다음 matrix를 분해해보겠습니다.

• $A$의 singular value구하기

임을 이용하면

이므로 $A$의 singular value는

입니다.

• $\Sigma$ 구하기

따라서, $\Sigma$는

입니다.

• $A^TA$의 eigenvector 구하기

$\lambda_1 = 18, \lambda_2=0$일 때의 크기 1인 eigenvector는

입니다. 이를 이용하면

을 구할 수 있습니다.

• $\boldsymbol u_1$ 구하기

$\boldsymbol u_1$은

으로 구할 수 있습니다.

• $U$ 구하기

$U$는 $3\times 3$ matrix여야 하는데, 지금 이전 단계에서 $\boldsymbol u_1$밖에 구하지 못했습니다. 이 후 나머지 벡터 $\boldsymbol u_2, \boldsymbol u_3$는 $\boldsymbol u_1, \boldsymbol u_2, \boldsymbol u_3$가 orthogonormal하도록 만들어주면 됩니다.

여기서,

해당 조건을 만족하는 $\boldsymbol w$는 $\boldsymbol u_1$과 orthogonal합니다. 여기서, $\boldsymbol u_2, \boldsymbol u_3$가 서로 orthogonal하도록 만들어주면 됩니다.

으로 지정하면, $\boldsymbol w_3$는 위의 subspace에 속하면서 $\boldsymbol w_1$과 orthogonal해야 합니다. Gram-Schmidt process를 이용하면

가 나와

를 구할 수 있습니다. 따라서,

가 되고,

가 됩니다.

지금까지 Singular Value Decomposition에 대해 알아보았습니다. 다음 포스트에서는 Singular Value Decomposition를 이용한 다양한 matrix의 성질에 대해 다루어보겠습니다. 질문이나 오류 있으면 댓글 남겨주세요! 감사합니다!

Appendix : Proof of Theorem

Theorem

Suppose $\{\boldsymbol v_1, ..., \boldsymbol v_n\}$ is an orthonormal basis of $\mathbb R^n$ consisting of eigenvectors fo $A^TA$, arranged so that the corresponding eigenvalues of $A^TA$ satisfy $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_n$, and suppose $A$ has $r$ nonzero singular values. Then $\{A\boldsymbol v_1, ..., A\boldsymbol v_r\}$ is an orthogonal basis for $ColA$, and $rankA = r$

• Proof

은 $A^TA$의 eigenvector이고, 각각의 eigenvectors에 해당하는 eigenvalue가

입니다. 여기서 $\lambda_1, ..., \lambda_r\geq 0$이고, 이 후의 $\lambda_{r+1}, ..., \lambda_{n}=0$입니다. 먼저

가 orthogonal한 것을 먼저 보이겠습니다. $i\neq j$에 대해서

을 만족합니다. 이는 $A^TA$는 symmetric matrix이므로, $A^TA$의 서로 다른 eigenvalue에 해당하는 eigenvector는 orthogonal하기 때문입니다. (만약 eigenvalue가 같다면, eigenspace의 dimension과 해당 eigenvalue의 중복도가 같으므로, 해당 eigenspace에서 orthogonal한 벡터를 중복도만큼 만들 수 있습니다.)

두 번째로

가 $ColA$의 basis인 것을 보이겠습니다. 먼저

입니다. $A\boldsymbol v_i$는 $A$의 column의 linear combination이기 때문입니다. 현재 linear independence는 만족하였으므로(orthogonal하므로), 위 집합을 이용하여 span하였을 때 column space가 되는지만 확인하면 됩니다. 이를 확인하기 위해

를 생각해봅시다. 해당 벡터들은 orthogonal하고, $\mathbb R^n$에 속해있습니다. 따라서 해당 집합은 $\mathbb R^n$의 basis가 됩니다. 한편

이 성립됩니다. 여기서, $\boldsymbol x \in \mathbb R^n$이므로

이 되고

가 됩니다. 즉,

를 만족합니다. 그런데, $i>r$부터의 $A^TA$의 eigenvalue는 0이므로, $A\boldsymbol v_i = 0$ 또한 0이 됩니다. 즉 위의 식이

을 만족하게 되죠. 위의 식에서 $0$을 제외하더라도

가 성립합니다. 따라서

는 $ColA$의 basis가 되고, $rankA = r$이 성립합니다.