Some Software Packages for Partial SVD Computation (implementation)

Following up on the Online SVD/PCA resources entry that Danny just put up on his blog, I wanted to mention some resources that, after some checking, I seemingly failed to mention before. They are all listed in: Some Software Packages for Partial SVD Computation by Zhouchen Lin. The abstract reads:

This technical report introduces some software packages for partial SVD computation, including optimized PROPACK, modified PROPACK for computing singular values above a threshold and the corresponding singular vectors, and block Lanczos with warm start (BLWS). The current version is preliminary. The details will be enriched soon.

If you recall most folks, as recently as Matrix ALPS seem to be using PROPACK:

The software package PROPACK contains a set of functions for computing the singular value decomposition of large and sparse or structured matrices. The SVD routines are based on the Lanczos bidiagonalization algorithm with partial reorthogonalization (BPRO). The Lanczos routines can also be used directly, and form the basis of efficient algorithms for solving linear systems of equations and linear least squares problems, in particular for systems with multiple right-hand sides. 

Eventually I would not be surprised if it were to be used for algo such as SL0 and family. Zhouchen  went on and produced (links to implementations)

• an Optimized PROPACK then,
• a modified PROPACK and then 
• a Block Lanczos with warm start (BLWS).

For more on the BLWS, the attendant paper is: A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms  by Zhouchen Lin and Siming Wei. The abstract reads: 

Recent years have witnessed the popularity of using rank minimization as a regularizer for various signal processing and machine learning problems. As rank minimization problems are often converted to nuclear norm minimization (NNM) problems, they have to be solved iteratively and each iteration requires computing a singular value decomposition (SVD). Therefore, their solution suffers from the high computation cost of multiple SVDs. To relieve this issue, we propose using the block Lanczos method to compute the partial SVDs, where the principal singular subspaces obtained in the previous iteration are used to start the block Lanczos procedure. To avoid the expensive reorthogonalization in the Lanczos procedure, the block Lanczos procedure is performed for only a few steps. Our block Lanczos with warm start (BLWS) technique can be adopted by different algorithms that solve NNM problems. We present numerical results on applying BLWS to Robust PCA and Matrix Completion problems. Experimental results show that our BLWS technique usually accelerates its host algorithm by at least two to three times.

As partial SVD is important in algorithms dedicated to nuclear norm minimization, these resources are listed in the Matrix Factorization Jungle.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.