Comment calculer 2-norme d'une matrice efficacement?

Question

Supposons que j'ai une matrice A. Je veux calculer sa norme 2/norme spectrale. Comment puis-je calculer cela efficacement?

Je sais que la norme 2 d'une matrice est égale à sa plus grande valeur singulière. Donc, le résultat du code suivant sera Matlab zéro

>> [u,s,v]=svd(A,'econ'); 
norm(A,2)-s(1,1) 

Mais savoir 2-norme, je dois calculer SVD de matrice complète A, est-il un moyen efficace pour calculer 2-norme? Réponse sous forme de code MATLAB sera très appréciée.

Answer 1

Cet exemple avec norm et des données aléatoires

A = randn(2000,2000); 
tic; 
n1 = norm(A) 
toc; 

donne

n1 = 89.298 
Elapsed time is 2.16777 seconds. 

Vous pouvez eigs trouver un seul (le plus grand) des valeurs propres de la matrice symétrique A'*A (ou A*A' si elle est plus petit pour A rectangulaire). Il utilise une méthode Lanczos iteration.

tic; 
B = A'*A; % symmetric positive-definite. B = A*A' if it is smaller 
n2 = sqrt(eigs(B, 1)), 
toc 

il sort:

n2 = 89.298 
Elapsed time is 0.311942 seconds. 

Si vous ne souhaitez pas utiliser norm ou eigs, et votre matrice A possède de bonnes propriétés (valeurs singulières correctement séparées), vous pouvez essayer de se rapprocher avec une méthode power iteration:

tic; 
B = A'*A; % or B = A*A' if it is smaller 
x = B(:,1); % example of starting point, x will have the largest eigenvector 
x = x/norm(x); 
for i = 1:200 
    y = B*x; 
    y = y/norm(y); 
    % norm(x - y); % <- residual, you can try to use it to stop iteration 
    x = y; 
end; 
n3 = sqrt(mean(B*x./x)) % translate eigenvalue of B to singular value of A 
toc 

qui, pour la même matrice aléatoire (pas de propriétés particulièrement bonnes) donne une ~0.1% solution précise:

n3 = 89.420 
Elapsed time is 0.428032 seconds.