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
2 Proof of the central limit error scaling
The main proof roadmap is the same as the previous work [LLF20] with small modifications. All technical proofs and calculations are deferred to Appendix C
This result is similar to existing results such as [Moi15, Lem. 2.7] and [LLF20, Lems. 2, 5, & 6] and our proof (in Appendix C.2) is based on similar ideas. The main ingredients in our proof of this result are Moitra’s bounds on the singular values of Vandermonde matrices (Appendix B.1), standard results in matrix perturbation theorem (Appendix A.5), and a comparison lemma between the Vandermonde and eigenbases (Lemma 1.7)
To convert the bound Eq. (2.2) into actionable information for the ESPRIT algorithm, we use the following result:
This result slightly improves Lemma 2 in [LLF20] and is proven by the combination of the Bauer–Fike theorem (Theorem A.11) and the resolvent approach for eigenvalue perturbation (Lemma A.13). The proof is deferred to Appendix C.3.
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.
