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. 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.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. Acknowledgments 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. Disclaimer 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.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

ESPRIT Algorithm: The Proof of Theorem

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Guide to Exploiting Unknown Strategies From a Known Bias Set

The ESPRIT Algorithm and Central Limit Error Scaling

Error Cancellation in the Taylor Expansion: The Details You Need to Know

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

Proof of Central Limit Error Scaling for ESPRIT Algorithm

A Guide to Exploiting Unknown Strategies From a Known Bias Set

The ESPRIT Algorithm and Central Limit Error Scaling

Error Cancellation in the Taylor Expansion: The Details You Need to Know

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps