Highspeed highaccuracy matrix singular value decomposition method, program, and device
Foreign code  F110005491 

File No.  K07601WO 
Posted date  Sep 6, 2011 
Country  United States of America 
Application number  56989805 
Gazette No.  20090028455 
Gazette No.  8306361 
Date of filing  Jun 1, 2005 
Gazette Date  Jan 29, 2009 
Gazette Date  Nov 6, 2012 
International application number  JP2005010084 
International publication number  WO2005119507 
Date of international filing  Jun 1, 2005 
Date of international publication  Dec 15, 2005 
Priority data 

Title  Highspeed highaccuracy matrix singular value decomposition method, program, and device 
Abstract 
(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. 
Scope of claims 
[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(International Patent Classification) 

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 Email or facsimile if you have any interests on this patent.
Contact Information for " Highspeed highaccuracy matrix singular value decomposition method, program, and device "
 Japan Science and Technology Agency Department of Intellectual Property Management
 URL: http://www.jst.go.jp/chizai/
 Email:
 Address: 53, Yonbancho, Chiyodaku, Tokyo, Japan , 1028666
 Fax: 81352148417