Uniform Bounds for Invariant Subspace Perturbations

Anil Damle, Yuekai SunSIAM J. Matrix Anal. Appl 2020 · DOI

TL;DR

This paper develops new, deterministic bounds for how invariant subspaces of a symmetric matrix change under perturbation. These bounds are particularly useful for understanding how spectral properties are preserved in "row-wise" error metrics, which are relevant in many modern applications like spectral clustering and principal component analysis.

What Problem Does This Paper Address?

Understanding how the properties of a matrix change when it's perturbed is a fundamental problem in linear algebra with broad applications. A key aspect of this is how invariant subspaces – the fundamental building blocks of a matrix's structure – are affected by perturbations. Traditional methods often focus on global subspace distances. However, many modern applications, particularly in data science and machine learning (e.g., spectral clustering, principal component analysis, matrix completion), require understanding how these subspaces change when measured by "row-wise" metrics. This means we're interested in how the error is distributed across the rows of the subspace representation, rather than just a single overall distance. This paper aims to provide purely deterministic bounds for these row-wise subspace perturbations, offering a more nuanced understanding than existing methods.

Methods

The authors develop new deterministic bounds for the row-wise perturbation of invariant subspaces of symmetric matrices. They introduce and utilize a specific "two-to-infinity" induced matrix norm ($|| \cdot ||_{2,\infty}$) which captures row-wise error. A key part of their approach involves analyzing the structure of the perturbed matrix using its eigen-decomposition and relating it to the original matrix's structure. They leverage concepts like "separation" of matrices (a measure of how close their eigenvalues are) and the orthogonal Procrustes problem to derive their bounds. The proofs involve constructing specific matrix forms and using techniques like Newton's method for root-finding and the Newton-Kantorovich theorem. They also provide theoretical arguments for why their bounds are sharp and discuss extensions to non-normal matrices.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds and uses constructed examples for numerical illustration rather than real-world datasets.

Key Insights and Ideas

  • Row-wise error matters: The paper highlights that for many applications, understanding the distribution of error across rows of subspace representations is crucial, and traditional global distance metrics can be misleading.
  • New bounds for row-wise error: The core contribution is the development of deterministic bounds specifically tailored for row-wise error metrics, offering a more refined analysis than existing methods.
  • Sharpness of bounds: The authors demonstrate that their bounds are "tight," meaning they can be achieved in specific adversarial cases, suggesting they are not overly conservative.
  • Incoherence is key: The paper shows that when the perturbation E and the original subspace basis V have "incoherent" row norms (meaning the error is spread out), the row-wise perturbation bounds can be significantly better than traditional bounds.
  • Separation is essential: The concept of "separation" between eigenvalues plays a critical role in controlling the perturbation of invariant subspaces. The paper introduces and utilizes a norm-specific separation measure.

Key Results

The paper presents Theorem 3.1, which provides a deterministic upper bound on the row-wise error ($||V_1\tilde{U} - V_1||_{2,\infty}$) of an invariant subspace under a symmetric perturbation E. This bound is expressed in terms of:

  • The norm of the original subspace basis ($||V_1||_{2,\infty}$).
  • Components of the perturbation matrix E projected onto different subspaces ($||E_{2,1}||_2$, $||V_2E_{2,1}||_{2,\infty}$, $||V_2E_{2,2}V_2^T||_{2,\infty}$).
  • The "gap" between eigenvalues, which is related to matrix separation.

They also provide Corollary 3.2 and Corollary 3.3, which offer simplified versions of the main bound under specific assumptions. The numerical simulations (Figures 1, 2, and 3) demonstrate that their bounds accurately capture the asymptotic behavior of the row-wise error, often outperforming traditional bounds in specific scenarios, especially when the perturbation is structured in a way that saturates the bounds.

Limitations and Future Work

  • Symmetric matrices: The primary results are for symmetric matrices A and symmetric perturbations E. The paper briefly discusses extensions to non-normal matrices in Section 5, but this is an area for further development.
  • Worst-case bounds: While the bounds are deterministic, they are worst-case bounds. The paper acknowledges that in specific probabilistic settings (e.g., random perturbations), tighter bounds might be achievable, and suggests future work in this direction.
  • Probabilistic settings: The paper discusses how their bounds can be used to analyze probabilistic scenarios but notes that achieving the conjectured optimal rates in some random settings might require more intricate techniques.
  • Singular subspaces: The authors believe their proof strategy can be extended to analyze perturbations of singular subspaces for non-normal matrices, which is a promising avenue for future research.

Summary updated

BibTeX
@article{damle2020uniform,
  author = {Anil Damle and Yuekai Sun},
  title = {{Uniform Bounds for Invariant Subspace Perturbations}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2020},
  doi = {10.1137/19m1262760},
}
Figure