Sharp error bounds for Ritz vectors and approximate singular vectors
HTML articles powered by AMS MathViewer
- by Yuji Nakatsukasa HTML | PDF
- Math. Comp. 89 (2020), 1843-1866 Request permission
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 $\sin \theta$ theorem by a factor that can be arbitrarily large, and can give nontrivial information even when the $\sin \theta$ 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.References
- Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst (eds.), Templates for the solution of algebraic eigenvalue problems, Software, Environments, and Tools, vol. 11, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. A practical guide. MR 1792141, DOI 10.1137/1.9780898719581
- Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI 10.1137/0707001
- T. A. Driscoll, N. Hale, and L. N. Trefethen. Chebfun Guide. Pafnuty Publications, 2014.
- Gerald B. Folland, Fourier analysis and its applications, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1992. MR 1145236
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
- N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev. 53 (2011), no. 2, 217–288. MR 2806637, DOI 10.1137/090771806
- Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1991. MR 1091716, DOI 10.1017/CBO9780511840371
- John K. Hunter and Bruno Nachtergaele, Applied analysis, World Scientific Publishing Co., Inc., River Edge, NJ, 2001. MR 1829589, DOI 10.1142/4319
- Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452
- Andrew V. Knyazev, New estimates for Ritz vectors, Math. Comp. 66 (1997), no. 219, 985–995. MR 1415802, DOI 10.1090/S0025-5718-97-00855-7
- Andrew V. Knyazev, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput. 23 (2001), no. 2, 517–541. Copper Mountain Conference (2000). MR 1861263, DOI 10.1137/S1064827500366124
- Chi-Kwong Li and Ren-Cang Li, A note on eigenvalues of perturbed Hermitian matrices, Linear Algebra Appl. 395 (2005), 183–190. MR 2112884, DOI 10.1016/j.laa.2004.08.026
- Ruipeng Li, Yuanzhe Xi, Eugene Vecharynski, Chao Yang, and Yousef Saad, A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput. 38 (2016), no. 4, A2512–A2534. MR 3537014, DOI 10.1137/15M1054493
- Ren-Cang Li and Lei-Hong Zhang, Convergence of the block Lanczos method for eigenvalue clusters, Numer. Math. 131 (2015), no. 1, 83–113. MR 3383329, DOI 10.1007/s00211-014-0681-6
- Yuji Nakatsukasa, Accuracy of singular vectors obtained by projection-based SVD methods, BIT 57 (2017), no. 4, 1137–1152. MR 3736004, DOI 10.1007/s10543-017-0665-x
- E. Ovtchinnikov, Cluster robust error estimates for the Rayleigh-Ritz approximation. I. Estimates for invariant subspaces, Linear Algebra Appl. 415 (2006), no. 1, 167–187. MR 2214751, DOI 10.1016/j.laa.2005.06.040
- Beresford N. Parlett, The symmetric eigenvalue problem, Classics in Applied Mathematics, vol. 20, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. MR 1490034, DOI 10.1137/1.9781611971163
- Yousef Saad, Numerical methods for large eigenvalue problems, Classics in Applied Mathematics, vol. 66, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Revised edition of the 1992 original [ 1177405]. MR 3396212, DOI 10.1137/1.9781611970739.ch1
- G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- Lingfei Wu, Eloy Romero, and Andreas Stathopoulos, PRIMME$_-$SVDS: a high-performance preconditioned SVD solver for accurate large-scale computations, SIAM J. Sci. Comput. 39 (2017), no. 5, S248–S271. MR 3716557, DOI 10.1137/16M1082214
Additional Information
- Yuji Nakatsukasa
- Affiliation: Mathematical Institute, University of Oxford, Oxford, OX2 6GG, United Kingdom
- MR Author ID: 887438
- Email: nakatsukasa@maths.ox.ac.uk
- Received by editor(s): October 5, 2018
- Received by editor(s) in revised form: September 23, 2019
- Published electronically: January 29, 2020
- Additional Notes: This work was supported by JSPS grants No. 17H01699 and 18H05837, and JST grant JPMJCR1914.
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 1843-1866
- MSC (2010): Primary 15A18, 15A42, 65F15
- DOI: https://doi.org/10.1090/mcom/3519
- MathSciNet review: 4081920