선형대수학 (Linear Algebra) 개념 정리 Part 2

본 포스트에서는 주로 행렬대수학과 관련된 내용을 다룬다.

선형대수학 (Linear Algebra) 개념 정리 Part 1은 일반적인 선형대수학의 내용을 다룬다.
확률 이론에 대한 내용을 알고싶으면 확률 이론(Probability Theory) 개념 정리 포스트를 참조하면 된다.

 

Chapter 6 - Matrix algebra

Identity matrix

항등행렬(Identity Matrix)는 대각성분이 전부 1이고 나머지 성분이 전부 0인 $n\times n$ 크기의 정방행렬을 의미한다. 일반적으로 $\mathbf{I} \in \mathbb{R}^{n\times n}$ 으로 표현한다.
\begin{equation}
\begin{aligned}
\mathbf{I} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \in \mathbb{R}^{3\times 3}
\end{aligned}
\end{equation}
항등행렬에 임의의 벡터 $\mathbf{x} \in \mathbb{R}^{n}$울 곱하면 자기 자신이 도출된다.
\begin{equation}
\begin{aligned}
^{\forall} \mathbf{x} \in \mathbb{R}^{n}, \quad \mathbf{I}\mathbf{x} = \mathbf{x}
\end{aligned}
\end{equation}

 

 

Transpose of matrix

임의의 $m\times n$ 크기의 행렬 $\mathbf{A}$가 주어졌을 때 $\mathbf{A}$의 전치행렬(transpose matrix)는 $\mathbf{A}^{\intercal}$와 같이 나타내고 이는 행과 열의 성분을 서로 바꾼 행렬을 의미한다. 
\begin{equation}
\begin{aligned}
\big[ \mathbf{A} \big]_{ij} = a_{ij}
\end{aligned}
\end{equation}

위와 같은 행렬에 대하여 $\mathbf{A}^{\intercal}$는 다음과 같다.
\begin{equation}
\begin{aligned}
\big[ \mathbf{A}^{\intercal} \big]_{ij} = a_{ji}
\end{aligned}
\end{equation}

즉, $\mathbf{A} = \begin{bmatrix} a & b & c \\ d & e & f \end{bmatrix}$인 행렬에 대한 전치행렬은 $\mathbf{A}^{\intercal} = \begin{bmatrix}
a & d \\ b & e \\ c & f
\end{bmatrix}$가 된다.

Determinant of matrix

행렬식(determinant)는 임의의 정방행렬 $\mathbf{A}\in\mathbb{R}^{n\times n}$을 하나의 스칼라 값에 대응시키는 함수를 의미한다.  스칼라 값의 크기 및 부호에 따라 해가 존재하는지 유무가 결정되며 행렬식이 $0$인 경우 해당 정방행렬은 역행렬이 존재하지 않는다. 행렬식은 일반적으로 $\text{det}(\mathbf{A})$라고 표기하며 다음과 같다.
\begin{equation}
\begin{aligned}
\text{det}(\mathbf{A}) = \sum_{j=1}^{n}a_{ij}C_{ij}
\end{aligned}
\end{equation}
- $C_{ij} = (-1)^{i+j} M_{ij}$

$M_{ij}$는 $\mathbf{A}$에서 $i$ 행과 $j$ 열을 제거한 부분 행렬(submatrix)에 대한 행렬식(determinant)을 의미하며 $a_{ij}$에 대한 minor라고도 부른다. 그리고 $C_{ij}$는 cofactor라고도 부른다.  자세한 내용은 [4]를 참고하면 된다.

$2 \times 2$ 크기의 정방행렬 $\mathbf{A} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$가 있을 때 $\text{det}(\mathbf{A})$는 다음과 같다. 
\begin{equation}
\begin{aligned}
\text{det}(\mathbf{A})= \frac{1}{ad-bc}
\end{aligned}
\end{equation}

임의의 정방행렬 $\mathbf{A,B} \in \mathbb{R}^{n \times n}$에 대하여 행렬식은 다음과 같은 성질을 지닌다.

\begin{equation}
 \begin{aligned}
& \text{det}(\mathbf{A}^{\intercal}) = \text{det}(\mathbf{A}) \\
& \text{det}(c\mathbf{A}) = c^n \text{det}(\mathbf{A}) \\
& \text{det}(\mathbf{AB}) = \text{det}(\mathbf{A})\text{det}(\mathbf{B})\\
& \text{det}(\mathbf{A}^{-1}) = \frac{1}{\text{det}(\mathbf{A})} \\
\end{aligned} 
\end{equation}

 

Determinant of block triangle matrix

임의의 블록 행렬 $\mathbf{A}$가 상삼각(upper-triangle), 하삼각(lower-triangle) 또는 대각(diagonal)일 경우 행렬식은 다음과 같이 나타낼 수 있다.
\begin{equation} 
\begin{aligned}
\mathbf{A} = \begin{bmatrix}
\mathbf{A}_{11} & \mathbf{A}_{12} \\ 0 & \mathbf{A}_{22} 
\end{bmatrix}
\end{aligned}
\end{equation}
\begin{equation} 
\boxed{ \begin{aligned}
\text{det}(\mathbf{A}) = \text{det}(\mathbf{A}_{11}) \text{det}(\mathbf{A}_{22})
\end{aligned} }
\end{equation}

일반적인 정사각 행렬 ${ \mathbf{C}}$이 주어졌을 때 이는 다음과 같이 블록 삼각 행렬의 곱으로 LU 분해할 수 있다.
\begin{equation} 
\begin{aligned}
{ \begin{bmatrix} \mathbf{C}_{xx} & \mathbf{C}_{xy} \\ \mathbf{C}_{yx} & \mathbf{C}_{yy} \end{bmatrix} } =  \begin{bmatrix} \mathbf{I} & 0  \\ \mathbf{C}_{yx}\mathbf{C}_{xx}^{-1} & \mathbf{I} \end{bmatrix}  \begin{bmatrix}
\mathbf{C}_{xx} & \mathbf{C}_{xy} \\ 0 & \mathbf{C}_{yy} - \mathbf{C}_{yx}\mathbf{C}_{xx}^{-1}\mathbf{C}_{xy}
\end{bmatrix}
\end{aligned}
\end{equation}

따라서 ${ \mathbf{C}}$의 행렬식 $\text{det}({ \mathbf{C}})$은 다음과 같이 나타낼 수 있다.
\begin{equation} 
\boxed{ \begin{aligned}
\text{det}({ \mathbf{C}}) & = \text{det}(\mathbf{I})\text{det}(\mathbf{I})\text{det}(\mathbf{C}_{xx})\text{det}(\mathbf{C}_{yy} - \mathbf{C}_{yx}\mathbf{C}_{xx}^{-1}\mathbf{C}_{xy}) \\
& = \text{det}(\mathbf{C}_{xx})\text{det}(\mathbf{C}_{yy} - \mathbf{C}_{yx}\mathbf{C}_{xx}^{-1}\mathbf{C}_{xy}) 
\end{aligned} }
\end{equation}

 

Inverse matrix

정방행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$에 대한 역행렬(Inverse Matrix) $\mathbf{A}^{-1}$는 다음과 같이 정의된다.
\begin{equation}
\begin{aligned}
\mathbf{A}^{-1}\mathbf{A} = \mathbf{A}\mathbf{A}^{-1} = \mathbf{I}
\end{aligned}
\end{equation}
$2\times 2$ 크기의 정방행렬 $\mathbf{A} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$가 있을 때, 역행렬은 다음과 같이 정의된다.
\begin{equation}
\begin{aligned}
\mathbf{A}^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}
\end{aligned}
\end{equation}
$3\times 3$ 크기 이상의 정방행렬도 역행렬을 구할 수 있다. 역행렬은 정방행렬이면서 Full Rank인 행렬(= non-singular, $\det{\mathbf{A}} \neq 0$)에만 존재하며 역행렬이 존재하지 않는 행렬 $\mathbf{A}$는 singular하다고 한다.

 

역행렬은 다음과 같이 해석적(analytically)으로 표현할 수도 있다. 임의의 정방행렬 $\mathbf{A} \in \mathbb{R}^{n\times n}$의 역행렬은 다음과 같다.
\begin{equation}
\begin{aligned}
\mathbf{A}^{-1} = \frac{\mathbf{C}^{\intercal}}{\text{det}(\mathbf{A})}
\end{aligned}
\end{equation}
- $\mathbf{C} \in \mathbb{R}^{n\times n}$ : cofactor 행렬
- $[\mathbf{C}]_{ij} = (-1)^{i+j}M_{ij}$ 
- $M_{ij}$: $a_{ij}$의 minor라고 불리며 $\mathbf{A}$ 행렬에서 $i$행과 $j$열을 제거한 부분 행렬

 

Trace of matrix

Trace란 임의의 행렬 $\mathbf{A}$가 주어졌을 때 행렬의 trace는 행렬의 대각 성분의 합을 의미하며 $\text{tr}(\mathbf{A})$와 같이 표기한다.
\begin{equation}
\begin{aligned}
\text{tr} (\mathbf{A}) = \sum_{i} [\mathbf{A}]_{ii}
\end{aligned}  
\end{equation}
- $[\mathbf{A}]_{ij}$ : 행렬 $\mathbf{A}$의 $i$행 $j$열의 원소


Trace는 다음과 같은 성질을 지닌다.
\begin{equation}
\begin{aligned}
& \text{tr} (\mathbf{A}) = \text{tr} (\mathbf{A}^{\intercal}) \\
& \text{tr} (\mathbf{AB}) = \text{tr} (\mathbf{BA}) \\
& \text{tr} (\mathbf{A} + \mathbf{B}) = \text{tr} (\mathbf{A}) + \text{tr} (\mathbf{B}) \\
& \text{tr} (\mathbf{ABC}) = \text{tr} (\mathbf{BCA}) = \text{tr} (\mathbf{CAB}) \\
& \text{tr} (\mathbf{A}^{\intercal}\mathbf{B}) = \sum_{i=1}^{n}\sum_{j=1}^{n} [\mathbf{A}]_{ij}[\mathbf{B}]_{ij} \\
& \mathbf{a}^{\intercal}\mathbf{b} = \text{tr}(\mathbf{ba}^{\intercal})
\end{aligned}  
\end{equation}
- $\mathbf{a}$ : 임의의 벡터

Diagonal matrix

$\mathbf{A} \in \mathbb{R}^{n \times n}$ 크기의 대각 행렬(Diagonal Matrix)는 대각 성분을 제외한 나머지 성분이 $0$인 행렬을 의미한다($a_{ij} = 0$ for $i\neq j$).
\begin{equation}
\begin{aligned}
\mathbf{A} = \begin{bmatrix}
a_{11}&0&\cdots&0\\
0&a_{22}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&a_{nn}
\end{bmatrix}
\end{aligned}
\end{equation}

대각 행렬의 역함수는 단순히 각 원소의 역수가 되기 때문에 매우 간단한게 역행렬을 구할 수 있다는 특징이 있다. 
\begin{equation}
\begin{aligned}
\mathbf{A}^{-1} = \begin{bmatrix}
a_{11}^{-1}&0&\cdots&0\\
0&a_{22}^{-1}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&a_{nn}^{-1}
\end{bmatrix}
\end{aligned}
\end{equation}

각각의 원소가 block matrix인 경우에도 동일하게 적용된다.
\begin{equation}
\begin{aligned}
\mathbf{A}^{-1} = \begin{bmatrix}
\mathbf{A}_{11}^{-1}&0&\cdots&0\\
0&\mathbf{A}_{22}^{-1}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\mathbf{A}_{nn}^{-1}
\end{bmatrix}
\end{aligned}
\end{equation}
- $A_{ii}$: 대각 행렬을 만족하는 부분 행렬

이 때, 대각 행렬의 행렬식은 다음과 같다. 
\begin{equation}
\begin{aligned}
\text{det}(\mathbf{A}) = \Pi_{i=1}^{n} \text{det}(\mathbf{A}_{ii})
\end{aligned}
\end{equation}

Idempotent matrix

멱동 행렬(Idempotent Matrix)는 $n \times n$ 크기의 정방행렬이면서 다음을 만족하는 행렬을 의미한다.
\begin{equation}
\begin{aligned}
\mathbf{A}^2 = \mathbf{A}
\end{aligned}
\end{equation}

이는 $l \ge 1$에 대하여 $\mathbf{A}^{l} = \mathbf{A}$임을 의미한다. 최소제곱법에서 유도되는 프로젝션 행렬이 멱동 행렬에 해당한다.
\begin{equation}
\begin{aligned}
\mathbf{A} = \mathbf{H}(\mathbf{H}^{\intercal}\mathbf{H})^{-1}\mathbf{H}^{\intercal}
\end{aligned}
\end{equation}

 

Skew-symmetric matrix

3차원 벡터 $\mathbf{v} = [v_x, v_y, v_z]^{\intercal} \in \mathbb{R}^{3}$가 주어졌을 때 이에 대한 반대칭 행렬(skew-symmetric matrix)은 다음과 같이 정의한다.
\begin{equation}
\begin{aligned}
 \big[ \mathbf{v} \big]_{\times} = \begin{bmatrix} 0&-v_z&v_y \\ v_z & 0 & -v_x \\ -v_y & v_x & 0 \end{bmatrix}
\end{aligned}
\end{equation}

반대칭 행렬은 벡터와 곱해졌을 때 외적(outer product)를 수행한 것과 동일한 효과를 지닌다. 예를 들어, 반대칭 행렬 $[\mathbf{v}]_{\times}$와 벡터 $\mathbf{w} \in \mathbb{R}^{3}$가 주어진 경우 둘의 곱은 다음과 같다.
\begin{equation}
\begin{aligned}
\big[ \mathbf{v} \big]_{\times} \mathbf{w} & = \begin{bmatrix} 0&-v_z&v_y \\ v_z & 0 & -v_x \\ -v_y & v_x & 0 \end{bmatrix} \begin{bmatrix} w_x \\w_y \\ w_z \end{bmatrix} \\
& = \begin{bmatrix}
-v_z  w_y + v_y w_z \\ v_z w_x -v_x w_z \\ -v_y w_x + v_x w_y  \end{bmatrix} \\
& = \mathbf{v} \times \mathbf{w}
\end{aligned}
\end{equation}


반대칭 행렬은 다음과 같은 성질이 존재한다.
\begin{equation}
   \begin{aligned}
&[\mathbf{v}]_{\times}^{\intercal} = -[\mathbf{v}]_{\times} \\ 
& [\mathbf{v}]_{\times}^{2} = \mathbf{v}\mathbf{v}^{\intercal} - \mathbf{v}^{\intercal}\mathbf{v}\mathbf{I} \\
& [\mathbf{R}\mathbf{v}]_{\times} = \mathbf{R} [\mathbf{v}]_{\times} \mathbf{R}^{\intercal}
\end{aligned}  
\end{equation}
- $\mathbf{R} \in SO(3)$ : 임의의 회전 행렬

만약 $\left\| \mathbf{u} \right\|=1$을 만족하는 단위 벡터 $\mathbf{u}$가 주어진 경우 아래 공식이 성립한다.
\begin{equation}
   \begin{aligned}
&[\mathbf{u}]_{\times}^{3} = [\mathbf{u}]_{\times}^{\intercal} = -[\mathbf{u}]_{\times} \\ 
& [\mathbf{u}]_{\times}^{2} = \mathbf{u}\mathbf{u}^{\intercal} - \mathbf{I} \\
\end{aligned}  
\end{equation}

임의의 두 벡터 $\mathbf{a}, \mathbf{b} \in \mathbb{R}^{3}$가 주어졌을 때 다음 법칙이 성립한다.
\begin{equation}
   \begin{aligned}
& [\mathbf{a}]_{\times} \mathbf{b} = -[\mathbf{b}]_{\times} \mathbf{a}
\end{aligned}  
\end{equation}

임의의 세 벡터에 대하여 $\mathbf{a} = \mathbf{b} \times \mathbf{c}$ 관계가 주어진 경우 외적의 성질에 의해 다음 공식이 성립한다.
\begin{equation}
   \begin{aligned}
& [\mathbf{a}]_{\times} = \mathbf{cb}^{\intercal} - \mathbf{bc}^{\intercal}
\end{aligned}  
\end{equation}

 

 

Positive definite matrix

정방행렬 $\mathbf{A}\in\mathbb{R}^{n\times n}$이 있을 때 0이 아닌 모든 벡터 $\forall \mathbf{x} \neq 0$에 대하여 
\begin{equation}
\begin{aligned}
\mathbf{x}^{\intercal}\mathbf{A}\mathbf{x} > 0
\end{aligned}
\end{equation}

을 만족하는 경우 $\mathbf{A}$를 양의 정부호 행렬(positive definite matrix)이라고 한다. 만약 
\begin{equation}
\begin{aligned}
\mathbf{x}^{\intercal}\mathbf{A}\mathbf{x} \ge 0
\end{aligned}
\end{equation}

인 경우 양의 준정부호 행렬(positive semi-definite matrix)이라고 한다.

 

• $\mathbf{A} \in \mathbb{R}^{n \times n}$가 postivie definite인 경우 다음과 같은 필요충분조건을 만족한다.
  
  • full rank 행렬 $\mathbf{C} \in \mathbb{R}^{n\times n}$에 대하여
    \begin{equation}
    \begin{aligned}
    \mathbf{A}= \mathbf{CC}^{\intercal}
    \end{aligned}
    \end{equation}
  • $\mathbf{A}$의 고유값은 항상 모두 양수이다.
  • $\mathbf{A}$의 leading principal minors 값들이 항상 양수이다. Leading principal minor에 대한 설명은 다음과 같다.
  •  
  •  

    

   
• 만약 $\mathbf{C}$가 full rank가 아니면서 leading principal minors만 $0$보다 크거나 같은 값을 가지면 $\mathbf{A}$는 postivie semi-definite 행렬이 된다.
• $\mathbf{A}$가 positive definite 행렬이면 $\mathbf{A}$의 역행렬은 $\mathbf{A}^{-1}=(\mathbf{C}^{-1})^{\intercal}(\mathbf{C}^{-1})$과 같이 구할 수 있다. 또한 임의의 $m \times n$($m\leq n$) 크기의 행렬 $\mathbf{B}$이 full rank인 경우 $\mathbf{BAB}^{\intercal}$ 또한 positive definite 행렬이 된다.

 

Toeplitz matrix

퇴플리츠(Toepliz) 행렬은 독일의 수학자 오토 퇴플리츠(Otto Toeplitz)가 도입한 행렬로 $n\times n$ 크기의 정방 퇴플리츠행렬은 대각선의 성분들이 동일한 행렬을 의미하며 다음과 같이 정의한다.
\begin{equation}
\begin{aligned}
\big[ \mathbf{A} \big]_{ij} = a_{i-j}
\end{aligned}
\end{equation}
\begin{equation}
\begin{aligned}
\mathbf{A} = \begin{bmatrix}
a_0 & a_{-1} & a_{-2} & \cdots & a_{-(n-2)}  & a_{-(n-1)} \\
a_1 & a_{0} & a_{-1} & \cdots &a_{-(n-3)}  & a_{-(n-2)} \\
    a_2 & a_1 & a_0 & \cdots & a_{-(n-4)} & a_{-(n-3)} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & a_{n-3} & a_{n-4} & \cdots & a_{0}& a_{-1} \\
a_{n-1} & a_{n-2} & a_{n-3} & \cdots & a_{1} & a_{0} \\
\end{bmatrix}
\end{aligned}
\end{equation}

두 개의 $n \times n$ 퇴플리츠 행렬 $\mathbf{A}, \mathbf{A}'$에 대하여 연산의 시간복잡도는 다음과 같다.
\begin{equation}
\begin{aligned}
& \text{Add } : O(n) \\
& \text{Multiplication } : O(n^2) \\
& \text{Solution of } \mathbf{A}\mathbf{x}=\mathbf{b} : O(n^2) \\
& \text{Determinant } \text{det}(\mathbf{A}): O(n^2) \\
  \end{aligned}
\end{equation}

연립 일차방정식 $\mathbf{A}\mathbf{x}=\mathbf{b}$과 행렬식 $\text{det}(\mathbf{A})$은 레빈슨 재귀(Levinson recursion) 알고리즘을 사용하여 풀었을 때 시간복잡도를 의미한다.

 

 

 

Chapter 7 - Matrix decompositions

LU decomposition

LU 분해는 $\mathbf{Ax} = \mathbf{b}$ 의 시스템에서 행렬 $\mathbf{A}$를 하삼각(lower-triangle) 행렬 $\mathbf{L}$ 과 상삼각(upper-triangle) 행렬 $\mathbf{U}$의 곱으로 분해하는 방법이다.
\begin{equation}
  \begin{aligned}
    \mathbf{A} = \mathbf{LU} = \mathbf{b}
  \end{aligned}
\end{equation}

LU 분해를 사용하면 다음과 같이 방정식이 변형된다.
\begin{equation}
  \begin{aligned}
    \mathbf{Ax} = (\mathbf{LU})\mathbf{x}
  \end{aligned}
\end{equation}

이를 사용하여 $[1] \ \mathbf{Ly} = \mathbf{b}$ 방정식을 먼저 푼 후, $[2] \ \mathbf{Ux} = \mathbf{y}$ 를 순차적으로 계산할 수 있다. tridiagonal, band-diagonal 시스템에 효과적으로 사용할 수 있다.
\begin{equation}
  \begin{aligned}
    & \mathbf{L}(\mathbf{Ux}) = \mathbf{b} \\ 
    &\mathbf{Ly} = \mathbf{b} \quad \cdots [1] \\
     & \mathbf{Ux} = \mathbf{y} \quad \cdots [2]
  \end{aligned}
\end{equation}

위와 같이 행렬 $\mathbf{A}$를 $\mathbf{L}, \mathbf{U}$로 분해하면 $\mathbf{x}$를 두 스텝에 걸쳐 구해야하지만 삼각행렬의 특성 상 $\mathbf{x}$를 구하는 것이 훨씬 더 간단해진다.

PLU decomposition

만약 $\mathbf{A}$가 아래와 같은 3x3 행렬이라고 가정해보자.
\begin{equation}
  \begin{aligned}
     \mathbf{A} & = \begin{bmatrix}
         \mathbf{a}_{1}^{\intercal} \\ \mathbf{a}_{2}^{\intercal} \\ \mathbf{a}_{3}^{\intercal}
     \end{bmatrix} 
      = \begin{bmatrix}
        0 & * & * \\ *&*&* \\ *&*&*
    \end{bmatrix}
  \end{aligned}
\end{equation}

LU 분해는 가우스 조던 소거법으로 $\mathbf{L}$을 구하기 때문에 만약 $\mathbf{A}$의 첫 번째 원소가 0으로 시작하는 경우 정상적으로 분해할 수 없다. 따라서 첫번째 행과 두번째 행의 순서를 변환하는 permutation 행렬 $\mathbf{P}$를 앞에 곱해줘야 LU 분해를 수행할 수 있다.
\begin{equation}
  \begin{aligned}
     \mathbf{PA} = \begin{bmatrix} &1& \\ 1&&\\&&1 \end{bmatrix} \mathbf{A} & = \begin{bmatrix}
         \mathbf{a}_{2}^{\intercal} \\ \mathbf{a}_{1}^{\intercal} \\ \mathbf{a}_{3}^{\intercal}
     \end{bmatrix} = \begin{bmatrix}
         *&*&* \\ 0 & * & * \\  *&*&*
    \end{bmatrix}
  \end{aligned}
\end{equation}

permutation 행렬은 직교행렬이고 직교행렬의 특성 상 $\mathbf{P} = \mathbf{P}^{\intercal} = \mathbf{P}^{-1}$이므로 이를 넘긴 후 전개하면 다음과 같다.
\begin{equation}
  \begin{aligned}
     \mathbf{A} = \mathbf{PLU}
  \end{aligned}
\end{equation}

이와 같이 행벡터의 순서를 변경하는 $\mathbf{P}$를 곱한 후 LU 분해를 수행하는 방법을 PLU 분해라고 한다.

LDU decomposition

LU 분해에서 $\mathbf{L}, \mathbf{D}$ 행렬의 대각 성분을 1로 만들기 위해 중앙에 대각행렬 $\mathbf{D}$를 별도로 분해하는 방법을 LDU 분해라고 한다. 따라서 모든 LU 행렬은 LDU 행렬로 분해할 수 있다.
\begin{equation}
  \begin{aligned}
     \mathbf{A} = \mathbf{LU} = \mathbf{L}'\mathbf{D}\mathbf{U}'
  \end{aligned}
\end{equation}

Cholesky decomposition

Cholesky 분해는 $\mathbf{Ax} = \mathbf{b}$ 시스템에서 $\mathbf{A}$가 대칭행렬이면서 동시에 postive(-semi) definite인 경우에 이를 하삼각(lower-triangle) 행렬 $\mathbf{L}$의 곱으로 분해하는 방법을 말한다.
\begin{equation}
  \begin{aligned}
    \mathbf{A} = \mathbf{LL}^{\intercal} 
  \end{aligned}
\end{equation}

Cholesky 분해는 수치적으로 안정하다는 특징이 있다.

Detailed explanation

임의의 3x3 대칭행렬 $\mathbf{A}$가 주어졌다고 하자. 이를 cholesky 분해하면 다음과 같다.
\begin{equation}
  \begin{aligned}
    \mathbf{A} = \begin{bmatrix}
        a_{11} & a_{21} & a_{31} \\ 
        a_{21} & a_{22} & a_{32} \\
        a_{31} & a_{32} & a_{33}
    \end{bmatrix} = \mathbf{LL}^{\intercal}
    = \begin{bmatrix}
        l_{11} && \\ l_{21}&l_{22}& \\ l_{31}&l_{32}&l_{33} 
    \end{bmatrix}
    \begin{bmatrix}
        l_{11}&l_{21}&l_{31} \\  &l_{22}&l_{32} \\ && l_{33}  
    \end{bmatrix}
  \end{aligned}
\end{equation}

$\mathbf{LL}^{\intercal}$을 자세히 전개하면 다음과 같다.
\begin{equation}
  \begin{aligned}
    \begin{bmatrix}
        l_{11} && \\ l_{21}&l_{22}& \\ l_{31}&l_{32}&l_{33} 
    \end{bmatrix}
    \begin{bmatrix}
        l_{11}&l_{21}&l_{31} \\  &l_{22}&l_{32} \\ && l_{33}  
    \end{bmatrix} = \begin{bmatrix}
        l_{11}^{2} & l_{21}l_{11} & l_{31}l_{11} \\ 
        l_{21}l_{11} & l_{21}^{2} + l_{22}^{2} & l_{31}l_{21}+l_{32}l_{22} \\ 
        l_{31}l_{11} & l_{31}l_{21}  + l_{32}l_{22} & l_{31}^{2} + l_{32}^{2} + l_{33}^{3}
    \end{bmatrix}
  \end{aligned}
\end{equation}

이를 통해 일대일로 비교하면 $\mathbf{L}$의 원소는 다음과 같이 구할 수 있다.
\begin{equation}
  \begin{aligned}
    & l_{11} = \sqrt{a_{11}}   \quad \cdots \text{ up to sign} \\
    & l_{21} = a_{21}/l_{11} \\ 
    & l_{31} = a_{31}/l_{11} \\ 
    & l_{21} = \sqrt{a_{22} - l_{21}^{2}} \\ 
    & l_{32} = (a_{32} - l_{31}l_{21}) / l_{22} \\
    & l_{33} = \sqrt{a_{33} - l_{31}^{2}-l_{32}^{2}} 
  \end{aligned}
\end{equation}

이를 임의의 행렬에 대해 일반화하여 표현하면 다음과 같다.
\begin{equation}
  \begin{aligned}
    & l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^{2}}  \\
    & l_{ij} = \frac{1}{l_{jj}} \Big( a_{ij} - \sum_{k=1}^{j-1}l_{ik}l_{jk} \Big)
  \end{aligned}
\end{equation}

LDLT decomposition

Cholesky 분해에서 $\mathbf{L}$ 행렬의 대각 성분을 1로 만들기 위해 중앙에 대각행렬 $\mathbf{D}$를 별도로 분해하는 방법을 LDLT 분해라고 한다. 따라서 모든 cholesky 행렬은 LDLT 행렬로 분해할 수 있다.
\begin{equation}
  \begin{aligned}
    \mathbf{A} = \mathbf{LL}^{\intercal} = \mathbf{L}'\mathbf{D}\mathbf{L}^{'\intercal}
  \end{aligned}
\end{equation}

QR decomposition

QR 분해는 $\mathbf{Ax} = \mathbf{b}$ 시스템에서 행렬 $\mathbf{A}$를 직교(orthogonal) 행렬 $\mathbf{Q}$와  상삼각(upper-triangle) 행렬 $\mathbf{R}$의 곱으로 분해하는 방법을 말한다. 
\begin{equation}
    \begin{aligned}
        \mathbf{A} = \mathbf{QR}
    \end{aligned}
\end{equation}

$\mathbf{Q}$ 가 직교 행렬이므로 $\mathbf{QQ}^{\intercal} = \mathbf{I}$의 성질을 지닌다. 일반적으로 QR 분해는 LU 분해보다 느리지만 최소제곱법(least squares) 문제를 풀 때 효율적이어서 자주 사용된다.

Detailed explanation

임의의 3x3 행렬 $\mathbf{A}$가 주어졌을 때 이를 열벡터로 표현하면 다음과 같다. 자세한 내용은 [6]를 참고하면 된다.
\begin{equation}
    \begin{aligned}
        \mathbf{A} = [ \mathbf{a}_{1}, \mathbf{a}_{2}, \mathbf{a}_{3} ]
    \end{aligned}
\end{equation}

해당 행렬에 gram-schmidt 직교화를 수행하면 임의의 직교행렬 $\mathbf{Q}$를 만들 수 있다.
\begin{equation}
    \begin{aligned}
        \mathbf{Q} = [ \mathbf{q}_{1}, \mathbf{q}_{2}, \mathbf{q}_{3} ]
    \end{aligned}
\end{equation}

이 때, gram-schmidt 직교화의 특성 상 $\mathbf{q}_{1}$은 첫번째 열벡터와 동일한 단위 벡터이고 $\mathbf{q}_{2}$는 $\mathbf{q}_{1}$와 직교한 단위벡터이며 $\mathbf{q}_{3}$는 $\mathbf{q}_{1},\mathbf{q}_{2}$와 직교한 단위벡터이다. 이를 통해 $\mathbf{a}_{i}$를 구할 수 있다.
\begin{equation}
    \begin{aligned}
       & \mathbf{a}_{1} = \mathbf{a}_{1}^{\intercal}\mathbf{q}_{1} \cdot \mathbf{q}_{1} \\
       & \mathbf{a}_{2} = \mathbf{a}_{2}^{\intercal}\mathbf{q}_{1} \cdot \mathbf{q}_{1} + \mathbf{a}_{2}^{\intercal}\mathbf{q}_{2} \cdot \mathbf{q}_{2} \\
       & \mathbf{a}_{3} = \mathbf{a}_{3}^{\intercal}\mathbf{q}_{1} \cdot \mathbf{q}_{1} + \mathbf{a}_{3}^{\intercal}\mathbf{q}_{2} \cdot \mathbf{q}_{2} + \mathbf{a}_{3}^{\intercal}\mathbf{q}_{3} \cdot \mathbf{q}_{3} \\
    \end{aligned}
\end{equation}

이를 행렬 형태로 표현하면 다음과 같은 상삼각 $\mathbf{R}$ 행렬을 얻을 수 있다.
\begin{equation}
    \begin{aligned}
       \begin{bmatrix} \mathbf{a}_{1} &\mathbf{a}_{2} & \mathbf{a}_{3} \end{bmatrix} & = [ \mathbf{q}_{1}, \mathbf{q}_{2}, \mathbf{q}_{3} ] \begin{bmatrix}
           \mathbf{a}_{1}^{\intercal}\mathbf{q}_{1} & \mathbf{a}_{2}^{\intercal}\mathbf{q}_{1} & \mathbf{a}_{3}^{\intercal}\mathbf{q}_{1} \\ & \mathbf{a}_{2}^{\intercal}\mathbf{q}_{2} & \mathbf{a}_{3}^{\intercal}\mathbf{q}_{2} \\ &&\mathbf{a}_{3}^{\intercal}\mathbf{q}_{3} 
       \end{bmatrix} \\
       \mathbf{A} & = \mathbf{QR} \\
    \mathbb{R}^{3\times 3} & = \mathbb{R}^{3\times 3} \mathbb{R}^{3\times 3}
    \end{aligned}
\end{equation}

임의의 직사각 행렬에 대해서도 QR 분해를 수행할 수 있다. 만약 5x3 행렬 $\mathbf{A}$가 주어졌을 때 이는 다음과 같이 QR 분해된다.
\begin{equation}
    \begin{aligned}
       \begin{bmatrix} \mathbf{a}_{1} &\mathbf{a}_{2} & \mathbf{a}_{3} \end{bmatrix} & = [ \mathbf{q}_{1}, \mathbf{q}_{2}, \mathbf{q}_{3}, \mathbf{q}_{4}, \mathbf{q}_{5}] \begin{bmatrix}
           \mathbf{a}_{1}^{\intercal}\mathbf{q}_{1} & \mathbf{a}_{2}^{\intercal}\mathbf{q}_{1} & \mathbf{a}_{3}^{\intercal}\mathbf{q}_{1} \\ & \mathbf{a}_{2}^{\intercal}\mathbf{q}_{2} & \mathbf{a}_{3}^{\intercal}\mathbf{q}_{2} \\ &&\mathbf{a}_{3}^{\intercal}\mathbf{q}_{3} \\ &&& \\ &&&
       \end{bmatrix} \\
       \mathbf{A} & = \mathbf{QR} \\ 
       \mathbb{R}^{5\times 3} & = \mathbb{R}^{5\times 5} \mathbb{R}^{5\times 3}
    \end{aligned}
\end{equation}

$\mathbf{q}_{4}, \mathbf{q}_{5}$ 벡터는 곱셈에 의해 0이 되어서 실제 $\mathbf{A}$ 행렬에는 관여하지 않는다.

QR decomposition on least squares problem

Over-determined 시스템 $\mathbf{Ax} = \mathbf{b}$가 주어졌을 때 이에 대한 최적해는 다음과 같이 최소제곱법을 통해 구할 수 있다.
\begin{equation}
    \begin{aligned}
    & \min_{\mathbf{x}} \left \| \mathbf{Ax} - \mathbf{b} \right \|^{2}_{2} \\
     &  \mathbf{x} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal} \mathbf{b}
    \end{aligned}
\end{equation}

최소제곱법을 QR 분해를 통해 해석해보자. 임의의 직사각 행렬 $\mathbf{A}$를 QR 분해해보면 다음과 같다. 
\begin{equation}
    \begin{aligned}
\mathbf{A} & =  \mathbf{QR}
\\ & = \begin{bmatrix} \mathbf{Q}_{1} & \mathbf{Q}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R}_{1} \\ \mathbf{0} \end{bmatrix}
    \end{aligned}
\end{equation}

 $\left \| \mathbf{Ax} - \mathbf{b} \right \|^{2}_{2}$를 QR 분해해보면 다음과 같다.
\begin{equation}
    \begin{aligned}
    \left \| \mathbf{Ax} - \mathbf{b} \right \|^{2}_{2} & = \left \| \mathbf{QRx} - \mathbf{b} \right \|^{2}_{2} \\ 
    & = \left \| \mathbf{Q}(\mathbf{Rx} - \mathbf{Q}^{\intercal}\mathbf{b}) \right \|^{2}_{2} \\
    & = \left \| \mathbf{Rx} - \mathbf{Q}^{\intercal}\mathbf{b} \right \|^{2}_{2} \\
    & = \left \| \begin{bmatrix} \mathbf{R}_{1} \\ \mathbf{0} \end{bmatrix}\mathbf{x} - \begin{bmatrix} \mathbf{Q}_{1}^{\intercal} \\ \mathbf{Q}_{2}^{\intercal} \end{bmatrix} \mathbf{b} \right \|^{2}_{2}
    \end{aligned}
\end{equation}

위 식에서 세번째 줄은 $\left \| \mathbf{Q}(\cdot) \right \|^{2}_{2} = (\cdot)^{\intercal}\mathbf{Q}^{\intercal}\mathbf{Q}(\cdot) = (\cdot)^{\intercal}(\cdot) = \left \| (\cdot) \right \|^{2}_{2}$을 통해 구할 수 있다. 네번째 줄은 $\mathbf{QR}$ 행렬을 블록 행렬 $\mathbf{Q}_{i}, \mathbf{R}_{i}$로 표현한 모습이다. 벡터의 제곱의 합은 선형성을 가지므로 위 식의 마지막 줄을 전개하면 다음과 같다.
\begin{equation}
    \begin{aligned}
    \left \| \begin{bmatrix} \mathbf{R}_{1} \\ \mathbf{0} \end{bmatrix}\mathbf{x} - \begin{bmatrix} \mathbf{Q}_{1}^{\intercal} \\ \mathbf{Q}_{2}^{\intercal} \end{bmatrix} \mathbf{b} \right \|^{2}_{2} & = \left \| \mathbf{R}_{1}\mathbf{x} - \mathbf{Q}_{1}^{\intercal}\mathbf{b} \right \|^{2}_{2} + \left \| - \mathbf{Q}_{2}^{\intercal}\mathbf{b} \right \|^{2}_{2}
    \end{aligned}
\end{equation}

따라서 $\min_{\mathbf{x}} \Big(\left \| \mathbf{R}_{1}\mathbf{x} - \mathbf{Q}_{1}^{\intercal}\mathbf{b} \right \|^{2}_{2} + \left \| - \mathbf{Q}_{2}^{\intercal}\mathbf{b} \right \|^{2}_{2} \Big)$를 최소화하는 $\mathbf{x}$는 다음과 같이 구할 수 있다.
\begin{equation}
    \begin{aligned}
        \mathbf{x} = \mathbf{R}^{-1}\mathbf{Q}^{\intercal}\mathbf{b}
    \end{aligned} \label{eq:qr1}
\end{equation}

이 때, 최소제곱법 식의 크기는 $\left \| - \mathbf{Q}_{2}^{\intercal}\mathbf{b} \right \|^{2}_{2}$이다.

Eigen decomposition

정방행렬 $\mathbf{A} \in \mathbb{R}^{n\times n}$가 대각화 가능한 경우 다음과 같은 두 행렬 $\mathbf{V}\in \mathbb{R}^{n\times n}$과 대각행렬 $\mathbf{D} \in \mathbb{R}^{n\times n}$에 대하여 $\mathbf{A}$를 다음과 같이 분해할 수 있다. 
\begin{equation}
\begin{aligned}
\mathbf{A} = \mathbf{VDV}^{-1}
\end{aligned}
\end{equation}

이를 행렬 $\mathbf{A}$에 대한 고유값 분해(eigen decomposition) 라고 한다. 행렬 $\mathbf{A}$가 대각화 가능하다는 의미는 행렬 $\mathbf{A}$가 고유값 분해 가능하다는 말과 동치이다.

행렬 $\mathbf{A}$가 대각화(고유값분해)되기 위해서는 역행렬이 존재하는 행렬 $\mathbf{V}$가 존재해야 한다. 행렬 $\mathbf{V}$가 역행렬이 존재하기 위해서는 $\mathbf{V}$는 행렬 $\mathbf{A}$와 같은 $\mathbb{R}^{n \times n}$ 크기의 정방행렬이어야 하고 n개의 선형독립인 열벡터를 가지고 있어야 한다. 이 때, $\mathbf{V}$의 각 열은 행렬 $\mathbf{A}$의 고유벡터가 된다. 만약 행렬 $\mathbf{V}$가 존재하는 경우 행렬 $\mathbf{A}$는 대각화(고유값분해) 가능하다 고 한다.

Singular value decomposition

행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$이 주어졌을 때 특이값 분해(Singular Value Decomposition, SVD)는 다음과 같이 나타낼 수 있다.
\begin{equation}
\begin{aligned}
\mathbf{A} = \mathbf{U} \Sigma \mathbf{V}^{\intercal}
\end{aligned}
\end{equation}

이 때, $\mathbf{U} \in \mathbb{R}^{m \times m}, \mathbf{V} \in \mathbb{R}^{n\times n}$인 행렬이며 이들은 각 열이 Col $\mathbf{A}$와 Row $\mathbf{A}$에 의 정규직교기저벡터(Orthonormal Basis)로 구성되어 있다. $\Sigma \in \mathbb{R}^{m\times n}$은 대각행렬이며 대각 성분들이 $\sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{\min(m,n)}$ 특이값이며 큰 값부터 내림차순으로 정렬된 행렬이다.

Computing SVD

행렬 $\mathbf{A} \in \mathbb{R}^{m\times n}$에 대하여 $\mathbf{AA}^{\intercal}$와 $\mathbf{A}^{\intercal}\mathbf{A}$는 다음과 같이 고유값분해할 수 있다.
\begin{equation}
\begin{aligned}
& \mathbf{AA}^{\intercal} = \mathbf{U}\Sigma \mathbf{V}^{\intercal} \mathbf{V} \Sigma^{\intercal} \mathbf{U}^{\intercal} = \mathbf{U}\Sigma\Sigma^{\intercal}\mathbf{U}^{\intercal} = \mathbf{U}\Sigma^{2}\mathbf{U}^{\intercal} \\
& \mathbf{A}^{\intercal}\mathbf{A} = \mathbf{V}\Sigma^{\intercal}\mathbf{U}^{\intercal} \mathbf{U}\Sigma \mathbf{V}^{\intercal} = \mathbf{V}\Sigma^{\intercal}\Sigma \mathbf{U}^{\intercal} = \mathbf{V}\Sigma^{2}\mathbf{V}^{\intercal}
\end{aligned}
\end{equation}

이 때 계산되는 행렬 $\mathbf{U}, \mathbf{V}$은 직교하는 고유벡터를 각 열의 성분으로 하는 행렬이며 대각행렬 $\Sigma^{2}$의 각 성분은 항상 0보다 큰 양수의 값을 가진다. 그리고 $\mathbf{AA}^{\intercal}$와 $\mathbf{A}^{\intercal}\mathbf{A}$를 통해 계산되는 $\Sigma^{2}$의 값은 동일하다.

또한, 행렬 $\mathbf{A}$에 대하여 $\mathbf{AA}^{\intercal} = \mathbf{A}^{\intercal}\mathbf{A} = \mathbf{S}$인 대칭행렬이 존재할 때 $\mathbf{S}$가 Positive (Semi-)Definite한 경우
\begin{equation}
\begin{aligned}
& \mathbf{x}^{\intercal}\mathbf{AA}^{\intercal}\mathbf{x} = (\mathbf{A}^{\intercal}\mathbf{x})^{\intercal}(\mathbf{A}^{\intercal}\mathbf{x}) = \| \mathbf{A}^{\intercal}\mathbf{x} \| \ge 0 \\
& \mathbf{x}^{\intercal}\mathbf{A}^{\intercal}\mathbf{Ax} = (\mathbf{Ax})^{\intercal}(\mathbf{Ax}) = \| \mathbf{Ax} \|^{2} \ge 0
\end{aligned}
\end{equation}

즉, $\mathbf{AA}^{\intercal} = \mathbf{U}\Sigma^{2}\mathbf{U}^{\intercal}$와 $\mathbf{A}^{\intercal}\mathbf{A} = \mathbf{V}\Sigma^{2}\mathbf{V}^{\intercal}$에서 $\Sigma^{2}$의 값은 항상 양수가 된다.

임의의 직각 행렬 $\mathbf{A} \in \mathbb{R}^{m\times n}$에 대하여 특이값 분해는 언제나 존재한다. $\mathbf{A} \in \mathbb{R}^{n\times n}$ 행렬의 경우 고유값 분해가 존재하지 않을 수 있지만 특이값 분해는 항상 존재한다. 대칭이면서 동시에 Positive Definite인 정방 행렬 $\mathbf{S} \in \mathbb{R}^{n\times n}$은 항상 고유값 분해값이 존재하며 이는 특이값 분해와 동일하다.

Range and nullspace of SVD

SVD는 다른 행렬 분해 방법들과 달리 $\mathbf{A}$ 가 Singular하거나 Near-Singular한 경우에도 사용할 수 있는 방법이다. $\mathbf{A}$ 가 Non-Singular한 경우 역행렬은 $\mathbf{A}^{-1} = \mathbf{V} \cdot \text{diag}(1/\sigma_{j})\cdot \mathbf{U}^{\intercal}$ 와 같이 계산할 수 있다. 만약 $\mathbf{A}$ 가 Singular한 경우 역행렬을 구할 때 몇몇 $\sigma_{j}=0$ 이 되는데 이 때 $1/\sigma_{j} \Rightarrow 0$ 으로 설정함으로써 역행렬을 구할 수 있다. 특이값 $\sigma_{j}$와 관련하여 SVD 분해는 다음과 같은 성질을 갖는다.

• $\sigma_{j} \neq 0$ 일 때 이와 상응하는 $\mathbf{U}$ 의 column들을 $\mathbf{A}$ 행렬의 Orthogonal set of basis vector of Range라고 한다.
• $\sigma_{j} = 0$ 일 때 이와 상응하는 $\mathbf{V}$ 의 column들을 $\mathbf{A}$ 의 Orthogonal set of basis vector of Null Space라고 한다.
• 0이 아닌 특이값 $\sigma_j \neq 0$의 개수는 곧 행렬 $\mathbf{A}$의 rank와 같다.
  
  
  

SVD on under-determined system

$\mathbf{A}$ 가 Singular이면서 동시에 $\mathbf{b}$ 가 Range 안에 포함되는 경우 선형시스템은 다수의 해를 가진다. 이런 경우 $\mathbf{Ax} = \mathbf{b}$ 에서 $\left \| \mathbf{x} \right \|^{2}$ 가 최소가 되는 해를 구할 수 있다.

\begin{equation}
  \begin{aligned}
    & \min_{\mathbf{x}} \left \| \mathbf{x} \right \|^{2} \\
    & \mathbf{x} = \mathbf{V} \cdot \text{diag}(1/\sigma_{j}) \cdot \mathbf{U}^{\intercal} \cdot \mathbf{b} 
  \end{aligned}
\end{equation}

SVD on over-determined system

$\mathbf{A}$ 가 Singular이면서 동시에 $\mathbf{b}$ 가 Range에 존재하지 않는 경우 선형시스템은 해가 존재하지 않는다. 이런 경우 $\left \| \mathbf{Ax} - \mathbf{b} \right \|$ 가 최소가 되는 근사해를 구할 수 있다.

\begin{equation}
  \begin{aligned}
    & \min_{\mathbf{x}} \left \| \mathbf{Ax} - \mathbf{b} \right \| \\
    & \mathbf{x} = \mathbf{V} \cdot \text{diag}(1/\sigma_{j}) \cdot \mathbf{U}^{\intercal} \cdot \mathbf{b}
  \end{aligned}
\end{equation}

Pseudo inverse

Pseudo Inverse는 선형시스템에서 행렬 $\mathbf{A}$가 정방행렬이 아닐 경우 임의로 역행렬을 구하는 방법을 말한다. 이 때, 선형시스템은 일반적으로 full column rank 또는 full row rank일 때 pseudo inverse를 적용할 수 있다. Full rank가 아닌 행렬에 대한 pseudo inverse는 추후 섹션에서 설명한다.

Pseudo inverse on under-determined system

under-determined 시스템의 경우 $\mathbf{A}$는 full row rank가 되고 pseudo inverse는 다음과 같이 정의된다. lagrange multiplier $\mathbf{\lambda}$를 포함하여 최적화 문제를 정의하면 다음과 같다.
\begin{equation}\begin{aligned}
\min_{\mathbf{x}} || \mathbf{x} ||^{2} + \mathbf{\lambda}^{\intercal}(\mathbf{b} - \mathbf{Ax})\end{aligned} \end{equation} 

이를 미분 후 0으로 만드는 값을 찾으면 다음과 같다.
\begin{equation}\begin{aligned}
2\mathbf{x} - \mathbf{A}^{\intercal}\mathbf{\lambda}=0\end{aligned} \end{equation} 

$\mathbf{A}$가 정방행렬이 아니기 때문에 바로 해를 구할 수 없으므로 양변의 왼쪽에 $\mathbf{A}$를 곱한다.
\begin{equation}\begin{aligned}
2\mathbf{Ax} - \mathbf{AA}^{\intercal}\mathbf{\lambda}=0\end{aligned} \end{equation} 

이 때, $\mathbf{Ax} = \mathbf{b}$이므로 다음과 같은 식이 유도된다.
\begin{equation}\begin{aligned}
2\mathbf{b} = \mathbf{AA}^{\intercal}\mathbf{\lambda}\end{aligned} \end{equation} 
\begin{equation}\begin{aligned}
\mathbf{\lambda} = 2(\mathbf{AA}^{\intercal})^{-1}\mathbf{b}\end{aligned} \end{equation} 

따라서 $\mathbf{x}$는 다음과 같이 구할 수 있다.
\begin{equation}\begin{aligned}
\mathbf{x} = \mathbf{A}^{\intercal}(\mathbf{AA}^{\intercal})^{-1}\mathbf{b}\end{aligned} \end{equation} 

\begin{equation}
  \boxed{ \begin{aligned}
    \mathbf{A}^{\dagger} = \mathbf{A}^{\intercal}(\mathbf{A}\mathbf{A}^{\intercal})^{-1} \quad \cdots \text { for under-determined system}
  \end{aligned} }  \label{eq:pinv3}
\end{equation}

즉, under-determined 시스템에서 pseudo inverse는 오른쪽에 곱해지게 되며 이를 right pseudo inverse라고 부르기도 한다. (유도 과정이 불확실함. 확실하게 알게되는대로 업데이트 예정. 자세한 유도 과정을 아시는 분은 연락주시면 감사하겠습니다.)
\begin{equation}
    \begin{aligned}
        & \mathbf{A}\mathbf{A}^{\dagger}\mathbf{x} = \mathbf{A}^{\dagger}\mathbf{b} \\
        & \mathbf{x} = \mathbf{A}^{\dagger}\mathbf{b} \\
        & \mathbf{x} = \mathbf{A}^{\intercal}(\mathbf{AA}^{\intercal})^{-1}\mathbf{b} \quad \cdots \text { for under-determined system}
    \end{aligned}
\end{equation}

Pseudo inverse on over-determined system

over-determined 시스템의 경우 $\mathbf{A}$는 full column rank가 되고 pseudo inverse는 다음과 같이 정의된다. 우선, over-determined 시스템에 대한 최적화 문제는 다음과 같이 최소제곱법 문제가 된다. 
\begin{equation}\begin{aligned}
\min_{\mathbf{x}} || \mathbf{Ax} - \mathbf{b} ||^{2} = \min_{\mathbf{x}} || \mathbf{b} - \mathbf{Ax} ||^{2} = \min_{\mathbf{x}} (\mathbf{b}-\mathbf{Ax})^{\intercal}(\mathbf{b}-\mathbf{Ax})\end{aligned} \end{equation} 

이를 전개하면 다음과 같다.
\begin{equation}\begin{aligned}
\min_{\mathbf{x}} \mathbf{b}^{\intercal}\mathbf{b} - \mathbf{b}^{\intercal}\mathbf{Ax} - \mathbf{x}^{\intercal}\mathbf{A}^{\intercal}\mathbf{b} + \mathbf{x}^{\intercal}\mathbf{A}^{\intercal}\mathbf{Ax}\end{aligned} \end{equation} 

위 문제를 풀기 위해 $\mathbf{x}$에 대해 미분하면 다음과 같은 식이 얻어진다.
\begin{equation}\begin{aligned}
-(\mathbf{b}^{\intercal}\mathbf{A})^{\intercal} - (\mathbf{A}^{\intercal}\mathbf{b}) + 2\mathbf{A}^{\intercal}\mathbf{Ax} = 0\end{aligned} \end{equation} 

따라서 $\mathbf{x}$는 다음과 같이 구할 수 있다.
\begin{equation}\begin{aligned}
\mathbf{x} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal}\mathbf{b}\end{aligned} \end{equation} 

\begin{equation}
  \boxed{ \begin{aligned}
    & \mathbf{A}^{\dagger} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal} \quad \cdots \text { for over-determined system}
  \end{aligned} }  \label{eq:pinv1}
\end{equation}

즉, over-determined 시스템에서 pseudo inverse는 왼쪽에 곱해지게 되며 이를 left pseudo inverse라고 부르기도 한다.
\begin{equation}
    \begin{aligned}
        & \mathbf{A}^{\dagger}\mathbf{Ax} = \mathbf{A}^{\dagger}\mathbf{b} \\
        & \mathbf{x} = \mathbf{A}^{\dagger}\mathbf{b} \\
        & \mathbf{x} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal}\mathbf{b} \quad \cdots \text { for over-determined system}
    \end{aligned}
\end{equation}

SVD of pseudo inverse

선형 시스템 $\mathbf{Ax} = \mathbf{b}$이 주어졌을 때 임의의 직사각형 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$와 pseudo inverse $\mathbf{A}^{\dagger}$는 SVD 분해를 통해 다음과 같이 나타낼 수 있다.
\begin{equation}
    \begin{aligned}
    &   \mathbf{A} = \mathbf{U}\Sigma\mathbf{V}^{\intercal} \\
    &      \mathbf{A}^{\dagger} = \mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal} \\
    \end{aligned} \label{eq:pinv2}
\end{equation}
- $\mathbf{U} \in \mathbb{R}^{m\times m}$
- $\Sigma = \text{diag}(\sigma_{1},\sigma_{2},\sigma_{3},\cdots) \in \mathbb{R}^{m \times n}$ 
- $\Sigma^{\dagger} = \text{diag}(1/\sigma_{1},1/\sigma_{2},1/\sigma_{3},\cdots) \in \mathbb{R}^{n \times m}$ 
- $\mathbf{V} \in \mathbb{R}^{n\times n}$

Full column rank case

임의의 직사각형 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$가 full column rank를 가지면 pseudo inverse는  $\mathbf{A}^{\dagger}\mathbf{A}$와 같이 왼쪽에 곱해진다. 이를 SVD 분해하여 표현하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger}\mathbf{A} = \mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal} \mathbf{U}\Sigma\mathbf{V}^{\intercal} = \mathbf{I}_{n}
    \end{aligned}
\end{equation}


또한, 앞서 구한 (\ref{eq:pinv1})에서 $\mathbf{A}^{\dagger} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal}$를 풀어쓰면 다음과 같다. 
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger} & = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal} \\
        & = (\mathbf{V}\Sigma^{\intercal}\mathbf{U}^{\intercal}\mathbf{U}\Sigma\mathbf{V}^{\intercal})^{-1} \mathbf{V} \Sigma^{\intercal}\mathbf{U}^{\intercal} \\
        & = \mathbf{V}\Sigma^{-2}\Sigma\mathbf{U}^{\intercal} \quad \quad && \cdots \Sigma^{\intercal} = \Sigma \\
        & = \mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal} \quad \quad && \cdots \Sigma^{\dagger} = \Sigma^{-1}
    \end{aligned}
\end{equation}

이는 앞서 정의한 (\ref{eq:pinv2})와 동일하다.

Full row rank case

임의의 직사각형 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$가 full row rank를 가지면 pseudo inverse는  $\mathbf{A}\mathbf{A}^{\dagger}$와 같이 오른쪽에 곱해진다. 이를 SVD 분해하여 표현하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{A}\mathbf{A}^{\dagger} = \mathbf{U}\Sigma\mathbf{V}^{\intercal}\mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal} = \mathbf{I}_{m}
    \end{aligned}
\end{equation}


또한, 앞서 구한 (\ref{eq:pinv3})에서 $\mathbf{A}^{\dagger} = \mathbf{A}^{\intercal}(\mathbf{A}\mathbf{A}^{\intercal})^{-1}$를 풀어쓰면 다음과 같다. 
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger} & = \mathbf{A}^{\intercal}(\mathbf{A}\mathbf{A}^{\intercal})^{-1} \\
        & = \mathbf{V} \Sigma^{\intercal}\mathbf{U}^{\intercal}(\mathbf{U}\Sigma\mathbf{V}^{\intercal}\mathbf{V}\Sigma^{\intercal}\mathbf{U}^{\intercal})^{-1}  \\
        & = \mathbf{V}\Sigma\Sigma^{-2}\mathbf{U}^{\intercal} \quad \quad && \cdots \Sigma^{\intercal} = \Sigma \\
        & = \mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal} \quad \quad && \cdots \Sigma^{\dagger} = \Sigma^{-1}
    \end{aligned}
\end{equation}

이는 앞서 정의한 (\ref{eq:pinv2})와 동일하다.

Rank deficient case

만약 임의의 직사각형 행렬 $\mathbf{A}$이 full rank가 아닐 경우 pseudo inverse는 다음과 같이 나타낼 수 있다. 예를 들어 $\mathbf{A} \in \mathbb{R}^{3\times4}$ 일 때 이를 SVD 분해하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{A} & =  \mathbf{U}\Sigma\mathbf{V}^{\intercal} \\
        & = \mathbf{U} \begin{bmatrix}
            \sigma_{1} & 0& 0 & 0 \\ 
            0& \sigma_{2} & 0& 0 \\ 
            0& 0& 0& 0 
        \end{bmatrix} \mathbf{V}^{\intercal}
    \end{aligned}
\end{equation}

Pseudo inverse $\mathbf{A}^{\dagger}$를 SVD 분해하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger} & = \mathbf{V}\Sigma^{\dagger}\mathbf{U}^{\intercal}\\ 
        & = \mathbf{V} \begin{bmatrix}
            1/\sigma_{1} & 0& 0  \\ 
            0& 1/\sigma_{2} & 0 \\ 
            0& 0& 0 \\
            0&0&0
        \end{bmatrix} \mathbf{U}^{\intercal}
    \end{aligned}
\end{equation}

따라서 오른쪽 pseudo inverse $\mathbf{AA}^{\dagger}$는 다음과 같이 전개할 수 있다.
\begin{equation}
    \begin{aligned}
        \mathbf{AA}^{\dagger} & = \mathbf{U}\Sigma\mathbf{V}^{\intercal} \mathbf{V} \Sigma^{\dagger} \mathbf{U}^{\intercal}  \\
        & = \mathbf{U} \begin{bmatrix}
            1 & & \\  & 1 &  \\ &&
        \end{bmatrix} \mathbf{U}^{\intercal} \\
        & = \mathbf{u}_{1}\mathbf{u}_{1}^{\intercal} + \mathbf{u}_{2}\mathbf{u}_{2}^{\intercal}
    \end{aligned}
\end{equation}

만약 $\mathbf{A}$가 full rank인 경우 $\mathbf{AA}^{\dagger}$는 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{AA}^{\dagger} & = \mathbf{I}_{3} \\
        & = \mathbf{u}_{1}\mathbf{u}_{1}^{\intercal} + \mathbf{u}_{2}\mathbf{u}_{2}^{\intercal} + \mathbf{u}_{3}\mathbf{u}_{3}^{\intercal}
    \end{aligned}
\end{equation}

따라서 rank deficient 케이스의 경우 $\mathbf{AA}^{\dagger}$는 마지막 $\mathbf{u}_{3}\mathbf{u}_{3}^{\intercal}$이 없는 pseudo inverse가 구해진다. 이는 항등행렬 $\mathbf{I}_{3}$와 유사한 값을 갖지만 동일하지는 않은 행렬이다.

다음으로 왼쪽 pseudo inverse $\mathbf{A}^{\dagger}\mathbf{A}$는 다음과 같이 전개할 수 있다.
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger}\mathbf{A} & = \mathbf{V} \Sigma^{\dagger} \mathbf{U}^{\intercal}\mathbf{U}\Sigma\mathbf{V}^{\intercal}   \\
        & = \mathbf{V} \begin{bmatrix}
            1 & & & \\  & 1 & & \\ &&& \\ &&&
        \end{bmatrix} \mathbf{V}^{\intercal} \\
        & = \mathbf{v}_{1}\mathbf{v}_{1}^{\intercal} + \mathbf{v}_{2}\mathbf{v}_{2}^{\intercal}
    \end{aligned}
\end{equation}

만약 $\mathbf{A}$가 full rank인 경우 $\mathbf{A}^{\dagger}\mathbf{A}$는 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{A}^{\dagger}\mathbf{A} & = \mathbf{I}_{4} \\
        & = \mathbf{v}_{1}\mathbf{v}_{1}^{\intercal} + \mathbf{v}_{2}\mathbf{v}_{2}^{\intercal} + \mathbf{v}_{3}\mathbf{v}_{3}^{\intercal} + \mathbf{v}_{4}\mathbf{v}_{4}^{\intercal}
    \end{aligned}
\end{equation}

따라서 rank deficient 케이스의 경우 $\mathbf{A}^{\dagger}\mathbf{A}$는 마지막 $\mathbf{v}_{3}\mathbf{v}_{3}^{\intercal} + \mathbf{v}_{4}\mathbf{v}_{4}^{\intercal}$이 없는 pseudo inverse가 구해진다. 이는 항등행렬 $\mathbf{I}_{4}$와 유사한 값을 갖지만 동일하지는 않은 행렬이다. 이는 $\mathbf{AA}^{\dagger}$를 통해 구한 행렬보다 덜 항등행렬에 근접하다.

따라서 임의의 non-full rank를 가지는 직사각형 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$이 주어졌을 때, $m<n$인 경우 $\mathbf{AA}^{\dagger}$를 수행하는 것이 더 항등행렬에 근접한 pseudo inverse를 수횅할 수 있고 $m>n$인 경우 $\mathbf{A}^{\dagger}\mathbf{A}$를 수행하는 것이 더 항등행렬에 근접한 pseudo inverse를 수행할 수 있다.

QR decomposition of pseudo inverse when singular case

간혹 $\mathbf{A}^{\intercal}\mathbf{A}$ 가 singular하거나 near-singular한 경우 QR 분해를 사용하여 pseudo inverse를 구한다.
\begin{equation}
  \begin{aligned}
   \mathbf{x} & = \mathbf{A}^{\dagger}\mathbf{b} \\ 
   & = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal}\mathbf{b} \\
   & = (\mathbf{R}^{\intercal}\mathbf{Q}^{\intercal}\mathbf{Q}\mathbf{R})^{-1}\mathbf{R}^{\intercal}\mathbf{Q}^{\intercal}\mathbf{b} \\
   & = (\mathbf{R}^{\intercal}\mathbf{R})^{-1}\mathbf{R}^{\intercal}\mathbf{Q}^{\intercal}\mathbf{b} \\
   & = \mathbf{R}^{-1}\mathbf{Q}^{\intercal}\mathbf{b}
  \end{aligned}
\end{equation}

위 식은 (\ref{eq:qr1})와 동일하다.

Woodbury's indentity

역행렬이 존재하는 임의의 행렬 $\mathbf{A}$에 대해 rank 1 업데이트를 하는 방법을 Sherman-Morrison 공식이라고 한다. 또는 Woodbury's identity라고도 한다. 해당 공식에 대한 보다 자세한 내용은 [6]를 참조하면 된다.       
\begin{equation}
\boxed{    \begin{aligned}
        (\mathbf{A} + \mathbf{u}\mathbf{v}^{\intercal})^{-1} = \mathbf{A}^{-1} - \frac{\mathbf{A}^{-1}\mathbf{uv}^{\intercal}\mathbf{A}^{-1}}{1 + \mathbf{v}^{\intercal}\mathbf{A}^{-1}\mathbf{u}}
    \end{aligned} } \label{eq:sm1}
\end{equation}

 위 식에서 $(1 + \mathbf{v}^{\intercal}\mathbf{A}^{-1}\mathbf{u}) \neq 0$와 $(\mathbf{A} + \mathbf{u}\mathbf{v}^{\intercal})^{-1}$이 역행렬이 존재하는 조건은 동치이다. 이 때, $\mathbf{u}, \mathbf{v}$는 임의의 두 벡터를 의미하며 이를 $\mathbf{u}\mathbf{v}^{\intercal}$와 같이 곱하면 항상 rank 1 행렬이 생성된다.
\begin{equation}
    \begin{aligned}
        \mathbf{u}\mathbf{v}^{\intercal} = \begin{bmatrix}
            u_{1} \\ u_{2}
        \end{bmatrix} \begin{bmatrix}
            v_{1} & v_{2}
        \end{bmatrix} 
        = \begin{bmatrix}
            v_{1} \begin{bmatrix}u_{1} \\ u_{2} \end{bmatrix} & v_{2} \begin{bmatrix}u_{1} \\ u_{2} \end{bmatrix}
        \end{bmatrix} \quad \cdots \text{ linearly dependent = rank 1}
    \end{aligned}
\end{equation}

Recursive least squares

Sherman-Morrison 공식은 데이터가 계속 추가되는 최소제곱법 문제에 사용하면 연산량을 적게 소모하면서 효율적으로 역행렬을 업데이트할 수 있다. 다음과 같은 선형 시스템 $\mathbf{Ax} = \mathbf{b}$가 주어졌다고 하자. $\mathbf{A} \in \mathbb{R}^{m\times n}, \mathbf{x} \in \mathbb{R}^{n\times 1}, \mathbf{b} \in \mathbb{R}^{m\times 1}$ 일 때 이를 풀어서 쓰면 아래와 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{Ax} &= \mathbf{b} \\
        \begin{bmatrix}
            \mathbf{a}_{1}^{\intercal} \\ 
            \mathbf{a}_{2}^{\intercal} \\
            \vdots \\
            \mathbf{a}_{m}^{\intercal}
        \end{bmatrix} \begin{bmatrix}
            x_{1} \\ x_{2} \\ \vdots \\ x_{n}
        \end{bmatrix} & = \begin{bmatrix}
            b_{1} \\ b_{2} \\ \vdots \\ b_{m}
        \end{bmatrix}
    \end{aligned}
\end{equation}

선형시스템의 최소제곱법의 해는 다음과 같다. 
\begin{equation}
    \begin{aligned}
        \mathbf{x} = (\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal} \mathbf{b}
    \end{aligned}
\end{equation}

만약 $m+1$ 번째 데이터 $\mathbf{a}_{m+1}^{\intercal}$이 입력되면 이에 맞게 최적해를 업데이트해줘야 한다. 표현의 편의를 위해 $m+1$ 번째 데이터를 $\mathbf{a}$로 표현하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        \mathbf{x} & = \bigg( \begin{bmatrix} \mathbf{A}^{\intercal} & \mathbf{a} \end{bmatrix}\begin{bmatrix} \mathbf{A}^{\intercal} \\ \mathbf{a} \end{bmatrix} \bigg)^{-1} \begin{bmatrix} \mathbf{A}^{\intercal} & \mathbf{a} \end{bmatrix} \begin{bmatrix} \mathbf{b} \\ b \end{bmatrix} \\
         & = (\mathbf{A}^{\intercal}\mathbf{A} + \mathbf{a}\mathbf{a}^{\intercal})^{-1}(\mathbf{A}^{\intercal}\mathbf{b} + \mathbf{a}b_{m+1})
    \end{aligned} \label{eq:sm2}
\end{equation}

이 때, 앞 부분 $(\mathbf{A}^{\intercal}\mathbf{A} + \mathbf{a}\mathbf{a}^{\intercal})^{-1}$에 Sherman-Morisson 공식 (\ref{eq:sm1})을 적용하면 연산량을 적게 소모하면서 효율적으로 최적해를 업데이트할 수 있다. 이는 다음과 같이 전개 후 치환하여 간결하게 나타낼 수 있다.
\begin{equation}
   \begin{aligned}
        (\mathbf{A}^{\intercal}\mathbf{A} + \mathbf{a}\mathbf{a}^{\intercal})^{-1} 
        & = (\mathbf{A}^{\intercal}\mathbf{A})^{-1} - \frac{(\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{aa}^{\intercal}(\mathbf{A}^{\intercal}\mathbf{A})^{-1}}{1 + \mathbf{a}^{\intercal}(\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{a}} \\
        & = \mathbf{P} - \frac{\mathbf{P}\mathbf{aa}^{\intercal}\mathbf{P}}{1 + \mathbf{a}^{\intercal}\mathbf{P}\mathbf{a}}  \\
        & = \mathbf{P}_{a}
    \end{aligned} 
\end{equation}
- $(\mathbf{A}^{\intercal}\mathbf{A})^{-1} = \mathbf{P}$ 표현의 편의를 위해 치환한다 

위 치환한 식을 기반으로 (\ref{eq:sm2})를 전개하면 다음과 같다.
\begin{equation}
    \begin{aligned}
        (\mathbf{A}^{\intercal}\mathbf{A} + \mathbf{a}\mathbf{a}^{\intercal})^{-1}(\mathbf{A}^{\intercal}\mathbf{b} + \mathbf{a}b_{m+1}) 
        & = \Big( \mathbf{P} - \frac{\mathbf{P}\mathbf{aa}^{\intercal}\mathbf{P}}{1 + \mathbf{a}^{\intercal}\mathbf{P}\mathbf{a}} \Big) (\mathbf{A}^{\intercal}\mathbf{b} + \mathbf{a}b_{m+1}) \\
        & = \mathbf{P}\mathbf{A}^{\intercal} \mathbf{b} + \frac{\mathbf{P}\mathbf{aa}^{\intercal}\mathbf{P}}{1 + \mathbf{a}^{\intercal}\mathbf{P}\mathbf{a}} \mathbf{A}^{\intercal}\mathbf{b} + \mathbf{P}_{a} \mathbf{a}b \\
        & = \mathbf{x} - \frac{\mathbf{P}\mathbf{aa}^{\intercal}\mathbf{P}}{1 + \mathbf{a}^{\intercal}\mathbf{P}\mathbf{a}} \mathbf{A}^{\intercal}\mathbf{b} + \mathbf{P}_{a} \mathbf{a}b \\
        & = \mathbf{x} - \Big( \frac{\mathbf{P}\mathbf{a}}{1 + \mathbf{a}^{\intercal}\mathbf{P}\mathbf{a}} \Big) \mathbf{a}^{\intercal}\mathbf{x} + \mathbf{P}_{a} \mathbf{a}b \\
        & = \mathbf{x} - (\mathbf{P}_{a}\mathbf{a})\mathbf{a}^{\intercal}\mathbf{x} + \mathbf{P}_{a} \mathbf{a}b \\
        & = \mathbf{x} + \mathbf{P}_{a}\mathbf{a} (b - \mathbf{a}^{\intercal}\mathbf{x} )
    \end{aligned} 
\end{equation}
- $\mathbf{P}\mathbf{A}^{\intercal} \mathbf{b} = \mathbf{x}$ 

위 식에서 5번째 줄은 $\mathbf{P}_{a}\mathbf{a}$를 전개한 후 분모를 통분하여 정리함으로써 유도할 수 있다. 따라서 데이터가 증가했을 때 새로운 최적해는 이전 최적해 식으로부터 아래와 같이 업데이트된다. 이를 recursive least squares(RLS)라고 한다.
\begin{equation}
   \boxed{ \begin{aligned}
        \mathbf{x} \leftarrow \mathbf{x} + \mathbf{P}_{a}\mathbf{a} (b - \mathbf{a}^{\intercal}\mathbf{x} )
    \end{aligned}  }
\end{equation}

Matrix inversion lemma

Matrix inversion lemma는 역행렬 변환 공식을 의미하며 선형 시스템을 다룰 때 자주 쓰이는 트릭 중 하나이다. 이는 Sherman-Morrison-Woodbury 공식이라고도 불린다. Matrix inversion lemma는 는 다음과 같이 정의된다. Lemma에 대한 보다 자세한 내용은 [6]를 참조하면 된다.         
\begin{equation}
   \boxed{  \begin{aligned}
        (\mathbf{A} + \mathbf{UCV})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1} + \mathbf{VA}^{-1}\mathbf{U})^{-1}\mathbf{VA}^{-1}
    \end{aligned} }  \label{eq:lemma3}
\end{equation}
- $\mathbf{A} \in \mathbb{R}^{n\times n}$ 
- $\mathbf{U} \in \mathbb{R}^{n\times k}$ 
- $\mathbf{C} \in \mathbb{R}^{k\times k}$ 
- $\mathbf{V} \in \mathbb{R}^{k\times n}$
- $\mathbf{A}, \mathbf{C}, \mathbf{C}^{-1} + \mathbf{VA}^{-1}\mathbf{U} \text{ is invertible}$

 

공식을 자세히 보면 matrix inversion lemma는 Woodbury's identity의 행렬 확장버전으로 볼 수 있다. $\mathbf{C}$는 스칼라이고 $\mathbf{B},\mathbf{D}$가 각각 $n \times 1$, $1 \times n$인 경우 Woodbury's identity와 동일한 공식이 유도된다.
 

Derivation of matrix inversion lemma

Matrix inversion lemma를 유도하기 위해 4개의 블록 행렬로 구성된 $\mathbf{M}$가 주어졌다고 하자. 
\begin{equation}
    \begin{aligned}
        \mathbf{M} = \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D}
        \end{bmatrix}
    \end{aligned}
\end{equation}

LDU decomposition

다음으로 $\mathbf{M}$를 LDU 분해하려고 한다. 아래와 같이 $\mathbf{C}$를 소거하기 위한 행렬을 곱해서 LU 행렬을 만들 수 있다.
\begin{equation}
    \begin{aligned}
         \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{CA}^{-1} & \mathbf{I}
        \end{bmatrix}^{-1} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{CA}^{-1} & \mathbf{I}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D}
        \end{bmatrix} = \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{CA}^{-1} & \mathbf{I}
        \end{bmatrix}^{-1} \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{0} & \mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}
        \end{bmatrix}
    \end{aligned}
\end{equation}

이 때, $\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}$를 $\mathbf{A}$의 schur complement ($\mathbf{M}/\mathbf{A}$)라고 한다. 다음으로 대각 행렬 성분만 남기기 위해 아래와 같이 오른쪽에 행렬을 전개하면 LDU 분해가 마무리된다.
\begin{equation}
    \begin{aligned}
          \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{CA}^{-1} & \mathbf{I}
        \end{bmatrix}^{-1}\begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{0} & \mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}
        \end{bmatrix} = \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{CA}^{-1} & \mathbf{I}
        \end{bmatrix}^{-1}\begin{bmatrix}
            \mathbf{A} & \mathbf{0} \\ \mathbf{0} & \mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{A}^{-1}\mathbf{B} \\ \mathbf{0} & \mathbf{I} 
        \end{bmatrix} 
    \end{aligned}
\end{equation}

$\mathbf{M}^{-1}$은 다음과 같이 LDU 행렬을 사용하여 전개할 수 있다.
\begin{equation}
    \boxed {\begin{aligned}
          \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D}
        \end{bmatrix}^{-1} & = \begin{bmatrix}
            \mathbf{I} & -\mathbf{A}^{-1}\mathbf{B} \\ \mathbf{0} & \mathbf{I}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{A}^{-1} & \mathbf{0} \\ \mathbf{0} & (\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B})^{-1}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\  -\mathbf{C}^{-1}\mathbf{A} & \mathbf{I}
        \end{bmatrix}
        \\ & = 
        \begin{bmatrix}
            \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B}(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B})^{-1}\mathbf{CA}^{-1} & 
            -\mathbf{A}^{-1}\mathbf{B}(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B})^{-1} \\ 
            -(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B})^{-1}\mathbf{CA}^{-1} & (\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B})^{-1}
        \end{bmatrix}
    \end{aligned} } \label{eq:lemma1}
\end{equation}

UDL decomposition

행렬 $\mathbf{M}$ LDU 뿐만아니라 UDL로도 분해될 수 있다. 아래와 같이 $\mathbf{B}$를 소거하기 위한 행렬을 곱해서 UL 행렬을 만들 수 있다.
\begin{equation}
    \begin{aligned}
         \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix}^{-1} 
        = 
         \begin{bmatrix}
            \mathbf{A} - \mathbf{BD}^{-1}\mathbf{C} & \mathbf{B} \\ \mathbf{0} & \mathbf{D} 
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix}^{-1} 
    \end{aligned}
\end{equation}

이 때, $\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C}$를 $\mathbf{D}$의 schur complement ($\mathbf{M}/\mathbf{D}$)라고 한다. 다음으로 대각 행렬 성분만 남기기 위해 아래와 같이 왼쪽에 행렬을 전개하면 UDL 분해가 마무리된다.
\begin{equation}
    \begin{aligned}
         \begin{bmatrix}
            \mathbf{A} - \mathbf{BD}^{-1}\mathbf{C} & \mathbf{B} \\ \mathbf{0} & \mathbf{D} 
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix}^{-1} 
        =
        \begin{bmatrix}
            \mathbf{I} & \mathbf{BD}^{-1} \\ \mathbf{0} & \mathbf{I}
        \end{bmatrix}
        \begin{bmatrix}
            \mathbf{A} - \mathbf{BD}^{-1}\mathbf{C} & \mathbf{0} \\ \mathbf{0} & \mathbf{D} 
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix}^{-1} 
    \end{aligned}
\end{equation}

$\mathbf{M}^{-1}$은 다음과 같이 UDL 행렬을 사용하여 전개할 수 있다.
\begin{equation}
    \boxed{ \begin{aligned}
          \begin{bmatrix}
            \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D}
        \end{bmatrix}^{-1} & = \begin{bmatrix}
            \mathbf{I} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{C} & \mathbf{I}
        \end{bmatrix} \begin{bmatrix}
            (\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C})^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{D}^{-1}
        \end{bmatrix} \begin{bmatrix}
            \mathbf{I} & -\mathbf{BD}^{-1} \\  \mathbf{0} & \mathbf{I}
        \end{bmatrix}
        \\ & = \begin{bmatrix}
            (\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C})^{-1} & -(\mathbf{A}-\mathbf{BD}^{-1}\mathbf{C})^{-1}\mathbf{BD} \\ 
            -\mathbf{D}^{-1}\mathbf{C}(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C})^{-1} & \mathbf{D}^{-1} + \mathbf{D}^{-1}\mathbf{C}(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C})^{-1}\mathbf{BD}
        \end{bmatrix}
    \end{aligned} } \label{eq:lemma2}
\end{equation}

Back to matrix inversion lemma

앞서 구한 (\ref{eq:lemma1}), (\ref{eq:lemma2})는 분해 방법만 달랐을 뿐 모든 원소는 서로 같아야 한다. 따라서 첫번째 원소를 비교해보면 다음과 같다.
\begin{equation}
    \begin{aligned}
         (\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C})^{-1} = \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B}(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B})^{-1}\mathbf{CA}^{-1}
    \end{aligned}
\end{equation}

해당 식에서 아래와 같이 기호만 변경해주면 matrix inversion lemma 식 (\ref{eq:lemma3})가 된다.
\begin{equation}
    \begin{aligned}
     \mathbf{B} & \rightarrow \mathbf{U} \\
     \mathbf{C} &\rightarrow \mathbf{V} \\
     \mathbf{D}^{-1} &\rightarrow -\mathbf{C}   \\
    \therefore (\mathbf{A} + \mathbf{UCV})^{-1} &= \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1} + \mathbf{VA}^{-1}\mathbf{U})^{-1}\mathbf{VA}^{-1}
    \end{aligned}
\end{equation}

또한 (\ref{eq:lemma1}), (\ref{eq:lemma2})의 두번째 원소를 비교하면 다음과 같다. 해당 식도 자주 사용되는 행렬 변환 트릭 중 하나이다.
\begin{equation}
    \boxed {\begin{aligned}
    -\mathbf{A}^{-1}\mathbf{B}(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B})^{-1} = -(\mathbf{A}-\mathbf{BD}^{-1}\mathbf{C})^{-1}\mathbf{BD}
    \end{aligned} }
\end{equation}

지금까지 소개한 matrix inversion lemma 행렬 변환 트릭은 칼만 필터(kalman filter)의 공식을 유도할 때 종종 사용되며 이외에도 많은 공학 분야에서 사용된다.
 

References

[1] (Lecture) 인공지능을 위한 선형대수 - 주재걸 교수님 (edwith)

[2] (Book) Kay, Steven M. Fundamentals of statistical signal processing: estimation theory. Prentice-Hall, Inc., 1993.
[3] (Blog) 다크프로그래머 - Gradient, Jacobian 행렬, Hessian 행렬, Laplacian
[4] (Blog) [행렬대수학] 행렬식(Determinant) 1 - 행렬식의 개념

[5] (Pdf) Pseudo Inverse 유도 과정
[6] (Youtube) Matrix Inversion Lemma 강의 영상 - 혁펜하임