Table of Links Abstract and 1 Introduction 1.1 ESPRIT algorithm and central limit error scaling 1.2 Contribution 1.3 Related work 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 5.4 Proof of Theorem 5.1 A Preliminaries B Vandermonde matrice C Deferred proofs for Section 2 D Deferred proofs for Section 4 E Deferred proofs for Section 5 F Lower bound for spectral estimation References 5 Strong eigenvector comparison The goal of this section is to prove the strong version of the eigenvectors comparison theorem stated below, which is the key component of obtaining the optimal convergence rate of the ESPRIT algorithm. Theorem 5.1 (Eigenvectors comparison: strong estimation, formal version of Theroem 1.9). Assume Eq. (1.3) and Eq. (1.4). Suppose Our proof of Theorem 5.1 consists of three steps: • Step 1: Construction of the “good” aligning matrix P (Section 5.1) • Step 2: Taylor expansion with respect to the error terms (Section 5.2) • Step 3: Error cancelation in the Taylor expansion (Section 5.3) We will introduce these three steps in Section 5.1 - Section 5.3 and prove Theorem 5.1 in Section 5.4. Most detialed calculations are deferred to Appendix E. 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. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 1.1 ESPRIT algorithm and central limit error scaling 1.1 ESPRIT algorithm and central limit error scaling 1.2 Contribution 1.2 Contribution 1.3 Related work 1.3 Related work 1.4 Technical overview and 1.5 Organization 1.4 Technical overview and 1.5 Organization 2 Proof of the central limit error scaling 2 Proof of the central limit error scaling 3 Proof of the optimal error scaling 3 Proof of the optimal error scaling 4 Second-order eigenvector perturbation theory 4 Second-order eigenvector perturbation theory 5 Strong eigenvector comparison 5 Strong eigenvector comparison 5.1 Construction of the “good” P 5.1 Construction of the “good” P 5.2 Taylor expansion with respect to the error terms 5.2 Taylor expansion with respect to the error terms 5.3 Error cancellation in the Taylor expansion 5.3 Error cancellation in the Taylor expansion 5.4 Proof of Theorem 5.1 5.4 Proof of Theorem 5.1 A Preliminaries A Preliminaries B Vandermonde matrice B Vandermonde matrice C Deferred proofs for Section 2 C Deferred proofs for Section 2 D Deferred proofs for Section 4 D Deferred proofs for Section 4 E Deferred proofs for Section 5 E Deferred proofs for Section 5 F Lower bound for spectral estimation F Lower bound for spectral estimation References References 5 Strong eigenvector comparison The goal of this section is to prove the strong version of the eigenvectors comparison theorem stated below, which is the key component of obtaining the optimal convergence rate of the ESPRIT algorithm. Theorem 5.1 (Eigenvectors comparison: strong estimation, formal version of Theroem 1.9). Assume Eq. (1.3) and Eq. (1.4). Suppose Theorem 5.1 (Eigenvectors comparison: strong estimation, formal version of Theroem Our proof of Theorem 5.1 consists of three steps: • Step 1: Construction of the “good” aligning matrix P (Section 5.1) Step 1: • Step 2: Taylor expansion with respect to the error terms (Section 5.2) Step 2: • Step 3: Error cancelation in the Taylor expansion (Section 5.3) Step 3: We will introduce these three steps in Section 5.1 - Section 5.3 and prove Theorem 5.1 in Section 5.4. Most detialed calculations are deferred to Appendix E. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv 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. Authors: 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.