Sharp error bounds for Ritz vectors and approximate singular vectors

DOI10.1090/MCOM/3519zbMATH Open1441.65038arXiv1810.02532OpenAlexW3000491885WikidataQ126385966 ScholiaQ126385966MaRDI QIDQ4960077FDOQ4960077

Yuji Nakatsukasa

Publication date: 8 April 2020

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We derive sharp bounds for the accuracy of approximate eigenvectors (Ritz vectors) obtained by the Rayleigh-Ritz process for symmetric eigenvalue problems. Using information that is available or easy to estimate, our bounds improve the classical Davis-Kahan $sinheta$ theorem by a factor that can be arbitrarily large, and can give nontrivial information even when the $sinheta$ theorem suggests that a Ritz vector might have no accuracy at all. We also present extensions in three directions, deriving error bounds for invariant subspaces, singular vectors and subspaces computed by a (Petrov-Galerkin) projection SVD method, and eigenvectors of self-adjoint operators on a Hilbert space.

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

Recommendations

• Cluster-robust accuracy bounds for Ritz subspaces
• New estimates for Ritz vectors
• Optimal a priori error bounds for the Rayleigh-Ritz method
• scientific article; zbMATH DE number 1368803
• Cluster robust error estimates for the Rayleigh-Ritz approximation. I: Estimates for invariant subspaces
• A generalisation of the Rayleigh-Ritz approximation
• Majorization bounds for Ritz values of Hermitian matrices
• On Ritz approximations for positive definite operators. I: Theory
• Rayleigh-Ritz majorization error bounds with applications to FEM
• Accuracy of computed eigenvectors via optimizing a Rayleigh quotient

zbMATH Keywords

eigenvectorsself-adjoint operatorsinvariant subspacessingular vectorsDavis-Kahan theoremRayleigh-Ritz process

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cites Work

• Templates for the Solution of Algebraic Eigenvalue Problems
• PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations
• Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
• The Rotation of Eigenvectors by a Perturbation. III
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Perturbation theory for linear operators.
• Numerical Methods for Large Eigenvalue Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applied analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence of the block Lanczos method for eigenvalue clusters
• A note on eigenvalues of perturbed Hermitian matrices
• New estimates for Ritz vectors
• Accuracy of singular vectors obtained by projection-based SVD methods
• A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems
• Cluster robust error estimates for the Rayleigh-Ritz approximation. I: Estimates for invariant subspaces

Cited In (8)

• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• New estimates for Ritz vectors
• Fully computable a posteriori error bounds for eigenfunctions
• Efficient bounds and estimates for canonical angles in randomized subspace approximations
• Accuracy of computed eigenvectors via optimizing a Rayleigh quotient
• Efficient semidefinite programming with approximate ADMM
• Accuracy of approximate projection to the semidefinite cone
• Computable Pointwise Error Bounds and the Ritz Method in One Dimension

Uses Software

• JDQR
• PRIMME
• Chebfun
• JDQZ
• PRIMME_SVDS
• lobpcg.m

This page was built for publication: Sharp error bounds for Ritz vectors and approximate singular vectors

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