Asymptotic complexity of fixed-rank SVD

Question

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)?

Federico Poloni · Answer

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)$.

Answered by Federico Poloni on June 25, 2021

Asymptotic complexity of fixed-rank SVD

One Answer

Add your own answers!

Ask a Question