Cubically Convergent Iterations for Invariant Subspace Computation

Pierre-Antoine Absil, Rodolphe Sepulchre, Paul Van Dooren, Robert E. MahonySIAM J. Matrix Anal. Appl 2004 · DOI

TL;DR

This paper introduces and compares four algorithms for finding invariant subspaces of symmetric matrices, focusing on methods that converge cubically. The authors propose modifications to existing methods to significantly improve their global convergence behavior, ensuring they are more robust and reliable in practice.

What Problem Does This Paper Address?

Computing invariant subspaces (or eigenspaces) of a matrix is a fundamental problem in many scientific and engineering fields, including control theory, pattern recognition, and data compression. While many methods exist, this paper focuses on those that offer rapid, cubic convergence to a solution. However, existing cubically convergent methods often suffer from poor global behavior, meaning they might fail to converge to the desired subspace if the initial guess is not sufficiently close. This paper aims to analyze and improve the global convergence properties of these advanced algorithms, making them more practical for real-world applications.

Methods

The paper presents and compares four cubically convergent algorithms for invariant subspace computation:

  • RSQR (Rank-Selective QR): A shifted inverse iteration method that uses multiple scalar shifts derived from Ritz values.
  • GRQI (Grassmannian Rayleigh Quotient Iteration): Another shifted inverse iteration, but it uses a matrix shift.
  • NG (Newton-Grassmann): A Newton-like iteration that operates directly on the Grassmann manifold.
  • NH (Newton-Homogeneous): A least-squares approach derived from a homogeneous Newton method.

The authors also propose modifications to improve global convergence:

  • Modified GRQI: A simple threshold on the distance between successive iterates to prevent large jumps and improve basin of attraction shape.
  • Modified Newton Methods (NG-tau, NH-tau): A deformation parameter is introduced to smoothly transition between the Newton iteration and a gradient descent flow, which has larger basins of attraction.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments using synthetic matrices designed to illustrate specific properties, particularly the influence of eigenvalue gaps.

Key Insights and Ideas

  • Cubic Convergence is Not Enough: While cubic convergence is desirable for its speed, it doesn't guarantee that an iteration will find the correct subspace from any starting point. The "basins of attraction" (the set of initial guesses that lead to convergence) can be surprisingly small and fragile.
  • Eigenvalue Gaps Matter: The proximity of eigenvalues (both internal gaps within a cluster and external gaps between clusters) significantly impacts the basins of attraction. Small gaps can cause iterations to converge to the wrong subspace or fail entirely.
  • Inverse Iterations vs. Newton Methods: The paper highlights fundamental differences in how these two classes of methods handle singularities and their behavior with clustered eigenvalues. Inverse iterations can sometimes "over-cooperate" with clustered eigenvalues, leading to oversized basins for those subspaces at the expense of others.
  • Deformation Parameter for Robustness: Introducing a deformation parameter in Newton-like methods provides a powerful way to bridge the gap between fast local convergence and broad global convergence, effectively creating a hybrid approach.

Key Results

  • Comparison of Four Methods: The paper provides a detailed comparison of RSQR, GRQI, NG, and NH, showing that while they all offer cubic local convergence, their global behavior differs significantly, especially for $p > 1$.
  • GRQI Sensitivity: GRQI is shown to be particularly sensitive to both small internal and external eigenvalue gaps, leading to deteriorated basins of attraction.
  • RSQR's "Cooperation": RSQR can exhibit oversized basins of attraction for eigenspaces corresponding to clustered eigenvalues, potentially at the expense of other eigenspaces.
  • Improved Global Behavior: The proposed modifications (thresholding for GRQI, deformation parameter for Newton methods) significantly enlarge the basins of attraction, making the algorithms much more robust. For instance, the modified Newton methods (NG-tau, NH-tau) showed dramatic improvements in global behavior in numerical experiments.
  • Computational Cost: For dense matrices, all methods have a comparable complexity of $O(np^3)$ if not pre-processed. However, with pre-processing (e.g., reducing A to tridiagonal form), the cost per iteration can be reduced to $O(np^2)$ for all four methods.

Limitations and Future Work

  • Low-Dimensional Illustrations: While the paper uses low-dimensional examples ($n=3, p=1,2$) to visualize basins of attraction, the behavior in higher dimensions is inferred and confirmed through numerical experiments.
  • Geometrical Limit: The paper notes a fundamental geometrical limit to basin size related to the overlap of eigenspaces, suggesting that the proposed methods push these limits but cannot overcome them entirely.
  • Future Work: The authors suggest exploring acceleration techniques for solving the Newton equations more efficiently, potentially using iterative solvers, which could further improve performance, especially for large-scale problems. They also hint at the potential for a "block Jacobi-Davidson" method for $p > 1$.

Summary updated

BibTeX
@article{absil2004cubically,
  author = {Pierre-Antoine Absil and Rodolphe Sepulchre and Paul Van Dooren and Robert E. Mahony},
  title = {{Cubically Convergent Iterations for Invariant Subspace Computation}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2004},
  doi = {10.1137/s0895479803422002},
}
Figure