[선형대수] 행렬의 여러 가지 분해(Matrix decomposition) 정리 (EV, SV, LU, Cholesky, QR) #1

 

 

 

 

 

이전에 논문을 읽다 QR decomposition 키워드가 나온 것을 계기로 여러 행렬 분해(Matrix decomposition)를 간단히 공부해 보게 되었다. (선형대수 복습도 살짝 하는 겸 해서...)

 

https://istein.tistory.com/156

[Bio-inspired][Designing] 걷기, 점핑 등이 가능한 새 모방 로봇 다리, Fast ground-to-air transition with avian-ins

 

 

이번 공부는 수학이 아닌 로봇공학을 공부하는 학생의 관점에서 정리했습니다. 수학적인 의미를 깊게 아는 것도 공학에서 중요하다고 생각하지만 이번에는 의미, 용도, 적용사례 정도에 초점을 두고 공부했습니다.

 

 

*늘 그렇듯 틀린 내용이 있을 수 있습니다.

 

 

 

 

 

 

 

 

우선 시작에 앞서 행렬 분해가 구체적 무엇을 하는 것인지 부터 알아봤다.

 

 

행렬 분해(Matrix decomposition) : 하나의 행렬을 여러 행렬의 곱으로 나타내는 것, 행렬의 인수분해(factorization).

 

●즉 어떤 행렬 $A$를 여러 행렬($B,C,D,\cdots$의 곱으로 나타내는 과정 $A=BCD\cdots$이다.

 

 

●행렬 분해를 하는 이유는 정말 다양하지만 나는 크게 "선형대수학의 문제(연립방정식, 미분방정식, 최소제곱법 등)를 효율적으로 풀기 위함"이라고 이해했다.

※Systems of linear equations, Differential equation, Least square equation, etc.

 

 

●여러 글을 찾아봤는데 Allan Steinhardt 박사님이 설명하신 게 가장 짧고, 쉽게 머리에 들어왔다. (가장 얕게 설명한 글이라 지금의 내가 가장 쉽게 받아들인 것 같다.)

https://www.quora.com/What-is-the-purpose-of-matrix-factorization

What is the purpose of matrix factorization?

 

 

●Eigenvalue-decomposition, LU-decomposition, QR-decomposition, Singular-value-decomposition, Cholesky-decomposition 등 다양한 방법이, 각기 다른 목적을 위해 사용된다.

 

 

 

 

 

 

 

이번 글에선 내가 배웠거나, 한번이라도 들어본 적 있는 분해법에 대해서만 공부했다.

 

 

Eigenvalue decomposition(EVD, 고윳값 분해)

Square matrix A의 eigenvector matrix가 full rank면 A를 다음과 같이 분해할 수 있다.

 

$A=PDP^{-1}$        $P\text{: Eigenvector matrix}$,     $D\text{: Eigenvalue matrix}$

 

※P와 D는 coupled 되어 있다. P의 eigenvector의 순서에 맞게 D가 구성된다.

 

※Eigenvector matrix는 Orthogonal matrix이고, Eigenvalue matrix는 Diagonal matrix이다.

 

 

●Eigenvalue와 Eigenvector를 배울 때 같이 배우는 대각화(diagonalization) $D=P^{-1}AP$와 사실상 같은 개념이다.

 

 

●①Caluation of the Analytic function of a matrix, ②Decoupling the dynamics equation 등에 사용할 수 있다.

 

 

①Caluation of the Analytic function of a matrix

●모든 analytic function of a scalar는 analytic function of a matrix로 사용할 수 있다. 물론 무턱대고 함수에 square matrix의 각 값을 넣어 계산하면 안 된다. Analytic function을 행렬 계산에 사용 가능한 형태로 바꿔줘야 사용 가능하다.

 

●예를 들어 $f(x)=\text{sin}(x)$는 테일러급수(Taylor series)를 통해 $f(x)=\text{sin}(x)=\sum\limits_{n=0}^{\infty}\frac{(-1)^n}{(2n+1)!}x^{2n+1}$로 표현할 수 있다. 바뀐 식은 $x$에 대해서 제곱 밖에 없으므로 square matrix로도 계산할 수 있다.

 

●$A=\begin{bmatrix}1 & 3\\2 & 1\end{bmatrix}$,             $f(A)=\sum\limits_{n=0}^{\infty}\frac{(-1)^n}{(2n+1)!}A^{2n+1}=A-\frac{A^3}{3!}+\frac{A^5}{5!}-\cdots=\begin{bmatrix}-0.6479 & 0.4223 \\0.2815 & -0.6479\end{bmatrix}$

 

●한편 square matrix가 diagonalable, 즉 EVD가 가능하다면 $\color{Red}f(A)=P\begin{bmatrix}f(D_{1}) & 0 & 0 \\0 & \ddots &0  \\0 & 0 & f(D_{n})\end{bmatrix}P^{-1}$를 이용해 굳이 함수를 square matrix 계산이 가능한 형태로 바꿀 필요가 없어진다.

 

●$f(A)=\begin{bmatrix}0.7746 & -0.7746 \\0.6325 & 0.6325\end{bmatrix}\begin{bmatrix}\text{sin}(3.4495) & 0 \\0 & \text{sin}(-1.4495)\end{bmatrix}\begin{bmatrix}0.7746 & -0.7746 \\0.6325 & 0.6325\end{bmatrix}^{-1}=\begin{bmatrix}-0.6479 & 0.4223 \\0.2815 & -0.6479\end{bmatrix}$

 

 

 

 

②Decoupling the dynamics equation 

●운동방정식에 coupled 된 coordinate가 있다면 일반적으로 이 방정식은 그렇지 않은 방정식보다 해를 구하기 어렵다.

 

 

●위와 같은 2-DOF mass spring system을 예로 들면, $x=\begin{bmatrix}x_{1} \\ x_{2}\end{bmatrix}$,     $\begin{bmatrix}m & 0 \\0 & m\end{bmatrix}\ddot{x}=\begin{bmatrix}-2k & k \\k & -2k\end{bmatrix}x$에서 우항의 matrix(Stiffness matrix)가 coupled 되어 있기에 바로 해를 구할 수 없다.

 

 

●하지만 위 운동방정식을 하나의 행렬만 갖도록 정리한 후 EVD를 하면 운동방정식을 Decoupling 할 수 있다.

 

$\begin{bmatrix}m & 0 \\0 & m\end{bmatrix}\ddot{x}= \begin{bmatrix}-2k & k \\k & -2k\end{bmatrix}x \longrightarrow \color{Red} \ddot{x}=\begin{bmatrix}-2k/m & k/m \\k/m & -2k/m\end{bmatrix}x$

 

+)계산 편의를 위해 $m=1, k=1$로 둔다.

 

$\ddot{x}=\begin{bmatrix}-2 & 1 \\1 & -2\end{bmatrix}x$,     $A=\begin{bmatrix}-2 & 1 \\1 & -2\end{bmatrix}$,  $ \color{Red} A=PDP^{-1}$

 

$P^{-1}\ddot{x}=DP^{-1}x$         $ \color{Red} \begin{bmatrix}u_{1} \\ u_{2}\end{bmatrix}=u=P^{-1}x$,        $ \color{Red} \ddot{u}=P^{-1}\ddot{x}$

 

$\ddot{u}=Du$            $\begin{bmatrix}\ddot{u}_1 \\ \ddot{u}_2\end{bmatrix}=\begin{bmatrix}-3 & 0 \\0 & -1\end{bmatrix}\begin{bmatrix}u_1 \\u_2\end{bmatrix}$  (Decoupled!)

 

 

Decoupled된 운동방정식에서 $u$의 해를 구하는 것은 매우 쉽고, 이후 $Pu=x$를 이용하면 $x$의 해를 구할 수 있다.

 

 

※이번 글은 진동학과 관련된 글이 아니므로 얻은 해의 분석, Eigenvector=Mode, Eigenvalue=Natural frequency, Mass matrix와 Stiffness matrix의 특징에 대한 설명은 따로 하지 않겠습니다.

 

 

●위와 같은 방법으로 운동방정식을 Decouple 해서 쉽게 해를 구할 수 있다!

 

 

 

 

 

 

 

 

Single Value Decomposition(SVD, 특잇값 분해)

모든 matrix A($m\times n$)는 다음과 같이 분해할 수 있다.

 

$A=U\Sigma V^{T}$       $U\text{: Left-singular vector matrix}$,    $\Sigma\text{: Singular value matrix}$,   $V\text{: Right-singular vector matrix}$

 

※Singular vector matrices와 Singular value matrix는 coupled 되어 있다. $U$와 $V$의 singular vector의 순서에 맞게 $\Sigma$가 구성된다.

 

※Left-singular vector matrix는 $m\times m$ Orthogonal matrix이고, Right는 $n\times n$ Orthogonal matrix, 그리고 Singular value matrix는 $m\times n$ Diagonal matrix이다.

 

※$m\times n$ Diagonal matrix는 $m,n$중에 작은 값으로 square diagonal matrix를 만든 다음 0을 붙여서 $m\times n$을 만들어주면 된다.

 

※일반적으로 $\Sigma$는 큰 Eigenvalue가 먼저 오도록 만든다. $\Sigma_{1,1}>\Sigma_{2,2}>\cdots >\Sigma_{r,r}$

 

 

●EVD가 square matrix 중에서도 diagonalize가 가능한 matrix에만 사용할 수 있는 반면, SVD는 행렬, rectangular 행렬에도 사용이 가능하다. 개인적으로는 EVD의 general 한 버전이라고 외웠다.(불확실)

 

 

●$U, V, \Sigma$를 구하는 방법은 두 가지가 있다.(사실 둘은 본질적으로는 같은 방법이다.)

 

 

ⓐEVD를 이용

$AA^T$의 Eigenvector matrix  = $U$ (Left singular vector matrix)

$A^TA$의 Eigenvector matrix = $V$ (Right singular vector matrix)

$AA^T$의 Eigenvalue matrix = $A^TA$의 Eigenvalue matrix = $\Sigma^2$  (둘 중 크기가 큰 행렬의 0 eigenvalue는 무시)

 

●위 방법의 문제는 Eigenvector의 ambiguity(모호성)에서 발생한다. Eigenvalue는 한 행렬에 대해 unique 하지만 그 Eigenvalue와 연관된 Eigenvector는 unique하지 않다. Eigenvector matrix는 normalize 한 eigenvector들로 구성되어 있기에 크기에 대한 모호성은 사라지지만 아직 부호에 대한 모호성이 남아 있기에 문제가 발생한다.

 

e.g. eigenvector $\begin{Bmatrix}0.7071 \\ -0.7071\end{Bmatrix}$와 $\begin{Bmatrix}-0.7071 \\ 0.7071\end{Bmatrix}$은 같다

 

 

●따라서 $AA^T$와 $A^TA$를 EVD해서 $U, \Sigma, V$를 구하면 $A\neq U \Sigma V^T$ 가 될 수 있다.

 

 

●계산 과정에서 부호를 어떻게 해야 $A = U \Sigma V^{T}$를 만족하는 singular matrix를 구할 수 있을지는 결과를 보기 전에는 알 수 없다고 하기에 다른 방식의 접근이 필요하다.

 

 

 

 

ⓑ$AV=U\Sigma$ 이용

●기본적으로 SVD는 $AV=U\Sigma$ 로부터 만들어졌다.

+)"어떤 Orthogonal set of vectors $V$에 $A$변환을 했을 때 만들어지는 크기만 다를 뿐 서로 Orthogonal한 Set of vectors $U\Sigma$를 찾는다."가 SVD의 접근법이다.

 

 

●위 Set of vectors(Matrix)에 대한 식을 단일 벡터에 대한 식으로 분해해 이용하면 $AA^T$나 $A^TA$ 중 하나의 EVD 값만 갖고서 $U, \Sigma, V$를 계산할 수 있다. 

 

 

●아래는 내가 한번 구성해 본 SVD 계산 알고리즘이다. 더 효율적인 알고리즘이 있겠지만 아래는 어디까지나 내가 이해한 부분을 바탕으로 만들어 본 것이다.

 

 

 

 

●①Image compression, ②Calculate the pseudo inverse of a rectangular matrix, ③Least square method 등에 사용할 수 있다.

 

①Image compression

●비트맵 이미지는 하나의 행렬로 볼 수 있다. 예를 들어 1920*1080 해상도의 이미지는 1920*1080 크기의 행렬로 볼 수 있고 각 요소(elements)들은 한 픽셀을 의미하며 그 값으로 픽셀의 정보(색, 명암 등)를 나타낸다.

 

●한편 SVD를 시각화하면 A라는 행렬을 같은 크기의 여러 layer의 linear combination으로 나타내는 과정으로 표현할 수 있다.

 

●Singular value, 즉 $\Sigma$의 값들은 일종의 각 layer의 weight를 나타낸다. 앞쪽 singular value가 더 크므로($\Sigma_{1} > \Sigma_{2}$) 앞쪽 layer가 원본 행렬 A의 전반적인 윤곽을 나타내고, 뒤쪽 layer로 갈수록 세부적인 부분을 나타내게 된다.

 

●어떤 비트맵 그림을 SVD를 이용해 n개의 layer로 쪼갠 후 $1$st layer부터 $r$th layer ($1<r<n$)까지만의 linear combination으로 나타내면 원본 이미지를 더 적은 layer만으로도 나타낼 수 있다.

 

●물론 이 과정에서 뒤쪽의 $(r+1)$th - $n$th layer는 버려지는 것이기에 세부 묘사가 안 좋아지긴 한다.

 

●이 과정은 "공돌이의 수학정리노트"님의 유튜브 영상 후반부를 보는 편이 훨씬 이해가 쉬울 것이다.

https://angeloyeo.github.io/2019/08/01/SVD.html

특이값 분해(SVD) - 공돌이의 수학정리노트 (Angelo's Math Notes)

 

 

 

 

②Calculate the pseudo-inverse of a rectangular matrix (Moore-Penrose pseudo-inverse)

●본래 Inverse matrix(역행렬)는 Non singular square matrix(determinant≠0)에서만 정의된다. 하지만 SVD로 Rectangular matrix를 분해하면 나오는 $U,\Sigma, V$에 inverse를 해주면 원래 Rectangular matrix의 Pseudo inverse matrix(유사역행렬)을 구할 수 있고 이 유사역행렬은 Moore-Penrose pseudo-inverse matrix라 불린다.

 

●유사역행렬은 역행렬과 같은 역할을 하며 기호는 $\dagger$나 $+$를 사용한다.

 

Example

 

$A=\begin{bmatrix}1 & 2 \\5 & 3 \\1 & 0\end{bmatrix}$

 

$\longrightarrow U=\begin{bmatrix}-0.31 & 0.87 & 0.38 \\-0.94 & -0.23 & -0.25 \\-0.13 & -0.44 & 0.89\end{bmatrix},\Sigma=\begin{bmatrix}6.20 & 0 \\0& 1.27 \\0& 0\end{bmatrix},V=\begin{bmatrix}-0.83& -0.56 \\-0.56 & 0.83\end{bmatrix}$

 

$A=U\Sigma V^T\longrightarrow A^\dagger=(U\Sigma V^T)^{-1}=(V^T)^{-1}\Sigma^{-1}U^{-1}=V\Sigma^{\dagger}U^T$

 

※$U, V$는 Orthogonal matrix이기에 Transpose와 Inverse가 같다.

 

$\Sigma$또한 rectangular matrix이기에 역행렬이 불가능하기에 $\dagger$를 사용한다. 이 경우 square diagonal 부분의 역행렬을 구해주고 0을 차원에 맞게 추가해 주면 된다. 

 

$\Sigma^{\dagger}=\begin{bmatrix}\frac{1}{6.20} & 0 & 0 \\0 & \frac{1}{1.27} & 0\end{bmatrix}$

 

$A^{\dagger}=V\Sigma^{\dagger}U^{T}=\begin{bmatrix}-0.34 & 0.23 & 0.21 \\0.60& -0.06 &-0.27\end{bmatrix}$

 

$\color{Red}A^{\dagger}A=I$

 

 

 

 

 

③Least square method

●어떤 systems of linear equations $Ax=b\longrightarrow Ax-b=0$가 있다고 하고 solution $x$이 없다고 해보자. ($A$가 Square matrix임에도 해가 없거나 $A$가 retangular matrix인 경우)

 

●이 경우 $Ax-b$가 $=0$이 되는 경우의 $x$(exact solution) 대신 아닌 가장 작은 값($\approx 0$)을 갖도록 하는 $x$(approximate solution)를 찾는 방법이 이용될 수 있다. 즉 $\left\| Ax-b \right\|^{2}=\left( Ax-b \right)^2$를 최소로 만드는 $x$를 찾는 것이며 이를 Least Square Method(LSM)라고 한다.

 

●LSM은 systems of linear equations 근사해를 찾거나 혹은 데이터의 선형회귀분석(Linear regression)에 사용된다. (사실상 둘은 같은 말이다.)

 

Example

 

$\begin{matrix}3x+2y=2 \\4x+y=1 \\5x+3y=4\end{matrix}\longrightarrow \begin{bmatrix}3&2\\4&1\\5&3\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}2\\1\\4\end{bmatrix}\longrightarrow Ax=b$

 

$x=A^{-1}b$ 불가능

 

대신 $Ax=b\text{ }\longrightarrow \text{ }(U\Sigma V^T)x=b\text{ }\longrightarrow\text{ } x=(U\Sigma V^T)^{-1}b \text{ }\longrightarrow \text{ }\color{Red} x=A^{\dagger}b$ 

 

$\color{Red}x\approx\begin{bmatrix}0.1429 \\0.5717\end{bmatrix}$

 

이렇게 구한 $\color{Red}x, y$는 위 연립방정식의 엄밀 해는 아니지만 가장 근사한 해가 된다.

 

 

※SVD는 ill-conditioned least square method에서 사용된다는데 ill-conditioned가 구체적으로 어떤 경우를 말하는 지에 대한 공부가 추가적으로 필요하다.

 

 

 

 

생각보다 글이 많이 길어져서 #1, #2로 나눈다...

 

 

Reference

https://en.wikipedia.org/wiki/Matrix_decomposition

Matrix decomposition - Wikipedia

(25.01.10 접속)

 

 

https://www.quora.com/What-is-the-purpose-of-matrix-factorization

What is the purpose of matrix factorization?

(25.01.10 접속)

 

 

https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix

Eigendecomposition of a matrix - Wikipedia

(25.01.10 접속)

 

 

https://en.wikipedia.org/wiki/Analytic_function_of_a_matrix

Analytic function of a matrix - Wikipedia

(25.01.10 접속)

 

 

https://math.mit.edu/~jorloff/suppnotes/suppnotes03/ls4.pdf

(Arthur Mattuck and M.I.T, "M.I.T. Ordinary Differential Equations 18.03 Notes and Exercises",  25.01.10 접속)

 

 

https://darkpgmr.tistory.com/106

[선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용

(25.01.10 접속)

 

 

https://angeloyeo.github.io/2019/08/01/SVD.html

특이값 분해(SVD) - 공돌이의 수학정리노트 (Angelo's Math Notes)

(25.01.10 접속)

 

 

https://math.stackexchange.com/questions/2359992/how-to-resolve-the-sign-issue-in-a-svd-problem

How to resolve the sign issue in a SVD problem?

(25.01.10 접속)

 

 

https://pasus.tistory.com/31

유사 역행렬 (Pseudo Inverse Matrix)

(25.01.10 접속)

 

 

Dennis G. Zill, "Advanced Engineering Mathematics" 6th international student edition, 2017. 

 

 

 

========================================================================
정확한 정보 전달보단 공부 겸 기록에 초점을 둔 글입니다.
틀린 내용이 있을 수 있습니다.
틀린 내용이나 다른 문제가 있으면 댓글에 남겨주시면 감사하겠습니다. : )
========================================================================