コレスキー分解による最小二乗法
アルゴリズム
$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 $$
■