Jacobi-Davidson method on low-rank matrix manifolds

Maxim Rakhuba, Ivan Oseledets

This paper, "Jacobi-Davidson method on low-rank matrix manifolds" by M. V. Rakhuba and I. V. Oseledets, presents a significant optimization for a classic problem in numerical linear algebra: finding eigenvalues and eigenvectors for massive matrices. By exploiting the hidden "low-rank" structure of eigenvectors, the authors provide a way to solve these problems with drastically lower computational and memory costs.

TL;DR

The authors generalize the Jacobi-Davidson (JD) eigenvalue method to work directly on manifolds of low-rank matrices. This approach allows for the efficient calculation of eigenvectors that possess a low-rank structure, reducing computational complexity from the size of the full vector to the much smaller dimensions of its low-rank components.

What Problem Does This Paper Address?

In many scientific computing applications—such as solving the Schrödinger equation or discretized partial differential equations (PDEs)—we need to find the eigenvalues ($\lambda$) and eigenvectors ($x$) of a matrix $A$. As the resolution of these problems increases, the size of $x$ (denoted as $N$) grows exponentially, often becoming too large to store in memory.

However, in many physical systems, if you reshape the long vector $x$ into a matrix $X$, that matrix often has a very low rank ($r$). Standard eigenvalue solvers like the original Jacobi-Davidson method don't "know" about this structure; they treat $x$ as a generic high-dimensional vector. The challenge addressed here is: How can we perform the Jacobi-Davidson iteration while staying strictly within the space of low-rank matrices?

Methods

The authors frame the eigenvalue problem as a Riemannian optimization task. Instead of searching the entire high-dimensional space, they restrict the search to the intersection of two "manifolds":

  1. The Unit Sphere: Because eigenvectors are typically normalized ($\|x\|=1$).
  2. The Fixed-Rank Manifold ($M_r$): The set of all matrices with a specific rank $r$.

Key Innovations:

  • Low-Rank Jacobi Correction Equation: The heart of the JD method is a "correction equation" that tells you how to improve your current guess. The authors derive a new version of this equation that projects the problem onto the tangent space of the low-rank manifold.
  • Curvature Omission: In their derivation of the Hessian (the second derivative used in Newton-like methods), they intentionally omit a "curvature" term. This term involves the inverse of singular values, which can become very small and cause numerical instability. This makes their method a "constrained Gauss-Newton" approach.
  • Subspace Acceleration with Vector Transport: To speed up convergence, JD methods usually keep a history of previous guesses. In the low-rank setting, simply adding these guesses would cause the rank to explode. The authors use "vector transport" to project previous search directions onto the tangent space of the current guess, keeping the rank controlled.

Datasets

The paper does not use traditional machine learning datasets. Instead, it evaluates the algorithm using a standard numerical benchmark:

  • Convection-Diffusion Operator: A 2D PDE discretized on a grid (up to $2000 \times 2000$, resulting in a matrix $A$ of size $4,000,000 \times 4,000,000$).
  • Potential Function: A specific potential $V(x, y)$ was chosen to ensure the resulting eigenvector has a low-rank structure, making it a suitable test case for the proposed method.

Key Insights and Ideas

  • Complexity Breakthrough: If the matrix $A$ can be represented as a sum of Kronecker products (common in grid-based physics), the complexity of the algorithm scales as $O((n+m)r(R+r))$. For a grid of $n \times n$, this is roughly linear in $n$, whereas standard methods are at least quadratic ($n^2$).
  • Robustness to Inexactness: A major advantage of the JD approach over the simpler Davidson method is that it remains efficient even when the internal linear systems are solved only approximately (inexactly). The authors demonstrate that their low-rank version inherits this robustness.
  • Manifold Commutativity: The authors prove that the projection onto the sphere and the projection onto the low-rank tangent space commute, which simplifies the math significantly and ensures the algorithm stays on the correct mathematical "track."

Key Results

  • Efficiency: The low-rank JD method achieved the same accuracy as the original JD method but with significantly fewer "expensive" operations.
  • Convergence: In numerical tests, the method outperformed the Alternating Linear Scheme (ALS), which is the current standard for low-rank optimization.
  • Stagnation: The authors noted that the low-rank version eventually "stagnates" (stops improving) once it reaches the accuracy limit of the best rank-$r$ approximation of the true eigenvector. This is expected behavior for any fixed-rank method.

Limitations and Future Work

  • Fixed Rank: The current algorithm requires the user to choose the rank $r$ in advance. If $r$ is too small, the solution won't be accurate; if it's too large, the computational gains diminish.
  • Two-Dimensional Focus: The paper focuses on the matrix (2D) case. While the authors mention that the results can be generalized to higher-dimensional tensors (using the Tensor Train format), they leave the cumbersome formulas and practical implementation of the multidimensional case for future work.
  • Symmetry Assumptions: While the derivation assumes the matrix $A$ is symmetric, the authors successfully tested it on non-symmetric matrices, suggesting the method is more versatile than strictly proven.

Summary updated

Abstract

In this work we generalize the Jacobi-Davidson method to the case when eigenvector can be reshaped into a low-rank matrix. In this setting the proposed method inherits advantages of the original Jacobi-Davidson method, has lower complexity and requires less storage. We also introduce low-rank version of the Rayleigh quotient iteration which naturally arises in the Jacobi-Davidson method.
BibTeX
@article{rakhuba2017jacobi,
  author = {Maxim Rakhuba and Ivan Oseledets},
  title = {{Jacobi-Davidson method on low-rank matrix manifolds}},
  journal = {SIAM J. Sci. Comput.},
  year = {2017},
  doi = {10.48550/arxiv.1703.09096},
}
Figure