優決定系の線形方程式の最小二乗解を与える際の式変形（導出）

注意：本記事では厳密でない表現を随所に用いています。

優決定系の線形方程式

大雑把にいって、優決定系 (overdetermined system) とは変数の数に対して制約式が多く、解が存在しないような問題です。

線形方程式

$\displaystyle{\mathbf{A}\mathbf{x}=\mathbf{b}}$
において、行列 $\mathbf{A}$ が縦長の場合が優決定系と考えると簡単です。

最小二乗解

このような場合、解が存在しないので、近似解を求めることになります。

そこで、残差 $\mathbf{A}\mathbf{x}-\mathbf{b}$ を二乗した値が最小になるような近似解を求める (最小二乗法, least squares method) ということがよく行われます。つまり近似解 $\mathbf{x}^*$ を

$\displaystyle{ \mathbf{x}^{*}= \mathrm{aug} \min_{\mathbf{x}} || \mathbf{A}\mathbf{x}-\mathbf{b} ||^2 }$
と定め、これを求めるようにします。

結論からいうと、そのような最小二乗解は、線形方程式

$\displaystyle{ \mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{A}^T\mathbf{b} }$
を解くことで得られます。これは正規方程式とか呼ばれたりするらしいです。

プログラミングするときは、正規方程式はコレスキー分解とか LU 分解を使って解を求めます。私は Eigen というライブラリを使って計算しています。少し前までは boost の uBLAS を使っていました。

正規方程式の導出

基本的には、最小化したい部分 $|| \mathbf{A}\mathbf{x}-\mathbf{b} ||^2$ をベクトル $\mathbf{x}$ で微分して、それが $\mathbf{0}$ になるような $\mathbf{x}$ を求めるという流れになります。

微分すると

$\displaystyle{ \frac{d}{d\mathbf{x}} || \mathbf{A}\mathbf{x}-\mathbf{b} ||^2 \\ =\frac{d}{d\mathbf{x}}(\mathbf{A}\mathbf{x}-\mathbf{b})^T(\mathbf{A}\mathbf{x}-\mathbf{b}) \\ =\frac{d}{d\mathbf{x}}\mathbf{x}^T\mathbf{A}^T\mathbf{A}\mathbf{x}-\frac{d}{d\mathbf{x}}\mathbf{b}^T\mathbf{A}\mathbf{x}-\frac{d}{d\mathbf{x}}\mathbf{x}^T\mathbf{A}^T\mathbf{b}+\frac{d}{d\mathbf{x}}\mathbf{b}^T\mathbf{b} \\ =(\mathbf{A}^T\mathbf{A}+(\mathbf{A}^T\mathbf{A})^T)\mathbf{x}-\mathbf{A}^T\mathbf{b}-\mathbf{A}^T\mathbf{b}-\mathbf{0} \\ =2(\mathbf{A}^T\mathbf{A}\mathbf{x}-\mathbf{A}^T\mathbf{b}) }$
ですので、結局
$\displaystyle{ \frac{d}{d\mathbf{x}} || \mathbf{A}\mathbf{x}-\mathbf{b} ||^2=\mathbf{0} \Rightarrow \mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{A}^T\mathbf{b} }$

となることから、正規方程式が得られます。

~~微分を計算する際には「行列やベクトルをベクトルで微分するための公式」をいくつか使用しました。~~
~~下記の記事が参考になります。~~
~~http://www.eb.waseda.ac.jp/murata/junichi.mimura/knowledgh.html~~
~~everything is photogenic~~
~~追記 (2015/07/12)：上記記事がリンク切れになっていたようなので、別の記事を紹介します：~~
~~http://sci-tech.ksc.kwansei.ac.jp/~inagai/self_study/self_study.html~~
追記 (2016/09/20)：追記したものもリンク切れになってしまったようなので、行列やベクトルに関する微分については次の記事に随時まとめていこうと思います：
yuki-koyama.hatenablog.com