Top > Search of International Patents > High-speed high-accuracy matrix singular value decomposition method, program, and device

High-speed high-accuracy matrix singular value decomposition method, program, and device achieved

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
  • P2004-166437 (Jun 3, 2004) JP
  • 2005WO-JP10084 (Jun 1, 2005) WO
Title High-speed high-accuracy matrix singular value decomposition method, program, and device achieved
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 three-dimensional image from a plurality of two-dimensional 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 two-dimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and
computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the step of computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional 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 three-dimensional 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 BTB-sigma 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 BTB-sigma 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 non-transitory computer readable medium storing a program for causing a computer to execute an image restoring process for restoring a three-dimensional image from a plurality of two-dimensional 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 two-dimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and
computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the step of computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional 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 three-dimensional 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 BTB-sigma 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 non-transitory 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 BTB-sigma 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 three-dimensional image from a plurality of two-dimensional images of an object, the apparatus comprising: means for receiving m number (m is an integer greater than or equal to 3) of two-dimensional 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 two-dimensional images j (j=1, . . . , m); and
means for computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the means for computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional 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 three-dimensional 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 BTB-sigma 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 BTB-sigma 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.
  • Inventor, and Inventor/Applicant
  • NAKAMURA YOSHIMASA
  • IWASAKI MASASHI
  • SAKANO SHINYA
  • JAPAN SCIENCE AND TECHNOLOGY AGENCY
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 E-mail or facsimile if you have any interests on this patent.

PAGE TOP

close
close
close
close
close
close