Linear Algebra
///
///
📁

5. Singular Value Decomposition

태그
SVD
orthogonally diagonalizable
s.p.d

Singular Value Decomposition (SVD)

rectangular 행렬 A∈Rm×nA \in \mathbb{R}^{m \times n}이 주어졌을 때, SVD는 아래와 같이 정의됩니다.
A=UΣVT=∑i=1nσiuiviT, where σ1≥σ2≥⋯≥σnA=U \Sigma V^{T}=\sum_{i=1}^{n} \sigma_{i} \mathbf{u}_{i} \mathbf{v}_{i}^{T}, \quad \text { where } \sigma_{1} \geq \sigma_{2} \geq \cdots \geq \sigma_{n}
이 때, SVD를 구성하는 각 행렬들은 아래와 같은 특징을 가집니다.
•
U∈Rm×mU \in \mathbb{R}^{m \times m} → Col⁡A\operatorname{Col} A의 orthonormal basis에 해당하는 orthonormal column들로 이루어진 행렬
•
V∈Rn×nV \in \mathbb{R}^{n \times n} → Row⁡A\operatorname{Row} A의 orthonormal basis에 해당하는 orthonormal column으로 이루어진 행렬
•
Σ∈Rm×n\Sigma \in \mathbb{R}^{m \times n} → σ1≥σ2≥⋯≥σmin⁡(m,n)\sigma_{1} \geq \sigma_{2} \geq \cdots \geq \sigma_{\min (m, n)}의 내림차순으로 정렬된 singular value값들을 entries로 가지는 diagonal matrix
시각적으로 표현하면 아래와 같다.
이와 같이 표현할 경우, U∈Rm×m→U′∈Rm×n\mathbf{U} \in \mathbb{R}^{m \times m} \rightarrow \mathbf{U}^{\prime} \in \mathbb{R}^{m \times n}, D∈Rm×n→D′∈Rn×n\mathbf{D} \in \mathbb{R}^{m \times n} \rightarrow \mathbf{D}^{\prime} \in \mathbb{R}^{n \times n}로 축소되어 표현되며, 이를 Reduced form of SVD라고한다.

Another Perspective of SVD

앞서 배운 Gram-Schmidt orthogonalization을 활용하면, 쉽게 2개의 orthonormal basis 집합을 구할 수 있다. Col⁡A\operatorname{Col} A에 해당하는 {u1,…,un}\left\{\mathbf{u}_{1}, \ldots, \mathbf{u}_{n}\right\}, Row⁡A\operatorname{Row} A에 해당하는 {v1,…,vn}\left\{\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\right\} 그러나 이러한 orthonormal basis는 unique하지 않으며 여러가지 형태로 존재할 수 있다. 각 벡터 vi,ui\mathbf{v_{i}, u_{i}}는 아래와 같은 식을 만족한다.
Avi=σiui,∀i=1,…,nA \mathbf{v}_{i}=\sigma_{i} \mathbf{u}_{i}, \quad \forall i=1, \ldots, n
앞서 다룬, EVD에서의 Ax=λxA \mathbf{x}=\lambda \mathbf{x}와 굉장히 유사한 형태인것을 확인할 수 있다. 단지, EVD의 경우 양변의 orthonormal vector들의 dimension이 동일했던 것 대비, SVD에서는 양변의 orthonormal vector들의 dimension이 동일하지 않다.

Singular Values of an m×nm \times n Matrix

행렬 AA를 m×nm \times n 행렬로 가정하면, 이 때, ATA A^{T}A는 symmetric하기 때문에 orthogonally diagonalizable 합니다. (이전 챕터에서 다루었음) {v1,…,vn}\left\{\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\right\}을 해당하는 eigenvector를 구성하는 orthonormal basis라고 가정한다면, 아래 조건을 만족합니다.
∥Avi∥2=(Avi)TAvi=viTATAvi=viT(λivi)=λi\left\|A \mathbf{v}_{i}\right\|^{2}=\left(A \mathbf{v}_{i}\right)^{T} A \mathbf{v}_{i}=\mathbf{v}_{i}^{T} A^{T} A \mathbf{v}_{i} \\\begin{array}{l} =\mathbf{v}_{i}^{T}\left(\lambda_{i} \mathbf{v}_{i}\right) \\ =\lambda_{i} \end{array}
행렬 AA의 singular value는 행렬 ATAA^{T}A의 eigenvector 값의 square root로 정의할 수 있다. 이는 벡터 Av1,…,AvnA \mathbf{v}_{1}, \ldots, A \mathbf{v}_{n} 의 길이로도 해석할 수 있다.
σi=λi for 1≤i≤n\sigma_{i}=\sqrt{\lambda_{i}} \text { for } 1 \leq i \leq n

임의의 행렬 A∈Rm×nA\in \mathbb{R}^{m \times n} 의 rank 구하는 방법

•
행렬 AA를 row-reduction 한 후에 echelon form으로 만들어 pivot의 개수 구하기
•
행렬 ATAA^{T}A에 해당하는 eigenvalue, eigenvector를 구한 후 0이 아닌 rr개의 singular values를 구하면, {Av1,…,Avr}\left\{A \mathbf{v}_{1}, \ldots, A \mathbf{v}_{r}\right\}이 Col⁡A\operatorname{Col} A의 orthogonal basis가 되고, rank⁡A=r\operatorname{rank} A=r을 만족하게 된다.
몇몇의 경우에 한해서, 행렬 AA의 rank는 내부 원소의 조그마한 변화에도 민감하다. 컴퓨터로 row-reduction하는 경우 echelon form으로 변환하는 과정에서 round off-error가 발생하기 때문에 정확하게 되지 않게 된다. 따라서 첫번째 방법이 잘 동작하지 않게 된다. 실제 상황에서는 2번째 방법을 채택하여 큰 행렬에 대해서 rank를 구한다.

Computing SVD

먼저, eigendecomposition을 구하기 위해 AAT,ATAAA^{T}, A^{T}A를 형성한다.
AAT=UΣVTVΣTUT=UΣΣTUT=UΣ2UTATA=VΣTUTUΣVT=VΣTΣUT=VΣ2VT\begin{array}{l}A A^{T}=U \Sigma V^{T} V \Sigma^{T} U^{T}=U \Sigma \Sigma^{T} U^{T}=U \Sigma^{2} U^{T} \\A^{T} A=V \Sigma^{T} U^{T} U \Sigma V^{T}=V \Sigma^{T} \Sigma U^{T}=V \Sigma^{2} V^{T}\end{array}
이 때, AAT,ATAAA^{T}, A^{T}A는 symmetric이기 때문에 orthogonally diagonalizable 합니다. 이에 맞추어 eigendecomposition을 실행하면,
S=UDUT=[u1u2⋯un][λ10⋯00λ2⋱⋮⋮⋱⋱00⋯0λn][u1Tu2T⋮unT]=λ1u1u1T+λ2u2u2T+⋯+λnununT where λj>0,∀j=1,⋯ ,n\begin{array}{c}S=U D U^{T}=\left[\begin{array}{llll}\mathbf{u}_{1} & \mathbf{u}_{2} & \cdots & \mathbf{u}_{n}\end{array}\right]\left[\begin{array}{cccc}\lambda_{1} & 0 & \cdots & 0 \\0 & \lambda_{2} & \ddots & \vdots \\\vdots & \ddots & \ddots & 0 \\0 & \cdots & 0 & \lambda_{n}\end{array}\right]\left[\begin{array}{c}\mathbf{u}_{1}^{T} \\\mathbf{u}_{2}^{T} \\\vdots \\\mathbf{u}_{n}^{T}\end{array}\right] \\=\lambda_{1} \mathbf{u}_{1} \mathbf{u}_{1}^{T}+\lambda_{2} \mathbf{u}_{2} \mathbf{u}_{2}^{T}+\cdots+\lambda_{n} \mathbf{u}_{n} \mathbf{u}_{n}^{T}\end{array} \\ \text { where } \lambda_{j}>0, \forall j=1, \cdots, n
각각의 term λiujujT\lambda_{i} \mathbf{u}_{j} \mathbf{u}_{j}^{T}는 uj \mathbf{u}_{j}에 의해 span되는 subspace로의 projection matrix로 해석할 수 있으며, 이 것은 eigenvalue λi\lambda_{i}로 Scale 됩니다.
이 때, 행렬 SS에 대한 특징을 2가지로 정리할 수 있습니다.
•
Symmetric → (AAT)T=AAT and (ATA)T=ATA\left(A A^{T}\right)^{T}=A A^{T} \text { and }\left(A^{T} A\right)^{T}=A^{T} A
•
Positive-(semi-)definite → 아래 성질을 만족
xTAATx=(ATx)T(ATx)=∥ATx∥2≥0xTATAx=(Ax)T(Ax)=∥Ax∥2≥0\begin{array}{l}\mathbf{x}^{T} A A^{T} \mathbf{x}=\left(A^{T} \mathbf{x}\right)^{T}\left(A^{T} \mathbf{x}\right)=\left\|A^{T} \mathbf{x}\right\|^{2} \geq 0 \\\mathbf{x}^{T} A^{T} A \mathbf{x}=(A \mathbf{x})^{T}(A \mathbf{x})=\|A \mathbf{x}\|^{2} \geq 0\end{array}
위의 s.p.d 조건을 통해 항상 orthogonal한 eigenvector 행렬 U,VU,V를 찾을 수 있으며, Σ2\Sigma^{2}로 표현되는 eigenvalues는 항상 positive하다는 것을 알 수 있습니다!
정리하면, 임의의 rectangular matrix A∈Rm×n\mathbf{A} \in \mathbb{R}^{m \times n}에 대해 SVD는 항상 존재합니다. 이 행렬 AA를 가지고 만든 s.p.d matrix SS는 항상 EVD 가능하며, SVD와 동일합니다.

실제 값으로 SVD 진행해보기

Reference

인공지능을 위한 선형대수 강좌소개 : edwith
인공지능을 위한 선형대수
https://www.edwith.org/ai251
Linear Algebra and Its Applications
Buy Linear Algebra and Its Applications on Amazon.com ✓ FREE SHIPPING on qualified orders
https://www.amazon.com/Linear-Algebra-Its-Applications-5th/dp/032198238X
Made with