특이값 분해를 통한 최소제곱법

특이값 분해를 통한 최소제곱법

알고리즘

$A \in \mathbb{C}^{m \times n}$ 과 벡터 $\mathbb{b} \in \mathbb{C}^{m}$ 에 대해 $\text{rank} A = n$ 이고 $A \mathbb{x} = \mathbb{b}$ 의 최소제곱해를 $\mathbb{x}_{\ast}$ 이라고 하자.

Step 1. 특이값 분해

$A = \widehat{U} \widehat{\Sigma} V^{\ast}$ 를 만족하는 정규직교행렬 $\widehat{U}$ 과 대각행렬 $\widehat{\Sigma}$ 과 유니터리 행렬 $V$ 를 구한다.


Step 2.

특이값 분해에서 얻은 $\widehat{U}$ 를 통해 정사영 $P : = \widehat{U} \widehat{U}^{\ast}$ 을 구한다.

$A \mathbb{x}_{\ast} = P \mathbb{b}$ 이므로 $\widehat{U} \widehat{\Sigma} V^{\ast} \mathbb{x}_{\ast} = \widehat{U} \widehat{U}^{\ast} \mathbb{b}$ 이고 양변의 왼쪽에 $\widehat{U}^{\ast}$ 을 곱해 $\widehat{\Sigma} V^{\ast} \mathbb{x}_{\ast} = \widehat{U}^{\ast} \mathbb{b}$ 를 얻는다.


Step 3.

$\mathbb{y} := \widehat{U}^{\ast} \mathbb{b}$ 를 계산해 $\widehat{\Sigma} V^{\ast} \mathbb{x}_{\ast} = \mathbb{y}$ 를 얻는다.


Step 4.

$\widehat{\Sigma} V^{\ast} \mathbb{x}_{\ast} = \mathbb{y}$ 에서 $\mathbb{w} : = V^{\ast} \mathbb{x}_{\ast}$ 라 두고 $\mathbb{w}$ 에 대한 방정식 $\widehat{\Sigma} \mathbb{w} = \mathbb{y}$ 의 해를 구한다.


Step 5.

$V$ 는 유니터리 행렬이므로 $\mathbb{x}_{\ast} = V \mathbb{w}$ 를 계산한다.


댓글