同次式の最小二乗問題

同次式(Homogeneous Equations)とは

同次式とは,すべての項の次数が等しい多項式を言います.下記に一例を示します.
f:id:rkoichi2001:20180318163935j:plain

逆に,下記のような例は項の次数が異なっているため,非同次式(Non Homogeneous Equations)といいます.
f:id:rkoichi2001:20180318164135j:plain

同次式の最小二乗問題

非同次式の最小二乗法問題は, Ax =b を満たすベクトル x を求めるという問題で,実用上多く見かけます.通常コンピュータビジョンでこの問題を解くときは,方程式の未知数よりも多いデータが与えられるけどもそれぞれのデータが少しずつノイズを含んでいるために最小二乗法を用いて誤差が一番少ないベクトル x を求めます.今回の同次式の最小二乗法問題では, Ax = 0 となるベクトル x を求めます.x = 0 は当たり前に成り立つので,求めたい解は x = 0 以外のものになります.例としては,複数の二次元点が与えられたときに,近似直線を求める問題です.
f:id:rkoichi2001:20180318165325j:plain

また,コンピュータビジョンでは楕円当てはめをすることがありますが,これも同次式の最小二乗問題として考えることができます.
f:id:rkoichi2001:20180318171007j:plain

同次式の最小二乗問題の特徴

当時式の最小二乗解には次の二つの特徴があります.
1.x = 0 は常に解になる.が,これは当たり前.
2.x ≠ 0 が解になったばあい,このスカラー倍 kx も同様に解になる.

上記の2番の特徴から,ベクトル x は大きさが不定になることがわかります.つまり,もう一つ条件を付けてあげる必要があります.追加の条件としては,下記の条件がよくつかわれます.
f:id:rkoichi2001:20180318172347j:plain

同次式の最小二乗問題の定義

下記,同次式の最小二乗問題の定義です.
f:id:rkoichi2001:20180318172202j:plain

同次式の最小二乗問題の解

ここでようやく特異値分解を使って解を求めます.簡単のために,上記ノートの B を I とします.この簡単化によって,解の不定性を取り除くための条件は「解ベクトルのノルムが1となるもの」となります.
行列 A が下記のように特異値分解できたとすると,,,,
f:id:rkoichi2001:20180318174516j:plain

このAの特異値分解を用いて,最小化すべき式 ||Ax|| = 0 を書き直すと下記のようになります.
f:id:rkoichi2001:20180318175605j:plain

最終的に y を求める問題になりましたが,行列 S は 行列 A の特異値を対角成分に持つ行列で,かつ || y || = 1 より y は単位ベクトルとなるので,y は A の最小特異値に対応するベクトルとなり,肝心の x は下記のようになります.
f:id:rkoichi2001:20180318180424j:plain