Power Iterationの収束加速法に関する検討

• Item type: SIG Technical Reports(1)
• 公開日: 2017-03-02
• タイトル: Power Iterationの収束加速法に関する検討
• タイトル / 言語: en
• タイトル: A study on accelerating convergence of power iteration
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学大学院システム工学研究科
• 著者所属: 和歌山大学大学院システム工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Wakayama University, Faculty of Systems Engineering.
• 著者所属(英): en
• 著者所属(英): Graduate School of Wakayama University, Faculty of Systems Engineering.
• 著者名: 平松, 幹洋; 和田, 俊和
• 著者名(英): Mikihiro, Hiramatsu; Toshikazu, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本報告では Power Iteration による第 1 固有値，固有ベクトル計算の高速化について検討する．パターン認識やコンピュータ ・ ビジョンの問題には，主成分分析や判別分析など，固有値問題に帰着する問題は多数存在する．通常， n×n の行列の固有値問題を解く際には，QR 分解など全ての非ゼロ固有値に対応する固有ベクトルを求める O (n3) のアルゴリズムがよく使われる．しかし，行列の第 1 固有ベクトルのみが必要なタスクも多くあり，そのようなタスクでは，計算量が O (n2) である Power Iteration を用いることができる．これは，適当な初期ベクトル x0 に行列 A を左から十分な回数かけ，Anx0 /
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11131797
• 書誌情報: 研究報告コンピュータビジョンとイメージメディア（CVIM）; 巻 2017-CVIM-206, 号 9, p. 1-7, 発行日 2017-03-02
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8701
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会