Table of Links
1.1 ESPRIT algorithm and central limit error scaling
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
C Deferred proofs for Section 2
D Deferred proofs for Section 4
E Deferred proofs for Section 5
F Lower bound for spectral estimation
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.