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 C Deferred proofs for Section 2 In this section, we prove Lemmas 2.1 and 2.2 from Section 2. We begin in Appendix C.1 by proving some supplementary error bounds that we will use. Then, we prove Lemma 2.1 in Appendix C.2 and Lemma 2.2 in Appendix C.3. C.1 Error matrix bounds This result appears in the proof of [Mec07, Thm. 2 (Page 320)] for Ej real. Estimates of this form with explicit constants in the real or complex case can easily be obtained from the theory of matrix concentration (see, e.g., [Tro15, sec. 4.4] for a specific calculation). Using this result, we can bound the norm of the error matrix in total: Proposition C.2 (Error matrix, norm bound). It holds that Proposition C.3 (Tail error in the dominant eigenspace). We have the bound C.2 Proof of Lemma 2.1 In this section, we provide a proof of Lemma 2.1, broken into two steps. Step 1: Proof of Eq. (2.1). The result of Eq. (2.1) follows directly by combining matrix perturbation theorems (Appendix A.5), singular value bounds for Vandermonde matrices (Appendix B.1), and the error matrix bounds developed in Appendix C.1. By Weyl’s theorem (Theorem A.7) and Proposition C.2, By Ostrowski’s theorem (Theorem A.8) and Theorem B.1, C.3 Proof of Lemma 2.2 The proof of the lemma is then completed. 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 C Deferred proofs for Section 2 In this section, we prove Lemmas 2.1 and 2.2 from Section 2. We begin in Appendix C.1 by proving some supplementary error bounds that we will use. Then, we prove Lemma 2.1 in Appendix C.2 and Lemma 2.2 in Appendix C.3. C.1 Error matrix bounds This result appears in the proof of [Mec07, Thm. 2 (Page 320)] for E j real. Estimates of this form with explicit constants in the real or complex case can easily be obtained from the theory of matrix concentration (see, e.g., [Tro15, sec. 4.4] for a specific calculation). j Using this result, we can bound the norm of the error matrix in total: Proposition C.2 (Error matrix, norm bound). It holds that Proposition C.2 (Error matrix, norm bound). It holds that Proposition C.3 (Tail error in the dominant eigenspace). We have the bound Proposition C.3 (Tail error in the dominant eigenspace). We have the bound C.2 Proof of Lemma 2.1 In this section, we provide a proof of Lemma 2.1, broken into two steps. Step 1: Proof of Eq. (2.1). The result of Eq. (2.1) follows directly by combining matrix perturbation theorems (Appendix A.5), singular value bounds for Vandermonde matrices (Appendix B.1), and the error matrix bounds developed in Appendix C.1. Step 1: Proof of Eq. By Weyl’s theorem (Theorem A.7) and Proposition C.2, By Ostrowski’s theorem (Theorem A.8) and Theorem B.1, C.3 Proof of Lemma 2.2 The proof of the lemma is then completed. 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.

Quant

Explicit Expansion and Bounds of Spectral Projector in ESPRIT Analysis

Vandermonde Matrices in Spectral Estimation Analysis

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Get Free Unlimited IP Geo Data With IPinfo Lite

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Using T-tests for Abnormal Data in AB Testing

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Explicit Expansion and Bounds of Spectral Projector in ESPRIT Analysis

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

The ESPRIT Algorithm and Central Limit Error Scaling

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Using T-tests for Abnormal Data in AB Testing

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Explicit Expansion and Bounds of Spectral Projector in ESPRIT Analysis

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

The ESPRIT Algorithm and Central Limit Error Scaling

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps