チェビシェフ多項式近似を使用した極分解による特異値分解の高速化

摘要

本報告では，行列の極分解を用いた特異値分解（SVDPD）を，チェビシェフ多項式近似（CPA）を用いて高速化する．特異値分解（SVD）は様々な分野で利用されているが，処理対象の行列が非常に大きい場合は膨大な計算時間を要する．実際に，画像処理や機械学習などでは処理対象となる行列のサイズが大きいことが多く，SVDの高速化が様々な場面で必要とされている．その問題を解決する一つの手法として，SVDPDが提案された．SVDPDは，独立したブロック対角行列ごとの行列分解を行うことで，元の行列の特異値と特異ベクトルを計算することが可能であるため，並列計算を用いて高速化が可能となる．しかし，行列の極分解に用いられるQR分解は更に高速化する必要がある．本報告では，行列の極分解をCPAを用いて高速化し，SVDPDの計算時間を削減する．具体的には，QR分解を用いずとも，行列の固有値を適切に操作するだけで行列の極分解が可能なことを示し，さらに，その固有値の操作をCPAを用いて高速化する．実験において，本手法が従来法よりも高速であることを示し，さらに実際の応用の性能を劣化させないことを示す．