抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本報告ではPower Iterationによる第1固有値,固有ベクトル計算の高速化について検討する。パターン認識やコンピュータ・ビジョンの問題には,主成分分析や判別分析など,固有値問題に帰着する問題は多数存在する。通常,n×nの行列の固有値問題を解く際には,QR分解など全ての非ゼロ固有値に対応する固有ベクトルを求めるO(n
3)のアルゴリズムがよく使われる。しかし,行列の第1固有ベクトルのみが必要なタスクも多くあり,そのようなタスクでは,計算量がO(n
2)であるPower Iterationを用いることができる。これは,適当な初期ベクトルx
0に行列Aを左から十分な回数かけ,A
nx
0/||A
nx
0||が収束するまで計算を反復する手法である。この結果はAの第1固有ベクトルに収束することが知られている。Power Iterationは,Aの第1固有値と,他の固有値の比の絶対値によって,収束の速度が変化する。例えば,第1固有値と第2固有値の比の絶対値が1に近い場合,収束に要する回数が増大する。この問題を回避する二通りの方法がある。一つは,数列の収束加速法を用いる方法,もう一つは,行列Aの固有値をずらすことで収束回数を減らす方法である。本報告では,これらの手法を融合することによるさらなる高速化法を提案し,収束に要する行列とベクトルの乗算回数について,実験を通じて比較し,オリジナルのPower Iterationよりも少なくとも2倍以上の高速化ができることを確認した。(著者抄録)