How does `svd(A*A')` reduce the computational cost?

3 views (last 30 days)

Commented: 鹏程 张 on 21 Jun 2021
Computing singular value decomposition is the main computational cost in many algorithms .
For a matrixA(m*n) ,if m is much larger than n , one can compute the SVD of A*A',and then get an approximate SVD of by simple operations to reduce the computational cost.
How does it reduce the computational cost?

I want to know facing a unbalanced matrix, such as 3*5000, why someone reduce the computational cost by svd(A*A') .
The code is as follows.
function [S, V, D, Sigma2] = MySVD(A)
[m, n] = size(A);
if 2*m < n
AAT = A*A';
[S, Sigma2, D] = svd(AAT);
Sigma2 = diag(Sigma2);
V = sqrt(Sigma2);
tol = max(size(A)) * eps(max(V));
R = sum(V > tol);
V = V(1:R);
S = S(:,1:R);
D = A'*S*diag(1./V);
V = diag(V);
return;
end
if m > 2*n
[S, V, D, Sigma2] = MySVD(A');
mid = D;
D = S;
S = mid;
return;
end
[S,V,D] = svd(A);
Sigma2 = diag(V).^2;

Cutie on 21 Jun 2021
SVD reduces computational costs because it provides a numerically stable matrix decomposition. You may refer to https://www.youtube.com/playlist?list=PLMrJAkhIeNNSVjnsviglFoY2nXildDCcv for detailed wokrings of SVD

Thank you for your answer! Maybe I don't express what I want to know!
what I want to know is when facing a unbalanced matrix, such as 3*5000, why someone reduce the computational cost by svd(A*A') .
The code is as follows.
function [S, V, D, Sigma2] = MySVD(A)
[m, n] = size(A);
if 2*m < n
AAT = A*A';
[S, Sigma2, D] = svd(AAT);
Sigma2 = diag(Sigma2);
V = sqrt(Sigma2);
tol = max(size(A)) * eps(max(V));
R = sum(V > tol);
V = V(1:R);
S = S(:,1:R);
D = A'*S*diag(1./V);
V = diag(V);
return;
end
if m > 2*n
[S, V, D, Sigma2] = MySVD(A');
mid = D;
D = S;
S = mid;
return;
end
[S,V,D] = svd(A);
Sigma2 = diag(V).^2;