MATLABで効率的な低ランクappoximation

Question

私はFrobeniusノルムの下で最適な行列の低ランク近似を計算したいと思います。これを行う簡単な方法は、行列のSVD分解を計算し、最小の特異値をゼロに設定し、因子を掛けて低ランク行列を計算することです。 MATLABでこれを行う簡単で効率的な方法はありますか？

Answer 1

マトリックスが疎である場合は、svdsを使用してください。

スパースではありませんが大きければ、ランダムな投影を使用して低速近似を高速で実行できます。 tutorialから

：

最適な低ランク近似は容易O（MN^2 ）にのSVDを使用して計算することができます。ランダム投影を使用して、O（mn log（n））に「ほぼ最適な」低ランクpproximationを達成する方法を示します。

blogからMATLABコード：また

clear 
% preparing the problem 
% trying to find a low approximation to A, an m x n matrix 
% where m >= n 
m = 1000; 
n = 900; 
%// first let's produce example A 
A = rand(m,n); 
% 
% beginning of the algorithm designed to find alow rank matrix of A 
% let us define that rank to be equal to k 
k = 50; 
% R is an m x l matrix drawn from a N(0,1) 
% where l is such that l > c log(n)/ epsilon^2 
% 
l = 100; 
% timing the random algorithm 
trand =cputime; 
R = randn(m,l); 
B = 1/sqrt(l)* R' * A; 
[a,s,b]=svd(B); 
Ak = A*b(:,1:k)*b(:,1:k)'; 
trandend = cputime-trand; 
% now timing the normal SVD algorithm 
tsvd = cputime; 
% doing it the normal SVD way 
[U,S,V] = svd(A,0); 
Aksvd= U(1:m,1:k)*S(1:k,1:k)*V(1:n,1:k)'; 
tsvdend = cputime -tsvd; 

、svdのeconパラメータを覚えています。

Answer 2

svds関数を使用すると、SVDに基づいて低ランク近似を迅速に計算できます。

[U,S,V] = svds(A,r); %# only first r singular values are computed 

svds特異値のサブセットを計算するためにeigsを使用しています - それは大規模な、スパース行列に対して特に速いとなります。ドキュメントを参照してください。許容差と最大反復回数を設定するか、大きな値ではなく小さな特異値を計算することができます。

私はsvdsとeigsがsvdと密行列のためeigよりも速いと考えていたが、その後、私はいくつかのベンチマークをしました。十分にいくつかの値が要求されたとき、彼らはより速く、大行列のためにある：秒、サイズn正方行列で

n  k  svds   svd   eigs   eig   comment 
10  1  4.6941e-03 8.8188e-05 2.8311e-03 7.1699e-05 random matrices 
100 1  8.9591e-03 7.5931e-03 4.7711e-03 1.5964e-02  (uniform dist) 
1000 1  3.6464e-01 1.8024e+00 3.9019e-02 3.4057e+00 
     2  1.7184e+00 1.8302e+00 2.3294e+00 3.4592e+00 
     3  1.4665e+00 1.8429e+00 2.3943e+00 3.5064e+00 
     4  1.5920e+00 1.8208e+00 1.0100e+00 3.4189e+00 
4000 1  7.5255e+00 8.5846e+01 5.1709e-01 1.2287e+02 
     2  3.8368e+01 8.6006e+01 1.0966e+02 1.2243e+02 
     3  4.1639e+01 8.4399e+01 6.0963e+01 1.2297e+02 
     4  4.2523e+01 8.4211e+01 8.3964e+01 1.2251e+02 


10  1  4.4501e-03 1.2028e-04 2.8001e-03 8.0108e-05 random pos. def. 
100 1  3.0927e-02 7.1261e-03 1.7364e-02 1.2342e-02 (uniform dist) 
1000 1  3.3647e+00 1.8096e+00 4.5111e-01 3.2644e+00 
     2  4.2939e+00 1.8379e+00 2.6098e+00 3.4405e+00 
     3  4.3249e+00 1.8245e+00 6.9845e-01 3.7606e+00 
     4  3.1962e+00 1.9782e+00 7.8082e-01 3.3626e+00 
4000 1  1.4272e+02 8.5545e+01 1.1795e+01 1.4214e+02 
     2  1.7096e+02 8.4905e+01 1.0411e+02 1.4322e+02 
     3  2.7061e+02 8.5045e+01 4.6654e+01 1.4283e+02 
     4  1.7161e+02 8.5358e+01 3.0066e+01 1.4262e+02 

、k特異/固有値およびランタイム。私はSteve Eddinsのtimeitファイル交換機能を使用して、オーバーヘッドとランタイムの変動を考慮してベンチマークを試みました。

svdsおよびeigsは、非常に大きなマトリックスからいくつかの値を取得する方が速いです。それはまた問題のマトリックスの特性に依存します（edit svdsはあなたに何らかのアイデアを与えるべきです）。