5 Spectral uncertainty and exact completion
On this page · Permalink · Source line 1
A useful operator approximation is not automatically a useful tail approximation. This chapter transports phase-pruning error to eigenvalue intervals, measures unresolved range through trace information, and completes small residual ranges exactly. A separate post-verification theorem connects stored binary64 factors to rigorous spectral intervals.
5.1 From phase pruning to certified quadratic-form tails
On this page · Permalink · Source line 7
The previous sections certify the effect of phase pruning on Krylov propagation. A SKAT-like test ultimately depends on the spectrum itself, so one more bridge is needed:
5.1.1 Block-norm operator domination
On this page · Permalink · Source line 22
Let
be the self-adjoint error introduced by phase pruning. Using the same orthogonal phase projectors \(P_h\), define
Theorem 5.1: Block-norm operator certificate
Proof
For any vector \(x\), let
Then
Orthogonality of the phase decomposition gives
Taking the supremum over unit vectors proves the claim.
The important computational point is that \(\mathcal C\) is only a phase-by-phase matrix. The same block norms already used to construct the polyphase scheduler therefore provide a global operator certificate.
5.1.2 Weyl enclosure of the quadratic-form coefficients
On this page · Permalink · Source line 79
Assume
and let the eigenvalues of \(H\) and \(H_0\), in decreasing order, be
If
Weyl's inequality gives
Corollary 5.2: Positive spectral interval
For every \(i\),
This remains valid even if symmetric phase pruning makes \(H_0\) slightly indefinite.
5.1.3 Certified generalized-\(\chi^2\) tail bracket
On this page · Permalink · Source line 120
For independent standard normal variables \(Z_i\), define
Theorem 5.3: Stochastic tail enclosure
For every threshold \(q\),
Proof
Couple all three quadratic forms using the same normal variables \(Z_i\). Since
for every \(i\),
almost surely. Taking upper-tail events yields the result.
The endpoint probabilities are separate tail queries. Each must satisfy the hypotheses of the numerical backend used to evaluate it. In particular, zero lower coefficients can reduce the active rank below the directed backend's coverage. The stochastic enclosure remains valid in that case, but it does not by itself supply a supported numerical evaluation. Numerical error is separate from the spectral uncertainty above.
5.1.4 A dual-budget pruning rule
On this page · Permalink · Source line 164
The local Krylov certificate from the previous section and the global spectral certificate answer different questions. The former asks whether omitted couplings matter to the current Krylov query. The latter asks whether they can move the spectrum enough to matter to the final test.
An execution schedule should therefore enforce
The implementation uses a conservative greedy rule: phase pairs are considered in increasing query-risk order, and a pair is omitted only when adding it preserves both inequalities. The rule is certified but is not claimed to be globally optimal under the two simultaneous constraints.
In the deterministic ten-phase experiment, fixing the query budget at \(0.05\) and the operator budget at \(0.005\) removed \(23\) of \(45\) undirected phase pairs. At a reference probability near \(10^{-8}\), the analytic tail bracket was
a width of about \(0.221\) decades. These endpoints summarize the real-arithmetic error analysis evaluated in floating point, not a directed rounding enclosure. With an operator budget of \(0.0075\), \(34\) pairs were removed and the interval widened to about \(0.320\) decades. By contrast, allowing a strong coupling to be removed under a very loose operator budget produced a multi-decade interval.
5.1.5 Certify after prune
On this page · Permalink · Source line 214
There is a second route that does not use the pruned operator as the final spectral approximation. Let \(U\) be any orthonormal sample-space basis, possibly generated cheaply from a pruned or approximate Krylov process, and define
Theorem 5.4: Range-core singular-value certificate
For \(A\in\mathbb R^{n\times m}\), list the singular values of \(A\) and \(B\) in decreasing order and pad both lists with zeros to length \(n\). Write these lists as \(\sigma_i(A)\) and \(\widetilde\sigma_i(B)\), respectively. They are the square roots of the \(n\) eigenvalues of \(AA^\top\) and \((UB)(UB)^\top\). Then, for \(1\le i\le n\),
Consequently,
Proof
Because \(U\) has orthonormal columns,
and
The nonzero singular values of \(UB\) and \(B\) agree, with multiplicity, and their zero-padded lists agree in the stated ambient convention. The standard singular-value perturbation inequality gives the stated bound. Squaring the nonnegative endpoints gives the eigenvalue interval.
This provides a useful architecture:
5.1.6 A retained negative result
On this page · Permalink · Source line 283
The preceding theorem is exact, but a correct interval need not be useful.
In a full-rank \(50\times50\) stress test, a pruned Krylov basis of dimensions \(12\) through \(48\) left range residuals between roughly \(0.87\) and \(0.99\) times the leading singular value. The corresponding \(10^{-8}\) tail intervals were therefore vacuous or thousands of decades wide. At dimension \(50\), the range residual fell to approximately \(1.2\times10^{-15}\), and the tail interval collapsed to the exact value.
The practical lesson is that range-core certification is a stopping test, not a promise that a severely incomplete basis automatically yields a useful full-spectrum tail bound.
5.2 Trace-aware residual certification and exact completion
On this page · Permalink · Source line 307
The spectral bridge in the preceding section used an operator-norm residual as if every unresolved coefficient could move independently by the same amount. That is rigorous but unnecessarily pessimistic once a nontrivial range basis has already been captured. The residual has considerably more structure.
Let \(U\in\mathbb R^{n\times r}\) have orthonormal columns and define
Then
Theorem 5.5: Exact core–residual decomposition
In particular the unresolved spectral term
is positive semidefinite.
Proof
Expand \((UB+F)^\top(UB+F)\). The two cross terms vanish because \(U^\top F=0\), while \(U^\top U=I\).
This changes the certification problem. Instead of an arbitrary Hermitian error, the missing term is a positive residual with measurable spectral moments. Define
Then
The first quantity is the exact missing mean of the Gaussian quadratic form. The second records how concentrated the residual spectrum is. The third is its largest coefficient.
5.2.1 A trace–Frobenius–cap MGF envelope
On this page · Permalink · Source line 371
Set
For \(0<2\theta(c+\rho)<1\), put
Theorem 5.6: Trace–Frobenius–cap log-MGF certificate
For the Gaussian quadratic form with coefficient matrix \(H\),
satisfies
Proof
Factor the determinant through the known core:
where
Since
we have
For every eigenvalue \(x\) of \(T\),
The scalar inequality follows from the power series of \(-\log(1-u)\) and a geometric bound on all terms of degree at least two. Summing over the eigenvalues of \(T\) proves the result.
Corollary 5.7: Trace-aware Chernoff upper tail
For \(Q=Z^\top HZ\) with \(Z\sim N(0,I)\),
where \(\widehat\kappa_H\) is the preceding MGF upper bound.
A complementary lower endpoint is immediate from
Using the same normal vector,
almost surely, and therefore
The lower endpoint can be evaluated by K-COS on the captured core spectrum, while the upper endpoint is obtained from the optimized trace-aware Chernoff bound.
5.2.2 Finite stress test
On this page · Permalink · Source line 481
The previous coefficient-wise Weyl interval was intentionally conservative. On the same full-rank, 50-dimensional stress test used in the preceding section, its \(10^{-8}\) tail interval remained thousands of decades wide until essentially the complete range had been captured. Preserving the exact residual trace and higher residual moments changes that behavior substantially.
| Krylov depth | basis dimension | Weyl width | moment width |
|---|---|---|---|
| 4 | 24 | 90,097 | 11.86 |
| 5 | 30 | 16,511 | 9.76 |
| 6 | 36 | 3,747 | 7.67 |
| 7 | 42 | 2,275 | 5.70 |
| 8 | 48 | 1,165 | 3.39 |
A separate random implementation audit used 120 random factor/range pairs and four admissible positive tilts per pair, for 480 MGF comparisons. Both the trace/cap and trace–Frobenius–cap envelopes dominated the exact log MGF in every tested case. The trace–Frobenius–cap form was at least as tight as the trace/cap form in approximately 83.5% of those comparisons. This finite sweep audits the implementation. The theorem above supplies the universal argument.
5.2.3 Residual rank from moments
On this page · Permalink · Source line 522
The same invariants determine when it is better to stop approximating the missing spectrum and complete it exactly. Let
If the nonzero eigenvalues of \(R\) are \(r_1,\ldots,r_s\), then
Theorem 5.8: Residual-rank bracket
The zero-residual case is interpreted separately as rank zero.
Proof
The inequality \(t\le s\rho\) gives \(s\ge t/\rho\). Cauchy–Schwarz gives
so \(s\ge t^2/v\). Finally, every column of \(F\) lies in \(\operatorname{range}(U)^\perp\), whose dimension is \(n-r\).
Whenever the integer lower bound equals \(n-r\), the missing rank is certified exactly without computing a residual SVD.
5.2.4 Exact residual completion
On this page · Permalink · Source line 580
Suppose a compact factorization of the residual is
where the columns of \(W\) form an orthonormal basis of \(\operatorname{range}(F)\). Zero residual directions are omitted. Since this range lies in the orthogonal complement of \(U\),
Theorem 5.9: Exact residual completion
Consequently, the nonzero singular values of \(A\) are exactly the nonzero singular values, with multiplicity, of the stacked completion core
Proof
The decomposition \(A=UB+F\) and the identity \(F=WD\) give the factorization. The matrix \([U\;W]\) has orthonormal columns, so \(A^\top A=\mathcal C_{\rm complete}^\top\mathcal C_{\rm complete}\). The nonzero singular values therefore agree with multiplicity. If the combined basis contains directions outside \(\operatorname{range}(A)\), its row Gram may include additional zeros. Its entire spectrum is the nonzero spectrum of \(AA^\top\) only when the combined basis spans exactly \(\operatorname{range}(A)\).
This identity admits a column-streamed implementation. For each residual column block, project against the residual basis accumulated so far, append only genuinely new directions through rank-revealing QR or SVD, and extend the coordinate matrices of earlier blocks with zero rows. New residual directions are orthogonal to every earlier residual block by construction, so no earlier data block must be revisited.
In the deterministic stress test, exact residual completion reproduced the full singular spectrum at relative errors between approximately \(2\times10^{-16}\) and \(6\times10^{-16}\) for all tested incomplete bases. The resulting \(10^{-8}\) tail differed from the full-spectrum reference by less than \(10^{-14}\) decades. At depth 8 the candidate range had dimension 48, the missing rank was certified as exactly two, and appending those two residual directions closed the spectrum without another approximate Krylov stage.
5.2.5 Hybrid stopping rule
On this page · Permalink · Source line 642
Residual information supplies a stopping rule for approximate iteration and a handoff to exact completion:
The trace-aware tail certificate remains useful as a rigorous intermediate bound and as a stopping diagnostic. Once only a small number of residual directions remain, exact completion is mathematically preferable to forcing a worst-case tail envelope to become artificially sharp.
5.3 Verified matrix-to-spectrum bridge
On this page · Permalink · Source line 667
A tail enclosure is conditional on the spectrum supplied to it. To certify a matrix-defined problem, the spectrum itself must be enclosed. This section post-verifies a candidate eigensystem against the exact Gram matrix defined by the stored factor entries. Chapter 9 supplies the positive-tail backend used at the endpoint of this construction.
5.3.1 Binary64 input semantics
On this page · Permalink · Source line 675
Let
be supplied as an IEEE binary64 array. Each stored entry is treated as its exact dyadic rational value. The target operator is therefore the exact Gram matrix
defined by those binary64 values, not an unspecified nearby real matrix.
A high-precision symmetric eigensolver is used only to generate candidate quantities
No correctness claim depends on trusting this eigensolver.
5.3.2 Post-certified spectral enclosure theorem
On this page · Permalink · Source line 700
Theorem 5.10: Candidate eigensystem post-certification
Let
Suppose directed-rounding computation proves
and
Then the ordered eigenvalues of the positive semidefinite matrix \(H\) satisfy
for every \(i\).
Proof
Set
The first hypothesis gives the Loewner inequalities
The eigenvalues of
are the same as those of
Hence
and eigenvalue monotonicity yields
Weyl's perturbation inequality and \(\|H-B\|_2\le\rho\) then give
Combining the two bounds and using \(H\succeq0\) proves the claim.
The implementation does not attempt to evaluate the spectral norms above exactly. Instead it encloses every entry of
with directed-rounding interval arithmetic and uses
Thus the reported \(\eta\) and \(\rho\) are conservative certified upper bounds.
5.3.3 Monotone propagation into the tail
On this page · Permalink · Source line 783
Let the spectral theorem produce
Using the same independent standard normals in all three sums gives
Therefore
The lower endpoint is evaluated by the rigorous positive-tail backend on the lower spectrum, and the upper endpoint by the same backend on the upper spectrum. The controller requires more than two strictly positive coefficients in each endpoint spectrum and a threshold above both endpoint means. An endpoint spectrum outside these implemented conditions is rejected or reported as unsupported. Monotone coupling itself remains valid. The final matrix-defined probability interval is accepted only when its multiplicative ratio satisfies the requested accuracy.
5.3.4 Random dense spectral-containment audit
On this page · Permalink · Source line 816
Three unrelated dense binary64 factors were tested against independently recomputed high-precision eigenvalues of their exact dyadic Gram matrices:
| factor size | all eigenvalues contained | maximum relative width | time (s) |
|---|---|---|---|
| \(12\times18\) | yes | \(3.36\times10^{-58}\) | 0.09 |
| \(20\times30\) | yes | \(1.44\times10^{-57}\) | 0.35 |
| \(28\times36\) | yes | \(1.20\times10^{-56}\) | 0.80 |
No reference eigenvalue fell outside its certified interval.
5.3.5 End-to-end matrix-defined tail near \(10^{-16}\)
On this page · Permalink · Source line 835
A dense \(64\times64\) exact-binary factor was constructed from a normalized Hadamard basis with four singular-value groups. The stored binary64 entries are exact dyadic rationals. The spectral postcheck returned
The leading coefficient, whose exact value is one in this control, was enclosed with a width of order \(10^{-49}\). The full outward-rounded endpoints are preserved in the spectral record. Ellipsized decimal strings are not used as interval endpoints.
At
the tail lies near \(10^{-16}\). Starting from the factor matrix itself:
| requested relative accuracy | achieved ratio minus one | certified |
|---|---|---|
| \(10^{-10}\) | \(2.60\times10^{-12}\) | yes |
| \(10^{-12}\) | \(4.09\times10^{-15}\) | yes |
For the \(10^{-12}\) request, the final enclosure was approximately
This closes the basic numerical chain
at moderate matrix dimension.
5.3.6 Scalability boundary
On this page · Permalink · Source line 887
The theorem applies in every finite dimension, but the present verifier forms a full candidate basis \(Q\) and postchecks dense matrices. It therefore closes the correctness boundary before it closes the large-scale memory boundary. For very large streamed factors, a memory-bounded guarantee would require a verified range-core/residual certificate and an interval completion step in place of the full-basis postcheck. Those extensions are not part of the implemented dense verifier.