Designazione efficiente a basso rango in MATLAB

Question

Mi piacerebbe calcolare un'approssimazione di basso rango su una matrice che è ottimale secondo la norma di Frobenius. Il modo più semplice per farlo è calcolare la decomposizione SVD della matrice, impostare i valori singolari più piccoli a zero e calcolare la matrice di basso rango moltiplicando i fattori. Esiste un modo semplice ed efficiente per farlo in MATLAB?

Answer 1

Se la matrice è sparsa, utilizzare svds.

Supponendo che non sia scarso ma è grande, è possibile utilizzare proiezioni casuali per un'approssimazione veloce di basso rango.

Da un tutorial:

Un ottimale partire ravvicinamento rango può essere facilmente calcolato utilizzando la SVD di A in O (mn^2 ). Usando proiezioni casuali, mostriamo come ottenere una approssimazione approssimata "quasi ottimale" in O (mn log (n)).

codice Matlab da 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; 

Inoltre, ricorda il parametro econ di svd.

Answer 2

È possibile calcolare rapidamente un'approssimazione di basso livello basata su SVD, utilizzando la funzione svds.

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

svds utilizza eigs per calcolare un sottoinsieme dei valori singolari - sarà particolarmente veloce per grandi matrici sparse. Vedi la documentazione; è possibile impostare la tolleranza e il numero massimo di iterazioni o scegliere di calcolare piccoli valori singolari anziché grandi.

ho pensato svds e eigs potrebbe essere più veloce di svd e eig per le matrici dense, ma poi ho fatto un po 'di benchmarking. Sono solo più veloce per le grandi matrici quando vengono richiesti sufficientemente pochi valori:

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 Grandezza- n matrici quadrate, k singolari/eigen valori e tempi di esecuzione in pochi secondi. Ho utilizzato la funzione di scambio di file timeit di Steve Eddins per il benchmarking, che cerca di tenere conto delle variazioni di sovraccarico e di runtime.

svds e eigs sono più veloci se si desidera alcuni valori da una matrice molto grande. Dipende anche dalle proprietà della matrice in questione (edit svds dovrebbe darti un'idea del perché).