[LA] Singular Value Decomposition (특이값분해, SVD)

Singular Value Decomposition

$$A=U\Sigma V^\top$$

Rank가 $n$인 matrix $A\in \mathbb{R}^{m\times n}\text{ where }m\ge n$ 에서

• orthonormal vector set$\{\textbf{v}_1, \dots, \textbf{v}_n\}, \{\textbf{u}_1, \dots \textbf{u}_n\}$ 와
• non-negative scalr set $\{\sigma_1, \dots, \sigma_n\}$에 대하여

$$A\textbf{v}_i=\sigma_i\textbf{u}_i \text{ where } i=1,2,\dots,n$$

를 만족한다고 가정하자.

---

Singular Values and Left/Right Singular Vectors

이때, non-negative scalar 인 $\sigma_1, \dots,\sigma_n$들을 matrix $A$의

• singular value (특이값)이라고 한다.

$A$가 Rank Deficient인 경우,
Singular Value 중 0이 존재하므로
Positive가 아닌 Non-Negative임.

동시에, 해당 singular value들에 각각 대응하는 orthonomal vector $\textbf{v}_i$와 $\textbf{u}_i$를 각각

• right singular vector,
• left singular vector 라고 함.

즉, 다음이 성립함:

• $\{\textbf{v}_1,\dots,\textbf{v}_n\}$는 행렬 $A^\top A$의 Eigenvector(고유 벡터)로 이루어진 orthonormal set임.
• $\{\textbf{u}_1,\dots,\textbf{u}_m\}$는 행렬 $A A^\top$의 Eigenvector로 이루어진 orthonormal set이다.
• $\{ \sigma_1, \dots, \sigma_n \}$은 행렬 $A$의 singular value (특이값)이며, $\sigma_i = \sqrt{\lambda_i}$ 임.($\lambda_i$는 $A^\top A$의 eigen value).

---

Singular Value Decomposition

이를 기반으로 $A$는 다음과 같이 분해됨.

$$A=U\Sigma V^\top$$

---

SVD의 경우, non-negative singular values는 내림차순으로 나열되는 게 일반적이며 이는 다음이 성립함을 의미함.

 

$$\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_n \ge 0$$

 

• 행의 수가 열보다 크면서 Full Column Rank면 Singular Value는 모두 양수임 (0 초과)
• 행의 수가 열보다 작으면서 Full Row Rank면 Singular Value는 모두 양수임 (0 초과)
• Full Rank가 아닌 경우엔 0의 값을 가지는 Singular Value가 존재할 수 있음: SVD는 가능.

SVD는 어떠한 matrix에서도 얻을 수 있음: 가장 넓은 응용범위를 가짐.

• singular value가 0이 아닌 갯수는 $r=\text{rank}(A)$와 일치!
• reduced form은 0이 아닌 singular value만을 고려하는 게 이상적이나, approximation을 수행할 경우엔 $r$보다 적게 사용도 가능
• 단, Approximation 경우엔 등식이 성립하지 못함.

---

Rank와 Singular Values

$A\in \mathbb{R}^{m\times n} \text{ where }m \ge n$이면서 $A$의 rank가 $n$일 때

$S=A^\top A$ 인 경우로 한정할 경우,

$S$는 symmetric matrix ($S^\top =S$)이기 때문에 항상 orthogonal diagonalization이 가능함.

2022.11.17 - [.../Math] - [LA] Diagonalization, Orthogonal Diagonalization, and Symmetric Matrix

[LA] Diagonalization (Eigen-Decomposition), Orthogonal Diagonalization, and Symmetric Matrix

 

또한 $S=A^\top A$는 $A$의 rank가 $n$이기 때문에 $n \times n$ matrix이면서 역시 rank가 $n$임.

• 이는 $S$가 $n$개의 0이 아닌 Eigenvalues (muliplicity 를 개별로 카운팅)를 가짐을 의미함.
• 만약 $A$ Full Column Rank가 아니면, 0인 Eigenvalue가 존재함.

동시에 $S=A^\top A$는 $A$의 rank에 상관없이 Positive semi-definite이기 때문에

• $S$의 모든 eigenvalue는 0 이상임: 0일수도 있다는 애기임.

위의 두 내용을 고려하면 rank 가 $n$인 $S$는 항상 0보다 큰 positive eigenvalue를 $n$개 가짐.

($A$가 rank deficient이면, $S=A^\top A$는 0을 포함한 non-negative eigenvalue를 $n$ 개 가짐.)

 

즉, 항상 $S=A^\top A$는 항상 Eigen Decomposition이 가능하며  $n$개의 non-negative 인 Eigenvalues를 항상 구할 수 있음.

 

결론적으로, 구해지는

• $S$의 Eigenvalue $\lambda_i(A^\top A)$ (이는 $S=A^\top A$에서 구해진 $i$번째 Eigenvalue를 의미함)와
• $A$에 구해진 Singular Value $\sigma_i(A)$들이

다음의 순서로 Sorting시킬 경우 ($A$가 full-rank 인 경우임) 

$$ \sigma_1(A) \ge \sigma_2(A) \ge \dots \ge \sigma_n(A) > 0$$

$$ \lambda_1(A^\top A) \ge \lambda_1(A^\top A) \ge \dots \ge \lambda_n(A^\top A) > 0$$

다음의 관계를 가짐.

$$\sigma_i(A)=\sqrt{\lambda_i(A^\top A)}$$

• Singular Value는 위의 식에서 제곱근이므로 항상 positive ($A$가 full-rank)여야 함 ($A$가 rank deficient이면, non-negative만 보장).
• 앞서 말했지만, $S$의 rank가 $n$이고 symmetric하고, positive semi-definite이므로 $S$의 eigenvalues는 positive임.
• 때문에 $A$의singular value도 역시 positive임.

---

같이보면 좋은 자료들

2022.11.17 - [.../Linear Algebra] - [LA] Diagonalization (Eigen-Decomposition), Orthogonal Diagonalization, and Symmetric Matrix

[LA] Diagonalization (Eigen-Decomposition), Orthogonal Diagonalization, and Symmetric Matrix

---

2025.01.21 - [.../Linear Algebra] - [Summary] Linear Algebra (작성중)

[Summary] Linear Algebra (작성중)

---