The Singular Value Decomposition and It’s Applications in Image Processing
5년 전 글 백업.
Christopher Jason Ogden, Tammie Huff “The Singular Value Decomposition and It’s Applications in Image Processing”, 1997
1. Introduction
SVD는 행렬을 더 작은 invertible, square matrix로 factorization, approximation하는 효과적은 테크닉입니다.
2. Mathematrics Behind the SVD
m * n의 크기의 랭크 r인 행렬 A가 있다고 합시다. 그러면 그것의 SVD는 다음과 같습니다.
$$A = UDV^T$$
여기서 D는 m * n diagonal 행렬이고 아래와 같은 성분을 가집니다.
$$\sigma_1 \gt \sigma_2 \gt \dots \gt \sigma_r \gt 0, \ r = \min(m, n)$$
U와 V는 orthogonal 행렬로 U는 m * m, V는 n * n 행렬입니다. D의 각 성분들은 행렬 A의 singular value라고 불리며, U와 V는 A의 left, right singluar vector라고 합니다. 아래와 같이 각각의 해당하는 singular value와 singular vector를 곱하면 A의 컬럼 벡터가 나옵니다.
$$A_i = U_i \sigma_i V_i^T$$
2.1 Linear Transformations
행렬 A의 unit eigenvector를 $x$, 그의 eigenvalue를 $\lambda$라고 하면 아래와 같이 됩니다.
$$|| Ax||^2 = (Ax)^T(Ax) \\
= x^T A^T Ax = x^T (A^TA)x \\
= x^T S x$$
S가 inverable square matrix이고 x가 unit eigenvector이므로, S의 가장 큰 eigenvalue $v_1$와 그의 unit eigenvector는 위의 식을 최대화(maximize)합니다. 즉 $ x = v_1$ 일 때, $||Ax||^2$는 최대가 됩니다.
$$Ax = \lambda x \\
(A^TA)v = \sigma v \\
||Ax|| = || \lambda x || = | \lambda | || x || = | \lambda|$$
$$|| Ax ||^2 = | \lambda|^2 = x^T (A^TA) x \\
x | \lambda|^2 = x x^T (A^TA) x \\
|\lambda|^2 x = (A^TA) x$$
$$x = v$$
$$|\lambda|^2 v = \sigma v \\
|\lambda|^2 v v ^T = \sigma v v^T \\
|\lambda|^2 = \sigma$$
따라서 S를 최대화하는 S의 eigenvalue는 $\lambda$의 제곱입니다.
2.2 Invertible Square Matrix
$$A = UDV^T \\ U = AVD^{-1}$$
2.3 Consolidating a Matrix Using SVD
A의 랭크가 r이라면 D는 r * diagonal 행렬이 되고 S는 r개의 eigenvalue를 원소로 갖는 행렬이 됩니다. 만약 m * n 행렬 A에서 $ m \gt r $이거나 $ n \gt r $이라면 D 행렬은 m * n 행렬이 되고 m - r의 행과 n -r개의 열 자리에는 0으로 채워집니다.