最適化計算1 直線の当てはめ 理論編

最近の投稿,行列やら最適化やら数学ネタ中心の投稿が続いてますが,これ全部「三次元復元」の理解のためです.おもった以上に数学のハードルが高く,一度きっちりと勉強しようと思いやり始めたらまあ時間がかかること...ここからは最適化の勉強をしていきます.今回の投稿では,ノイズを含むデータに対して直線を当てはめるという一番基本的なケースですが,主に金谷先生・菅谷先生の本・論文を拾い集めてきてまとめます.

1.直線当てはめ問題

実験で取得したデータをプロットしてまとめることって,高校とか大学の実験で結構やったと思います.実験なので所得したデータが何か既知の理論式に支配されているという前提で進めると思うのですが,取得データにはもちろん誤差が含まれるので完全にきれいには直線に乗りません.この時に,エクセルとか使って「一番それっぽい直線」を計算して求めたと思います.この「一番それっぽい直線」を求めるのが直線当てはめ問題です.
f:id:rkoichi2001:20180326072517j:plain

2.一番それっぽい直線とは??

問題設定で「一番それっぽい直線」と書きましたが,「一番それっぽい」の定義を決めてあげないといけません.この種の直線当てはめ問題では,最小二乗法がよくつかわれますが,最小二乗法で使う評価式は下記になります.
f:id:rkoichi2001:20180326073727j:plain

上記の評価式ですが,実験で取得したデータが理論的には何かの直線上 "Ax + By + C = 0" に存在するとしたときに, それぞれの取得データ(点)と直線の距離が最も小さくなるような直線を求めています. ちなみに,直線を "y = ax + b" として最小二乗法を計算すると,評価式は下記のようになります.
f:id:rkoichi2001:20180326075622j:plain

この評価式では,評価データと直線の距離が最も小さくなるような直線ではなく,理論式と実験データの y の値のずれが最も小さくなる直線を計算しています.x を実験時に比較的正確に入力できるような場合はこちらのほうが感覚的には有用な気がしますね.

3.計算方法

計算方法ですが,自分が勉強した感じ,1.評価式の微分を 0 として計算する方法2.評価式を二次形式に変換して固有値問題に帰着させる方法の二つがありましたが,ここでは2の線形代数アプローチで計算方法を求めてみます.

満たしたい方程式

まず,取得データが直線に乗るはずだという前提があると思いますので,下記の連立一次方程式群ができます.
f:id:rkoichi2001:20180326081530j:plain

上記Px = 0 をできる限り満たすベクトル x を求めるために,最小二乗法の評価式を使います.
f:id:rkoichi2001:20180327060935j:plain

式変換から,評価式が二次形式になりました.ここで,PTP=M は実対称行列であり,このことよりMは
1.固有値固有ベクトルすべて実数
2.対角化できる
ので,スペクトル分解して最小固有値を計算してあげれば最小固有値に対応する単位ベクトルが求める直線の係数ベクトルになります.

行列Mのスペクトル分解

n x n の対称行列 M に対して,n個の固有値 λ1, λ2, ... λn が存在し,対応する固有ベクトルは互いに直交するので,この正規直交系を u1, u2, ... un とします.この時,正規直交系からなる行列 U は直交行列であり M は下記のように対角化できます.
f:id:rkoichi2001:20180327061433j:plain

上記スペクトル分解を用いて評価式の二次形式を再度考察します.
f:id:rkoichi2001:20180327063154j:plain

ということで,最小固有値に対する固有ベクトル x が直線のパラメータとなることがわかります.

4.最小2乗法

つまり,,,,整理して書くとこの問題は下記のようになります.
f:id:rkoichi2001:20180327064557j:plain

参考文献

参考文献1

3次元コンピュータビジョン計算ハンドブック

3次元コンピュータビジョン計算ハンドブック

参考文献2
画像の三次元理解のための最適化計算[Ⅰ]