# Alternatives to SVD for rank factorization

I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \times m}$.

A popular approach is to compute the singular value decomposition (SVD) $M = UDV^*$ and keep the columns of $U$ and rows of $V$ corresponding to the non-zero singular values. This is a great approach, especially since it behaves nicely under noise. However, SVD seems to compute more than I need for just rank factorization (and the noise tolerance is cool, but not necessary).

What are the other approaches I can use? In particular, I am interested in algorithms that have one (or more) of the following properties:

1. Outperform SVD asymptotically.
2. Outperform SVD in practice, or on special inputs (for a reasonably interesting class of special inputs).
3. Performance under small perturbation of $M$ is well understood.

I am fine with giving $k$ to the algorithm ahead of time. Note that SVD does not require this (unless we are doing a perturbation analysis, but even then we usually give a bound on perturbation size and determine $k$ at run-time based on that).

-
Minpack uses a qr decomposition with pivoting. Even a normal LU decomposition (=Gaussian elimination) with pivoting is able to do the trick. There are also Krylov subspace based methods to compute the SVD. For a general matrix, all these methods are O(n^2 m), assuming no tricks like Strassen multiplication are used. I decided against giving more details here, because Computational Science would be a much better place to ask such questions, and I don't want to set wrong precedences. –  Thomas Klimpel Jan 6 '13 at 23:13
Did you find an answer? If not you may want to repost this on Theoretical Computer Science. –  Kaveh Feb 14 '13 at 18:38
@Kaveh thanks, I will flag this question for migration to cstheory. Since you are a moderator there, I assume it is alright from that end? –  Artem Kaznatcheev Feb 15 '13 at 2:03
@Artem, if it is possible it should be fine but unfortunately question older than 60 days cannot be migrated so you have to repost it manually. –  Kaveh Feb 15 '13 at 5:48
@ArtemKaznatcheev What Kaveh said. Please remember to link from here to the new question. –  Raphael Feb 15 '13 at 6:54