🔢 mathematics

Stabilizing the Rayleigh--Ritz procedure by randomization

This paper resolves a long-standing open problem in eigenvalue computation by introducing a randomized Rayleigh--Ritz procedure that guarantees the convergence of approximate eigenpairs at a rate comparable to the ideal projection, overcoming the potential failure of the standard method.

Original authors: Nian Shao

Published 2026-04-02

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Nian Shao

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

Imagine you are trying to find a specific, unique needle in a giant haystack. In the world of mathematics and physics, this "needle" is a special solution to a complex equation called an eigenpair (a specific number and a specific direction).

Often, we don't have the whole haystack to look at. Instead, we only have a small, manageable basket of hay (a subspace) that we think contains the needle. The goal is to look inside this basket and pull out the best possible approximation of that needle.

The Old Problem: The "Standard" Way Fails

For decades, mathematicians have used a standard method called the Rayleigh-Ritz procedure to look inside this basket. Think of this method as a very rigid, straight-line flashlight.

The Good News: If the needle is at the very top or bottom of the haystack (an "exterior" eigenvalue), the flashlight works perfectly.
The Bad News: If the needle is hidden somewhere in the middle of the haystack (an "interior" eigenvalue), or if the hay is tangled in a weird way (non-Hermitian or generalized problems), the flashlight often goes dark.
- It might point to the wrong spot.
- It might spin in circles and never settle on a direction.
- In the worst cases, it gives you a result that looks like garbage, even if you have a very good basket.

The paper's author, Nian Shao, points out that this has been a frustrating, unsolved mystery for a long time: How do we reliably find the needle in the middle of the haystack without the flashlight breaking?

The New Solution: The "Randomized" Flashlight

The author introduces a new method called the Randomized Rayleigh-Ritz (RRR) procedure. Instead of using a rigid, straight flashlight, this new method uses a spray of glitter.

Here is how the analogy works:

The Standard Method (Rigid Flashlight): It tries to project the needle directly onto the basket. If the basket is slightly tilted or the needle is slippery, the projection fails. It's like trying to balance a wet bar of soap on a moving boat; one small wobble sends it flying.
The Randomized Method (Spray of Glitter): Instead of a single rigid line, this method throws a handful of random, magical glitter (a complex Gaussian random matrix) over the basket.
- This glitter doesn't care about the weird angles or the slippery soap.
- Because the glitter is random, it is almost guaranteed to "stick" to the needle in a way that reveals its true position, even if the basket is messy.
- It acts like a stabilizer. Just as a gyroscope keeps a ship steady in rough waves, this randomization keeps the math stable, preventing the calculation from collapsing.

Why is this a Big Deal?

The paper proves mathematically that this "glitter" method works almost every time.

Speed: It finds the needle just as fast as the "perfect" theoretical method (which we can't actually use because we don't have the whole haystack).
Reliability: It works even when the old method fails completely. Whether the needle is in the middle, the hay is tangled, or the math is non-linear, the RRR method keeps finding the answer.
Refinement: Once the glitter helps you find a "rough" location, the method has a second step (like polishing the needle) to make the answer incredibly precise.

The "Butterfly" and "Hamiltonian" Examples

The author tested this on some very tricky real-world problems:

Hamiltonian Systems: Imagine a spinning top that is perfectly balanced. The old method would get confused and say the top is falling over or spinning wildly. The new method correctly identifies that it's just spinning steadily.
The Butterfly Problem: A complex shape where the math gets very wiggly. The old method stumbled, but the new method glided right through, finding the answer with high precision.

The Takeaway

For a long time, mathematicians had to guess if their calculations would work or if they would crash. This paper says: "Stop guessing. Use the randomizer."

By adding a little bit of controlled randomness (the glitter), we can stabilize the most difficult math problems, ensuring that we find the right answer every time, no matter how messy the data is. It turns a fragile, breakable process into a robust, reliable one.

1. Problem Statement

The paper addresses a fundamental challenge in numerical linear algebra: extracting accurate eigenpairs $(\lambda, v)$ from a prescribed low-dimensional subspace $W_\epsilon$ .

Context: Subspaces $W_\epsilon$ are often generated by iterative methods (e.g., Krylov subspace methods, reduced-basis techniques) where the target eigenvector $v$ lies close to the subspace, defined by the canonical angle $\epsilon = \angle(v, W_\epsilon)$ .
The Core Issue: While the standard Rayleigh–Ritz (RR) procedure is the industry standard for this task, it suffers from severe stability issues:
- Hermitian Interior Eigenvalues: Convergence of Ritz values may degrade from quadratic to linear, and Ritz vectors may fail to converge entirely.
- Non-Hermitian Problems: Convergence rates can deteriorate to $O(\epsilon^{1/m})$ due to the compressed matrix becoming nearly defective.
- Generalized/Nonlinear Problems: The compressed matrix pencil can become singular even if the original problem is regular, causing the RR procedure to fail completely.
Open Question: How can one reliably extract an eigenpair with a convergence rate comparable to the ideal projection (i.e., matching the accuracy of projecting $v$ onto $W_\epsilon$ ) without requiring the matrix to be Hermitian or the eigenvalue to be exterior?

2. Methodology: Randomized Rayleigh–Ritz (RRR)

The author proposes a Randomized Rayleigh–Ritz (RRR) procedure to stabilize the extraction process.

Algorithm Overview

Instead of imposing the standard Galerkin condition ( $W_\epsilon^H A_0 W_\epsilon y = \mu y$ ), the RRR procedure imposes a Petrov–Galerkin condition using a complex Gaussian random matrix $\Omega \in \mathbb{C}^{n \times m}$ :

Sketching: Generate a random matrix $\Omega$ with i.i.d. complex Gaussian entries.
Compression: Solve the compressed generalized eigenvalue problem:
$\Omega^H A_0 W_\epsilon y_\epsilon = \mu_\epsilon \Omega^H W_\epsilon y_\epsilon$
(For nonlinear problems $A(\xi)$ , solve $\Omega^H A(\xi) W_\epsilon y = 0$ ).
Refinement: Compute a refined eigenvalue estimate $\rho_\epsilon$ using the standard Rayleigh quotient (for linear problems) or a Rayleigh functional/stationary point search (for nonlinear problems):
$\rho_\epsilon = \frac{(W_\epsilon y_\epsilon)^H A_0 (W_\epsilon y_\epsilon)}{(W_\epsilon y_\epsilon)^H (W_\epsilon y_\epsilon)}$

Theoretical Mechanism

The core insight is that while the standard projection $W_\epsilon^H (A_0 - \lambda I) W_\epsilon$ can degenerate (e.g., become zero or defective), compressing the operator with an oblivious random matrix $\Omega$ preserves the simplicity of the zero singular value with high probability.

The randomization ensures that the condition numbers of the compressed problem (eigenvalue and eigenvector) remain bounded by moderate multiples of the original problem's condition numbers, preventing the catastrophic loss of accuracy seen in deterministic RR.

3. Key Contributions

Resolution of a Long-Standing Open Problem: The paper provides the first method that guarantees convergence rates for Ritz vectors and values comparable to the ideal projection for general eigenvalue problems (non-Hermitian, generalized, and nonlinear), provided the target eigenvalue is simple.
Non-Asymptotic Probabilistic Bounds: The analysis provides rigorous, non-asymptotic error bounds. Unlike previous works that rely on asymptotic limits, these bounds hold for finite dimensions with explicit probability guarantees.
Extension to Nonlinear Problems: The methodology is generalized to nonlinear eigenvalue problems (NEVPs) $A(\lambda)v=0$ , utilizing Rayleigh functionals and stationary point refinements.
Comparison with Existing Methods:
- Unlike sketched Rayleigh–Ritz (which requires oversampling and provides only a posteriori estimates), RRR requires no oversampling and provides a priori convergence guarantees.
- Unlike refined or harmonic RR (which require extra SVD/QR costs and lack rigorous convergence guarantees for generalized problems), RRR offers both efficiency and theoretical stability.

4. Main Results and Convergence Rates

Let $\epsilon = \angle(v, W_\epsilon)$ . The paper establishes that with high probability ( $1 - O(\delta)$ ):

Problem Type	Standard RR (Value)	Standard RR (Vector)	RRR (Value)	RRR (Vector)	RRR (Refined Value)
Hermitian (Exterior)	$O(\epsilon^2)$	$O(\epsilon)$	$O(\epsilon)$	$O(\epsilon)$	$O(\epsilon^2)$
Hermitian (Interior)	$O(\epsilon)$	Fails	$O(\epsilon)$	$O(\epsilon)$	$O(\epsilon^2)$
Non-Hermitian	$O(\epsilon^{1/m})$	Fails	$O(\epsilon)$	$O(\epsilon)$	$O(\epsilon)$
Generalized/Nonlinear	Fails	Fails	$O(\epsilon)$	$O(\epsilon)$	$O(\epsilon)$ (or $O(\epsilon^2)$ if Hermitian)

Ritz Vectors: The randomized Ritz vectors $W_\epsilon y_\epsilon$ converge linearly ( $O(\epsilon)$ ) regardless of whether the matrix is Hermitian or the eigenvalue is interior/exterior.
Refined Values: The refined values $\rho_\epsilon$ achieve quadratic convergence ( $O(\epsilon^2)$ ) for Hermitian problems (matching the ideal projection) and linear convergence ( $O(\epsilon)$ ) for non-Hermitian problems.
Conditioning: The convergence constants depend on the condition numbers of the original problem ( $\kappa_{val}, \kappa_{vec}$ ) and the subspace dimension $m$ , but are independent of the specific basis of $W_\epsilon$ .

5. Numerical Experiments

The paper validates the theory through three experiments:

Hamiltonian Neutral Modes: In a scenario where standard RR fails completely (compressed pencil vanishes) due to neutral modes, RRR successfully extracts the eigenpair with optimal accuracy.
Butterfly Nonlinear Eigenvalue Problem: Demonstrates that for Hermitian nonlinear problems, RRR achieves quadratic convergence for refined values, matching the performance of standard RR on exterior eigenvalues but working for interior ones.
Oversampling Analysis: Confirms that the probabilistic factor $1/\sqrt{\delta}$ in the error bound is sharp. Unlike other randomized algorithms (e.g., Randomized SVD), oversampling does not improve the convergence rate or stability of RRR, as the failure mode is structural rather than statistical.

6. Significance

This work fundamentally changes the approach to eigenpair extraction from subspaces. It demonstrates that randomization acts as a stabilizer against the structural instabilities (defectiveness, singularity) that plague deterministic projection methods.

Practical Impact: It allows for the reliable computation of interior eigenvalues and solutions to generalized/nonlinear problems where standard methods are known to fail or produce erratic results.
Theoretical Impact: It bridges the gap between the "ideal" projection accuracy and practical subspace extraction, proving that randomization can recover the optimal convergence rates without requiring the restrictive assumptions (Hermiticity, exterior eigenvalues) previously thought necessary.