Time Complexity of Singular Value Decomposition

Question

I've been trying to implement SVD in C for the past few weeks now, and currently I've been using the algorithm 6 found here, and from my understanding this algorithm will run in time O(n^5) because there are two loops (One of the loops does not go from 0 to n, I know but n^5 works as a crude bound), and inside the inner loop matrix multiplication has to be done which is an n^3 process.

However, according this website, for an n by n matrix, SVD can be calculated in O(2n^3). Does anyone know where I can find an algorithm for that time complexity?

Answer 1

In the event anyone is looking for an answer to this in the future, the algorithm to calculate SVD in O(n^3), if the matrix is a square matrix, is the method of Jacobi Rotations.

For more information on the specific algorithm you can look at Algorithm 7 on this website.

The notation on the website is a little confusing, because of the typos, but in the step when determining the values of d1, d2, c, and č (sorry that's the closest I could get to c with the hat on top), what they mean is that c = cos(theta), s = sin(theta), č = cos(phi) and š = sin(phi).

You can calculate these values of theta and phi by elimination and substitution or you can check out this StackExchange post to see how to calculate them.

After that it is just following that algorithm.