1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ If you know the rank k, randomized SVD is extremely fast in practice (though asymptotically not better than rank revealing QR). $\endgroup$ Nov 29 '20 at 22:36
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.