svdsketch
低ランクの行列スケッチの SVD の計算
構文
説明
例
svdsketch を使用して、低ランク行列近似の SVD 係数を計算します。
gallery を使用して、幾何学的に分布する特異値をもつ 200 行 200 列の乱数行列を作成します。
A = gallery('randsvd',200);svdsketch を使用して、A の低ランク近似の SVD を計算します。
[U,S,V] = svdsketch(A);
出力のサイズを確認します。
size(S)
ans = 1×2
120 120
結果は、A の低ランク行列近似はランク 120 をもつことを示しています。
svdsketch を使用して許容誤差を指定して、低ランク行列近似の SVD 係数を計算します。svdsketch は、指定された許容誤差に基づいて行列スケッチの適切なランクを適応的に決定します。
gallery を使用して、幾何学的に分布する特異値をもつ 200 行 200 列の乱数行列を作成します。
A = gallery('randsvd',200);svdsketch を使用して A の低ランク近似の SVD を計算します。1e-2 の許容誤差を指定し、出力 S のサイズを見つけて、svdsketch が行列スケッチに使用するランクを決定します。
tol = 1e-2; [U,S,V] = svdsketch(A,tol); size(S)
ans = 1×2
60 60
結果は、A の低ランク行列近似はランク 60 をもつことを示しています。
A を U*S*V' と比較して、行列スケッチが A をどの程度よく近似しているかを調べます。
norm(U*S*V' - A,'fro')/norm(A,'fro')
ans = 0.0048
結果は、行列スケッチが、指定された許容誤差 1e-2 内で A を近似していることを示しています。
ゆっくり減衰する特異値をもつ行列に対して MaxSubspaceDimension オプションを指定して svdsketch を使用します。このオプションを使用して、行列スケッチで svdsketch が強制的に A の特徴のサブセットを使用するようにできます。
標準正規分布から得た値をもつ 5000 行 5000 列の行列を作成します。行列の特異値の分布を表示します。
A = randn(5000);
semilogy(svd(A),'-o')
A の特異値はゆっくり減衰するため、A には多くの重要な特徴があり、低ランクの近似には適していません。A を適度によく近似する行列スケッチを形成するには、ほとんど、またはほぼすべての特徴が保持されている必要があります。
1e-5 の許容誤差をもつ行列に対して svdsketch を使用します。それぞれの反復で SVD 係数と相対近似誤差を返す 4 つの出力を指定します。
tol = 1e-5; [U1,S1,V1,apxError1] = svdsketch(A,tol); size(S1)
ans = 1×2
5000 5000
S のサイズは、その許容誤差を満たすには svdsketch は A のすべての特徴が保持されている必要があることを示しています。大規模なスパース入力行列では、これによってメモリの問題が生じる可能性があります。svdsketch によって形成される A の低ランク近似は、A とおおむね同じサイズであり、密な行列としてメモリに収まらない可能性があるためです。
出力の近似誤差を確認します。svdsketch は A のすべてを保持するため、計算された解は正確ですが、svd(X) を計算する方法としてはこの計算は高コストでした。
apxError1(end)
ans = 1.9075e-08
ここで、同じ計算を行いますが、A をスケッチするのに使用される部分空間のサイズを制限するため、MaxSubspaceDimension を 650 として指定します。これは、svdsketch が、行列スケッチを形成するのに A の特徴のサブセットのみを強制的に使用するようにするのに有用です。これにより出力のサイズが削減されます。
[U2,S2,V2,apxError2] = svdsketch(A,tol,'MaxSubspaceDimension',650);
size(S2)ans = 1×2
650 650
出力のサイズが小さくなりました。
新しい出力の近似誤差を確認します。出力を強制的に小さくすることのトレードオフは、A の多くの重要な特徴が行列スケッチでは省略される必要があることであり、結果として得られる A のランク 650 の近似は、指定された許容誤差を満たしていません。
apxError2(end)
ans = 0.8214
入力引数
名前と値の引数
出力引数
ヒント
svdsにどのランクを指定するかは事前にわからないが、SVD の近似が満たすべき許容誤差はわかる場合にはsvdsketchを使用します。svdsは (既定の"largest"メソッドを使用して) SVD の可能な限り最善のランク k 近似を計算します。svdsketchはそのランク k 近似が最善であることを保証するものではありません。svdsに対する速度の面での優位性が考慮されます。
アルゴリズム
svdsketch は許容誤差を適用して、入力行列 A の低ランク行列近似 を形成します。この低ランクの近似は "行列スケッチ" と呼ばれます。行列スケッチは、A から不要な情報をフィルターで除外して重要な特徴のみを保持します。行列スケッチの相対近似誤差 apxErr は、指定された許容誤差 tol を満たすことを目的としています。
行列スケッチの形成のために svdsketch が従うプロセスは次のとおりです。
svdsketchは行列スケッチを反復して形成します。各反復では新しい列を Q に、新しい行を B に追加します。新しい列と行は、ランダムなサンプル行列を使用してAから特徴を抽出して作成されます。各反復で追加される列と行の数をBlockSizeの名前と値のペアで制御できます。それぞれの反復中、
svdsketchはべき乗の反復を使用して Q の新しい列の直交性を向上させます。NumPowerIterations名前と値のペアを使用してべき乗の反復の数を調整できます。行列スケッチを形成する反復は、次の場合に停止します。Q の列の数と B の行の数が
MaxSubspaceDimensionについて指定された値に到達するとき、反復の回数がMaxIterationsに到達するとき、または相対近似誤差が収束 (apxErr <= tol) するとき。収束速度を向上させるため、
svdsketchは、apxErrの減衰が十分でない場合にBlockSizeの指定された初期値を反復ごとに増加させる場合があります。
行列スケッチ が形成された後、svdsketch は行列スケッチの特異値分解 (SVD) を [U1,S,V] = svd(B,'econ') を通じて次のように計算します。
svdsketch が指定された許容誤差に基づいて A のいくつかの特徴をフィルターで除外できる場合、結果として得られる SVD 係数に含まれる特異値と特異ベクトルは、A に対して完全な SVD を実行した場合よりも少なくなります。
参照
[1] Yu, Wenjian, Yu Gu, and Yaohang Li. “Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation.” SIAM Journal on Matrix Analysis and Applications 39, no. 3 (August 2018): 1339–1359. https://doi.org/10.1137/17M1141977.
拡張機能
バージョン履歴
R2020b で導入
