Epopoximación eficiente de bajo rango en MATLAB

Question

Me gustaría calcular una aproximación de bajo rango a una matriz que sea óptima según la norma Frobenius. La forma trivial de hacer esto es calcular la descomposición SVD de la matriz, establecer los valores singulares más pequeños a cero y calcular la matriz de bajo rango multiplicando los factores. ¿Hay una manera simple y más eficiente de hacer esto en MATLAB?

Answer 1

Si su matriz es escasa, use svds.

Suponiendo que no es escaso pero es grande, puede usar proyecciones aleatorias para una aproximación rápida de bajo rango.

Desde un tutorial:

Un óptimo bajo aproximación rango se puede calcular fácilmente usando la SVD de A en O (mn^2 ). Usando proyecciones aleatorias mostramos cómo lograr una aproximación de rango bajo "casi óptima" en O (mn log (n)).

código Matlab de un 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; 

Además, recuerda el parámetro econ de svd.

Answer 2

Puede calcular rápidamente una aproximación de bajo rango basada en SVD, utilizando la función svds.

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

svds utiliza para calcular eigs un subconjunto de los valores singulares - será especialmente rápido para matrices grandes y dispersas. Ver la documentación; puede establecer la tolerancia y el número máximo de iteraciones o elegir calcular pequeños valores singulares en lugar de grandes.

pensé svds y eigs podría ser más rápido que svd y eig para matrices densas, pero luego he hecho un poco de evaluación comparativa. Son sólo es más rápido para grandes matrices cuando se solicitan suficientemente pocos valores:

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 

Con reducción de tamaño n matrices cuadradas, k singular/eigen valores y tiempos de ejecución en segundos. Utilicé la función de intercambio de archivos de Steve Eddins timeit para la evaluación comparativa, que intenta dar cuenta de las variaciones generales y de tiempo de ejecución.

svds y eigs son más rápidos si quiere algunos valores de una matriz muy grande. También depende de las propiedades de la matriz en cuestión (edit svds debería darle alguna idea de por qué).