# Asymptotic complexity of fixed-rank SVD

According to the Wikipedia article on Singular Value Decomposition, the asymptotic complexity of computing the SVD of an arbitrary m×n matrix M with m>n by the popular Householder QR methods is O(mn2). Are there any algorithms (perhaps Householder QR) that provide better asymptotic guarantees for fixed-rank matrices?

In other words: let Sn,k be the collection of n×n matrix of rank k. Are there algorithms that provide a better asymptotic complexity of computing the SVD of elements of Sn,k as n→∞ than O(n3)?

• If you know the rank k, randomized SVD is extremely fast in practice (though asymptotically not better than rank revealing QR). Nov 29, 2020 at 22:36

Yes. You can run rank-revealing QR on your matrix $$A$$, which will stop at step $$k$$ (hence effectively terminating in $$O(mnk)$$) and produce $$A = QRP$$, where $$R$$ has nonzeros only in its first $$k$$ rows, and $$Q,P$$ are orthogonal. You can now compute and SVD of $$R$$, and use it to piece back the factors with a few matrix products with cost $$O(\max(m,n)k^2)$$.