New matrix perturbation bounds with relative norm: Perturbation of eigenspaces

Phuc Tran, Van Khu VuarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces a "relative norm" to replace the standard spectral norm in matrix perturbation theory, significantly tightening the classical Davis-Kahan bounds. By using a novel "combinatorial contour expansion" method, the authors show that when noise is random rather than adversarial, eigenspace perturbations are often much smaller—sometimes by a factor of $\sqrt{n}$—than previously thought.

What Problem Does This Paper Address?

In data science and statistics, we often deal with a "ground truth" matrix $A$ (the signal) that is corrupted by a noise matrix $E$, giving us an observed matrix $\tilde{A} = A + E$. A fundamental question is: how much do the eigenvectors (the "eigenspaces") of our observed matrix deviate from the truth?

For decades, the gold standard for answering this has been the Davis-Kahan theorem. However, Davis-Kahan relies on the spectral norm of the noise ($\|E\|$), which represents a worst-case scenario. It assumes the noise is perfectly aligned to disrupt the signal in the most damaging way possible.

In reality, noise is rarely that malicious. If you have a large dataset where the noise is random, it's unlikely to align perfectly with your signal's eigenvectors. The authors argue that classical bounds are too pessimistic for practical applications like Principal Component Analysis (PCA) or matrix completion, and they set out to find a more "realistic" measurement of noise.

Methods

The authors introduce a new parameter called the relative norm ($\|E\|_{A,p}$). Unlike the spectral norm, which looks at the noise in isolation, the relative norm measures the interaction between the noise matrix and the specific eigenvectors of the signal matrix.

To prove these tighter bounds, they developed a new mathematical framework called combinatorial contour expansion. This technique combines:

  1. Complex Analysis: Using Cauchy’s integral theorem to represent the difference between two projection matrices as a contour integral.
  2. Combinatorics: Expanding the "resolvent" (a matrix-valued function) into a power series and using graph-based combinatorial arguments to track how noise terms cancel each other out.

This method allows them to "profile" the noise, separating its impact into first-order and second-order effects, which leads to much more precise results than the standard Taylor expansion used in previous literature.

Datasets

As a theoretical mathematics paper, this work does not use empirical "training" datasets. Instead, it validates its findings using:

  • Random Matrix Ensembles: Specifically Wigner matrices, Generalized Wigner matrices, and "Regular" random matrices.
  • Spiked Covariance Models: Theoretical models used to simulate high-dimensional data with a few strong signals (the "spikes").
  • Synthetic Counter-examples: In Appendix E, the authors construct specific matrices to prove that their new terms are "necessary" and that the bounds are "sharp" (meaning they cannot be improved further without new assumptions).

Key Insights and Ideas

  • Adversarial vs. Random Noise: The "aha moment" is the realization that for a signal in $n$-dimensional space, random noise is "spread out." While the total energy of the noise might be large ($\sqrt{n}$), its impact on any specific signal direction is much smaller (often just logarithmic or constant).
  • The "Magic" of Regularity: The authors discovered that for "regular" random matrices (where the expected sum of squares of each row is equal), a "magic algebraic cancellation" occurs. This explains why certain error terms that plague other models simply vanish in regular ones.
  • Safe Distance: The paper introduces the concept of a "safe distance" ($\bar{\lambda}$). If an eigenvalue is far enough away from the signal of interest, its corresponding eigenvector won't significantly influence the perturbation, allowing for dimension reduction in the analysis.

Key Results

  • $\sqrt{n}$ Improvement: In cases with random Wigner noise, the new bounds save a factor of roughly $\sqrt{n}$ compared to Davis-Kahan. For a matrix with 1,000,000 entries, this is a massive difference in predicted accuracy.
  • Beyond the "Gap" Requirement: Classical bounds require a large "eigenvalue gap" to be meaningful. The new relative norm bounds remain non-trivial even when the gap is small, provided the noise doesn't interact strongly with the signal's eigenvectors.
  • Application to Privacy: The authors show that their bounds can better predict the "utility error" in Differential Privacy, where noise is intentionally added to a matrix to protect individual data points.

Limitations and Future Work

The authors acknowledge that while their bounds are sharp up to a factor of $12\sqrt{p}$ (where $p$ is the dimension of the eigenspace), there is still room to optimize these constant factors.

This paper is explicitly framed as the first in a series. While this work focuses on eigenspaces, the authors note that the "combinatorial contour expansion" method is robust enough to handle other matrix functionals. Future papers are expected to apply this relative norm approach to:

  • General matrix functions ($f(A)$).
  • Singular value stability in rectangular matrices.
  • More complex "low-rank + noise" recovery problems in high-dimensional statistics.

Summary updated

Abstract

Matrix perturbation bounds (such as Weyl and Davis-Kahan) are used abundantly in many areas of mathematics and data science. Many bounds (such as the above two) involve the spectral norm of the noise matrix and are sharp in worst case analysis. In order to refine these classical bounds, we introduce a new parameter, which we refer to as the relative norm. This parameter measures the strength of the action of the noise matrix on the relevant eigenvectors of the ground matrix. It has turned out that in a number of situations, we can use the relative norm as a replacement for the spectral norm. This has led to a number of notable improvements under certain sets of assumptions, which are frequently met in practice. For instance, our new results apply very well in the case when the noise matrix is random. For the purpose of our study, we introduce a new method of analysis, which combines the classical contour integral argument with new (combinatorial) ideas. This method is robust and of independent interest. In the current paper, we focus on the perturbation of eigenspaces (Davis-Kahan type results). Perturbation bounds for eigenspaces are essential in statistics and theoretical computer science, and thus deserve a special treatment. Furthermore, this will lay the ground for the more technical treatment of general matrix functionals, which appears in a future paper.
BibTeX
@misc{tran2024new,
  author = {Phuc Tran and Van Khu Vu},
  title = {{New matrix perturbation bounds with relative norm: Perturbation of eigenspaces}},
  year = {2024},
  eprint = {2409.20207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.20207},
}
Figure