1. 양의 정부호 행렬

양의 정부호(positive definite) 행렬이란 0이 아닌 어떤 벡터 $\mathbf{x}$가 주어졌을 때, 다음을 만족하는 대칭행렬 $\mathbf{A}$이다.

만약 다음을 만족한다면 양의 준정부호(positive semidefinite) 행렬이라고 한다.

$\mathbf{x}$에 양의 정수 2를 곱하였을 때 $\mathbf{x}^T \cdot 2\mathbf{x}$은 두 개의 같은 방향 벡터 곱이기 때문에 양수가 되지만, 음의 정수 -2를 곱하면 $\mathbf{x}^T \cdot -2\mathbf{x}=-2|\mathbf{x}|$가 되어 음수가 된다. 이때, 양의 정부호 행렬은 마치 양의 정수처럼 어떤 벡터에 곱하여도 그 방향에 따른 부호가 유지됨을 의미한다.

양의 정부호 행렬은 여러가지 성질을 갖는다. 우선 위의 식에 나온 $\mathbf{x}^T\mathbf{A}\mathbf{x}$은 다음과 같은 2차식을 의미한다.

또한 양의 정부호 행렬은 non-singular하여 역행렬을 갖는다. 아래의 마지막 단계에서 양의 정부호 행렬 정의가 사용되었다.

또한 $\mathbf{e_i}=(0,0,\cdots,0,1_{ith\;element},0,0,\cdots,0)$라고 하면 $\mathbf{e_i}^T\mathbf{A}\mathbf{e_i}=A_{ii}>0$이므로 양의 정부호 행렬의 대각 성분은 모두 양수이다.

만약 행렬 $\mathbf{A}$의 고유값 $\lambda=0$이라면 그에 해당하는 고유벡터 $\mathbf{x}$에 대해서 $\mathbf{x}^T\mathbf{A}\mathbf{x}=\mathbf{x}^T\lambda\mathbf{x}=\lambda|\mathbf{x}|^2$가 0이 되어버린다. 마찬가지로 $\lambda<0$이라면 위의 값이 음수가 되어버린다. 따라서 양의 정부호행렬의 고유값은 모두 양수이다.

그리고, $\mathbf{A}^T\mathbf{A}$가 주어지면 이는 positive semidefinite 행렬이며, 이는 $\mathbf{A}\mathbf{x}=\mathbf{y}$라 할 때, $\mathbf{x}^T\mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{y}^T\mathbf{y} \ge0$으로 보일 수 있다.

또한 $\mathbf{A}$의 column vector들이 일차독립임과 $\mathbf{A}^T\mathbf{A}$는 positive definite라는 것은 동치이며, 이때 $\mathbf{A}^T\mathbf{A}$는해당 가역행렬이다.

먼저 positive definite가 아니라고 가정할 때 $\mathbf{0}$이 아닌 벡터 $\mathbf{c}$에 대해서 $\mathbf{c}^T\mathbf{A}^T\mathbf{A}\mathbf{c}=\mathbf{y}^T\mathbf{y}=|\mathbf{y}|\le0$인 $\mathbf{c}$가 존재해야하는데, $|\mathbf{y}|<0$라면 $\mathbf{y}$가 실수가 아니게 되며, $\mathbf{y}=\mathbf{A}\mathbf{c}=0$이라면, $\mathbf{A}$의 column vector들이 일차독립이라는 가정에 모순이다. 따라서 $\mathbf{A}$의 column vector들이 일차독립이면, $\mathbf{A}^T\mathbf{A}$는 positive definite이다.

반대로 $\mathbf{A}^T\mathbf{A}$가 positive definite라면, 임의의 $\mathbf{0}$이 아닌 벡터 $\mathbf{c}$에 대해서 $\mathbf{c}^T\mathbf{A}^T\mathbf{A}\mathbf{c}=|\mathbf{A}\mathbf{c}|>0$이며, $\mathbf{A}\mathbf{c}$가 0이 아니므로 $\mathbf{A}$의 column vector들이 일차독립이다.

$\mathbf{A}$의 column vector들이 일차독립이라면, QR decomposition이 가능하여 $\mathbf{A}^T\mathbf{A}=(\mathbf{Q}\mathbf{R})^T\mathbf{Q}\mathbf{R}=\mathbf{R}^T\mathbf{Q}^T\mathbf{Q}\mathbf{R}=\mathbf{R}^T\mathbf{R}$인데, $\mathbf{R}$은 삼각행렬로 가역행렬이므로 $\mathbf{R}^T\mathbf{R}=\mathbf{A}^T\mathbf{A}$또한 가역행렬이다.

2. Cholesky Decomposition

Cholesky decomposition은 임의의 양의 정부호 행렬이 다음과 같이 상삼각행렬 $\mathbf{R}$로 분해될 수 있다는 것이다.

$\mathbf{R}^T\mathbf{R}$은 다음과 같이 블록행렬로 쓸 수 있다..

이때, $\mathbf{R}^T\mathbf{R} = \mathbf{A}$를 만족하기 위하여 다음과 같이 $\mathbf{R}$의 원소를 선택할 수 있다.

이것으로 첫번째 row/column이 결정되고, $\mathbf{A}$가 양의 정부호 행렬이기 때문에 제곱근 및 나누기를 사용할 수 있다. 이제 다음 step을 위한 $R_{2:n,2:n}^TR_{2:n,2:n}$를 구하면 다음과 같다.

이때, Schur complement로 인해 $A_{2:n,2:n}-\frac{1}{A_{1,1}}A_{2:n, 1}A_{2:n, 1}^T$ 또한 양의 정부호 행렬이며, 따라서 $R_{2:n,2:n}^TR_{2:n,2:n}$에 대해 위와 같은 방법을 적용하여 두번째, 세번째, ...의 row/column을 구할 수 있다.

Schur complement은 양의 정부호 행렬 $\mathbf{A}$가 주어졌을 때, $\mathbf{S}=A_{2:n,2:n}-\frac{1}{A_{1,1}}A_{2:n, 1}A_{2:n, 1}^T$ 또한 양의 정부호 행렬이라는 것으로, 다음과 같이 보일 수 있다 (임의의 벡터 $\mathbf{x}$에 대해 $\mathbf{y} = -(A_{2:n, 1}^T\mathbf{x})/A_{1,1})$).

결국 $\mathbf{x}^T\mathbf{S}\mathbf{x}$는 $(\mathbf{y}, \mathbf{x})\mathbf{A}(\mathbf{y}, \mathbf{x})^T$와 같은 형태로 나타나며, $\mathbf{A}$는 양의 정부호 행렬이기 때문에 마지막 부등호가 성립하고, 따라서 $\mathbf{S}$ 또한 양의 정부호 행렬이다.