スペクトル分解を実際に行ってみる
2008-05-31 - malibu-bulldogの日記
の続きです。
このうち固有値は実対称行列なのですべて実数になり、ラプラシアンマトリックスの性質上最小の固有値は0というのは前回の日記で書きました。
さて、イエール大学（普通はエール大学だよと知り合いに突っ込まれましたがなんとなくイエールで通します）のDanさんの講義ノートSpectral Graph Theory and its Applicationsを読んでいくと、この固有値に対応する固有ベクトルについての説明があります。
固有値ベクトルは、グラフ構造でいう各ノードに対して新しい意味のある値を与えていると。
どんな意味があるのかはまだはっきりしたことは言えないそうです。（これからの研究らしいです）
さて、僕の身近にあるグラフ構造というと…3DCGのメッシュデータがあります。
ポリゴンは辺を介して隣のポリゴンに接していると言えます。
例えば三角形なら三つの辺を介して隣の三角形と隣接している状態になります。
このポリゴンのデータを使って、ラプラシアン行列を作り固有値と固有ベクトルを求めてみるとどうなるか？
このように5×5の25個の四角形で構成されたポリゴンデータからラプラシアン行列を作ってみます。
各四角形に一意の番号が振られているとして、それぞれの隣接関係は
2 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 2 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 3 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 4 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 2 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 2
となります。
四隅が隣接数が２、四隅以外の外側が３です。
この行列の固有値のうち、２番目に小さいものをFiedler valueといい、それに対応する固有ベクトルをFiedler vectorというそうです。
このFiedler vectorを使って横軸に各四角形の番号を、縦軸に対応するベクトルの成分でグラフをプロットしみると
なにやら面白いものが出てきました。
では、縦軸がプラスかマイナスかで場合わけしてグループ化しみると、
このようにほぼ半分に分ける事ができました。
これを利用してポリゴンデータを細かく分割できそうです。
