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

  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Jan 6 '13 at 23:13
  • $\begingroup$ Did you find an answer? If not you may want to repost this on Theoretical Computer Science. $\endgroup$ – Kaveh Feb 14 '13 at 18:38
  • $\begingroup$ @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? $\endgroup$ – Artem Kaznatcheev Feb 15 '13 at 2:03
  • 3
    $\begingroup$ @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. $\endgroup$ – Kaveh Feb 15 '13 at 5:48
  • $\begingroup$ @ArtemKaznatcheev What Kaveh said. Please remember to link from here to the new question. $\endgroup$ – Raphael Feb 15 '13 at 6:54

Your Answer

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

Browse other questions tagged or ask your own question.