SVD

<SVD>

    1. Singular Value Decomposition

---

Singular Value Decomposition

 

 

이전에 배운 Eigendecomposition

• Sqaure Matrix에서만 적용
• Matrix D, P, P^-1  등을 orthogonal atrix로 설정 시, 이를 rotation, reflection 등으로 해석

    (항상 orthogonal matrix이지는 않다.)

 

 

 

 

Singular Value Decomposition (SVD)

• dimensionaliy reduction, low-rank matrix approximation, recommendation system 등 다양한 분야에 사용

• Rectangular Matrix A → Span (m x n)
• Matrix U → Span (m x m) + orthonormal columns

    left singluar vector: Matrix u의 각 column vector

• Matrix V → Span (n x n) + orthonormal columns

    right singluar vector: Matrix V의 각 column vector

• Diagonal Matrix S → Span (m x n) + decreasing entries (s1 ≧ s2 ≧ ... ≧)

    singular value: Matrix S의 0 초과의 요소들 개수

    singular value의 개수 (k) = Matrix A의 rank

 

 

Basic Form of SVD

Matrix A가 full-rank가 아닌 경우 SVD

↓

Redeuced Form of SVD

singular value = 0 인 부분 제거

 

 

 

• {v1, v2, ..., vn}은 A^T*A의 orthonormal basis라고 가정하고,
• λ1 ≧ λ2 ≧ ... ≧ λn을 만족하고,
• A가 r개의 nonzero singular values라고 가정할 시,

    → {Av1, Av2, ..., Avr}은 Col A의 orthogonal basis이며, rank A = r이다.

 

proof) vi와 λj*vj가 orthogonal 하기 때문에

(Avi)T*(Avj) = (vi)T*A^T*Avj = (vi)T(λj*vj) = 0을 만족하므로, (내적 = 90˚)

{Av1, Av2, ..., Avr}은 orthogonal한 set을 만족한다.

 

 

• {Av1, Av2, ..., Avn}의 길이 = A의 singular value 개수이고,
• r개의 nonzero singular value가 존재하기 때문에,

    → {Av1, Av2, ..., Avn}은 linearly independent vector들이고 Col A에 Span 되어있다.

 

• y = Ax에서, x = C1V1 + ... + CnVn이고,
• y = Ax = C1AV1 + ... + CrAVr + Cr+1AVr+1 + ... + CnAVn
•    = C1AV1 + ... + CrAVr + 0 + ... + 0 이므로,

    → y는 Col A의 orthogonal basis인 Span{AV1, ..., AVr}

    → rank A = dim Col A = r

 

 

• 각 AVi는 orthonormal basis인 {u1, u2, ..., ur}을 얻을 수 있고, (ui = AVi / norm(AVi) = AVi / ∂i) 이므로,

    → AVi = ∂iui

 

• U = [u1 u2 ... um], V =[v1 v2 ... vn] 일 시,

    → Matrix U와 Matrix V는 Orthogonal Matrix이다.

 

• AV = [Av1, ... Avr, 0, ... 0 ] = [∂1u1, ... ∂rur, 0 ... 0]이고,
• Matrix V는 orthogonal Matrix 이므로,

    → USV^T = AVV^T = A