TOP > 外国特許検索 > High-speed high-accuracy matrix singular value decomposition method, program, and device

High-speed high-accuracy 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)
優先権データ
  • 特願2004-166437 (2004.6.3) JP
  • 2005JP010084 (2005.6.1) WO
発明の名称 (英語) High-speed high-accuracy matrix singular value decomposition method, program, and device 実績あり
発明の概要(英語) 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 &sgr; of the matrix B as singular values of the matrix A; and obtaining a singular vector of the matrix A for the &sgr;.
The step of obtaining a singular vector of the matrix A includes a step of performing a Twisted decomposition on a matrix BTB−&sgr;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.
従来技術、競合技術の概要(英語) BACKGROUND ART
At present, a standard method used in order to perform a singular value decomposition in a computer is a DBDSQR routine published by international-known numerical computation library LAPACK.
This DBDSQR routine was created based on a QR method and can be divided into three sections; preprocess, main loop and postprocess.
The preprocess computes an upper limit and lower limit of a singular value and computes precision used for a convergence criterion.
The main loop gradually perform divisions and reductions of a matrix while repeating a QR method and completes a process when the size of the matrix eventually becomes 1 * 1.
When a block of matrix 2 * 2 appears while the main loop is being performed, another process is performed.
The postprocess changes, where computed singular values are changed from negative to positive values.
If necessary, the postprocess performs a scalar multiplication on the singular values.
The singular values are rearranged in the descending order, and singulars vectors are also rearranged so as to correspond to the singular values.
In a DBDSQR, an extremely large amount of computation is required and thus, it is not possible to avoid an increase of time to be required for a computation, especially in a large-scale problem.
In a DBDSQR routine, singular values and singular vectors are simultaneously computed.
LAPACK publishes a DLASQ routine for computing singular values and a DSTEGR routine for diagonalization, which is used when singular vectors are computed by using the computed singular values.
A DLASQ routine can obtain singular values at high speed with high precision.
However, it can not compute singular vectors.
In view of such a numerical defect, it is difficult to practically use a DSTEGR routine for a singular value decomposition.
Using a DBDSQR routine published by LAPACK as an example, a conventional singular value decomposition method will be described.
A DBDSQR routine first applies a Householder transformation to standard matrix A having l1 * l2 in order to perform a singular value decomposition on the matrix A. In other words, the matrix A can be represented by using orthogonal matrices UA and UV as:
(Equation image 1 not included in text)
B obtained in this case is called upper bidiagonal matrix.
Herein, it should be noted that a singular value of A=a singular value of B. Accordingly, a singular value decomposition problem for the standard matrix A is replaced with a singular value decomposition problem for upper bidiagonal matrix BTB,
B=UBSIGMA VBT
where matrices UB and VB are left and right orthogonal matrices, respectively,
SIGMA ≡diag(sigma 1, sigma 2, . . . , sigma m)sigma 1 >= sigma 2 >= . . . sigma m >= 0, and
sigma j is a singular value of B.
Next, matrix BTB will be considered.
Diagonalization of this matrix B is performed by:
LAMBDA =VTBTBV
where LAMBDA ≡diag(lambda 1, lambda 2, . . . , lambda m) lambda 1 >= lambda 2 >= . . . lambda m >= 0
V≡(v1, v2, . . . , vm)
lambda j is an eigenvalue of BTB, and
vj is an eigenvector for the eigenvalue lambda j.
Herein, the following is normally established: (1) BTB is a symmetric tridiagonal matrix; (2) Eigenvalues of BTB are all positive, and singular value sigma j (sigma 1 >= sigma 2 >= . . . >= sigma m >= 0) of B is equal to a positive square root of eigenvalue lambda j (lambda 1 >= lambda 2 >= . . . >= lambda m >= 0) of BTB; (3) VB=V, i.e., eigenvector vj of BTB is equal to a right singular vector of B. Accordingly, when the diagonalization of the matrix BTB has been obtained, SIGMA is obtained since LAMBDA =SIGMA 2 from (2), and further, left orthogonal matrix UB=BVBSIGMA -1=BVSIGMA -1 is obtained from (3).
Therefore, B is singular-value-decomposed.
In other words, the singular value decomposition of B can be replaced with a problem of diagonalization of BTB.
Not only can this principle be applied to obtaining all m number of singular values and singular vectors, but also this principle can be applied to obtaining at least one singular value and singular vector.
As described above, the singular value decomposition of the standard matrix A includes the problem of diagonalization of the symmetric tridiagonal matrix BTB.

特許請求の範囲(英語) [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.
  • 発明者/出願人(英語)
  • NAKAMURA YOSHIMASA
  • IWASAKI MASASHI
  • SAKANO SHINYA
  • JAPAN SCIENCE AND TECHNOLOGY AGENCY
国際特許分類(IPC)
米国特許分類/主・副
  • 382/285
参考情報 (研究プロジェクト等) PRESTO The Innovation of Simulation Technology and the Construction of Foundations for its Practical Use AREA
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。

PAGE TOP

close
close
close
close
close
close