特異値分解ってどうやるの?

特異値分解 - Wikipedia


特異値分解とは正方行列とは限らない行列Aを

  • A=U\Sigma V^\dag

と分解すること。ここで、U,Vはユニタリ行列で\SigmaはサイズがAと同じで、対角要素以外は0となっている。


いろいろぐぐって拾い集めて妄想した結果をここにメモしておく。あくまでも妄想なのであっているかは分からないし、あっていても計算速度は保証しない。単に本を探せば良い話なんだけどねw



Aのサイズは(m,n)だとし、m<=nだと仮定しておく。そうでない場合は転置したものに適用すれば良い。
そしたら、行列A^\dag Aはエルミート行列であるので正規直交完全基底で対角化可能。

  • A^\dag A v_i=\lambda_i v_i

このとき、\lambda_iは0でないものを先に並べることにする。階数がm以下のはずなので、0でないものがm個より多くあることは無い。
そこで\sigma_i =\sqrt{\lambda_i}とおき、\sigma_iが0でないiに対して

  • Av_i=\sigma_i u_i

となるようにベクトルu_iをおく。これらは正規直交になっている。(内積を計算すればわかる。)それ以上のi(<=m)に対しては、シュミットの直交化などをつかって、空間を完備にしておく。
すると、行列Vをベクトルv_iを横に並べたもの、行列Uをベクトルu_iを横に並べたものとして(これらはユニタリ行列になる)

  • AV=U\Sigma <=> A=U\Sigma V^\dag

が成り立つ。ここで\Sigmaはサイズ(m,n)で対角要素は\sigma_iが並んでいるもの。



それともヤコビ法の真似をすることで直接できる?



調べたらもっと速い方法があるらしい