2026-05-14T17:19:52Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00178336 2025-01-20T05:09:44Z 1164:4619:9026:9125

Power Iterationの収束加速法に関する検討 A study on accelerating convergence of power iteration 平松, 幹洋 和田, 俊和 Mikihiro, Hiramatsu Toshikazu, Wada 本報告では Power Iteration による第 1 固有値，固有ベクトル計算の高速化について検討する．パターン認識やコンピュータ ・ ビジョンの問題には，主成分分析や判別分析など，固有値問題に帰着する問題は多数存在する．通常， n×n の行列の固有値問題を解く際には，QR 分解など全ての非ゼロ固有値に対応する固有ベクトルを求める O (n3) のアルゴリズムがよく使われる．しかし，行列の第 1 固有ベクトルのみが必要なタスクも多くあり，そのようなタスクでは，計算量が O (n2) である Power Iteration を用いることができる．これは，適当な初期ベクトル x0 に行列 A を左から十分な回数かけ，Anx0 / This report proposes several acceleration methods for finding the first eigenvalue and eigenvector by power iteration. A lot of problems in Computer Vision and Pattern Recognition are formalized as eigenvalue problems, e.g. principal component analysis, linear discriminant analysis, and so on. In order to find the eigenvalues and eigenvectors of n×n matrix, we often use O(n3) algorithms, such as QR decomposition. However, some problems need only first eigenvector of a matrix A. For solving such problems, we can use power iteration, whose computational complexity is 0(n2). Power iteration algorithm iteratively premultiply a matrix A with an arbitrary vector x0 until the resulted vector Anx0/∥Anx0∥ converges to the first eigenvector of A. The number of premultiplication depends on the absolute ratio of the first and other eigenvalues. For example, the number of iteration increases when the absolute ratio of the first and the second eigenvalues are close to 1. We can reduce the number of this iteration by the following approaches. The first approach is to accelerate the convergence of vector series Anx0/∥Anx0∥. The other approach is so called “shifted method” which modifies the original matrix to shifted eigenvalue matrix so as to reduce the absolute ratio of the eigenvalues while keeping the eigenvectors. We propose an integration of these two approaches. In the experiments, we examined some integrated methods and confirmed that the best method is at least two times faster than the original method. technical report 情報処理学会 2017-03-02 application/pdf 研究報告コンピュータビジョンとイメージメディア（CVIM） 9 2017-CVIM-206 1 7 2188-8701 AA11131797 https://ipsj.ixsq.nii.ac.jp/record/178336/files/IPSJ-CVIM17206009.pdf jpn