logo

특이값 분해를 통한 최소제곱법 📂행렬대수

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

알고리즘

$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 = \widehat{U} \widehat{\Sigma} V^{\ast}$ 를 만족하는 직교행렬 $\widehat{U}$ 과 대각행렬 $\widehat{\Sigma}$ 과 유니터리 행렬 $V$ 를 구한다.

Step 2.

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

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

Step 3.

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

Step 4.

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

Step 5.

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