Randomized low-rank approximation for symmetric indefinite matrices

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.

• Publication year

  2022

• Venue

  SIAM Journal on Matrix Analysis and Applications

• Publication date

  2022-12-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/22M1538648arXiv 2212.01127
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Fast Deterministic Approximation of Symmetric Indefinite Kernel Matrices with High Dimensional Datasets

  2021influential reference
• Sublinear Time Approximation of Text Similarity Matrices

  2021influential reference
• Randomized Nyström Preconditioning

  2021cited by this paper
• Fast and stable randomized low-rank matrix approximation

  2020influential reference
• Randomized numerical linear algebra: Foundations and algorithms

  2020influential reference
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation

  2019cited by this paper
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

  2019cited by this paper
• Low-rank approximation in the Frobenius norm by column and row subset selection

  2019cited by this paper
• Scalable Learning in Reproducing Kernel Krein Spaces

  2018cited by this paper
• Algorithm 971

  2017cited by this paper
• Why Are Big Data Matrices Approximately Low Rank?

  2017cited by this paper
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

  2017cited by this paper
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds

  2017influential reference
• Practical Sketching Algorithms for Low-Rank Matrix Approximation

  2016cited by this paper
• FINDING STRUCTURE WITH RANDOMNESS : PROBABILISTIC ALGORITHMS FOR CONSTRUCTING

  2016influential reference
• Randomized Clustered Nystrom for Large-Scale Kernel Machines

  2016cited by this paper
• Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities

  2016cited by this paper
• Recursive Sampling for the Nystrom Method

  2016cited by this paper
• Large-Scale Nyström Kernel Matrix Approximation Using Randomized SVD

  2015cited by this paper
• Sketching as a Tool for Numerical Linear Algebra

  2014cited by this paper
• Metric and non-metric proximity transformations at linear costs

  2014cited by this paper
• SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions

  2014cited by this paper
• Eigenvalues of a matrix in the streaming model

  2013cited by this paper
• Revisiting the Nystrom Method for Improved Large-scale Machine Learning

  2013influential reference
• OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

  2012cited by this paper
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform

  2012cited by this paper
• Low-Rank Approximation and Regression in Input Sparsity Time

  2012cited by this paper
• Generalized Wasserstein Distance and its Application to Transport Equations with Source

  2012cited by this paper
• The spectral norm error of the naive Nystrom extension

  2011cited by this paper
• Improved Analysis of the subsampled Randomized Hadamard Transform

  2010cited by this paper
• CUR matrix decompositions for improved data analysis

  2009cited by this paper
• A fast randomized algorithm for the approximation of matrices ✩

  2007cited by this paper
• Improved Approximation Algorithms for Large Matrices via Random Projections

  2006cited by this paper
• On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning

  2005cited by this paper
• Economic inequality and burden-sharing in the provision of local environmental quality

  2002influential reference
• Using the Nyström Method to Speed Up Kernel Machines

  2000cited by this paper
• Über Die Praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben

  1930cited by this paper

• Stochastic trace estimation for parameter-dependent matrices applied to spectral density approximation

  2025cites this paper
• Accuracy and Stability of CUR decompositions with Oversampling

  2024cites this paper
• Graph Laplacian-based Bayesian Multi-fidelity Modeling

  2024cites this paper
• A generalized Nystrom method with column sketching for low-rank approximation of nonsymmetric matrices

  2024influential citation
• A New Matrix Truncation Method for Improving Approximate Factorization Preconditioners

  2023influential citation
• Efficient training of Gaussian processes with tensor product structure

  2023cites this paper
• A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format

  2023cites this paper