ESPRIT Algorithm: The Proof of Theorem

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.4 Proof of Theorem 5.1

By Eq. (5.4) and Eq. (5.15),

And by Eq. (5.18),

Thus, we obtain that

which completes the proof of the theorem.

Acknowledgments. This material is partially supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Quantum Systems Accelerator (Z.D.), by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship under Award Number DE-SC0021110 (E.N.E.), by the Applied Mathematics Program of the US Department of Energy (DOE) Office of Advanced Scientific Computing Research under contract number DE-AC02- 05CH1123 and the Simons Investigator program (L.L.), and by the Simons Institute for the Theory of Computing, through a Quantum Postdoctoral Fellowship (R.Z.). We thank the Institute for Pure and Applied Mathematics (IPAM) for its hospitality throughout the semester-long program “Mathematical and Computational Challenges in Quantum Computing” in Fall 2023 during which this work was initiated. We thank Haoya Li, Hongkang Ni, Joel Tropp, Rob Webber, and Lexing Ying for insightful discussions.

Disclaimer. This report was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor any agency thereof, nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government or any agency thereof. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof.