Top > Search of Japanese Patents > (In Japanese)特異値分解装置、及び特異値分解方法

(In Japanese)特異値分解装置、及び特異値分解方法 meetings foreign

Patent code P110004743
File No. 1112
Posted date Aug 18, 2011
Application number P2007-549031
Patent number P5011545
Date of filing Sep 21, 2006
Date of registration Jun 15, 2012
International application number JP2006318713
International publication number WO2007066445
Date of international filing Sep 21, 2006
Date of international publication Jun 14, 2007
Priority data
  • P2005-351089 (Dec 5, 2005) JP
Inventor
  • (In Japanese)中村 佳正
  • (In Japanese)譽田 太朗
  • (In Japanese)岩▲崎▼ 雅史
  • (In Japanese)阪野 真也
  • (In Japanese)高田 雅美
Applicant
  • (In Japanese)国立大学法人京都大学
Title (In Japanese)特異値分解装置、及び特異値分解方法 meetings foreign
Abstract (In Japanese)
【課題】
 高速・高精度であり、並列処理可能な特異値分解装置を提供する。
【解決手段】
 2重対角行列Bを2個の2重対角行列に分割する処理を繰り返し行う行列分割部14と、分割後の2重対角行列を特異値分解する特異値分解部15と、特異値分解部15によって特異値分解された特異値と、特異ベクトルからなる左右直交行列の一部の要素である行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出する処理を、2重対角行列Bの特異値を算出するまで繰り返す特異値算出部17と、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの特異ベクトルを算出する特異ベクトル算出部19と、を備える。
【選択図】
 図1
Outline of related art and contending technology (In Japanese)

特異値分解(SVD:Singular Value Decomposition)はデータ処理の中心的な行列演算として、画像処理やデータ検索等の多くの分野に応用されている。
なお、特異値分解の従来例としては、例えば、下記の非特許文献1のものなどが知られている。
【非特許文献1】
Ming Gu and Stanley C. Eisenstat、「A Divide-and-Conquer Algorithm for the Bidiagonal SVD」、SIAM Journal on Matrix Analysis and Applications、Vol.16,N0.1,pp.79-92(1995)

Field of industrial application (In Japanese)

本発明は、特異値分解を行う特異値分解装置等に関する。

Scope of claims (In Japanese)
【請求項1】
 
2重対角行列Bが記憶される対角行列記憶部と、
前記2重対角行列Bが2個の2重対角行列に分割され、その2重対角行列が2個の2重対角行列に分割される処理が、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返され、当該あらかじめ決められた大きさ以下の各2重対角行列に対して特異値分解が行われた結果である、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルからなる左右直交行列の一部の要素である行列要素とが記憶される特異値分解記憶部と、
前記2重対角行列Bの特異値が記憶される特異値記憶部と、
各2重対角行列の特異値と、行列要素とを前記特異値分解記憶部から読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を前記特異値記憶部に蓄積する特異値算出部と、
前記2重対角行列Bの特異ベクトルが記憶される特異ベクトル記憶部と、
前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する特異ベクトル算出部と、を備えた特異値分解装置。

【請求項2】
 
前記対角行列記憶部には、前記あらかじめ決められた大きさ以下の各2重対角行列も記憶され、
前記あらかじめ決められた大きさ以下の各2重対角行列を前記対角行列記憶部から読み出し、前記各2重対角行列に対して特異値分解を行い、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルとを算出し、当該特異値と、当該特異ベクトルからなる左右直交行列の一部の要素である行列要素とを前記特異値分解記憶部に蓄積する特異値分解部をさらに備えた請求項1記載の特異値分解装置。

【請求項3】
 
2重対角行列Bが記憶される対角行列記憶部と、
前記対角行列記憶部から前記2重対角行列Bを読み出し、当該2重対角行列Bを2個の2重対角行列に分割して前記対角行列記憶部に蓄積し、その2重対角行列を2個の2重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割部と、
前記あらかじめ決められた大きさ以下の各2重対角行列を前記対角行列記憶部から読み出し、前記各2重対角行列に対して特異値分解を行い、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルとを算出する特異値分解部と、
前記特異値分解部によって特異値分解された特異値と、特異ベクトルからなる左右直交行列の一部の要素である行列要素とが記憶される特異値分解記憶部と、
前記2重対角行列Bの特異値が記憶される特異値記憶部と、
各2重対角行列の特異値と、行列要素とを前記特異値分解記憶部から読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を前記特異値記憶部に蓄積する特異値算出部と、
前記2重対角行列Bの特異ベクトルが記憶される特異ベクトル記憶部と、
前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する特異ベクトル算出部と、を備えた特異値分解装置。

【請求項4】
 
前記特異ベクトル算出部は、qd型ツイスト分解法により特異ベクトルを算出する、請求項3記載の特異値分解装置。

【請求項5】
 
前記特異ベクトル算出部は、LV型ツイスト分解法により特異ベクトルを算出する、請求項3記載の特異値分解装置。

【請求項6】
 
前記特異ベクトル算出部は、
前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、前記2重対角行列Bの各要素に関してミウラ変換、dLVv型変換、逆ミウラ変換を行うことによって、前記2重対角行列Bを上2重対角行列B(+1)及び下2重対角行列B(-1)にコレスキー分解するコレスキー分解部と、
前記上2重対角行列B(+1)及び下2重対角行列B(-1)の各要素と、前記2重対角行列Bの特異値とを用いて一方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第1特異ベクトル算出部と、
前記第1特異ベクトル算出部が算出した一方の左右直交行列を構成する特異ベクトルと、前記2重対角行列Bの特異値と、前記2重対角行列Bとを用いて他方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第2特異ベクトル算出部と、をさらに備えた、請求項5記載の特異値分解装置。

【請求項7】
 
前記コレスキー分解部は、複数のコレスキー分解手段を備え、
前記複数のコレスキー分解手段が、前記2重対角行列Bをコレスキー分解する処理を並列実行する、請求項6記載の特異値分解装置。

【請求項8】
 
前記第1特異ベクトル算出部は、複数の第1特異ベクトル算出手段を備え、
前記複数の第1特異ベクトル算出手段が、特異ベクトルを算出する処理を並列実行する、請求項6または請求項7記載の特異値分解装置。

【請求項9】
 
前記第2特異ベクトル算出部は、複数の第2特異ベクトル算出手段を備え、
前記複数の第2特異ベクトル算出手段が、特異ベクトルを算出する処理を並列実行する、請求項6から請求項8のいずれか記載の特異値分解装置。

【請求項10】
 
前記特異値算出部は、複数の特異値算出手段を備え、
前記複数の特異値算出手段が、分割元の2重対角行列の特異値と、行列要素とを算出する処理を並列実行する、請求項3から請求項9のいずれか記載の特異値分解装置。

【請求項11】
 
前記特異値分解部は、複数の特異値分解手段を備え、
前記複数の特異値分解手段が、2重対角行列に対して特異値分解を行う処理を並列実行する、請求項3から請求項10のいずれか記載の特異値分解装置。

【請求項12】
 
行列Aが記憶される行列記憶部と、
前記行列Aを前記行列記憶部から読み出し、前記行列Aを2重対角化した前記2重対角行列Bを算出して前記対角行列記憶部に蓄積する対角化部と、をさらに備えた請求項3から請求項11のいずれか特異値分解装置。

【請求項13】
 
前記行列分割部は、2重対角行列を略半分の2個の2重対角行列に分割する、請求項3から請求項12のいずれか記載の特異値分解装置。

【請求項14】
 
前記特異値算出部は、2重対角行列Bの全ての特異値を算出する、請求項3から請求項13のいずれか記載の特異値分解装置。

【請求項15】
 
前記特異ベクトル算出部は、2重対角行列Bの全ての特異ベクトルを算出する、請求項14記載の特異値分解装置。

【請求項16】
 
前記行列Aは、2次元画像j(j=1,…,m、mは3以上の整数)から抽出された特徴点i(i=1,…,n、nは2以上の整数)の座標(xij,yij)から構成される行列である、請求項12記載の特異値分解装置。

【請求項17】
 
前記行列Aは、索引語の重みを要素とするベクトルであって、検索対象となる文書を示すベクトルであるd1,…,dn(nは2以上の整数)を各列に有する行列である索引語文書行列である、請求項12記載の特異値分解装置。

【請求項18】
 
2重対角行列Bが記憶される対角行列記憶部と、前記2重対角行列Bが2個の2重対角行列に分割され、その2重対角行列が2個の2重対角行列に分割される処理が、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返され、当該あらかじめ決められた大きさ以下の各2重対角行列に対して特異値分解が行われた結果である、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルからなる左右直交行列の一部の要素である行列要素とが記憶される特異値分解記憶部と、前記2重対角行列Bの特異値が記憶される特異値記憶部と、特異値算出部と、前記2重対角行列Bの特異ベクトルが記憶される特異ベクトル記憶部と、特異ベクトル算出部とを備えた特異値分解装置で用いられる特異値分解方法であって、
前記特異値算出部が、各2重対角行列の特異値と、行列要素とを前記特異値分解記憶部から読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を前記特異値記憶部に蓄積する特異値算出ステップと、
前記特異ベクトル算出部が、前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する特異ベクトル算出ステップと、を備えた特異値分解方法。

【請求項19】
 
2重対角行列Bが記憶される対角行列記憶部と、行列分割部と、特異値分解部と、前記特異値分解部によって特異値分解された特異値と、特異ベクトルからなる左右直交行列の一部の要素である行列要素とが記憶される特異値分解記憶部と、前記2重対角行列Bの特異値が記憶される特異値記憶部と、特異値算出部と、前記2重対角行列Bの特異ベクトルが記憶される特異ベクトル記憶部と、特異ベクトル算出部と、を備えた特異値分解装置で用いられる特異値分解方法であって、
前記行列分割部が、前記対角行列記憶部から前記2重対角行列Bを読み出し、当該2重対角行列Bを2個の2重対角行列に分割して前記対角行列記憶部に蓄積し、その2重対角行列を2個の2重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割ステップと、
前記特異値分解部が、前記あらかじめ決められた大きさ以下の各2重対角行列を前記対角行列記憶部から読み出し、前記各2重対角行列に対して特異値分解を行い、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルとを算出する特異値分解ステップと、
前記特異値算出部が、各2重対角行列の特異値と、行列要素とを前記特異値分解記憶部から読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を前記特異値記憶部に蓄積する特異値算出ステップと、
前記特異ベクトル算出部が、前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する特異ベクトル算出ステップと、を備えた特異値分解方法。

【請求項20】
 
前記特異ベクトル算出部は、コレスキー分解部と、第1特異ベクトル算出部と、第2特異ベクトル算出部と、をさらに備えており、
前記特異ベクトル算出ステップは、
前記コレスキー分解部が、前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、前記2重対角行列Bの各要素に関してミウラ変換、dLVv型変換、逆ミウラ変換を行うことによって、前記2重対角行列Bを上2重対角行列B(+1)及び下2重対角行列B(-1)にコレスキー分解するコレスキー分解ステップと、
前記第1特異ベクトル算出部が、前記上2重対角行列B(+1)及び下2重対角行列B(-1)の各要素と、前記2重対角行列Bの特異値とを用いて一方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第1特異ベクトル算出ステップと、
前記第2特異ベクトル算出部が、前記第1特異ベクトル算出ステップで算出した一方の左右直交行列を構成する特異ベクトルと、前記2重対角行列Bの特異値と、前記2重対角行列Bとを用いて他方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第2特異ベクトル算出ステップと、をさらに備えた、請求項19記載の特異値分解方法。

【請求項21】
 
コンピュータに、
2重対角行列Bが2個の2重対角行列に分割され、その2重対角行列が2個の2重対角行列に分割される処理が、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返され、当該あらかじめ決められた大きさ以下の各2重対角行列に対して特異値分解が行われた結果である、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルからなる左右直交行列の一部の要素である行列要素とが記憶される特異値分解記憶部から、各2重対角行列の特異値と、行列要素とを読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を特異値記憶部に蓄積する特異値算出ステップと、
前記2重対角行列Bが記憶される対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して特異ベクトル記憶部に蓄積する特異ベクトル算出ステップと、を実現させるためのプログラム。

【請求項22】
 
コンピュータに、
2重対角行列Bが記憶される対角行列記憶部から前記2重対角行列Bを読み出し、当該2重対角行列Bを2個の2重対角行列に分割して前記対角行列記憶部に蓄積し、その2重対角行列を2個の2重対角行列に分割して前記対角行列記憶部に蓄積する処理を、分割後の各2重対角行列があらかじめ決められた大きさ以下となるまで繰り返す行列分割ステップと、
前記あらかじめ決められた大きさ以下の各2重対角行列を前記対角行列記憶部から読み出し、前記各2重対角行列に対して特異値分解を行い、前記各2重対角行列の特異値と、前記各2重対角行列の特異ベクトルとを算出し、特異値分解された特異値と、特異ベクトルからなる左右直交行列の一部の要素である行列要素とを特異値分解記憶部に蓄積する特異値分解ステップと、
各2重対角行列の特異値と、行列要素とを前記特異値分解記憶部から読み出し、前記特異値と、前記行列要素とから、分割元の2重対角行列の特異値と、分割元の2重対角行列の行列要素とを算出して前記特異値分解記憶部に蓄積し、その分割元の2重対角行列の特異値と、行列要素とを算出する処理を、2重対角行列Bの少なくとも1個の特異値を算出するまで繰り返し、前記2重対角行列Bの少なくとも1個の特異値を特異値記憶部に蓄積する特異値算出ステップと、
前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、2重対角行列Bとその特異値とから、ツイスト分解法を用いて2重対角行列Bの少なくとも1個の特異ベクトルを算出して特異ベクトル記憶部に蓄積する特異ベクトル算出ステップと、を実行させるためのプログラム。

【請求項23】
 
前記特異ベクトル算出ステップは、
前記対角行列記憶部から2重対角行列Bを読み出し、前記特異値記憶部から前記2重対角行列Bの特異値を読み出し、前記2重対角行列Bの各要素に関してミウラ変換、dLVv型変換、逆ミウラ変換を行うことによって、前記2重対角行列Bを上2重対角行列B(+1)及び下2重対角行列B(-1)にコレスキー分解するコレスキー分解ステップと、
前記上2重対角行列B(+1)及び下2重対角行列B(-1)の各要素と、前記2重対角行列Bの特異値とを用いて一方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第1特異ベクトル算出ステップと、
前記第1特異ベクトル算出ステップで算出した一方の左右直交行列を構成する特異ベクトルと、前記2重対角行列Bの特異値と、前記2重対角行列Bとを用いて他方の左右直交行列を構成する特異ベクトルを算出して前記特異ベクトル記憶部に蓄積する第2特異ベクトル算出ステップと、をさらに備えた、請求項22記載のプログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007549031thum.jpg
State of application right Registered
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.


PAGE TOP

close
close
close
close
close
close
close