如何有效地计算矩阵的 2-范数？

Question

假设我有一个矩阵A。我想计算它的2-norm/spectral范数。我怎样才能有效地计算这个？

我知道矩阵的 2-范数等于它的最大奇异值。因此，以下 MATLAB 代码的结果将为零

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

但是要知道 2-范数我必须计算全矩阵 A 的 SVD，有没有有效的方法来计算 2-范数？以 MATLAB 代码形式回答将不胜感激。

Answer 1

这个例子 norm 和随机数据

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

给予

n1 =  89.298
Elapsed time is 2.16777 seconds.

你可以试试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方法。

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

它输出：

n2 =  89.298
Elapsed time is 0.311942 seconds.

如果您不想使用 norm 或 eigs，并且您的矩阵 A 具有良好的属性（正确分隔奇异值），您可以尝试用它来近似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

对于相同的随机矩阵（不是特别好的属性）给出了 ~0.1% 准确的解决方案：

n3 =  89.420
Elapsed time is 0.428032 seconds.

如何有效地计算矩阵的 2-范数？

How to calculate 2-norm of a matrix efficiently?

matlab

matrix

svd

norm