Как эффективно вычислять 2-норму матрицы?

Question

Предположим, что у меня есть матрица А. Я хочу рассчитать ее 2-норму/спектральную норму. Как я могу рассчитать это эффективно?

Я знаю, что 2-норма матрицы равна ее наибольшему сингулярному значению. Таким образом, результат следующего кода MATLAB будет нулевой

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

Но знать 2-норму, я должен вычислить СВД полной матрицы А, есть ли эффективный способ расчета 2-норма? Ответ в виде кода MATLAB будет значительно опереться.

Answer 1

Этот пример с norm и случайными данными

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

дает

n1 = 89.298 
Elapsed time is 2.16777 seconds. 

Вы можете попробовать eigs найти только один (самый большой) собственное значение симметричной матрицы A'*A (или A*A' если он меньше для 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.