SVD : singular value decomposition ( 특이값 분해 ) - 출처 : 보리님 블로그

모든 m×n 행렬 A은 다음과 같이 분해할 수 있다.A = UΣV^TU는 m×m 직교 행렬(orthogonal matrix)이고, V는 n×n 직교 행렬이다. m×n 행렬인 Σ는 대각선에만 그 값이 있는데, 0 또는 양수이다. 이 값을 특이값(singular value)이라고 한다. 고유값-고유벡터 분해(eigenvalue-eigenvector decomposition)A = QΛQ^T는 대칭 행렬(symmetric matrix)에 대해서 먹히는 반면에 (사실 충분 조건이다. 필요충분조건을 말하려면 너무 길어지니깐...) , SVD는 모든 행렬에 대해 (정방행렬이 아니더라도) 써 먹을 수 있는 만능이다.행렬 A를 벡터 공간(vector space) 간 선형 사상(linear mapping)으로 보면 (엮인 글을 참고하시오), s = min(m, n)y = Ax = UΣV^Tx = (v₁^Tx)σ₁u₁ + ... + (v_s^Tx)σ_su_s위 식에서 {v_i} 를 입력 공간의 직교 베이스(orthogonal basis)로 보고 {u_i} 를 출력 공간의 직교 베이스로 볼 수 있다. 그러면 v_i^Tx 는 입력 벡터 x 를 베이스 {v_i} 에 대해 표현할 때의 좌표이다. 그리고 출력 벡터 y는 베이스 {u_i}의 선형 조합(linear combination)으로 표현되는데 각 계수는 대응하는 입력 좌표와 특이값의 곱이다. (넓은 의미로 decouple 되었다고 볼 수 있다.)

 

0이 아닌 특이값이 r 개라고 하고 그것을 내림차순으로 정렬하자. 즉, σ₁ > σ₂ > ... > σ_r그러면 {u₁, ..., u_r}이 칼럼공간(column space)의 베이스가 되고, {v_r+1, ..., v_n}은 영공간(null space)의 베이스가 된다. (위 식과 그림을 유심히 보라.)이제 선형 방정식의 풀이에 대해 생각해 보자.Ax = b아까는 x가 주어지고 y를 구하는 것을 생각했지만, 이제는 y = b가 주어지고 그것을 충족하는 x를 찾는 문제다.UΣV^Tx = bx = VΣ^-1U^Tb위 식에서 Σ^-1는 {1/σ_i}가 대각선에 있는 n×m 행렬이다. 위 식만 놓고 보면 말이 안된다. 하지만 그 위의 풀어 헤쳐 놓은 식을 보라. 그러면 말이 된다. 그렇기 때문에 Σ⁺란 기호를 쓴다.위 식에서 U^Tb는 b를 칼럼 공간 {u₁, ..., u_r}에 투영(projection)하는 것이다. (r 보다 큰 칼럼은 Σ^-1이 지워주므로 위 명제에 대해 걱정하지 말라.) 그리고 VΣ^-1은 x 중 영 공간(null space)에 있는 벡터 성분을 0 벡터로 바꿔준다. 입력 공간과 출력 공간 모두에 대해서 최소제곱해(least-square solution)을 제공한다.x = VΣ⁺U^Tb = A⁺b위 식에서 A^{+ =} VΣ⁺U^T를 A의 pseudo-inverse라고 한다.