Highspeed highaccuracy matrix singular value decomposition method, program, and device
外国特許コード  F110005491 

整理番号  K07601WO 
掲載日  2011年9月6日 
出願国  アメリカ合衆国 
出願番号  56989805 
公報番号  20090028455 
公報番号  8306361 
出願日  平成17年6月1日(2005.6.1) 
公報発行日  平成21年1月29日(2009.1.29) 
公報発行日  平成24年11月6日(2012.11.6) 
国際出願番号  JP2005010084 
国際公開番号  WO2005119507 
国際出願日  平成17年6月1日(2005.6.1) 
国際公開日  平成17年12月15日(2005.12.15) 
優先権データ 

発明の名称 （英語）  Highspeed highaccuracy matrix singular value decomposition method, program, and device 
発明の概要（英語） 
(US8306361) A singular value decomposition method according to the present invention is a method for performing a singular value decomposition on an arbitrary matrix A using a computer, the method including the steps of: performing an upper bidiagonalization on the matrix A so as to obtain an upper bidiagonal matrix B of the matrix A; obtaining at least one singular value σ of the matrix B as singular values of the matrix A; and obtaining a singular vector of the matrix A for the σ. The step of obtaining a singular vector of the matrix A includes a step of performing a Twisted decomposition on a matrix BTB－σ2I (where I is a unit matrix) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB. 
特許請求の範囲（英語） 
[claim1] 1. A method for restoring a threedimensional image from a plurality of twodimensional images of an object, the method comprising the steps of: extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in twodimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates based on the twodimensional coordinates dij (xij, yij) of the feature points, wherein the step of computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates includes the steps of: performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as (Equation image 18 not included in text) obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3; computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=L' (SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order; computing the matrix C from the matrix E; and computing the threedimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C, wherein the step of obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes a step of performing a Twisted decomposition on a matrix BTBsigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. [claim2] 2. A method for searching information relating to a given keyword, the information being included in a given document, the method comprising the steps of: receiving query vector q corresponding to the keyword; performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D; obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; selecting k such that k<r; computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order; computing a similarity between the matrix Dk and the query vector q; and outputting a search result based on the computed similarity, wherein the step of obtaining left and right orthogonal matrices Uk, Vk of a matrix Dk includes a step of performing a Twisted decomposition on a matrix BTBsigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. [claim3] 3. A nontransitory computer readable medium storing a program for causing a computer to execute an image restoring process for restoring a threedimensional image from a plurality of twodimensional images of an object, the image restoring process including the steps of: extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in twodimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates based on the twodimensional coordinates dij (xij, yij) of the feature points, wherein the step of computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates includes the steps of: performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as (Equation image 19 not included in text) obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3; computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=(L'(SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order; computing the matrix C from the matrix E; and computing the threedimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C, wherein the step of obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes a step of performing a Twisted decomposition on a matrix BTBsigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. [claim4] 4. A nontransitory computer readable medium storing a program for causing a computer to execute a document search process for searching information relating to a given keyword, the information being included in a given document, the document search process including the steps of: receiving query vector q corresponding to the keyword; performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D; obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; selecting k such that k<r; computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order; computing a similarity between the matrix Dk and the query vector q; and outputting a search result based on the computed similarity, wherein the step of obtaining left and right orthogonal matrices Uk, Vk of the matrix Dk includes a step of performing a Twisted decomposition on a matrix BTBsigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. [claim5] 5. An apparatus for restoring a threedimensional image from a plurality of twodimensional images of an object, the apparatus comprising: means for receiving m number (m is an integer greater than or equal to 3) of twodimensional images; means for extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in twodimensional images j (j=1, . . . , m); and means for computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates based on the twodimensional coordinates dij (xij, yij) of the feature points, wherein the means for computing threedimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from twodimensional coordinates to threedimensional coordinates includes: means for performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as (Equation image 20 not included in text) means for obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; means for obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3; means for computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=L'(SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order; means for computing the matrix C from the matrix E; and means for computing the threedimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C, wherein the means for obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes means for performing a Twisted decomposition on a matrix BTBsigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. [claim6] 6. An apparatus for searching information relating to a given keyword, the information being included in a given document, the apparatus comprising: means for receiving query vector q corresponding to the keyword; means for performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D; means for obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D; means for selecting k such that k<r; means for computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order; means for computing a similarity between the matrix Dk and the query vector q; and means for outputting a search result based on the computed similarity, wherein the means for obtaining left and right orthogonal matrices Uk, Vk of the matrix Dk includes means for performing a Twisted decomposition on a matrix BTBsigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix. 


国際特許分類(IPC) 

参考情報 （研究プロジェクト等）  PRESTO The Innovation of Simulation Technology and the Construction of Foundations for its Practical Use AREA 
日本語項目の表示
発明の名称  行列の高速高精度特異値分解方法、プログラムおよび装置 

※
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。
『 Highspeed highaccuracy matrix singular value decomposition method, program, and device 』に関するお問合せ
 国立研究開発法人科学技術振興機構（ＪＳＴ） 知的財産マネジメント推進部
 URL: http://www.jst.go.jp/chizai/
 Email:
 Address: 〒1028666 東京都千代田区四番町53
 TEL: 0352148486
 FAX: 0352148417