Sharp Error Bounds for Approximate Eigenvalues and Singular Values from Subspace Methods.
Saved in:
| Title: | Sharp Error Bounds for Approximate Eigenvalues and Singular Values from Subspace Methods. |
|---|---|
| Authors: | Haas, Irina-Beatrice1 (AUTHOR) haas@maths.ox.ac.uk, Nakatsukasa, Yuji1 (AUTHOR) nakatsukasa@maths.ox.ac.uk |
| Source: | SIAM Journal on Matrix Analysis & Applications. 2026, Vol. 47 Issue 1, p308-329. 22p. |
| Subjects: | Rayleigh-Ritz method, Approximation error, Eigenvalues, Krylov subspace, Symmetric matrices, Algorithms |
| Abstract: | Subspace methods are commonly used for finding approximate eigenvalues and singular values of large-scale matrices. Once a subspace is found, the Rayleigh–Ritz method (for symmetric eigenvalue problems) and Petrov–Galerkin projection (for singular values) are the de facto method for extraction of eigenvalues and singular values. In this work we derive quadratic error bounds for approximate eigenvalues of symmetric matrices obtained via the Rayleigh–Ritz process. Our bounds take advantage of the fact that extremal eigenpairs tend to converge faster than the rest, hence having smaller residuals \(\|A\widehat {x}_i-\theta_i\widehat {x}_i\|_2\) , where \((\theta_i,\widehat {x}_i)\) is a Ritz pair (approximate eigenpair). The proof uses the structure of the perturbation matrix underlying the Rayleigh–Ritz method to bound the components of its eigenvectors. In this way, we obtain a bound of the form \(c\frac {\|A\widehat {x}_i-\theta_i\widehat {x}_i\|_2^2}{\textrm{Gap}_i}\) , where \(\textrm{Gap}_i\) is roughly the gap between the \(i\) th Ritz value and the eigenvalues that are not approximated by the Ritz process, and \(c\gt 1\) is a modest scalar. Our bound is adapted to each Ritz value and is robust to clustered Ritz values, which is a key improvement over existing results. We further show that the bound is asymptotically sharp, and generalize it to singular values of arbitrary real matrices. Finally, we apply these bounds to several methods for computing eigenvalues and singular values, and illustrate the sharpness of our bounds in a number of computational settings, including Krylov methods and randomized algorithms. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 192769980 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Sharp Error Bounds for Approximate Eigenvalues and Singular Values from Subspace Methods. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Haas%2C+Irina-Beatrice%22">Haas, Irina-Beatrice</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> haas@maths.ox.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Nakatsukasa%2C+Yuji%22">Nakatsukasa, Yuji</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> nakatsukasa@maths.ox.ac.uk</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Matrix+Analysis+%26+Applications%22">SIAM Journal on Matrix Analysis & Applications</searchLink>. 2026, Vol. 47 Issue 1, p308-329. 22p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Rayleigh-Ritz+method%22">Rayleigh-Ritz method</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+error%22">Approximation error</searchLink><br /><searchLink fieldCode="DE" term="%22Eigenvalues%22">Eigenvalues</searchLink><br /><searchLink fieldCode="DE" term="%22Krylov+subspace%22">Krylov subspace</searchLink><br /><searchLink fieldCode="DE" term="%22Symmetric+matrices%22">Symmetric matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Subspace methods are commonly used for finding approximate eigenvalues and singular values of large-scale matrices. Once a subspace is found, the Rayleigh–Ritz method (for symmetric eigenvalue problems) and Petrov–Galerkin projection (for singular values) are the de facto method for extraction of eigenvalues and singular values. In this work we derive quadratic error bounds for approximate eigenvalues of symmetric matrices obtained via the Rayleigh–Ritz process. Our bounds take advantage of the fact that extremal eigenpairs tend to converge faster than the rest, hence having smaller residuals \(\|A\widehat {x}_i-\theta_i\widehat {x}_i\|_2\) , where \((\theta_i,\widehat {x}_i)\) is a Ritz pair (approximate eigenpair). The proof uses the structure of the perturbation matrix underlying the Rayleigh–Ritz method to bound the components of its eigenvectors. In this way, we obtain a bound of the form \(c\frac {\|A\widehat {x}_i-\theta_i\widehat {x}_i\|_2^2}{\textrm{Gap}_i}\) , where \(\textrm{Gap}_i\) is roughly the gap between the \(i\) th Ritz value and the eigenvalues that are not approximated by the Ritz process, and \(c\gt 1\) is a modest scalar. Our bound is adapted to each Ritz value and is robust to clustered Ritz values, which is a key improvement over existing results. We further show that the bound is asymptotically sharp, and generalize it to singular values of arbitrary real matrices. Finally, we apply these bounds to several methods for computing eigenvalues and singular values, and illustrate the sharpness of our bounds in a number of computational settings, including Krylov methods and randomized algorithms. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192769980 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/25M1764554 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 22 StartPage: 308 Subjects: – SubjectFull: Rayleigh-Ritz method Type: general – SubjectFull: Approximation error Type: general – SubjectFull: Eigenvalues Type: general – SubjectFull: Krylov subspace Type: general – SubjectFull: Symmetric matrices Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Sharp Error Bounds for Approximate Eigenvalues and Singular Values from Subspace Methods. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Haas, Irina-Beatrice – PersonEntity: Name: NameFull: Nakatsukasa, Yuji IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: 2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 08954798 Numbering: – Type: volume Value: 47 – Type: issue Value: 1 Titles: – TitleFull: SIAM Journal on Matrix Analysis & Applications Type: main |
| ResultId | 1 |
