Abstract
The Davis-Kahan theorem is a fundamental result in matrix analysis used to bound the distance between subspaces spanned by eigenvectors of two symmetric matrices. This paper extends the theorem by incorporating polynomial matrix transforms, allowing for the comparison of arbitrary unions of eigenspaces and providing tighter bounds. By shifting the requirements from the inherent eigenvalues to controllable transformation parameters, the proposed method overcomes the restrictive "eigengap" constraints of the original theorem. A proof-of-concept application to $d$-regular graphs demonstrates that the extended theorem can achieve zero-error bounds where the standard theorem fails.
Introduction
In fields ranging from data science to mathematical physics, understanding the stability of "principal directions" (eigenvectors) under perturbation is critical. The Davis–Kahan (DK) theorem serves as the standard analytical tool for bounding the distance between subspaces spanned by these eigenvectors. However, the theorem's utility is often limited by a strict "eigengap" requirement: the eigenvalues of the matrices being compared must follow a specific, well-separated structure. When comparing matrices with poorly aligned spectra—such as an adjacency matrix and a graph Laplacian—the standard DK theorem often yields loose or inapplicable bounds.
Methodology: Polynomial Matrix Transformations
To address these limitations, we introduce a framework based on polynomial matrix transformations. The core insight is that for any symmetric matrix $\Phi$, applying a polynomial $p(\cdot)$ results in a matrix $p(\Phi)$ that shares the same eigenvectors as $\Phi$, while its eigenvalues are transformed to $p(\lambda_i)$.
By selecting an appropriate polynomial, we can "rearrange" the eigenvalues of one matrix to satisfy the DK theorem's geometric requirements without altering the underlying subspaces of interest. This approach offers two primary advantages:
- Relaxed Constraints: The burden of satisfying the eigengap condition is moved from the fixed data to the transformation parameters, which are under the researcher's control.
- Optimized Bounds: The flexibility in choosing the polynomial allows for the minimization of the resulting distance bound.
The paper particularly highlights affine transforms ($f(\Phi) = c_1\Phi + c_0I$), demonstrating that even simple linear scaling and shifting can significantly improve the theorem's applicability.
Key Results and Proof of Concept
The extended theorem produces bounds that are guaranteed to be at least as tight as the standard DK theorem. Furthermore, it allows for the comparison of any $r$ consecutive eigenvectors, rather than just the "top $r$," which is vital for analyzing specific frequency bands in graph signal processing.
To demonstrate the power of this extension, we consider the comparison of unnormalized ($L$) and normalized ($L_{sym}$) graph Laplacians for $d$-regular graphs. In this specific case, the relationship is exactly affine ($L_{sym} = d^{-1}L$).
As shown in the figure above, the extended methodology automatically identifies this relationship, causing the bound to drop to zero—correctly indicating that the subspaces are identical. In contrast, the standard DK theorem provides a non-zero, less accurate bound.
Conclusion and Future Work
By leveraging polynomial invariance of eigenvectors, we have generalized the Davis-Kahan theorem to be more flexible and accurate. While this theoretical foundation focuses on the existence and properties of these transforms, future work (Paper II) will address the computational challenges of automatically identifying optimal high-degree polynomials using fractional programming.
Summary updated