A generalized Nystrom method with column sketching for low-rank approximation of nonsymmetric matrices

Yatian Wang, Hua Xiang, Chi Zhang, Songling ZhangarXiv 2024 · DOI · arXiv

Abstract

Low-rank approximation (LRA) is a fundamental tool in numerical linear algebra, enabling the compression and analysis of massive datasets. While the Nyström method is highly efficient for symmetric positive semidefinite matrices, extending its benefits to nonsymmetric matrices has historically been challenging due to numerical instability and lower accuracy. This paper introduces a Generalized Nyström method with column sketching (GN-c). By utilizing orthonormal bases to update sketching matrices, GN-c provides a stable and precise approximation that outperforms standard Randomized SVD (rSVD) and existing Generalized Nyström variants. Experimental results on synthetic and real-world sparse matrices demonstrate that GN-c achieves superior accuracy and, in many cases, improved computational efficiency.

Introduction

Finding a low-rank approximation for a massive matrix $A \in \mathbb{R}^{m \times n}$ typically involves the Singular Value Decomposition (SVD). However, the SVD's computational cost is often prohibitive for modern large-scale applications. Randomized algorithms, such as rSVD, address this by using random sketches of the matrix, but they can still require significant computational resources for multiple passes or dense matrix-matrix multiplications.

Historically, the Nyström method has served as a faster alternative for symmetric matrices. Existing "Generalized Nyström" (GN) approaches for nonsymmetric matrices often suffer from numerical instability because they rely on independent random sketches that do not effectively capture the matrix's range. This research proposes a refined approach to bring Nyström-level efficiency and stability to the nonsymmetric domain.

Methods

The researchers propose two primary variants of the Generalized Nyström method to address the limitations of the standard approach:

  1. GN-r&c (Row and Column Sketching): This version sketches both rows and columns independently and updates them using QR factorizations. It is highly accurate but computationally and memory-intensive.
  2. GN-c (Column Sketching): The paper's primary contribution, GN-c, uses a single random sketch to inform a second sketching step. By computing an orthonormal basis from the first sketch and using it to sketch the transpose, GN-c creates a feedback loop that more effectively captures the significant components of the matrix.
Algorithm 2-1: The standard Generalized Nyström (GN) approximation for nonsymmetric matrices, which serves as the baseline for the proposed improvements.

By incorporating orthonormalization (via QR factorization), the proposed methods bypass the stability issues common in standard GN, which often involve inverting ill-conditioned core matrices.

Experimental Evaluation

The algorithms were evaluated using a variety of benchmarks:

  • Synthetic Matrices: $10,000 \times 10,000$ and $15,000 \times 15,000$ matrices with controlled singular value decay (polynomial and exponential).
  • Real-World Sparse Matrices: Datasets from the Matrix Market, including fidap011 (fluid dynamics), bcsstm25 (structural engineering), and jan99jac060 (economic modeling).

Results and Discussion

The experimental results highlight several key advantages of the proposed methods:

  • Superior Accuracy: In both synthetic and real-world tests, the refined GN variants consistently achieved lower relative errors in the Frobenius norm compared to rSVD and standard GN.
  • Stability and Robustness: The use of orthonormal bases makes the methods robust against varying singular value decay rates and oversampling parameters.
  • Computational Efficiency: While the high-accuracy GN-r&c variant is slower due to its complexity, the optimized GN-c variant demonstrates competitive runtimes, particularly for large-scale sparse matrices where it can outperform rSVD.

Conclusion

The Generalized Nyström method with column sketching (GN-c) represents a significant advancement in low-rank approximation for nonsymmetric matrices. By combining the speed of Nyström-based sketching with the stability of orthonormalization, it offers a powerful alternative to rSVD. Future work will explore the integration of communication-avoiding randomized QR factorizations to further enhance performance on distributed computing systems.

Summary updated

BibTeX
@misc{wang2024generalized,
  author = {Yatian Wang and Hua Xiang and Chi Zhang and Songling Zhang},
  title = {{A generalized Nystrom method with column sketching for low-rank approximation of nonsymmetric matrices}},
  year = {2024},
  eprint = {2410.21829},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.21829},
}
Figure