logo

特異値分解による最小二乗法 📂行列代数

特異値分解による最小二乗法

アルゴリズム

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