13
$\begingroup$

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

$\endgroup$
5
  • $\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$ Jan 6, 2013 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, 2013 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$ Feb 15, 2013 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, 2013 at 5:48
  • $\begingroup$ @ArtemKaznatcheev What Kaveh said. Please remember to link from here to the new question. $\endgroup$
    – Raphael
    Feb 15, 2013 at 6:54

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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