担当：小林 勇也
題目：乱択特異値分解
概要：
行列の特異値や特異値ベクトルを求める古典的な手法として, 同時反復法とKrylov部分空間法が知られている。
Halko et al.は各要素が標準正規分布からサンプリングされた行列を初期値に用いた同時反復法により、高確率で特異値分解を得られる手法をまとめた[1]。初期値の取り方には任意性があるが、Guはその中で安定性を高める性質を調べ、上記の初期値が最適である理論保証を与えた[2]。
本発表では, 決定的な同時反復法と比べて, 乱択化された同時反復法が優れている理由を説明する. 時間があれば, Krylov部分空間法を乱択化することで特異値分解を求める手法[3]についても紹介する。
参考文献:
[1] N. Halko, P. G. Martinsson and J. A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review, 53(2), 2011, pp. 217 –288.
[2] M. Gu, Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37(3), 2015, pp. A1139 –A1173.
[3] C. Musco and C. Musco, Randomized block krylov methods for stronger and faster approximate singular value decomposition, In Advances in Neural Information Processing Systems 28, NIPS, 2015, pp. 1396 –1404.
