콜레스키 분해를 통한 최소제곱법
알고리즘
$A \in \mathbb{C}^{m \times n}$ 과 벡터 $\mathbf{b} \in \mathbb{C}^{m}$ 에 대해 $\text{rank} A = n$ 이고 $A \mathbf{x} = \mathbf{b}$ 의 최소제곱해를 $\mathbf{x}_{\ast}$ 이라고 하자.
Step 1.
주어진 방정식의 양변에 $A^{\ast}$ 을 곱해 표준방정식 $A^{\ast} A \mathbf{x} = A^{\ast} \mathbf{b}$ 을 세운다.
표준방정식의 해는 원래 방정식의 최소제곱해가 되므로, 표준방정식의 해 $\mathbf{x}$ 를 구하면 된다.
Step 2.
$\mathbf{y} := A^{\ast} \mathbf{b}$ 을 계산해 $A^{\ast} A \mathbf{x} = \mathbf{y}$ 을 얻는다.
Step 3. 콜레스키 분해
$A^{\ast} A = L L^{\ast}$ 을 만족하는 하삼각행렬 $L$ 을 구해 $L L^{\ast} \mathbf{x} = \mathbf{y}$ 을 얻는다.
Step 4. 전진대입법
$L L^{\ast} \mathbf{x} = \mathbf{y}$ 에서 $L^{\ast} \mathbf{x} : = \mathbf{w}$ 이라고 하면 $L \mathbf{w} = \mathbf{y}$
$L$ 은 하삼각행렬이므로 전진대입법을 통해 $\mathbf{w}$ 에 대한 방정식의 해를 구한다
Step 5. 후진대입법
$\mathbf{w}$ 을 구했고 $L^{\ast}$ 는 상삼각행렬이므로 후진대입법을 통해 $\mathbf{x}$ 에 대한 방정식 $L^{\ast} \mathbf{x} = \mathbf{w}$ 의 해를 구한다.
설명
콜레스키 분해는 본래 분해할 행렬이 양의 정부호 행렬이어야 한다는 강력한 조건이 있었다. 이 방법에서 핵심은 표준방정식을 세우는 트릭을 통해 그 까다로운 조건을 강제로 만족시켜버리는 것에 있다. 물론 그 트릭에는 $A^{\ast} A$ 가 양의 정부호라는 보장이 있어야하고, 그 증명은 그리 어렵지 않게 할 수 있다.
정리
행렬 $A \in \mathbb{C}^{m \times n} (m \ge n)$ 에 대해 $A^{\ast} A > 0 \iff \text{rank} A = n$
증명
임의의 벡터 $\mathbf{v} \ne \mathbb{0}$ 에 대해
$$ \mathbf{v}^{\ast} A^{\ast} A \mathbf{v} = (A \mathbf{v})^{\ast} A \mathbf{v} = | A \mathbf{v} |^{2} \ge 0 $$
이므로 $A^{\ast} A \ge 0$ 이다. $A^{\ast} A$ 의 역행렬이 존재하지 않는다고 가정하면 $A^{\ast} A \mathbf{v} = \mathbb{0}$ 를 만족하는 $\mathbf{v} \ne \mathbb{0}$ 이 존재한다. 위 식에서 양변의 왼쪽에 $\mathbf{v}^{\ast}$ 을 곱하면 $| A \mathbf{v} |^2 = 0$ 이고 놈의 정의에서 $A \mathbf{v} = 0$ 이다. 이는 $A$ 의 열벡터들이 일차종속이라는 뜻이므로 $\text{rank} A < n$ 이 된다.
역으로 $\text{rank} A < n$ 이라고 가정하면 $A \mathbf{v} = \mathbb{0}$ 을 만족하는 $\mathbf{v} \ne \mathbb{0}$ 가 존재한다.
위 식에서 양변의 왼쪽에 $A^{\ast}$ 을 곱하면 $A^{\ast} A \mathbf{v} = \mathbb{0}$ 이고, $A^{\ast} A$ 은 역행렬이 존재하지 않는다. $A^{\ast}A \ge 0$ 이고
$$ A^{\ast} A \ne 0 \iff \text{rank} A = n $$
이므로,
$$ A^{\ast} A > 0 \iff \text{rank} A = n $$
■