An implicitly restarted bidiagonal Lanczos Method forLarge-scale singular value problems

Xiaohui Wang, Hongyuan Zha1998 · DOI

TL;DR

This paper introduces a new, efficient algorithm for finding the most important components (singular triplets) of very large and sparse matrices, crucial for tasks like information retrieval. Their method, an "implicitly restarted bidiagonal Lanczos algorithm," improves upon existing techniques by simplifying implementation and maintaining computational efficiency.

What Problem Does This Paper Address?

In many real-world applications, we deal with massive matrices that are too large to analyze completely. Think of a matrix representing all documents in a library and all the words they contain – it would be enormous and mostly empty (sparse). To make sense of such data, we often need to find a "low-rank approximation," which means identifying the most significant underlying patterns or "singular triplets." This is directly related to the Singular Value Decomposition (SVD) of the matrix. The challenge is that computing the full SVD for these huge matrices is computationally prohibitive. Existing methods, like the bidiagonal Lanczos algorithm, can find a subset of these important singular triplets, but they suffer from issues like maintaining the accuracy of calculations (orthogonality) and computational overhead, especially when needing to restart the process. This paper aims to provide a more robust and efficient way to perform this crucial task.

Methods

The core of this paper is the development of an "Implicitly Restarted Bidiagonal Lanczos Algorithm" (IRBL). The standard bidiagonal Lanczos algorithm iteratively reduces a large matrix into a smaller, bidiagonal form, from which singular values can be extracted. However, to manage computational costs and maintain accuracy, this process often needs to be "restarted."

The novelty of IRBL lies in its "implicit restart" strategy. Instead of relying on computationally expensive QR decomposition methods (common in other restarted algorithms), IRBL uses a more direct approach to restore the bidiagonal form after truncating the Lanczos process. This involves a "two-way chasing scheme" and careful manipulation of matrix transformations. Additionally, the paper emphasizes the use of a "one-sided reorthogonalization" strategy to maintain the accuracy of the Lanczos vectors without the full cost of complete reorthogonalization. This means they focus on keeping one set of vectors (either left or right singular vectors) orthogonal, which indirectly helps maintain the accuracy of the other set.

Datasets

The paper evaluates its algorithm using three real-world datasets:

  • MEDLINE: A term-document matrix of size 3681 × 1033, commonly used in information retrieval.
  • CRANFIELD: Another term-document matrix, this one of size 2331 × 1400, also from information retrieval.
  • O. Marques' matrix: A very large term-document matrix of size 846968 × 96300, provided by a researcher.

These datasets are representative of the large, sparse matrices encountered in applications like information retrieval and document analysis.

Key Insights and Ideas

  • Implicit Restart Simplicity: The paper's key contribution is a simpler and more direct way to implement implicitly restarted Lanczos methods for SVD. This avoids the complexity and computational burden of traditional QR-based restarts.
  • One-Sided Reorthogonalization is Sufficient: For large-scale problems, maintaining full orthogonality of all Lanczos vectors is often unnecessary and costly. The paper demonstrates that focusing on reorthogonalizing just one set of vectors (left or right) is sufficient to achieve good accuracy, significantly reducing computational overhead.
  • Connection to Inverse Eigenvalue Problems: The authors highlight an interesting theoretical link between their SVD algorithm and inverse eigenvalue problems, suggesting potential for further algorithmic development.
  • Practical Efficiency: The numerical results show that their IRBL algorithm performs comparably to or better than existing methods in terms of accuracy and convergence speed, especially for large matrices.

Key Results

The paper presents numerical results demonstrating the effectiveness of the IRBL algorithm on the described datasets.

  • MEDLINE Example: For a 3681 × 1033 matrix, IRBL computed 10 singular triplets with an error of approximately 2.8 × 10⁻¹². It required 6 restart steps, similar to the implicitly restarted Lanczos (IRL) method.
  • CRANFIELD Example: For a 2331 × 1400 matrix, IRBL computed 5 singular triplets with an error of about 5.4 × 10⁻¹⁴ after just 2 restart steps.
  • Large Matrix Example (O. Marques'): While still preliminary, the application to an 846968 × 96300 matrix showed that reorthogonalization was the most time-consuming part of the computation (64.4% of the time). This highlights the importance of efficient reorthogonalization strategies, which their one-sided approach aims to provide.

Limitations and Future Work

  • Preliminary Results for Very Large Matrices: The results for the 846968 × 96300 matrix are noted as "preliminary," and the full implementation of their algorithm on such scales (e.g., on Cray-T3E) is still underway.
  • Future Work: The authors plan to extend their restart strategy to compute a small number of singular triplets for very large hypertext link structure matrices (on the order of 20 million by 20 million). They also mention that their algorithm is easier to implement than QR-based methods, which is a significant practical advantage.

Summary updated

Abstract

Low rank approximation of large and/or sparse rectangular matrices is a very import ant topic in many application problems and is closely related to the sin- gular value decomposition of the matrices. In this paper, we propose an implicit restart scheme for the bidiagonal Lanczos algorithm to compute a subset of the dominating singular triplets. We also illustrate the connection of the method with inverse eigenvalue problems. In the Lanczos process, we use the so-called one-sided reorthogonalization strategy to maintain the orthogonality level of the Lanczos vec- tors. The efficiency and the applicability of our algorithm are illustrated by some numerical examples from information retrieval applications.
BibTeX
@misc{wang1998implicitly,
  author = {Xiaohui Wang and Hongyuan Zha},
  title = {{An implicitly restarted bidiagonal Lanczos Method forLarge-scale singular value problems}},
  year = {1998},
  doi = {10.2172/6451},
}
Figure