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.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. 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.3 Error cancellation in the Taylor expansion Then, we find that the main components take the form: Lemma 5.6 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 Corollary 5.7 It holds that Proof . We have Proof 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. 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 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. 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.

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

References: Spectral Estimation, Signal Processing, and Quantum Computing

The ESPRIT Algorithm and Central Limit Error Scaling

ESPRIT Algorithm: The Proof of Theorem

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

References: Spectral Estimation, Signal Processing, and Quantum Computing

The ESPRIT Algorithm and Central Limit Error Scaling

ESPRIT Algorithm: The Proof of Theorem

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps