Abstract
The extended Davis-Kahan theorem makes use of polynomial matrix transformations to produce bounds at least as tight as the standard Davis-Kahan theorem. The optimization problem of finding transformation parameters resulting in optimal bounds from the extended Davis-Kahan theorem is presented for affine transformations. It is demonstrated how globally optimal bound values can be computed automatically using fractional programming theory. Two different solution approaches, the Charnes-Cooper transformation and Dinkelbach's algorithm are reviewed. Our implementation of the extended Davis--Kahan theorem is used to calculate bound values in three significant examples: pairwise comparison of stochastic block model graphs, distance between graph shift operators and generating matrices, and sample vs. population covariance in a spiked covariance model. Our extended bound values not only outperform standard bounds but also work where the standard theorem fails.
The Challenge of Eigenvector Perturbation
In fields ranging from statistics to network science, understanding how the "principal directions" (eigenvectors) of a matrix change under perturbation is critical. The Davis–Kahan (DK) theorem is the standard tool for this, providing an upper bound on the distance between subspaces spanned by eigenvectors.
However, the classic DK bound has a major weakness: it is highly sensitive to the "eigengap"—the distance between the eigenvalues of interest and the rest of the spectrum. If this gap is small, the bound becomes "loose" and uninformative. Furthermore, the classic theorem requires the two matrices to have a similar eigenvalue structure. For instance, comparing an Adjacency matrix to a Laplacian matrix in graph theory is often impossible with the classic DK theorem because their eigenvalues live on opposite ends of the spectrum.
Methodology: Optimization via Fractional Programming
This research builds upon an "Extended DK theorem" that applies a polynomial transformation to one of the matrices to better align its spectrum with the other. The focus is on affine transformations ($f(\Phi) = c_1\Phi + c_0I$).
The core challenge is finding the optimal scaling ($c_1$) and shifting ($c_0$) parameters to make the bound as tight as possible. The authors demonstrate that this is a fractional programming problem—specifically, a concave-convex fractional program. To solve it, they employ two sophisticated optimization techniques to guarantee global optimality:
- Charnes–Cooper Transformation: A method that transforms the ratio-based optimization into a single equivalent convex problem.
- Dinkelbach’s Algorithm: An iterative method that solves a sequence of simpler convex subproblems.
Key Results and Applications
The paper evaluates the method using synthetic datasets designed to mimic real-world challenges in data science, such as Stochastic Block Models (SBM) and Spiked Covariance Models.
Superior Tightness and Versatility
As shown in the figure above, the extended bound (b) is consistently and significantly tighter than standard metrics (a). In spiked covariance models, the extended bound was frequently twice as tight as the standard Davis–Kahan bound.
Because the transformation can "flip" or "stretch" the spectrum, the extended theorem can bridge different matrix types. It successfully produced tight bounds when comparing Adjacency matrices to Symmetric Laplacians, a case where the standard DK theorem is essentially useless.
Convergence Visualization
In graph experiments, the bound correctly tracks the convergence of eigenvectors. As the number of nodes ($n$) in a network increases, the eigenvectors of the observed graph converge toward the eigenvectors of the theoretical model, reflected by the decreasing values in the distance bounds.
Conclusion
By framing the search for optimal matrix transformations as a fractional programming problem, this work provides a robust computational "recipe" for tightening eigenvector distance bounds. While affine transformations are remarkably potent, future work may explore higher-order polynomials for even greater precision, though these present more complex non-convex optimization challenges. Additionally, scaling these methods for "Big Data" applications remains a key area for further development.
Summary updated