Top > Search of Japanese Patents > (In Japanese)行列の高速高精度特異値分解方法、プログラムおよび装置

(In Japanese)行列の高速高精度特異値分解方法、プログラムおよび装置 meetings achieved

Patent code P110003899
File No. K076P07
Posted date Jul 1, 2011
Application number P2006-514122
Patent number P4325877
Date of filing Jun 1, 2005
Date of registration Jun 19, 2009
International application number JP2005010084
International publication number WO2005119507
Date of international filing Jun 1, 2005
Date of international publication Dec 15, 2005
Priority data
  • P2004-166437 (Jun 3, 2004) JP
Inventor
  • (In Japanese)中村 佳正
  • (In Japanese)岩▲崎▼ 雅史
  • (In Japanese)阪野 真也
Applicant
  • (In Japanese)国立研究開発法人科学技術振興機構
Title (In Japanese)行列の高速高精度特異値分解方法、プログラムおよび装置 meetings achieved
Abstract (In Japanese)本発明による特異値分解方法は、コンピュータを用いて任意の行列Aに対して特異値分解を実行する方法であって、行列Aに対して上2重対角化を行い、行列Aの上2重対角行列Bを求めるステップと、行列Aの特異値として行列Bの特異値σを求めるステップと、σに対する行列Aの特異ベクトルを求めるステップとを包含する。行列Aの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σ2I(Iは単位行列)に対してツイスティッド分解を実行することにより、行列BTBを対角化するステップを含む。
Outline of related art and contending technology (In Japanese)

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

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

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

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

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

Field of industrial application (In Japanese)

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

Scope of claims (In Japanese)
【請求項7】
 
物体の複数の2次元画像から3次元画像を復元する方法であって、
2次元画像j(j=1,・・・,m、mは3以上の整数)における特徴点i(i=1,・・・,n、nは2以上の整数)の座標dij(xij,yij)を抽出するステップと、
該特徴点の2次元座標dij(xij,yij)より、該特徴点の3次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算するステップと
を包含し、
該特徴点の3次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算するステップは、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップであって、行列Dは、
【数1】
 
(省略)
と定義される、ステップと、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求めるステップと、
σ1、σ2およびσ3に対する行列Dの特異ベクトルを求めるステップと、
M=M’Cなる行列Cに対して、E=CCTを満たす行列Eを計算するステップであって、M’=L’(Σ’)1/2、Σ’はσ1、σ2およびσ3を対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ1、σ2およびσ3に対応するDの特異ベクトルを左から順に並べた行列である、ステップと、
行列Eから、行列Cを計算するステップと、
行列Cから、該3次元座標si(Xi,Yi,Zi)および該変換を表す行列Mを計算するステップと
を含み、
該σ1、σ2およびσ3に対する行列Dの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2Iに対してツイスティッド分解を実行することにより、行列BTBを対角化するステップを含み、Iは単位行列である、方法。

【請求項8】
 
与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する方法であって、
該キーワードに対応する質問ベクトルqを受け取るステップと、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップと、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求めるステップと、
k<rなるkを選択するステップと、
行列Dの擬似行列Dkを計算するステップであって、行列Dkは、σ1,σ2,・・・,σkを対角要素としそれ以外の要素が0である行列Σk、σ1,σ2,・・・,σkに対応する特異ベクトルのみを左から順に並べた左右直交行列Uk,Vkを用いて、Dk=UkΣkVkTと定義される、ステップと、
行列Dkと質問ベクトルqとの類似度を計算するステップと、
該計算された類似度を基準に、検索結果を出力するステップと
を包含し、
該行列Dkの左右直交行列Uk,Vkを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2I(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BTBを対角化するステップを含み、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次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算するステップと
を包含し、
該特徴点の3次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算するステップは、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップであって、行列Dは、
【数2】
 
(省略)
と定義される、ステップと、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求めるステップと、
σ1、σ2およびσ3に対する行列Dの特異ベクトルを求めるステップと、
M=M’Cなる行列Cに対して、E=CCTを満たす行列Eを計算するステップであって、M’=L’(Σ’)1/2、Σ’はσ1、σ2およびσ3を対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ1、σ2およびσ3に対応するDの特異ベクトルを左から順に並べた行列である、ステップと、
行列Eから、行列Cを計算するステップと、
行列Cから、該3次元座標si(Xi,Yi,Zi)および該変換を表す行列Mを計算するステップと
を含み、
該σ12およびσ3に対する行列Dの特異ベクトルを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2Iに対してツイスティッド分解を実行することにより、行列BTBを対角化するステップを含み、Iは単位行列である、プログラム。

【請求項11】
 
与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する文書検索処理をコンピュータに実行させるプログラムであって、
該文書検索処理は、
該キーワードに対応する質問ベクトルqを受け取るステップと、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求めるステップと、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求めるステップと、
k<rなるkを選択するステップと、
行列Dの擬似行列Dkを計算するステップであって、行列Dkは、σ1,σ2,・・・,σkを対角要素としそれ以外の要素が0である行列Σk、σ1,σ2,・・・,σkに対応する特異ベクトルのみを左から順に並べた左右直交行列Uk,Vkを用いて、Dk=UkΣkVkTと定義される、ステップと、
行列Dkと質問ベクトルqとの類似度を計算するステップと、
該計算された類似度を基準に、検索結果を出力するステップと
を包含し、
該行列Dkの左右直交行列Uk,Vkを求めるステップは、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2I(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BTBを対角化するステップを含み、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次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算する手段と
を備え、
該特徴点の3次元座標si(Xi,Yi,Zi)および2次元座標から3次元座標への変換を表す行列Mを計算する手段は、
行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求める手段であって、行列Dは、
【数3】
 
(省略)
と定義される、手段と、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求める手段と、
σ1、σ2およびσ3に対する行列Dの特異ベクトルを求める手段と、
M=M’Cなる行列Cに対して、E=CCTを満たす行列Eを計算する手段であって、M’=L’(Σ’)1/2、Σ’はσ1、σ2およびσ3を対角要素に持ちそれ以外の要素が0である3×3行列、L’はσ1、σ2およびσ3に対応するDの特異ベクトルを左から順に並べた行列である、手段と、
行列Eから、行列Cを計算する手段と、
行列Cから、該3次元座標si(Xi,Yi,Zi)および該変換を表す行列Mを計算する手段と
を含み、
該σ1、σ2およびσ3に対する行列Dの特異ベクトルを求める手段は、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2Iに対してツイスティッド分解を実行することにより、行列BTBを対角化する手段を含み、Iは単位行列である、装置。

【請求項14】
 
与えられた文書に含まれる情報であって、与えられたキーワードに関連する情報を検索する装置であって、
該キーワードに対応する質問ベクトルqを受け取る手段と、
該文書に対応する索引語文書行列Dに対して上2重対角化を行い、行列Dの上2重対角行列Bを求める手段と、
行列Dの特異値として行列Bの特異値σj(σ1≧σ2≧・・・≧σr>0、rは、行列Dのランクに等しい)を求める手段と、
k<rなるkを選択する手段と、
行列Dの擬似行列Dkを計算する手段であって、行列Dkは、σ1,σ2,・・・,σkを対角要素としそれ以外の要素が0である行列Σk、σ1,σ2,・・・,σkに対応する特異ベクトルのみを左から順に並べた左右直交行列Uk,Vkを用いて、Dk=UkΣkVkTと定義される、手段と、
行列Dkと質問ベクトルqとの類似度を計算する手段と、
該計算された類似度を基準に、検索結果を出力する手段と
を包含し、
該行列Dkの左右直交行列Uk,Vkを求める手段は、ミウラ型逆変換と、sdLVvs変換と、rdLVvs変換と、ミウラ型変換とを用いて行列BTB-σj2I(j=1,2,・・・,k)に対してツイスティッド分解を実行することにより、行列BTBを対角化する手段を含み、Iは単位行列である、装置。
IPC(International Patent Classification)
F-term
State of application right Registered
Reference ( R and D project ) PRESTO The Innovation of Simulation Technology and the Construction of Foundations for its Practical Use AREA
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close