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 D Deferred proofs for Section 4 This section provides supplementary proofs for Section 4. In Appendix D.1, we develop explicit formulas for the higher-order terms in the perturbation expansion result, Proposition 4.2. In Appendix D.2, we show how to bound the terms appearing in this expression. We conclude by proving Lemma 4.3 in Appendix D.3. D.1 Expansion of spectral projector: explicit formulas After deriving the explicit expansion, we need to employ the following two properties of the Schur polynomial [Mac15] to constrain the higher-order terms in Appendix D.2: We also need to use the standard cofactor expansion for the determinant calculation. Fact D.3 (Cofactor expansion of determinant). For any n-by-n matrix A, the cofactor expansion of the determinant along the first row is where the second step follows from We recognize the numerator of this expression of a cofactor expansion of a determinant (Fact D.3), obtaining where the second step follows from the definition of the Schur polynomial (Definition D.1). Substituting this expression back in Eq. (D.4) yields the stated result. Theorem D.7 (Expansion of spectral projector, explicit form). It holds that Thus, we obtain that The theorem then follows by Proposition 4.2. D.2 Expansion of spectral projector: bounds on terms In this section, we bound the terms appearing in the expansion of the spectral projector, Theorem D.7. Our result is as follows: Proof. For ease of reading, we break the proof into steps. Proof of (b). Using Eq. (D.12) and Eq. (D.9) to bound every term in Eq. (D.8), we conclude that where the second step follows from Corollary B.3, Lemma C.1, and Eq. (D.11). For the second term, we have D.3 Proof of Lemma 4.3 Lemma 4.3 (Expansion of spectral projector, simplified). It holds that Proof. Begin with the explicit expansion of the spectral projector (Theorem D.7) where the last step follows from C ∈ (0, 3/8). The lemma is then proved. 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 D Deferred proofs for Section 4 This section provides supplementary proofs for Section 4. In Appendix D.1, we develop explicit formulas for the higher-order terms in the perturbation expansion result, Proposition 4.2. In Appendix D.2, we show how to bound the terms appearing in this expression. We conclude by proving Lemma 4.3 in Appendix D.3. D.1 Expansion of spectral projector: explicit formulas After deriving the explicit expansion, we need to employ the following two properties of the Schur polynomial [Mac15] to constrain the higher-order terms in Appendix D.2: We also need to use the standard cofactor expansion for the determinant calculation. Fact D.3 (Cofactor expansion of determinant). For any n-by-n matrix A, the cofactor expansion of the determinant along the first row is Fact D.3 (Cofactor expansion of determinant). For any n-by-n matrix A, the cofactor expansion of the determinant along the first row is where the second step follows from We recognize the numerator of this expression of a cofactor expansion of a determinant (Fact D.3), obtaining where the second step follows from the definition of the Schur polynomial (Definition D.1). Substituting this expression back in Eq. (D.4) yields the stated result. Theorem D.7 (Expansion of spectral projector, explicit form). It holds that Theorem D.7 (Expansion of spectral projector, explicit form). It holds that Thus, we obtain that The theorem then follows by Proposition 4.2. D.2 Expansion of spectral projector: bounds on terms In this section, we bound the terms appearing in the expansion of the spectral projector, Theorem D.7. Our result is as follows: Proof . For ease of reading, we break the proof into steps. Proof Proof of (b). Using Eq. (D.12) and Eq. (D.9) to bound every term in Eq. (D.8), we conclude that Proof of (b). where the second step follows from Corollary B.3, Lemma C.1, and Eq. (D.11). For the second term, we have D.3 Proof of Lemma 4.3 Lemma 4.3 (Expansion of spectral projector, simplified). It holds that Lemma 4.3 (Expansion of spectral projector, simplified). It holds that Proof . Begin with the explicit expansion of the spectral projector (Theorem D.7) Proof where the last step follows from C ∈ (0, 3/8). The lemma is then proved. 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.

Eigenvector Perturbation in Aligning Matrix Construction for ESPRIT

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

Explicit Expansion and Bounds of Spectral Projector in ESPRIT Analysis

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

References: Spectral Estimation, Signal Processing, and Quantum Computing

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

New Technical Advancements in ESPRIT Spectral Analysis

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

ESPRIT Algorithm: The Proof of Theorem

References: Spectral Estimation, Signal Processing, and Quantum Computing

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

New Technical Advancements in ESPRIT Spectral Analysis

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

ESPRIT Algorithm: The Proof of Theorem

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps