TOP > 国内特許検索 > 行列の高速高精度特異値分解方法、プログラムおよび装置

行列の高速高精度特異値分解方法、プログラムおよび装置 新技術説明会 実績あり

国内特許コード P110003899
整理番号 K076P07
掲載日 2011年7月1日
出願番号 特願2006-514122
登録番号 特許第4325877号
出願日 平成17年6月1日(2005.6.1)
登録日 平成21年6月19日(2009.6.19)
国際出願番号 JP2005010084
国際公開番号 WO2005119507
国際出願日 平成17年6月1日(2005.6.1)
国際公開日 平成17年12月15日(2005.12.15)
優先権データ
  • 特願2004-166437 (2004.6.3) JP
発明者
  • 中村 佳正
  • 岩▲崎▼ 雅史
  • 阪野 真也
出願人
  • 独立行政法人科学技術振興機構
発明の名称 行列の高速高精度特異値分解方法、プログラムおよび装置 新技術説明会 実績あり
発明の概要

本発明による特異値分解方法は、コンピュータを用いて任意の行列Aに対して特異値分解を実行する方法であって、行列Aに対して上2重対角化を行い、行列Aの上2重対角行列Bを求めるステップと、行列Aの特異値として行列Bの特異値σを求めるステップと、σに対する行列Aの特異ベクトルを求めるステップとを包含する。行列Aの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σI(Iは単位行列)に対してツイスティッド分解を実行することにより、行列BBを対角化するステップを含む。

従来技術、競合技術の概要


現在、コンピュータ上で特異値分解を行うために用いられる標準的な方法は、国際的な数値計算ライブラリLAPACKにより公開されているDBDSQRルーチンである。DBDSQRルーチンは、QR法に基づいて作られたものであり、前処理、メインループ、後処理の3つの部分に分けることができる。前処理では、特異値の上限および下限を計算し、収束判定に用いる精度を計算する。メインループでは、QR法を繰り返しながら、除々に行列の分割および減次を行い、最終的に行列サイズが1となった時点でループを終了する。途中で2×2行列のブロックが現れたならば別処理を行う。後処理では、特異値として計算された値が負ならば正に直し、必要ならば特異ベクトルをスカラー倍する。特異値を降順に、それに対応するように特異ベクトルも並べ替える。DBDSQRは、計算量が非常に多く、特に大規模問題では計算時間の増大が避けられない。DBDSQRルーチンでは、特異値および特異ベクトルが同時に計算される。また、LAPACKには、特異値を計算するDLASQルーチン、および、計算された特異値を用いて特異ベクトルを計算する際に用いる対角化のためのDSTEGRルーチンがある。DLASQルーチンは、高速高精度に特異値を求めることができるが、特異ベクトルを計算できない。DSTEGRルーチンは、その数値的な欠点から、実際に特異値分解に使用することは難しい。



LAPACKによるDBDSQRルーチンを例として、従来の特異値分解方法を説明する。DBDSQRルーチンでは、l×lの一般行列Aを特異値分解するために、まず、行列Aに対してHouseholder(ハウスホルダー)変換を適用する。すなわち、行列Aは、直交行列U、Vを用いて、



【数式4】


と表わすことができる。このとき得られるBを、上2重対角行列という。ここで、Aの特異値=Bの特異値であることに注意する。このように、一般行列Aに対する特異値分解問題を上2重対角行列Bに対する特異値分解問題
B=UΣV
行列U、Vは、それぞれ左および右直交行列
Σ≡diag(σ,σ,・・・,σ) σ≧σ≧・・・≧σ≧0
σはBの特異値
に置き換える。



次に、行列BBを考える。この行列BBの対角化
Λ=VBV
Λ≡diag(λ,λ,・・・,λ) λ≧λ≧・・・≧λ≧0
V≡(v,v,・・・,v
λはBBの固有値
は固有値λに対する固有ベクトル
を行う。ここで、一般に、以下のことが成り立つ。(1)BBは対称な3重対角行列である。(2)BBの固有値は全て正であり、Bの特異値σ(σ≧σ≧・・・≧σ≧0)は、BBの固有値λ(λ≧λ≧・・・≧λ≧0)の正の平方根に等しい。(3)V=V、すなわち、BBの固有ベクトルvは、Bの右特異ベクトルに等しい。従って、行列BBの対角化が求まると、(2)よりΛ=Σであることから、Σが求まり、さらに(3)より左直交行列U=BVΣ-1=BVΣ-1が求まるので、Bが特異値分解される。すなわち、Bの特異値分解を、BBの対角化の問題に置き換えることができる。この原理は、m個全ての特異値および特異ベクトルを求める場合だけでなく、少なくとも1つの特異値および特異ベクトルを求める場合にも適用され得る。



以上のように、一般行列Aの特異値分解は、対称な3重対角行列BBの対角化の問題を含む。

産業上の利用分野


本発明は、任意の行列Aに対して高速かつ高精度に特異値分解を実行する方法、プログラムおよび装置に関し、より詳細には、行列の特異値を計算し、計算された特異値に対する特異ベクトルを計算することによって、高速かつ高精度に特異値分解を実行する方法、プログラムおよび装置に関する。

特許請求の範囲 【請求項7】 物体の複数の2次元画像から3次元画像を復元する方法であって、
2次元画像j(j=1,・・・,m、mは3以上の整数)における特徴点i(i=1,・・・,n、nは2以上の整数)の座標dij(xij,yij)を抽出するステップと、
該特徴点の2次元座標dij(xij,yij)より、該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算するステップと
を包含し、
該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算するステップは、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップであって、行列Dは、
【数式1】
と定義される、ステップと、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求めるステップと、
σ、σおよびσに対する行列Dの特異ベクトルを求めるステップと、
M=M’Cなる行列Cに対して、E=CCを満たす行列Eを計算するステップであって、M’=L’(Σ’)1/2、Σ’はσ、σおよびσを対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ、σおよびσに対応するDの特異ベクトルを左から順に並べた行列である、ステップと、
行列Eから、行列Cを計算するステップと、
行列Cから、該3次元座標s(X,Y,Z)および該変換を表す行列Mを計算するステップと
を含み、
該σ、σおよびσに対する行列Dの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σIに対してツイスティッド分解を実行することにより、行列BBを対角化するステップを含み、Iは単位行列である、方法。
【請求項8】 与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する方法であって、
該キーワードに対応する質問ベクトルqを受け取るステップと、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップと、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求めるステップと、
k<rなるkを選択するステップと、
行列Dの擬似行列Dを計算するステップであって、行列Dは、σ,σ,・・・,σを対角要素としそれ以外の要素が0である行列Σ、σ,σ,・・・,σに対応する特異ベクトルのみを左から順に並べた左右直交行列U,Vを用いて、D=UΣと定義される、ステップと、
行列Dと質問ベクトルqとの類似度を計算するステップと、
該計算された類似度を基準に、検索結果を出力するステップと
を包含し、
該行列Dの左右直交行列U,Vを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σI(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BBを対角化するステップを含み、Iは単位行列である、方法。
【請求項10】 物体の複数の2次元画像から3次元画像を復元する画像復元処理をコンピュータに実行させるプログラムであって、
該画像復元処理は、
2次元画像j(j=1,・・・,m、mは3以上の整数)における特徴点i(i=1,・・・,n、nは2以上の整数)の座標dij(xij,yij)を抽出するステップと、
該特徴点の2次元座標dij(xij,yij)より、該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算するステップと
を包含し、
該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算するステップは、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップであって、行列Dは、
【数式2】
と定義される、ステップと、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求めるステップと、
σ、σおよびσに対する行列Dの特異ベクトルを求めるステップと、
M=M’Cなる行列Cに対して、E=CCを満たす行列Eを計算するステップであって、M’=L’(Σ’)1/2、Σ’はσ、σおよびσを対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ、σおよびσに対応するDの特異ベクトルを左から順に並べた行列である、ステップと、
行列Eから、行列Cを計算するステップと、
行列Cから、該3次元座標s(X,Y,Z)および該変換を表す行列Mを計算するステップと
を含み、
該σおよびσに対する行列Dの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σIに対してツイスティッド分解を実行することにより、行列BBを対角化するステップを含み、Iは単位行列である、プログラム。
【請求項11】 与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する文書検索処理をコンピュータに実行させるプログラムであって、
該文書検索処理は、
該キーワードに対応する質問ベクトルqを受け取るステップと、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップと、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求めるステップと、
k<rなるkを選択するステップと、
行列Dの擬似行列Dを計算するステップであって、行列Dは、σ,σ,・・・,σを対角要素としそれ以外の要素が0である行列Σ、σ,σ,・・・,σに対応する特異ベクトルのみを左から順に並べた左右直交行列U,Vを用いて、D=UΣと定義される、ステップと、
行列Dと質問ベクトルqとの類似度を計算するステップと、
該計算された類似度を基準に、検索結果を出力するステップと
を包含し、
該行列Dの左右直交行列U,Vを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σI(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BBを対角化するステップを含み、Iは単位行列である、プログラム。
【請求項13】 物体の複数の2次元画像を3次元画像に復元する装置であって、
m枚(mは3以上の整数)の2次元画像を受け取る手段と、
2次元画像j(j=1,・・・,m)における特徴点i(i=1,・・・,n、nは2以上の整数)の座標dij(xij,yij)を抽出する手段と、
該特徴点の2次元座標dij(xij,yij)より、該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算する手段と
を備え、
該特徴点の3次元座標s(X,Y,Z)および2次元座標から3次元座標への変換を表す行列Mを計算する手段は、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求める手段であって、行列Dは、
【数式3】
と定義される、手段と、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求める手段と、
σ、σおよびσに対する行列Dの特異ベクトルを求める手段と、
M=M’Cなる行列Cに対して、E=CCを満たす行列Eを計算する手段であって、M’=L’(Σ’)1/2、Σ’はσ、σおよびσを対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ、σおよびσに対応するDの特異ベクトルを左から順に並べた行列である、手段と、
行列Eから、行列Cを計算する手段と、
行列Cから、該3次元座標s(X,Y,Z)および該変換を表す行列Mを計算する手段と
を含み、
該σ、σおよびσに対する行列Dの特異ベクトルを求める手段は、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σIに対してツイスティッド分解を実行することにより、行列BBを対角化する手段を含み、Iは単位行列である、装置。
【請求項14】 与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する装置であって、
該キーワードに対応する質問ベクトルqを受け取る手段と、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求める手段と、
行列Dの特異値として行列Bの特異値σ(σ≧σ≧・・・≧σ>0、rは、行列Dのランクに等しい)を求める手段と、
k<rなるkを選択する手段と、
行列Dの擬似行列Dを計算する手段であって、行列Dは、σ,σ,・・・,σを対角要素としそれ以外の要素が0である行列Σ、σ,σ,・・・,σに対応する特異ベクトルのみを左から順に並べた左右直交行列U,Vを用いて、D=UΣと定義される、手段と、
行列Dと質問ベクトルqとの類似度を計算する手段と、
該計算された類似度を基準に、検索結果を出力する手段と
を包含し、
該行列Dの左右直交行列U,Vを求める手段は、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BB-σI(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BBを対角化する手段を含み、Iは単位行列である、装置。
産業区分
  • 計算機応用
国際特許分類(IPC)
Fターム
出願権利状態 権利存続中
参考情報 (研究プロジェクト等) さきがけ シミュレーション技術の革新と実用化基盤の構築 領域
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。


PAGE TOP

close
close
close
close
close
close
close