The reverse Ritz inclusion: computable bounds on the pseudospectra of an operator by those of a finite-rank compression

Isaia Nisoli

Source-linked AI summary

The reverse Ritz inclusion: computable bounds on the pseudospectra of an operator by those of a finite-rank compression

Isaia Nisoli

arXiv:2610.30530v1Oct 21, 2026math.NAcs.NA

TL;DR

For nonnormal operators, a finite-dimensional compression can fail to locate the operator’s eigenvalues, and existing reverse bounds may rely on unknown subspaces or difficult separation estimates. This paper uses bounds on the far block and couplings to certify exterior pseudospectral inclusion, eigenvalue counts, and invariant subspaces. In reported matrix tests, the certified far-block bound exceeded its measured norm by at most 25%.

Problem
For nonnormal operators, compression eigenvalues need not be near operator eigenvalues, while existing reverse bounds may require unknown eigenspaces or difficult separation estimates.
Source: §1 · pp. 1–2
Method
The method combines a finite-rank compression with bounds on the far block and couplings, then checks a singular-value inequality on an exterior contour.
Source: §1 · p. 2, §2.3 · p. 7
Results
The certified far-block bound exceeded the measured norm by at most 25% in the reported tests.
Source: §7 · p. 29
Takeaways & Limitations
The bounds provide exterior pseudospectral inclusion and eigenvalue counts for bounded operators without assumptions of normality, self-adjointness, or positivity.
Source: §1 · p. 2, §2.3 · p. 7
Choosing the frame is an uncertified search; what is certified is the hypothesis on the returned frame.
Source: §5.3 · p. 20

Abstract

from arXiv · show

We consider a bounded operator on a separable complex Hilbert space, reached only through its action on vectors and that of its adjoint, and split it along a subspace of finite dimension into a compression, a far block acting on the complement, and the two couplings between them. Given upper bounds on the norms of the couplings and of the far block, we show that outside a disc a pseudospectrum of the operator lies in a pseudospectrum of the compression, with an explicit loss in the level; this reverses the classical inclusion of the Ritz values in a pseudospectrum of the operator. The same bounds, with the smallest singular value of the shifted compression, bound the resolvent of the operator, count its eigenvalues with algebraic multiplicity inside every contour outside the disc on which a computed inequality holds, and enclose its spectral projector; no normality, self-adjointness or positivity is used.

1 Introduction

For nonnormal operators, a compression alone cannot reveal how far its eigenvalues are from the operator’s spectrum. This paper gives computable bounds that use a finite-dimensional compression and bounds on the omitted block and couplings to enclose exterior pseudospectra, eigenvalue counts, and invariant subspaces.

1 Introduction

A nonnormal compression can miss the operator’s spectrum, while earlier reverse bounds often depend on unknown eigenvectors or difficult-to-compute separation quantities.The paper’s bounds instead use computable quantities associated with the compression, couplings, and far block.Source: §1 · pp. 1–2

1.1 The certificate

Outside a disc, the computed inequality bounds the operator’s pseudospectrum by that of the compression with an explicit loss and gives matching exterior eigenvalue counts.The condition uses the smallest singular value of the shifted compression and upper bounds on the far block and couplings; the additional compression eigenvalues may lie anywhere inside the disc.Source: §1 · p. 2, §1.1 · p. 3

1.2 The inputs

The certificate uses the compression’s shifted smallest singular value, two coupling bounds, and an upper bound on the far block.In finite dimension the far-block bound can be certified by a sweep; in infinite dimension it must be assumed.Source: §1.2 · pp. 3–4

1.3 Origin and reach

The result applies to bounded operators accessed through operator and adjoint actions, without requiring normality, self-adjointness, or positivity.The motivating application is certifying leading eigenvalues and counts for a 216-cell Ulam discretisation of a noisy Belousov–Zhabotinsky map; a bound for a computed frame’s distance from the exact singular subspaces is not supplied.Source: §1.3 · p. 4

1.4 Related work

The paper combines a frame joining exterior eigendirections with left and right singular vectors, a contour-checkable hypothesis, and a certified far-block bound; alternatives may require unavailable matrix factorizations or contour solves.Its bounds are a posteriori, unlike cited coarse-operator bounds that depend on projection errors of the true eigenfunctions.Source: §1.4 · p. 5

2 The two-block bound

The two-block bounds use compression and coupling information to control the operator outside a disc, where the far block is bounded in norm. They yield pseudospectral inclusion, eigenvalue counts, and projector enclosures, with a self-adjoint specialization and a threshold at or above the essential spectral radius.

2.1 The floor

The resolvent estimate combines the shifted compression and far-block quantities σ11 and σ22 with coupling bounds γ1 and γ2.When σ11σ22 > γ1γ2, the displayed bound gives a positive lower estimate for the inverse resolvent norm.Source: §2.1 · p. 6

2.3 Inclusion, count and projector

For δ given by the cited coupling, Λδ(A)∩{|z|>R} is contained in Λε(G11)∩{|z|>R}; thus the inclusion holds outside the threshold R.Source: §2.3 · p. 7
If σ11(z)σ22(z) > γ1γ2 along an exterior contour, A and G11 have the same eigenvalue count there, counted with algebraic multiplicity.The count is finite and at most k; nothing is counted inside |z| ≤ ḡ.Source: §2.3 · p. 7
A contour resolvent bound also encloses the spectral projector of A and bounds the gap between its range and the padded compression projector.The projector enclosure uses the resolvent bounds alone, without a fixed-point refinement.Source: §2.3 · pp. 8–9

2.4 Self-adjoint operators

For self-adjoint A, every spectral point with |λ| > ḡ satisfies min_i|λ − θ_i|(|λ| − ḡ) ≤ γ̄², and separated intervals have matching counts.The matching count applies to [x1, x2] under the stated separation condition, and likewise to [−x2, −x1].Source: §2.4 · p. 9

2.5 How far the bound reaches

The exterior region is |z| > ḡ, and the method returns eigenvalues and multiplicities read from G11; the threshold ḡ is at least the essential spectral radius.The bound does not specify how much ḡ may exceed that radius.Source: §2.5 · p. 10

3 The small blocks

The small-block procedures provide certified enclosures for singular values, compression eigenvalue counts, and coupling norms. They use ball arithmetic for matrix uncertainty and choose different coupling bounds depending on which singular values are needed and whether the frame is explicit.

3.1 The singular value enclosure

The singular-value enclosure applies Theorem 3.1 to a ball matrix midpoint and widens intervals using an upper bound on the entrywise-radius matrix norm.The resulting two-sided enclosure can bound the matrix norm above and the smallest singular value below.Source: §3.1 · p. 11
Truncating the first frame in Rump’s two-frame bound can make its upper singular-value bound fail, even when all truncated residuals vanish.The cited 2n × n example has every singular value equal to one.Source: §3.1 · p. 11

3.2 The compression

Compression eigenvalue counts are certified by cluster inclusions, with Schur-frame recursion and verified Gershgorin discs as fallback routes.Disc counts transfer to G11 when no disc meets the region boundary.Source: §3.2 · pp. 11–12

3.2.1 Transport, and why the block route is not used

Transporting a block-diagonal bound through a nonnormal frame can sharply weaken it through the frame condition number.For the Grcar matrix, κ reached 8.2 · 10^10 at k = 64, reducing the certified bound to 3 · 10^-11 of the SVD value.Source: §3.2.1 · p. 12

3.3 The couplings

Each coupling can be bounded through a small Gram matrix formed using 2 dim Q applications of A and A*, once per operator rather than per shift.The Gram route targets the largest singular value; forming C*C squares conditioning, so the direct singular-value enclosure is used when small singular values are needed.Source: §3.3 · p. 12

4 The far block

The far block is inaccessible as a small matrix, so the paper bounds its norm from operator and adjoint applications. A deterministic sweep gives certificates, with floating-point rounding accounted for in the computed bounds.

4.1 What the far block admits

The far-block norm is bounded by a family of trace-power and interpolation bounds, with the Frobenius norm as the first member.The same computed columns provide the bounds at every order without further applications.Source: §4.1 · p. 13

4.2 Bounding the far block from applications of the operator

Fewer than n adaptive queries to B or B∗ cannot certify any finite upper bound on ∥B∥; for a known far block, at least n−k queries are necessary.The sweep uses n applications at order m=1 and raises the order adaptively when greater accuracy is needed.Source: §4.2 · pp. 13–14
For any submultiplicative matrix norm, ∥B∥≤|||H^m|||^1/2m for H=B∗B, and these bounds converge to ∥B∥ as m grows.Applying the same limit directly to B does not give an upper bound for a nonnormal operator.Source: §4.2 · p. 14

4.3 The sweep in floating point

The floating-point sweep costs mn applications and certifies rounding using an error bound for A, rather than propagating enclosures that can widen when the far block is small relative to A.The application-error assumption is consequential: the stated bound for a stored sparse matrix does not apply when Ay is formed as a difference of much larger operators.Source: §4.3 · p. 15

5 The certified splitting

The certified splitting combines a compression with bounds on the far block and couplings, using a frame built from eigendirections and singular directions. Contour checks yield exterior resolvent and eigenvalue-count conclusions, while frame selection and orthonormality are handled with explicit qualifications.

5.1 The frame

Including the leading left and right singular vectors bounds both couplings and the far block by the first singular value left out of the frame.Including only one side can leave the opposite coupling as large as s1(A); no d-dimensional frame can reduce the far-block norm below s2d+1(A).Source: §5.1 · p. 19

5.2 The exterior

If the contour hypothesis holds and G11 has exactly one eigenvalue outside radius R, A has exactly one there and all its other eigenvalues lie inside R.The count is with algebraic multiplicity.Source: §5.2 · p. 19

5.3 Choosing the frame, cost and failure

Frame search is uncertified and may miss a smaller passing frame; certification applies to the returned frame, while larger frames increase the compression cost cubically.The search can also fail at its dimension cap, and singular-value decay bounds how small the far block can become.Source: §5.3 · p. 20

5.4 The frame is not orthonormal

With a nonorthonormal frame, the midpoint compression and the isometric compression have the same eigenvalue counts when the contour singular-value bound exceeds the frame-defect and rounding allowance.The stated threshold is ηα+ρ.Source: §5.4 · p. 21

6 Numerics

The numerics test which frame dimensions can support the certificate, compare alternative frame constructions, and evaluate certified bounds and eigenvalue counts on matrices and an operator accessed only through its action. Results show that certification depends strongly on the operator and radius, while certified counts match dense counts wherever reported.

6.1 What a frame can reach

For four size-199 matrices, dmin ≤ N at every gap; for rdb800l, points above dmin = N persisted through N = 15, while other matrices showed different reachability patterns.The condition dmin ≤ N is necessary, not sufficient: couplings and σ11 on the circle also determine whether a frame passes.Source: §6.1 · p. 22, Figure 1 · p. 23

6.2 Frames of one side and of two

Two-sided frames passed at every radius where a one-sided frame passed, plus 10 and 13 additional radii on rdb2048 and qh1484, respectively.On rdb200 and rdb800l only two-sided frames passed; on landau400 only one-sided frames did.Source: §6.2 · pp. 22, 24, Table 2 · p. 24

6.3 The far block, certified and measured

The order-8 certified far-block bound had median ratios to dense ∥G22∥ between 1.000 and 1.185 by operator, with a largest ratio of 1.244.The order-one bound alone had median ratios between 1.14 and 18.2.Source: §6.3 · p. 25, Table 3a · p. 25
On landau400, dense singular vectors brought ∥G22∥ below R at frame dimensions 199 and 200 at three tested radii, while either bidiagonalisation did not.At N = 1, both approaches passed.Source: §6.3 · p. 25, Table 3b · p. 26

6.4 The certificate

For davies200, the plane-wide bound existed at all grid points and had median ratio 0.999 to dense σmin(A − zI), with a minimum ratio of 0.697.At no grid point did the bound exceed the dense value.Source: §6.4 · p. 26, Figure 2 · p. 27
For rdb800l, the bound existed at 23,222 of 40,000 grid points and had median ratio 0.296 to dense σmin(A − zI), never exceeding the dense value.This radius had dmin > N.Source: §6.4 · p. 26, Figure 3 · p. 28
At every certified radius, the certified count equalled the dense count; the certified lower bound on the circle was at most 0.70 times the dense value wherever compared.Certification required frames ranging from near the eigenvalue count to near the n/2-column cap, depending on the matrix.Source: §6.4 · p. 26, Table 4 · p. 27

6.5 An operator that is not stored

At k = 2^12, counts and isolation discs were certified at every tested radius with N ≤7, and each count matched the dense eigenvalue count.At k = 2^16, certification held for N ≤4; no tried frame passed for N = 5 or 7.Source: §6.5 · p. 28

7 Discussion

The certificate’s reach depends on singular-value decay: some operators require frames near the dimension cap, while others admit no passing frame. The discussion also identifies limits on interior bounds, isolation-disc size, and contour choice.

7 Discussion

Frames certify five radii on qh1484 and selected radii on rdb2048 and rdb5000, but none on kahan500 or hatano2000.The successful frames are close to the n/2 cap for rdb2048 and rdb5000; Proposition 5.2 relates passing frames to singular-value decay.Source: §7 · p. 29
Inside the excluded disc, the available bound uses σmin(G22) and does not reach the interior; the proposed inverse-operator continuation requires certified solves and was not carried out.For compact A, the discussion says the excluded disc about a shift always contains the origin.Source: §7 · p. 29
Figure 4 maps certified log10 lower bounds on σmin(A − zI), with each panel on its own color scale and red points marking dense eigenvalues or leading Ritz values.White and dashed circles mark |z| = R and |z| = ḡ; yellow marks isolation discs and grey indicates no bound.Source: Figure 4 · p. 30
An isolation circle cannot be certified below roughly γ1γ2/(|λ| − ḡ), and the far-block bound depends on sweep order through singular-spectrum flatness.In the example, γ1γ2 = 7.0 · 10^-4; γ2 vanishes when the kept subspace is A-invariant.Source: §7 · p. 30
Contour certification can use bounded-spacing samples, but choosing a contour that makes the hypothesis margin uniform has not been carried out.The reported statements and experiments use circles.Source: §7 · p. 30