svdsketch

低ランクの行列スケッチの SVD の計算

R2020b 以降

構文

[U,S,V] = svdsketch(A)

[U,S,V] = svdsketch(A,tol)

[U,S,V] = svdsketch(A,tol,Name,Value)

[U,S,V,apxErr] = svdsketch(___)

説明

[U,S,V] = svdsketch(A) は、入力行列 A の低ランクの行列スケッチの特異値分解 (SVD) を返します。行列スケッチは、A (許容誤差まで) の最も重要な特徴のみを反映する低ランクの近似です。これにより、svds を使用する場合と比較して、大きな行列の部分的な SVD の計算がより高速に可能になります。

[U,S,V] = svdsketch(A,tol) は行列スケッチの許容誤差を指定します。svdsketch は tol を使用して、行列スケッチの近似のランクを適応的に決定します。許容誤差が大きくなると、行列スケッチで使用される A の特徴が少なくなります。

[U,S,V] = svdsketch(A,tol,Name,Value) は、1 つ以上の Name,Value のペアの引数を使用して追加オプションを指定します。たとえば、'MaxIterations' とスカラーを指定して、行列スケッチの形成に使用される反復の回数を調整できます。

[U,S,V,apxErr] = svdsketch(___) はさらに、それぞれの反復での相対近似誤差 norm(U*S*V'-A,'fro')/norm(A,'fro') を含むベクトル apxErr を返します。ベクトル apxErr(end) の最後のエントリは、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

入力引数

A — 入力行列

行列

入力行列。スパース行列または非スパース行列として指定します。A は通常 (必ずではない) 大規模なスパース行列です。svdsketch は、比較的小さい数の特徴をもつランクが欠落している行列での動作に最も適しています。

データ型: single | double
複素数のサポート: あり

tol — 行列スケッチの許容誤差

eps(class(A))^(1/4) (既定値) | 実数の数値スカラー

行列スケッチの許容誤差。sqrt(eps(class(A))) <= tol < 1 の範囲の実数の数値スカラーとして指定します。

svdsketch は tol の値を使用して、A の低ランクの近似 (行列スケッチ) で使用する A の特徴を適応的に決定します。tol の値が増加すると、行列スケッチを形成するために svdsketch が使用する A の特徴が少なくなります。

例: [U,S,V] = svdsketch(A,1e-4)

データ型: single | double

名前と値の引数

引数のオプションのペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後になければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用してそれぞれの名前と値を区切り、Name を引用符で囲みます。

例: [U,S,V] = svdsketch(A,1e-10,'MaxIterations',100) は svdsketch アルゴリズムで 100 回の反復を使用します。

MaxSubspaceDimension — 部分空間の最大次元

min(size(A)) (既定値) | 正の整数スカラー

部分空間の最大次元。正の整数スカラーとして指定します。部分空間の次元は svdsketch アルゴリズムのメモリ消費を制御します。アルゴリズムが指定された許容誤差に対してメモリ不足になる場合、MaxSubspaceDimension により小さい値を指定して、アルゴリズムがメモリ内にとどまるようにすることができます。たとえば、A がゆっくり減衰する特異値をもつ場合に、このパラメーターを調整することは有用となる可能性があります。

MaxSubspaceDimension オプションを指定する場合は、svdsketch によって使用される行列スケッチのランクに最大値を設定します。そのため、svdsketch が MaxSubspaceDimension より小さいランクで指定された許容誤差を満たせない場合、許容される最大ランクが使用され、結果として得られる出力は指定された許容誤差を満たさない可能性があります。

例: [U,S,V] = svdsketch(A,1e-7,'MaxSubspaceDimension',150)

データ型: single | double

BlockSize — 初期アルゴリズムのブロック サイズ

min(max(floor(0.1*size(A,1)), 5), MaxSubspaceDimension) (既定値) | 正の整数スカラー

初期アルゴリズムのブロック サイズ。正の整数スカラーとして指定します。ブロック サイズは行列スケッチのランクが各反復で増加する数です。ブロック サイズを大きくすると、反復ごとにより多くの作業を行うことで必要な反復の回数を減らせますが、収束に達するまでに、必要以上の情報が計算に付加される可能性があります。

アルゴリズムが進行すると、相対近似誤差 apxErr が十分に速く減衰していない場合に、収束を早めるために svdsketch がブロック サイズを初期値から調整する可能性があります。

BlockSize を指定する場合は、その値は MaxSubspaceDimension より小さくする必要があります。

例: [U,S,V] = svdsketch(A,1e-7,'BlockSize',10)

データ型: single | double

MaxIterations — アルゴリズムの最大反復回数

MaxSubspaceDimension/BlockSize (既定値) | 正の整数スカラー

アルゴリズムの最大反復回数。正の整数スカラーとして指定します。反復回数を多くすると高品質の行列スケッチが生成されますが、実行時間がかかりメモリ消費が高くなります。

例: [U,S,V] = svdsketch(A,1e-7,'MaxIterations',25)

データ型: single | double

NumPowerIterations — べき乗の反復数

1 (既定値) | 非負の整数スカラー

べき乗の反復数。非負の整数スカラーとして指定します。べき乗の反復は U と V の出力の直交性を向上させます。一般的には、べき乗の反復数は 0、1、または 2 を選択するべきです。値を大きくすると丸め誤差によくない影響を及ぼす可能性があります。

例: [U,S,V] = svdsketch(A,1e-7,'NumPowerIterations',2)

データ型: single | double

出力引数

U — 行列スケッチの左特異ベクトル

行列

行列スケッチの左特異ベクトル。行列として返されます。U の列は正規直交であり、A の行列スケッチの範囲で一連の基底ベクトルを形成します。

U のサイズは tol の値に依存します。tol が大きくなると、svdsketch が行列スケッチの形成に使用する入力行列の特徴は少なくなり、したがって U と V の列も少なくなります。

マシンや MATLAB^® のリリースが異なると、異なった特異ベクトルが生成されることがありますが、数値的にはいずれも正確です。U と V の対応する列で符号が反転する場合がありますが、これは、反転しても式 A = U*S*V' の値には影響がないためです。

S — 行列スケッチの特異値

正方対角行列

行列スケッチの特異値。正方対角行列として返されます。S の対角要素は、降順に並べられた行列スケッチの厳密な正の特異値です。

S のサイズは tol の値に依存します。許容誤差が増加すると、svdsketch が行列スケッチの形成に使用する入力行列の特徴が少なくなり、したがって S はそれに応じて少ない行と列をもちます。

V — 行列スケッチの右特異ベクトル

行列

行列スケッチの右特異ベクトル。行列として返されます。V の列は正規直交であり、A の行列スケッチのヌル空間について一連の基底ベクトルを形成します。

V のサイズは tol の値に依存します。tol が大きくなると、svdsketch が行列スケッチの形成に使用する入力行列の特徴は少なくなり、したがって U と V の列も少なくなります。

マシンや MATLAB のリリースが異なると、異なった特異ベクトルが生成されることがありますが、数値的にはいずれも正確です。U と V の対応する列で符号が反転する場合がありますが、これは、反転しても式 A = U*S*V' の値には影響がないためです。

apxErr — 各反復での相対近似誤差

ベクトル

各反復での相対近似誤差。ベクトルとして返されます。apxErr の長さは、svdsketch アルゴリズムで使用される反復の数と等しくなります。MaxIterations を使用して反復の数を調整します。

apxErr のエントリは各反復での相対近似誤差 norm(U*S*V'-A,'fro')/norm(A,'fro') です。ベクトル apxErr(end) の最後のエントリは、svdsketch によって返される出力の相対近似誤差です。

ヒント

• svds にどのランクを指定するかは事前にわからないが、SVD の近似が満たすべき許容誤差はわかる場合には svdsketch を使用します。

• svds は (既定の "largest" メソッドを使用して) SVD の可能な限り最善のランク k 近似を計算します。svdsketch はそのランク k 近似が最善であることを保証するものではありません。svds に対する速度の面での優位性が考慮されます。

アルゴリズム

svdsketch は許容誤差を適用して、入力行列 A の低ランク行列近似 $$A\approx QB$$ を形成します。この低ランクの近似は "行列スケッチ" と呼ばれます。行列スケッチは、A から不要な情報をフィルターで除外して重要な特徴のみを保持します。行列スケッチの相対近似誤差 apxErr は、指定された許容誤差 tol を満たすことを目的としています。

$$e_{\text{sketch}}=\frac{{\Vert QB-A\Vert }_F}{{\Vert A\Vert }_F}\le tol$$

行列スケッチの形成のために svdsketch が従うプロセスは次のとおりです。

• svdsketch は行列スケッチを反復して形成します。各反復では新しい列を Q に、新しい行を B に追加します。新しい列と行は、ランダムなサンプル行列を使用して A から特徴を抽出して作成されます。各反復で追加される列と行の数を BlockSize の名前と値のペアで制御できます。

• それぞれの反復中、svdsketch はべき乗の反復を使用して Q の新しい列の直交性を向上させます。NumPowerIterations 名前と値のペアを使用してべき乗の反復の数を調整できます。

• 行列スケッチを形成する反復は、次の場合に停止します。Q の列の数と B の行の数が MaxSubspaceDimension について指定された値に到達するとき、反復の回数が MaxIterations に到達するとき、または相対近似誤差が収束 (apxErr <= tol) するとき。

• 収束速度を向上させるため、svdsketch は、apxErr の減衰が十分でない場合に BlockSize の指定された初期値を反復ごとに増加させる場合があります。

行列スケッチ $$A\approx QB$$ が形成された後、svdsketch は行列スケッチの特異値分解 (SVD) を [U1,S,V] = svd(B,'econ') を通じて次のように計算します。

$$A\approx QB=\left(Q{U}_1\right)S{V}^H=US{V}^H.$$

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.

拡張機能

分散配列

Parallel Computing Toolbox™ を使用して、クラスターの結合メモリ上で大きなアレイを分割します。

この関数は分散配列を完全にサポートしています。詳細については、分散配列を使用した MATLAB 関数の実行 (Parallel Computing Toolbox)を参照してください。

バージョン履歴

R2020b で導入

参考

svds | eigs | svd | rank | svdappend

トピック

• 特異値
• 低ランク SVD を使用したイメージの圧縮
• スパース行列の演算