Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix
By Joel Friedman. 1998
Abstract Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ1. We consider the power method, i.e. that of choosing a vector v0 and setting vk = Akv0; then the Rayleigh quotients Rk = (Avk, vk)/(vk, vk) usually converge to λ1 as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to λ1. They are both based on a bound on λ1 − Rk involving the difference of two consecutive Rayleigh quotients and a quantity ωk. While we do not know how to directly calculate ωk, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ1 − Rk which is proportional to ( λ 2 λ 1 ) 2k , which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Issei Sato
- Yusuke Tsuzuku
- Masashi Sugiyama
- Balaji Lakshminarayanan
- Qiang Yang
- Hirotaka Hachiya
- Wouter M. Kouw
- Dacheng Tao
Citations in the corpus
- Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks (2018, background): “With probability higher than 1 − 2 /π , the error between (cid:107) φ 22 and R k is smaller than The proof is in Appendix C.3, which is mostly from Friedman [10].”