Search
Duplicate

수학/ Truncated SVD, LU factorization, Gram-Schmidt Orthogonalization, QR decomposition, Cholesky decomposition

Truncated SVD

•
A\bold{A}의 특잇값 분해(SVD)를 A=USV⊤\bold{A} = \bold{USV}^\top라 놓고, A^K=UKSKVK⊤\hat{\bold{A}}_K = \bold{U}_K \bold{S}_K \bold{V}_K^\top라 하자. 여기서 U\bold{U}와 V\bold{V}의 첫 kk개 컬럼을 사용한다. 이것은 ∥A−A^K∥F2\|\bold{A} - \hat{\bold{A}}_K\|_F^2을 최소화한다는 점에서 최적의 rank kk 근사로 표시될 수 있다.
•
만일 K=r=rank(A)K = r = \text{rank}(\bold{A})라면 이 분해로 인해 발생하는 오류가 없다. 그러나 K<rK < r이면 약간의 에러가 발생하는데 이것을 Truncated SVD라고 부른다.
•
만일 특잇값들이 자연 데이터에서 빠르게 죽으면 에러는 작아진다.
◦
rank KK 근사를 사용하여 N×DN \times D 행렬을 표현하는데 필요한 총 파라미터의 숫자는 다음과 같다.
NK+KD+K=K(N+D+1)NK +KD + K = K(N+D+1)
•
이 rank-KK 근사에서 오류는 다음과 같이 주어진다.
◦
여기서 σk\sigma_k는 A\bold{A}의 kk번째 특이값이다.
∥A−A^∥F=∑k=K+1rσk\|\bold{A} - \hat{\bold{A}}\|_F = \sum_{k = K+1}^r \sigma_k

LU factorization

•
어떤 정사각 행렬 A\bold{A}을 하삼각행렬 L\bold{L}과 상삼각행렬 U\bold{U}의 곱으로 분해할 수 있다. 예를 들어 다음과 같다.
[a11a12a13a21a22a23a31a32a33]=[l1100l21l220l31l32l33][u11u12u130u22u2300u33]\left[\begin{matrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix}\right] = \left[\begin{matrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{matrix}\right] \left[\begin{matrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{matrix}\right]
•
L\bold{L}과 U\bold{U}는 가우스-조던 소거법을 하는 과정에서 구할 수 있다.
◦
U\bold{U}를 구하기 위해 수행하는 소거를 lower triangle 행렬로 표현할 수 있는데, U\bold{U}를 얻는 동안 반복적으로 곱해진 모든 lower trinagle matrix를 곱하면 또 lower triangle 행렬이 되기 때문에 이것을 L\bold{L}로 합치면 최종적으로 A=LU\bold{A} = \bold{LU}로 만들수 있는데 이게 바로 LU decomposition이 된다.
•
일반적으로 이 분해를 생성하기 전에 행렬의 요소들을 순열해야 할 필요가 있다. 이것을 위해 a11=0a_{11} = 0일 가정한다.
◦
a11=l11u11a_{11} = l_{11} u_{11} 이기 때문에 l11l_{11}나 u11u_{11} 둘 중 하나는 0이어야 한다는 것을 의미하지만 이는 L\bold{L}이나 U\bold{U}이 특이라는 것을 암시한다.
◦
이것을 피하기 위해 이 알고리즘의 첫 번째 단계는 행을 첫 번째 요소가 0이 아니도록 간단하게 재정렬할 수 있다. 이것을 차후 단계에서도 반복한다. 이 절차를 다음처럼 나타낼 수 있다.
◦
1행의 맨 앞이 0이면 맨 앞이 0이 아닌 다른 행이랑 바꾸면 되는데, 이 교체 연산을 아예 행렬로 만들어서 A\bold{A}와 곱하게 한다. 그 행렬을 permutation matrix라고 한다.
PA=LU\bold{PA} = \bold{LU}
•
여기서 P\bold{P}는 순열 행렬(permutation matrix)이다. 예컨대 만일 행 ii가 행 jj로 순열되면 Pij=1\bold{P}_{ij} = 1인 정사각 이진 행렬이다. 이것을 partial pivoting이라고 한다.
◦
P\bold{P}는 orthogonal 하기 때문에 P−1=P⊤\bold{P}^{-1} = \bold{P}^\top가 성립한다.
•
P\bold{P}를 이용해서 LU\bold{LU} decomposition 하는것을 PLU\bold{PLU} decomposition이라고 한다.
•
LU\bold{LU} decomposition의 결과에 대해 L\bold{L}과 U\bold{U}의 대각 요소가 1이 아닌 경우 그것을 1로 만들어주는 행렬 D\bold{D}를 만들어 줄 수 있는데, 이것을 LDU\bold{LDU} decomposition이라고 한다.
◦
여기서 D\bold{D}는 대각 요소만 존재하는 대각 행렬이고, 놀랍게도 L\bold{L}과 U\bold{U}의 대각 성분을 동시에 1로 만들어준다.

Gram-Schmidt Orthogonalization

•
선형 독립이지만 orthogonal 하지 않은 벡터가 존재할 때, 그것들 orthogonal 하게 만드는 절차를 Gram-Schmit Orthogonalization 라고 한다.
•
아이디어는 벡터 하나를 normalize 한 후에 나머지 벡터들을 차례로 이전 모든 벡터와 직교하게 만드는 것으로 절차는 다음과 같다.
1.
먼저 벡터 하나를 normalize 해서 orthonormal한 벡터를 만들고,
•
q1=w1∥w1∥\bold{q}_{1} = {\bold{w}_{1} \over \|\bold{w}_{1}\|}
2.
normalize된 벡터를 이용해서 다음 벡터에서 처음 벡터와 평행한 성분을 제거해서 처음 벡터와 수직인 벡터를 만들고
•
v2=w2−⟨w2,q1⟩q1\bold{v}_{2} = \bold{w}_{2} - \langle \bold{w}_{2}, \bold{q}_{1} \rangle \bold{q}_{1}
◦
⟨w2,q1⟩\langle \bold{w}_{2}, \bold{q}_{1} \rangle 을 내적하면 w2\bold{w}_{2}를 q1\bold{q}_{1}에 투영하는 벡터의 크기(스칼라)가 나온다.
◦
그렇게 구한 크기에 다시 q1\bold{q}_{1}을 곱하면 q1\bold{q}_{1}에 대해 방금 구한 크기만큼 scale한 벡터가 만들어지고, 이게 바로 w2\bold{w}_{2}를 q1\bold{q}_{1}에 투영한 벡터가 된다.
◦
w2\bold{w}_{2}를 q1\bold{q}_{1}에 투영한 벡터를 다시 w2\bold{w}_{2}에서 빼주면 결국 w2\bold{w}_{2}에서 q1\bold{q}_{1}와 수직인 성분만 남는다. 이것을 화살표로 그려보면 이해가 쉽다.
3.
2에서 만든 벡터를 normalize해서 다음 orthonormal 벡터를 만들고
•
q2=v2∥v2∥\bold{q}_{2} = {\bold{v}_{2} \over \|\bold{v}_{2}\|}
4.
그 다음 벡터를 선택해서 이전의 모든 orthogonal 벡터에 대해 투영하고 원래 벡터에서 빼는 2-3의 과정을 반복한다. 모든 벡터가 orthonormal 벡터가 될 때까지.

Gram-Schmidt Orthogonalization 예시

•
만일 선형 독립이지만 직교하지는 않은 3개의 벡터 {w1,w2,w3}\{ \bold{w}_1, \bold{w}_2, \bold{w}_3 \}에 대해 Gram-Schmidit Orthogonalization 을 수행하면 각각의 벡터는 다음과 같이 변환된다.
1.
일단 가장 앞의 w1\bold{w}_1는 정규화만 해서 직교 정규 벡터 q1\bold{q}_1로 만든다.
•
q1=w1∥w1∥\bold{q}_{1} = {\bold{w}_{1} \over \|\bold{w}_{1}\|}
2.
다음으로 2번째 벡터 w2\bold{w}_2는 먼저 만들어진 q1\bold{q}_1과 직교해야 하므로 q1\bold{q}_1에 투영하고 w2\bold{w}_2에서 빼서 v2\bold{v}_2를 만든다.
•
v2=w2−⟨w2,q1⟩q1\bold{v}_{2} = \bold{w}_{2} - \langle \bold{w}_{2}, \bold{q}_{1} \rangle \bold{q}_{1}
3.
2번에서 만든 벡터 v2\bold{v}_2를 normalize 해서 직교 정규 벡터 q2\bold{q}_2를 만든다.
•
q2=v2∥v2∥\bold{q}_{2} = {\bold{v}_{2} \over \|\bold{v}_{2}\|}
4.
3번째 벡터 w3\bold{w}_3는 먼저 만들어진 q1,q2\bold{q}_1, \bold{q}_2와 모두 직교해야 하므로 q1,q2\bold{q}_1, \bold{q}_2에 각각 투영하고 w3\bold{w}_3에서 뺴서 v3\bold{v}_3를 만든다.
•
v3=w3−⟨w3,q1⟩q1−⟨w3,q2⟩q2\bold{v}_{3} = \bold{w}_{3} - \langle \bold{w}_{3}, \bold{q}_{1} \rangle \bold{q}_{1} - \langle \bold{w}_{3}, \bold{q}_{2} \rangle \bold{q}_{2}
5.
4번에서 만든 벡터 v3\bold{v}_3를 normalize 해서 직교 정규 벡터 q3\bold{q}_3를 만든다.
•
q3=v3∥v3∥\bold{q}_{3} = {\bold{v}_{3} \over \|\bold{v}_{3}\|}
6.
이렇게 만들어진 {q1,q2,q3}\{ \bold{q}_1, \bold{q}_2, \bold{q}_3 \}는 모두 서로에 대해 직교하는 정규 벡터이다.

QR decomposition

•
선형 독립 기저 벡터들의 집합으로 표현되는 (따라서 m≥nm \geq n) A∈Rm×n\bold{A} \in \mathbb{R}^{m \times n}을 가정하자. 그리고 span(a1),span(a1,a2)\text{span}(\bold{a}_1), \text{span}(\bold{a}_1, \bold{a}_2) 등의 연속적인 부분공간에 걸쳐 있는 일련의 직교정규 벡터 q1,q2,...\bold{q}_1, \bold{q}_2,...를 찾기 원한다고 하자. 다음과 같은 벡터 qj\bold{q}_j와 계수 rijr_{ij}를 찾기를 윈한다고 하자.
(∣∣∣a1a2...an∣∣∣)=(∣∣∣q1q2...qn∣∣∣)(r11r12...r1nr22...r2n⋱rnn)\left( \begin{matrix} \vert & \vert & & \vert \\ \bold{a}_1 & \bold{a}_2 & ... & \bold{a}_n \\ \vert & \vert & & \vert \end{matrix} \right) = \left( \begin{matrix} \vert & \vert & & \vert \\ \bold{q}_1 & \bold{q}_2 & ... & \bold{q}_n \\ \vert & \vert & & \vert \end{matrix} \right) \left( \begin{matrix} r_{11} & r_{12} & ... & r_{1n} \\ & r_{22} & ... & r_{2n} \\ & & \ddots \\ & & & r_{nn} \end{matrix} \right)
•
이것을 다음처럼 쓸 수 있다.
a1=r11q1a2=r12q1+r22q2⋮an=r1nq1+...+rnnqn\begin{aligned} \bold{a}_1 &= r_{11} \bold{q}_{1} \\ \bold{a}_2 &= r_{12} \bold{q}_{1} + r_{22} \bold{q}_2 \\ \vdots \\ \bold{a}_n &= r_{1n} \bold{q}_{1} + ... + r_{nn} \bold{q}_n \end{aligned}
•
이것은 Gram-Schmidt Orthogonalization과 같은 형식이다.
◦
모든 ai\bold{a}_i를 직교정규하도록 qi\bold{q}_i로 변환 시키면, —우선 a1\bold{a}_1를 q1\bold{q}_1로 잡고, 그 이후 a2\bold{a}_2는 q1\bold{q}_1과 직교하도록 q2\bold{q}_2로 변환하는 절차— 각 ai\bold{a}_i는 자신보다 인덱스가 작은 qi\bold{q}_i까지의 선형 결합으로 표현할 수 있다.
◦
그렇게 표현된 qi\bold{q}_i와 선형 결합 계수 rijr_{ij}을 각각 행렬 표현하면 위와 같이 표현할 수 있음. 앞의 벡터는 더 적은 수의 선형 결합만으로 표현 가능하지만, 뒤로 갈 수록 앞의 벡터와 직교해야 하기 때문에 더 많은 선형 결합이 필요하기 때문에 상삼각행렬로 표현이 됨.
•
따라서 q1\bold{q}_1이 a1\bold{a}_1의 공간을 span 하고 q1\bold{q}_1과 q2\bold{q}_2가 {a1,a2}\{\bold{a}_1, \bold{a}_2 \}의 공간을 span 하고 등을 볼 수 있다.행렬 표기로 다음과 같다.
A=Q^R^\bold{A} = \bold{\hat{Q}\hat{R}}
•
여기서 Q^\bold{\hat{Q}}는 m×nm \times n 직교 정규 열이고 R^\bold{\hat{R}}는 n×nn \times n 상삼각이다. 이것은 축소된 QR 또는 A\bold{A}의 경제적 크기의 QR 인수분해(factorization)이라고 한다.
•
전체 QR 인수분해는 추가적인 m−nm-n 직교정규 열을 Q^\bold{\hat{Q}}에 추가한다. 따라서 이것은 QQ⊤=Q⊤Q=I\bold{QQ}^\top = \bold{Q}^\top\bold{Q} = \bold{I}를 만족하는 직교정규 행렬 Q\bold{Q}로 정사각이 된다.
◦
또한 0으로 만들어진 행을 R^\bold{\hat{R}}에 추가하여 이것은 R\bold{R}이라고 불리는 m×nm \times n 상삼각행렬이 된다. R\bold{R}의 0으로 만들어진 요소들은 Q\bold{Q}의 새로운 열을 없애므로 결과는 Q^R^\bold{\hat{Q}\hat{R}}와 같다.
•
QR 분해는 일반적으로 선형 방정식의 시스템을 해결할 때 사용된다.

Cholesky decomposition

•
어떤 대칭인 양의 정부호(symmetric positive definite) 행렬은 A=R∗R\bold{A} = \bold{R}^*\bold{R}로 분해될 수 있다(실수라면 A=R⊤R\bold{A} = \bold{R}^\top\bold{R} ). 여기서 R\bold{R}은 상삼각이고 대각에는 양의 실수인 대각 성분을 갖고 있다. 이것을 Cholesky 인수분해(factorization) 또는 행렬 제곱근(matrix square root)이라고 한다.
◦
A=LL∗\bold{A} = \bold{L}\bold{L}^*로도 쓰일 수 있는데(실수라면 A=LL⊤\bold{A} = \bold{L}\bold{L}^\top), 여기서 L=R⊤\bold{L} = \bold{R}^\top은 하삼각이고 마찬가지로 대각성분은 양의 실수가 된다.
•
양의 정부호인 대칭 행렬 A\bold{A}이 아래와 같은 형태로 분해 될 수 있다는 이야기
A=[a11a12a13a12a22a23a13a23a33]=R∗R=[rˉ1100rˉ12rˉ220rˉ13rˉ23rˉ33][r11r12r130r22r2300r33]=LL∗=[l1100l21l220l31l32l33][lˉ11lˉ21lˉ310lˉ22lˉ3200lˉ33]\begin{aligned} \bold{A} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{bmatrix} &= \bold{R}^* \bold{R} = \begin{bmatrix} \bar{r}_{11} & 0 & 0 \\ \bar{r}_{12} & \bar{r}_{22} & 0 \\ \bar{r}_{13} & \bar{r}_{23} & \bar{r}_{33} \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & r_{13} \\ 0 & r_{22} & r_{23} \\ 0 & 0 & r_{33} \end{bmatrix} \\ &= \bold{LL}^* = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix} \begin{bmatrix} \bar{l}_{11} & \bar{l}_{21} & \bar{l}_{31} \\ 0 & \bar{l}_{22} & \bar{l}_{32} \\ 0 & 0 & \bar{l}_{33} \end{bmatrix} \end{aligned}
•
만일 A\bold{A}가 음의 정부호라면 음수를 붙이면 양의 정부호가 되므로 −A=R∗R=LL∗-\bold{A} = \bold{R}^* \bold{R} = \bold{LL}^*로 놓고 풀 수 있다.
•
LU\bold{LU} composition에서 L\bold{L}과 U\bold{U}의 대각 행렬을 모두 1로 만들어주는 대각 행렬 D\bold{D}를 추가해서 LDU\bold{LDU}로 분해할 수 있었는데, Cholesky도 마찬가지로 R∗DR\bold{R}^*\bold{DR}, LDL∗\bold{LDL}^*로 분해 가능하다.
•
공분산 행렬(covariance matrix)는 항상 대칭인 양의 정부호 행렬이므로 Cholesky decomposition이 가능하다)

참조

Made with