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}$を計算する。