How to calculate 2-norm of a matrix efficiently?

Question

Suppose I have a matrix A. I want to calculate its 2-norm/spectral norm. How can I calculate this efficiently?

I know 2-norm of a matrix is equal to its largest singular value. So, result of the following MATLAB code will be zero

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

But to know 2-norm I have to calculate SVD of full matrix A, is there any efficient way to calculate 2-norm? Answer in form of MATLAB code will be much appereciated.

s(0,0) is invalid MATLAB syntax. Did you even run this code? — Adriaan
What's the problem with norm(A,2) ? In general, if Matlab has a built-in function it's about the fastest you can get, especially for matrix algebra — Luis Mendo
I bet it will be hard to beat norm in terms of precision or speed — Luis Mendo

Iban Cereijo Iban Cereijo · Accepted Answer · 2017-02-14T11:02:53

This example with norm and random data

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

gives

n1 =  89.298
Elapsed time is 2.16777 seconds.

You can try eigs to find only one (the largest) eigenvalue of the symmetric matrix A'*A (or A*A' if it is smaller for A rectangular). It uses a Lanczos iteration method.

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

it outputs:

n2 =  89.298
Elapsed time is 0.311942 seconds.

If you don't want to use norm or eigs, and your matrix A has good properties (singular values properly separated), you can try to approximate it with a power iteration method:

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

which for the same random matrix (not particularly good properties) gives a ~0.1% accurate solution:

n3 =  89.420
Elapsed time is 0.428032 seconds.

How to calculate 2-norm of a matrix efficiently?

1 Answers