【Python】SciPyの特異値分解ともうちょっと速い特異値分解【SVD】
photo by Jared Tarbell
SciPyの特異値分解
SciPyには特異値分解のための関数が2種類入っています。- scipy.linalg.svd
- scipy.sparse.linalg.svds
前者(svd)が一般的な特異値分解、後者(svds)がスパース行列に対する特異値分解の関数となっています。しかし、おそらく svds は別の場面で使う場合が多いのではないでしょうか。
svd では全ての特異値を計算するのに対し、svds では上位 k 個の特異値のみを計算させるオプションが存在します。当然、k が小さいほど計算は速く終わるため、スパース行列でなくても、上位の特異値のみが必要な場合は svds を使ったほうが圧倒的に計算が速いことが多いです。
PROPACK
SVD のスピードについて調べているときに下のような記事を見つけました。Sparse SVDs in Python | Pythonic Perambulations
svds よりも計算の速い PROPACK なるライブラリが存在するそうです。
PROPACK は pypropack としてPythonライブラリ化されており、以下のリンクからダウンロードし、ビルドすることでインストール可能です。
GitHub - jakevdp/pypropack: A python wrapper for the PROPACK library
比較
pypropack のほうが本当に速いの?みたいなことを調べるため適当にテストしました。本当に適当なので、状況によって結果はかなり変わると思います。とりあえず、結果的にはちょっと速そうです。
テストコード
# -*- coding: utf-8 -*- from scipy import rand from time import time from scipy.linalg import svd from scipy.sparse.linalg import svds from pypropack import svdp def test_svd(): shape = [1000, 1000] svd_time = [] svds_time = [] svdp_time = [] k = 100 ## 計算したい特異値の数 for ii in xrange(10): M = rand(shape[0], shape[1]) t1 = time() svd(M) t2 = time() svds(M, k = k) t3 = time() svdp(M, k = k) t4 = time() svd_time.append(t2 - t1) svds_time.append(t3 - t2) svdp_time.append(t4 - t3) print "scipy.linalg.svd (full):\t\t", min(svd_time) print "scipy.sparse.linalg.svds (k = 100):\t", min(svds_time) print "pypropack.svdp (k = 100):\t\t", min(svdp_time) if __name__ == "__main__": test_svd()
出力
scipy.linalg.svd (full): 2.58191680908 scipy.sparse.linalg.svds (k = 100): 1.10373687744 pypropack.svdp (k = 100): 0.83057808876