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

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?

[SALAH ALRABEEI]

Read this nice topic https://towardsdatascience.com/understanding-singular-value-decomposition-and-its-application-in-data-science-388a54be95d?_branch_match_id=900491107502225277

[鹏程 张]

Thank you for your answer!

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;

Answer 1

[Cutie]

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;