Wydajne appoximation niskiej rangi w MATLAB

Question

Chciałbym obliczyć przybliżenie niskiego stopnia do matrycy, która jest optymalna zgodnie z normą Frobenius. Najprostszym sposobem na to jest obliczenie dekompozycji SVD macierzy, ustawienie najmniejszych pojedynczych wartości na zero i obliczenie macierzy niskiej rangi poprzez pomnożenie czynników. Czy w MATLAB jest prosty i wydajniejszy sposób na zrobienie tego?

Answer 1

Jeśli twoja macierz jest rzadka, użyj svds.

Zakładając, że nie jest rzadki, ale jest duży, możesz użyć losowych projekcji do szybkiego przybliżenia w niskiej skali.

Z tutorial:

Optymalny niski stopień przybliżenie może być łatwo obliczona z użyciem metody SVD w O (mn^2 ). Korzystając z losowych projekcji pokazujemy, jak uzyskać "prawie optymalne" pproximation o niskiej randze w O (mn log (n)).

Matlab kod z blog:

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; 

również pamiętać parametr svdecon.

Answer 2

Możesz szybko obliczyć przybliżenie niskiego poziomu w oparciu o SVD, używając funkcji svds.

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

svds wykorzystuje eigs obliczyć podzbiór wartości osobliwych - będzie to szczególnie szybko dla dużych, rzadki matrycach. Zobacz dokumentację; można ustawić tolerancję i maksymalną liczbę iteracji lub wybrać obliczanie małych wartości osobliwych zamiast dużych.

Myślałem svds i eigs mogłoby być szybsze niż svd i eig dla gęstych matryc, ale potem zrobiłem niektóre benchmarking. Są tylko szybciej dla dużych matrycach gdy dostatecznie kilka wartości są o:

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 

Z size- n macierzy kwadratowych, k osobliwe/eigen wartości i czasy pracy w ciągu kilku sekund. Użyłem funkcji wymiany plików Steve'a Eddinsa "timeit" do testowania porównawczego, która stara się uwzględnić zmiany narzutowe i runtime.

svds i eigs są szybsze, jeśli chcesz uzyskać kilka wartości z bardzo dużej matrycy. Zależy to również od właściwości matrycy, o której mowa (edit svds powinien dać ci jakiś pomysł, dlaczego).