Davis-Kahan Theorem under a moderate gap condition
Phuc Tran, Van Vu · 2025
Read Davis-Kahan Theorem under a moderate gap condition by Phuc Tran, Van Vu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22393.txt.
Introduction
Phuc Tran and co-author Van Vu revisit the Davis Kahan theorem, a classic bound on how much the eigenspaces of a matrix move when the matrix is perturbed. The known bound works well when the gap between eigenvalues is large. Their paper handles the harder case where that gap is only moderate.
Using a bootstrapping argument, they obtain a new bound that works well when the perturbation is uncorrelated with the original matrix. They believe the bound is sharp apart from a logarithmic term. The result helps judge when computed eigenspaces can be trusted under noise.
Catalog record
| CREATOR | Phuc Tran, Van Vu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22393
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Davis-Kahan Theorem under a moderate gap condition Thanks: Department of Mathematics, Yale University, 10 Hillhouse Ave, New Haven, Connecticut, USA; [email protected], [email protected] Phuc Tran, Van Vu Abstract . The classical Davis-Kahan theorem provides an efficient bound on the perturbation of eigenspaces of a matrix under a large (eigenvalue) gap condition. In this paper, we consider the case when the gap is moderate. Using a bootstrapping argument, we obtain a new bound which is efficient when the perturbation matrix is uncorrelated to the ground matrix. We believe that this bound is sharp up to a logarithmic term. Mathematics Subject Classifications: 47A55, 65C20, 68W40. 1. The classical Davis-Kahan Theorem Consider a real, symmetric matrix A of size n , with the spectral decomposition A=\sum_{i=1}^{n}\lambda_{i}u_{i}u_{i}^{\top}, where \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} are the eigenvalues of u_{i} the corresponding eigenvectors. For a subset S\subset\{1,\dots,n\} , we denote • \Pi_{S}:=\sum_{i\in S}u_{i}u_{i}^{\top} is the orthogonal projection onto the subspace spanned by the eigenvectors u_{i},i\in S , • \Lambda_{S}:=\{\lambda_{i}\,|\,i\in S\} and \Lambda_{S^{c}}=\{\lambda_{j}\,|\,j\in[n]\setminus S\} . Let E be a noise matrix and \tilde{A}=A+E . Define \tilde{\lambda}_{i} , \tilde{u}_{i},\tilde{\Lambda}_{S},\tilde{\Lambda}_{S^{c}} , and \tilde{\Pi}_{S} respectively. In this paper, our goal is to estimate the difference \|\tilde{\Pi}_{S}-\Pi_{S}\|, where \left\|\cdot\right\| denotes the spectral norm. We can extend our results to the asymmetric case via a simple symmetrization trick. A classical result in numerical linear algebra, the Davis-Kahan theorem, is the standard tool to estimate the perturbation of eigenspaces. This perturbation can also be defined as the sine of the angle between the two subspaces, and the Davis-Kahan theorem is often referred to as the Davis-Kahan sine theorem. Theorem 1.1 (Davis-Kahan [ 14 , 4 ] ) . Suppose that \text{dist}\,(\Lambda_{S},\tilde{\Lambda}_{S^{c}})=\delta>0 . Then, \|\tilde{\Pi}_{S}-\Pi_{S}\|\leq\frac{\pi\|E\|}{2\delta}. Here \text{dist}\,(\Lambda_{S},\tilde{\Lambda}_{S^{c}}):=\displaystyle\min_{\lambda_{i}\in\Lambda_{S},\tilde{\lambda}_{j}\in\tilde{\Lambda}_{S^{c}}}|\lambda_{i}-\tilde{\lambda}_{j}| . Remark 1.0.1 . It is well-known that the Davis-Kahan bound is sharp with the optimal constant factor \pi/2 (see [ 4 , 27 , 31 , 42 ] ). In practice, we usually do not know the spectrum of the noisy matrix \tilde{A} . It is desirable to use only the eigenvalues of A in the estimate. A simple way is to use Weyl’s inequality, which gives \left|\lambda_{i}-\tilde{\lambda}_{j}\right|\leq\left|\lambda_{i}-\lambda_{j}\right|+\left|\lambda_{j}-\tilde{\lambda}_{j}\right|\leq\left|\lambda_{i}-\lambda_{j}\right|+\|E\|. Therefore, replacing \text{dist}\,(\Lambda_{S},\tilde{\Lambda}_{S^{c}}) by \delta_{S}:=\min_{i\in S,j\notin S}|\lambda_{i}-\lambda_{j}| and paying a factor of 2 , one obtains the following corollary, which is more useful in applications. Corollary 1.1 . Let S be a subset of \{1,2,\cdots,n\}, one has (1) \|\tilde{\Pi}_{S}-\Pi_{S}\|\leq\frac{\pi\left\|E\right\|}{\delta_{S}}. Consider the important special case where S=\{1,2,\cdots,p\} , one obtains the following estimate for the perturbation of \Pi_{p} , the orthogonal projection onto the leading p -eigenspace of A . Corollary 1.2 . Let \delta_{p}:=\lambda_{p}-\lambda_{p+1} , one has (2) \|\tilde{\Pi}_{p}-\Pi_{p}\|\leq\frac{\pi\left\|E\right\|}{\delta_{p}}. Remark 1.0.2 . (The large gap assumption) In applications of Theorem 1.1 , Corollary 1.1 , or Corollary 1.2 , we often need to bound the RHS by some small quantity \epsilon . This requires a large eigenvalue gap assumption (3) \delta_{S}\geq\delta\geq\frac{\pi}{2\epsilon}\|E\|. For instance, if \epsilon=.01 , the gap needs to be at least 50\pi\|E\|\approx 157\|E\|. In applications, when the size of the matrices tends to infinity, one often needs an asymptotic bound which tends to zero. In this case, the gap \delta_{S} must be larger than \|E\| by an order of magnitude. The goal of this paper is to find effective bounds in the case where the gap is moderate, being only a small multiple of \|E\| (say, 3\|E\| or 4\|E\| ). The main idea of our analysis is to use a bootstrapping argument, combined with the moderate gap assumption, to reduce the estimation of eigenspace perturbation to the estimation of a contour integral. The evaluation of the integral is relatively simple and direct. This is different from the traditional contour integral approach; see the discussion at the beginning of Subsection 3.1 . Our new bounds will take into account the interaction between the noise matrix E and the eigenvectors of A . This seems to be a very natural quantity to consider. Our bounds are effective when there is no strong correlation between A and E . In particular, this is the case for most applications in data science, where noise is assumed to be random. The rest of the paper is organized as follows. In the next section, we present our new result. We will discuss the necessity of the terms in our new bounds and their sharpness, and make a comparison to recent developments in the field. In Section 3 , we describe the main idea which leads to a key lemma. In Section 4 , we prove our main theorem, using the key lemma and a series of technical lemmas. In Section 5 , we discuss an application in computer science, concerning the computation of the leading eigenvector of a large matrix. In Section 6 , we provide the proofs of the technical lemmas used in Section 4 . 2. New results To ease the presentation, we first focus on the case of the eigenspace spanned by a few leading eigenvectors. This is also one of the most important cases in applications. Another important case is when (4) S=\{1,2,\dots,k,n-(p-k)+1,\dots,n\}, for some properly chosen k\leq p such that the set \{\lambda_{1},\dots,\lambda_{k},-\lambda_{n-(p-k)+1},\dots,-\lambda_{n}\} is the set of the largest p singular values. In this case, we are talking about the projection on the subspace spanned by leading singular vectors. We fix a small index p and consider the eigenspace spanned by the eigenvectors corresponding to the leading eigenvalues \lambda_{1},\dots,\lambda_{p} . Notice that this space is well defined if \lambda_{p}>\lambda_{p+1} , even if there are indices i,j\leq p where \lambda_{i}=\lambda_{j} . We denote by \sigma_{1} the largest singular value of A , \sigma_{1}=\max_{i}|\lambda_{i}|=\|A\|. Theorem 2.1 . Let r\geq p be the smallest integer such that \frac{\left|\lambda_{p}\right|}{2}\leq\left|\lambda_{p}-\lambda_{r+1}\right| , and set x:=\max_{i,j\leq r}|u_{i}^{\top}Eu_{j}| . Assume furthermore that 4\|E\|\leq\delta_{p}:=\lambda_{p}-\lambda_{p+1}\leq\frac{|\lambda_{p}|}{4}. Then (5) \left\|\tilde{\Pi}_{p}-\Pi_{p}\right\|\leq 24\left(\frac{\|E\|}{\left|\lambda_{p}\right|}\log\left(\frac{6\sigma_{1}}{\delta_{p}}\right)+\frac{r^{2}x}{\delta_{p}}\right). Remark 2.0.1 . If we simply combine our contour bootstrapping argument in the next section with the trivial estimate of F_{1} in ( 25 ), then we get the Davis-Kahan bound (or at least up to some small constant). But now we proceed differently. It shows our new idea in a clearer way. In the large gap case where \delta_{p}>\frac{|\lambda_{p}|}{4} , Corollary 1.2 is better. Moreover, we need an upper bound on \delta_{p} here to guarantee that the logarithmic term is positive. The constant 4 can be replaced by any constant larger than 2 (at the cost of increasing the constant 24 on the RHS). To compare this theorem to Corollary 1.2 , let us ignore the logarithmic term and r^{2} (which is typically small in applications). The RHS is thus simplified to O\left(\frac{\|E\|}{\left|\lambda_{p}\right|}+\frac{x}{\delta_{p}}\right). In the first term on the RHS, we have \|E\| in the numerator, but \left|\lambda_{p}\right| instead of \delta_{p}=\lambda_{p}-\lambda_{p+1} in the denominator. Thus, we use the eigenvalue itself instead of the gap. The gap does not need to be large to make the bound effective as in the original Davis-Kahan theorem. This term will still be small if the leading eigenvalues themselves are large, but relatively close to each other. In the second term, the denominator is \delta_{p} , as in the original Davis-Kahan theorem. But here the numerator is x rather than \|E\| . It is clear that x\leq\|E\| . The key point, as we have already mentioned, is that if there is no strong correlation between E and