# 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. Jan 6, 2013 at 23:13
• Did you find an answer? If not you may want to repost this on Theoretical Computer Science. Feb 14, 2013 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? Feb 15, 2013 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. Feb 15, 2013 at 5:48
• @ArtemKaznatcheev What Kaveh said. Please remember to link from here to the new question.
– Raphael
Feb 15, 2013 at 6:54

The proper search term in scientific journals is "Rank-Revealing Decomposition". If You want some theoretic guarantees on numeric accuracy/stability, the search term would be "Strong Rank-Revealing Decomposition". There seems to exist a (strong) rank-revealing version of almost every type of decomposition:

## Practically Outperforming SVD

Most SVD implementations, e.g. in LAPACK, are incredibly highly optimized. The opposite is true for strong rank-revealing decompositions: There seem to be no optimized implementations at all. A while ago, I came up with an improved SRRQR variant. One of my very rough benchmarks seem to indicate that the aforementioned SRRQR version could potentially outperform LAPACK's SVD after putting a lot of elbow grease into it. A lot of research and development would be required. The same is likely true for all the other strong rank-revealing decompositions.

The only rank-revealing decomposition used in practice seems to be the RRQR. It outperforms the SVD by a considerable margin but not by an order of magnitude. In fact, the RRQR is used as part of the Jacobi SVD in LAPACK.

## Theoretically Outperforming the SVD

It is my strong belief that we do not yet know enough about decomposition algorithms to answer this question. In 1969, Strassen already found an $$\mathcal{O}(n^{\log_2{7}+\mathcal{o}(1)})$$ algorithm for matrix inversion. Even faster algorithms like Coppersmith-Winograd have been found since. Do such algorithms exist for SVD? For (strong) rank-revealing decompositions? Can we make such algorithms numerically stable? As far as I know, we do not have the answers to these questions yet.

Most decompositions (including the SRRQR) use an $$\mathcal{O}\left(\max{(m,n)}\cdot\min^2{(m,n)}\right)$$ implementation, making their complexity identical in practice.

Current R&D seems to be heavily focused on sparse and tensor decompositions, so we will likely not get an answer to these questions any time soon.

## Numeric Accuracy/Stability

While RRQR works really accurately in practice, it is easy to construct synthetic examples where it fails completely (see Matrix Computations, 4th ed., Chapter 5.4.3).

The strong rank-revealing factorizations all make some theoretic guarantees of one kind of another which should make them more resilient to pathologically bad inputs.

• I upvoted as this answered the question: RRQR is an alternative to SVD, is used in practice, and considerably outperforms SVD in practice. Feb 23 at 15:52