Randomized Low-Rank Approximation for Symmetric Indefinite Matrices

DOI10.1137/22M1538648zbMATH Open1522.65068arXiv2212.01127OpenAlexW4386539915MaRDI QIDQ6094751FDOQ6094751

Authors: Yuji Nakatsukasa 

Publication date: 14 September 2023

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: The Nystr"om method is a popular choice for finding a low-rank approximation to a symmetric positive semi-definite matrix. The method can fail when applied to symmetric indefinite matrices, for which the error can be unboundedly large. In this work, we first identify the main challenges in finding a Nystr"om approximation to symmetric indefinite matrices. We then prove the existence of a variant that overcomes the instability, and establish relative-error nuclear norm bounds of the resulting approximation that hold when the singular values decay rapidly. The analysis naturally leads to a practical algorithm, whose robustness is illustrated with experiments.

Full work available at URL: https://arxiv.org/abs/2212.01127

Recommendations

• Randomized algorithms for the low-rank approximation of matrices
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• The inertia of the symmetric approximation for low-rank matrices
• Low rank approximation of the symmetric positive semidefinite matrix
• Randomized methods for rank-deficient linear systems
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Efficient Low-Rank Approximation of Matrices Based on Randomized Pivoted Decomposition
• Low-rank matrix approximation in the infinity norm
• Randomized complete pivoting for solving symmetric indefinite linear systems
• Randomized Low-Rank Approximation of Monotone Matrix Functions

zbMATH Keywords

low-rank approximationsymmetric matricesrandomized linear algebraNyström method

Mathematics Subject Classification ID

Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Matrix Analysis
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Local operator theory, random matrices and Banach spaces.
• CUR matrix decompositions for improved data analysis
• Why Are Big Data Matrices Approximately Low Rank?
• Improved analysis of the subsampled randomized Hadamard transform
• Revisiting the Nyström method for improved large-scale machine learning
• Generalized Wasserstein distance and its application to transport equations with source
• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• Randomized numerical linear algebra: Foundations and algorithms
• A fast randomized algorithm for the approximation of matrices
• Eigenvalues of a matrix in the streaming model
• SPSD matrix approximation vis column selection: theories, algorithms, and extensions
• Streaming low-rank matrix approximation with an application to scientific simulation
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Sketching as a tool for numerical linear algebra
• Algorithm 971
• Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
• Practical sketching algorithms for low-rank matrix approximation
• Fast Deterministic Approximation of Symmetric Indefinite Kernel Matrices with High Dimensional Datasets
• Nearly tight oblivious subspace embeddings by trace inequalities
• Randomized Nyström Preconditioning

Cited In (11)

• Single-pass Nyström approximation in mixed precision
• Fast Deterministic Approximation of Symmetric Indefinite Kernel Matrices with High Dimensional Datasets
• Low rank approximation of the symmetric positive semidefinite matrix
• A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
• The inertia of the symmetric approximation for low-rank matrices
• Revisiting the Nyström method for improved large-scale machine learning
• Title not available (Why is that?)
• Making the Nystr\"om method highly accurate for low-rank approximations
• Randomized Low-Rank Approximation of Monotone Matrix Functions
• Title not available (Why is that?)
• Rigidity theorem for hypersurfaces in a unit sphere

This page was built for publication: Randomized Low-Rank Approximation for Symmetric Indefinite Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094751)