Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
From MaRDI portal
Publication:6094751
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.
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
Cites work
- A fast randomized algorithm for the approximation of matrices
- Algorithm 971
- CUR matrix decompositions for improved data analysis
- Eigenvalues of a matrix in the streaming model
- Fast Deterministic Approximation of Symmetric Indefinite Kernel Matrices with High Dimensional Datasets
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Generalized Wasserstein distance and its application to transport equations with source
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Local operator theory, random matrices and Banach spaces.
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Matrix Analysis
- Nearly tight oblivious subspace embeddings by trace inequalities
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Practical sketching algorithms for low-rank matrix approximation
- Randomized Nyström Preconditioning
- Randomized numerical linear algebra: Foundations and algorithms
- Revisiting the Nyström method for improved large-scale machine learning
- SPSD matrix approximation vis column selection: theories, algorithms, and extensions
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Sketching as a tool for numerical linear algebra
- Streaming low-rank matrix approximation with an application to scientific simulation
- Why Are Big Data Matrices Approximately Low Rank?
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
- scientific article; zbMATH DE number 4178733 (Why is no real title available?)
- Making the Nystr\"om method highly accurate for low-rank approximations
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- Rigidity theorem for hypersurfaces in a unit sphere
- scientific article; zbMATH DE number 4182700 (Why is no real title available?)
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)
