🔢 mathematics

Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace

This paper demonstrates that for positive semi-definite matrices, Nyström's method outperforms the standard Rayleigh-Ritz approach in accurately extracting leading eigenvalues and eigenvectors from a given subspace with the same computational cost, particularly when the matrix spectrum decays rapidly.

Original authors: Yuji Nakatsukasa, Zheng Tang

Published 2026-05-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuji Nakatsukasa, Zheng Tang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the "Heavyweights" in a Crowd

Imagine you have a massive, invisible crowd of people (a giant mathematical matrix). You want to find the "heavyweights"—the people with the most influence or the highest scores (the leading eigenvalues and eigenvectors).

However, you can't look at everyone at once because the crowd is too big. Instead, you pick a small, representative group of people (a subspace) to study. You know this small group is roughly like the heavyweights, but it's not perfect.

The paper asks a simple question: Once we have this small group, what is the best way to calculate their exact scores?

For decades, the standard answer was a method called Rayleigh-Ritz (RR). It's like taking a snapshot of the group and measuring them directly. The authors of this paper say: "Hold on. If we know these people are 'positive' (a specific mathematical property called Positive Semi-Definite), we can do better than the standard snapshot."

The Three Contenders

The paper compares three different ways to extract the scores from your small group:

Rayleigh-Ritz (RR): The old reliable. It projects the big problem onto the small group and solves it. It's fast and standard.
SVD-extract: A slightly more modern approach that looks at the group through a different mathematical lens (Singular Value Decomposition).
Nyström: The paper's star player. It's a method originally from machine learning that builds a "bridge" between the small group and the rest of the crowd to get a sharper picture.

The Main Discovery: Nyström is the Super-Res Lens

The authors prove that when dealing with "positive" matrices (which are common in things like data analysis and machine learning), Nyström is the winner.

The Analogy:
Imagine you are trying to guess the height of a giant mountain (the true eigenvalue) by looking at a small hill in front of you (your subspace).

RR is like measuring the hill and assuming the mountain is exactly that height. It's a good guess, but it has a big margin of error.
Nyström is like using a high-powered telescope that accounts for the curvature of the earth. It uses the fact that the mountain and the hill are made of the same "positive" material to infer the mountain's height much more accurately.

The Result:

Accuracy: Nyström's guesses are always closer to the truth than RR's.
The "Fast Decay" Bonus: If the mountain's height drops off very quickly (a "fast-decaying spectrum," common in real-world data), Nyström becomes dramatically better. The paper shows it can be arbitrarily more accurate—meaning the gap between Nyström and the others can be huge.
Cost: The best part? Nyström costs almost the same amount of computer power as RR. It's like getting a Ferrari engine for the price of a standard sedan.

The Catch: The "Tail" Problem

Every rule has an exception. The paper also looked at finding the trailing eigenvalues (the "lightweights" or the smallest scores at the bottom of the list).

The Reversal: When looking for the smallest numbers, Nyström actually performs the worst. It gets confused.
The Fix: The authors suggest a clever trick: Flip the script. Instead of looking for the smallest numbers directly, you look for the largest numbers of a "flipped" version of the data (mathematically, $-A + \gamma I$ ). Once you do this flip, Nyström becomes the hero again.

Summary of the Paper's Claims

The Problem: We often have a rough guess of the most important parts of a large data matrix. We need to refine that guess.
The Standard: For years, everyone used the Rayleigh-Ritz method.
The Breakthrough: If the data is "positive" (a common type), the Nyström method extracts the most accurate numbers, often beating the standard method by a massive margin, especially when the data has a "fast-decaying" pattern.
The Trade-off: There is no trade-off in speed; Nyström is just as fast as the standard method.
The Caveat: Nyström is terrible at finding the smallest numbers unless you use a "flip" trick to turn them into the largest numbers first.

In short: If you are analyzing big, positive data and want the most accurate top results without spending extra time, stop using the old standard method and switch to Nyström. Just remember to flip the data if you need the bottom results instead.

Technical Summary: Finding Accurate Eigenvalues and Eigenvectors of Positive Semi-Definite Matrices Given a Subspace

Problem Statement
The paper addresses a classical problem in numerical linear algebra: given an $n \times n$ positive semi-definite (PSD) matrix $A$ and a $k$ -dimensional subspace $Q$ (represented by an orthonormal basis matrix $Q \in \mathbb{R}^{n \times k}$ ) that approximates the leading eigenspace of $A$ , how can one extract high-accuracy eigenvalues and eigenvectors? While the Rayleigh-Ritz (RR) method is the standard approach for this task, the authors investigate whether the specific structural property of $A$ being PSD can be exploited to improve accuracy beyond what RR offers, without increasing computational complexity.

Methodology
The paper compares three projection-based methods that share the same computational complexity of $O(Nk + nk^2)$ , where $N$ is the cost of a matrix-vector multiplication with $A$ :

Rayleigh-Ritz (RR): The standard method which computes the eigenvalues of the projected matrix $Q^\top A Q$ . The approximate eigenvalues are $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$ .
SVD-extract: This method exploits the equivalence between eigenvalues and singular values for PSD matrices. It computes the singular values of the one-sided projection $AQ$. The approximate eigenvalues are $\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$ .
Nyström Method: This method constructs a low-rank approximation of $A$ , denoted as $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$ , and extracts eigenvalues from this approximation. The approximate eigenvalues are $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$ .

The authors analyze these methods theoretically by modeling the subspace $Q$ as an $\epsilon$ -approximation to the dominant invariant subspace $U_1$ of $A$ . They utilize perturbation analysis, Schur complements, and properties of PSD matrices to derive error bounds for the eigenvalue approximations.

Key Contributions and Theoretical Results

Accuracy Hierarchy for Leading Eigenvalues: The paper establishes a strict ordering of accuracy for approximating the leading eigenvalues (those corresponding to the largest eigenvalues of $A$ ). The authors prove the following inequality for the approximate eigenvalues:
$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$
Consequently, the absolute error satisfies:
$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$
This demonstrates that Nyström provides the most accurate estimates, followed by SVD-extract, with RR being the least accurate.
Higher-Order Accuracy of Nyström: The authors derive quantitative error bounds showing that Nyström achieves higher-order accuracy compared to RR and SVD-extract. Specifically, when the spectrum of $A$ decays rapidly (i.e., $\lambda_1 \gg \lambda_{k+1}$ ), the error of the Nyström method for the leading eigenvalues can be smaller than that of RR and SVD-extract by a factor proportional to $\lambda_1(A)/\lambda_{k+1}(A)$ . This improvement can be arbitrarily large.
Reversal for Trailing Eigenvalues: The paper notes that the situation reverses when targeting the trailing (smallest) eigenvalues. In this regime, the Nyström method performs poorly, and RR becomes the most accurate method. The authors attribute this to the fact that the subspace $\text{span}(AQ)$ (used by Nyström and SVD- $\tilde{U}$ ) is a better approximation of the leading invariant subspace $U_1$ but a worse approximation of the trailing invariant subspace $U_2$ compared to $\text{span}(Q)$ .
Remedy for Trailing Eigenvalues: To address the poor performance of Nyström for trailing eigenvalues, the authors suggest a shift-and-flip strategy. By computing the leading eigenpairs of the shifted matrix $\gamma I - A$ (where $\gamma \geq \lambda_{\max}(A)$ ), the Nyström method can be applied effectively to recover the trailing eigenvalues of the original matrix.

Results and Numerical Experiments
The theoretical findings are validated through numerical experiments:

Leading Eigenvalues: When $A$ has a rapidly decaying spectrum (exponential decay), the Nyström method significantly outperforms RR and SVD-extract, with error slopes indicating higher-order convergence. When the spectrum decays slowly (algebraic or linear), the advantage of Nyström diminishes but remains present.
Eigenvectors: Similar trends are observed for eigenvector approximations. Methods utilizing the subspace $\text{span}(AQ)$ (Nyström and SVD- $\tilde{U}$ ) yield more accurate leading eigenvectors than those restricted to $\text{span}(Q)$ (RR and SVD- $Q\tilde{V}$ ).
Trailing Eigenvalues: Experiments confirm that RR is superior for trailing eigenvalues, while Nyström fails unless the shift-and-flip technique is employed.

Significance and Claims
The paper claims to resolve an apparent inconsistency in the literature: while RR is known to be optimal in the sense of min-max characterization and subspace projection, this optimality does not preclude the existence of more accurate eigenvalue approximations when the PSD property is explicitly exploited.

The primary significance of the work is the demonstration that for PSD matrices, the Nyström method is a superior alternative to the standard Rayleigh-Ritz method for extracting leading eigenpairs, offering significantly higher accuracy at no additional computational cost. The authors emphasize that this improvement is particularly critical in applications involving matrices with fast-decaying spectra, such as kernel matrices in machine learning and covariance matrices in principal component analysis. The paper modestly notes that while the theoretical bounds are derived for real matrices, analogous results hold for complex matrices.