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

卒論でも修論でも扱ったにも関わらず、未だに導出方法を忘れ毎度ググってしまうので、ここにまとめておきたいと思います。今回は私の専門分野である CG や HCI に限らず一般的な話題です。

以下、記述が長くなると大変なので、厳密でない表現をところどころ用いています。

優決定系の線形方程式

大雑把にいって、優決定系 (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}
}

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

微分を計算する際には「行列やベクトルをベクトルで微分するための公式」をいくつか使用しました。
下記の記事が参考になります。
村田研究室 早稲田大学 先進理工学部 電気・情報生命工学科の研究室 | 村田研究室 - 早稲田大学 先進理工学部 電気・情報生命工学科
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