Extending the Davis-Kahan theorem for comparing eigenvectors of two symmetric matrices II: Computation and Applications

Johannes F. Lutzeyer, Andrew T. WaldenarXiv 2019 · DOI · arXiv

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:

  1. Charnes–Cooper Transformation: A method that transforms the ratio-based optimization into a single equivalent convex problem.
  2. 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.

Comparison of standard eigenvector distance metrics (a) and the optimized extended Davis-Kahan bounds (b), showing significantly improved tightness.

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.

Convergence of eigenvector distance bounds as the number of nodes $n$ increases (30, 120, 210, 300) across various stochastic block model configurations.

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

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. First, a pairwise comparison is made of the spaces spanned by the eigenvectors of the graph shift operator matrices corresponding to different stochastic block model graphs. Second our bound is calculated on the distance of the spaces spanned by eigenvectors of the graph shift operators and their corresponding generating matrices in the stochastic blockmodel, and, third, on the sample and population covariance matrices in a spiked covariance model. Our extended bound values, using affine transformations, not only outperform the standard Davis-Kahan bounds in all examples where both theorems apply, but also demonstrate good performance in several cases where the standard Davis-Kahan theorem cannot be used.
BibTeX
@misc{lutzeyer2019extending,
  author = {Johannes F. Lutzeyer and Andrew T. Walden},
  title = {{Extending the Davis-Kahan theorem for comparing eigenvectors of two symmetric matrices II: Computation and Applications}},
  year = {2019},
  eprint = {1908.03465},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.03465},
}
Figure