<p>Computing the SVD of an m × n matrix has complexity O(mn min(n, m)). Since this is super-linear in the size of the data, it becomes computationally expensive for large data sets. However, if we have a low rank matrix, we would need only k basis vectors, where k &lt;&lt; m, n. One way of computing the rank k approximation is to compute the SVD of the full matrix and retain only the k largest singular values and vectors.</p>
<p><a href="https://arxiv.org/pdf/1710.02812.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1710.02812.pdf</a></p>
Time Complexity of Singular Value Decomposition
<p>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 <a href="http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf" rel="noreferrer">here</a>, 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.</p>

<p>However, according <a href="http://rakaposhi.eas.asu.edu/s01-cse494-mailarchive/msg00028.html" rel="noreferrer">this website</a>, 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?</p>