Table of Links
1.1 ESPRIT algorithm and central limit error scaling
1.4 Technical overview and 1.5 Organization
2 Proof of the central limit error scaling
3 Proof of the optimal error scaling
4 Second-order eigenvector perturbation theory
5 Strong eigenvector comparison
5.1 Construction of the “good” P
5.2 Taylor expansion with respect to the error terms
5.3 Error cancellation in the Taylor expansion
C Deferred proofs for Section 2
D Deferred proofs for Section 4
E Deferred proofs for Section 5
F Lower bound for spectral estimation
5.3 Error cancellation in the Taylor expansion
Then, we find that the main components take the form:
Lemma 5.6
Proofs Lemmas 5.5 and 5.6 of are deferred to Appendix E.3.1. They immediately imply the first equation of Eq. (5.10
Corollary 5.7.** It holds that
Proof. We have
where the first step follows from Eq. (5.13a), the second step follows from Eq. (5.14).
Then, we upper-bound the four terms.
More specifically, we establish the following lemma:
Lemma 5.9.
Proofs of Lemmas 5.8 and 5.9 are deferred to Appendix E.3.2. They imply the second inequality of Eq. (5.10).
Corollary 5.10. It holds that
where the first step follows from Eq. (5.16), and the second step follows from Eq. (5.17a) and Eq. (5.17b).
This paper is available on arxiv under CC BY 4.0 DEED license.
Authors:
(1) Zhiyan Ding, Department of Mathematics, University of California, Berkeley;
(2) Ethan N. Epperly, Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA;
(3) Lin Lin, Department of Mathematics, University of California, Berkeley, Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, and Challenge Institute for Quantum Computation, University of California, Berkeley;
(4) Ruizhe Zhang, Simons Institute for the Theory of Computing.