Lanczos Bidiagonalization With Partial Reorthogonalization

By R. Larsen. 1998

A partial reorthogonalization procedure (BPRO) for maintaining semi-orthogonality among the left and right Lanczos vectors in the Lanczos bidiagonalization (LBD) is presented. The resulting algorithm is mathematically equivalent to the symmetric Lanczos algorithm with partial reorthogonalization (PRO) developed by Simon but works directly on the Lanczos bidiagonalization of A. For computing the singular values and vectors of a large sparse matrix with high accuracy, the BPRO algorithm uses only half the amount of storage and a factor of 3-4 less work compared to methods based on PRO applied to an equivalent symmetric system. Like PRO the algorithm presented here is based on simple recurrences which enable it to monitor the loss of orthogonality among the Lanczos vectors directly without forming inner products. These recurrences are used to develop a Lanczos bidiagonalization algorithm with partial reorthogonalization which has been implemented in a MATLAB package for sparse SVD and eigenvalue problems called PROPACK. Numerical experiments with the routines from PROPACK are conducted using a test problem from inverse helioseismology to illustrate the properties of the method. In addition a number of test matrices from the Harwell-Boeing collection are used to compare the accuracy and efficiency of the MATLAB implementations of BPRO and PRO with the svds routine in MATLAB 5.1, which uses an implicitly restarted Lanczos algorithm.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, methodology): “In (5) YSP has the same sparsity structure as the observed X, and YLR has the rank r ≪ m, n of the estimated Z. For large scale problems, we use iterative methods based on Lanczos bidiagonalization with partial re-orthogonalization (as in the PROPACK algorithm [ Lar98 ]), for computing the first r s”
RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images (2010, methodology): “These strategies include low-level tricks such as rank prediction [39], the use of the Lanczos algorithm for computing only a few singular vectors [40] with warm starts, as well as algorithmic modifications such as the use of randomized approximations to the SVD [41], [42].”
A collaborative framework for 3D alignment and classification of heterogeneous subvolumes in cryo-electron tomography (2010, methodology): “for the RPCA and MC problems is unnecessary: we only need those 11 singular values that are larger than a particular threshold and their corresponding singular vectors. So a software package, PROPACK [17], has been widely recommended in the community.To use PROPACK,one have to predict the dimension ”
A Multi-View Embedding Space for Modeling Internet Images, Tags, and Their Semantics (2012, methodology): “We apply sparse SVD (Larsen, 1998) to the tag feature T to obtain a low-rank decomposition as T = U1SU>2 .”
Low-Rank Modeling of Local k-Space Neighborhoods (LORAKS) for Constrained MRI (2014, methodology): “ˆ k (i) = arg min k∈C S Fk − d 2 2 +λ C PC (k) − Q (i) 2 F +λ G PG (k) − U (i) 2 F +λ S PS (k) − V (i) 2 F (34) used the older PROPACK [59] MATLAB toolbox.”
Augmented Implicitly Restarted Lanczos Bidiagonalization Methods (2005, methodology): “The code irlanb calls Larsen’s MATLAB code lanbpro [ 18 ] to compute partial Lanczos bidiagonalizations with partial reorthogonalization.”
Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix (2009, methodology): “For example, we may run PROPACK (or any other algorithms devoted to computing the leading singular spaces) with different random initial vectors simultaneously, each thread outputting a fraction of the singular vectors, and then choose an orthonormal basis among the collection of all output singular”
Unsupervised learning techniques for an intrusion detection system (2004, background): “the rank of the matrix and so r = min{p, q} [18].”
Handbook of Big Data (2016, methodology): “To avoid loss of orthogonality due to finite precision arithmetic, reorthogonalization is performed in lines 5 and 9 of the GKLB algorithm, and the reader is referred to the reorthogonalization strategies discussed in the literature, for example, [19,27,33].”
Randomized Matrix Decompositions using R (2016, methodology): “The svd package provides a wrapper for the PROPACK SVD algorithm (Larsen 1998).”
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation (2011, methodology): “…to apply the singular value shrinkage operator [2], with a threshold If N k is formed explicitly, the usual technique of partial SVD, using PROPACK [11], with rank prediction [12, 21, 17] can be utilized to compute the leading r singular values and associated vectors of N k efﬁciently, making the…”
Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations (2011, methodology): “As well-known, however, PROPACK is not able to compute automatically those singular values larger than the particular threshold, even it does have the ability to compute the first p singular values for any given p ≤ r.”