Facing a unbalanced matrix, such as 3*5000, why someone reduce the computational cost by svd(A*A') .

1 view (last 30 days)
Computing singular value decomposition is the main computational cost in many algorithms . For a matrix A(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?
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);
if m > 2*n
[S, V, D, Sigma2] = MySVD(A');
mid = D;
D = S;
S = mid;
[S,V,D] = svd(A);
Sigma2 = diag(V).^2;

Accepted Answer

Christine Tobler
Christine Tobler on 21 Jun 2021
The computational complexity of svd (when using the 'econ' option, which is very necessary for matrices that are far from square) is O(max(m,n)*min(m,n)^2). This can be seen as applying QR to A in a first step, and then computing the SVD of the R matrix coming out of this QR operation (which is relatively cheap in comparison). No need for you to call QR in MATLAB code, this is done internally in the SVD command already.
Instead computing A*A' / A'*A (whichever is smaller based on A's size) has the same computational complexity as above. However, matrix multiply is a cheaper operation than QR, so in practice it's going to be less expensive to apply this.
But this computation is also less accurate: Computing A*A' squares the condition number, so the SVD is applied to a matrix that is worse conditioned and will be less accurate than A applied to the original matrix.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!