COS Method

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Adaptive evaluation and numerical interfaces}\label{ch:adaptive}
2 \chapterlead{An adaptive solver should refine the representation responsible for the
3 largest unresolved error. The planner described here chooses packets, support,
4 and modes jointly. Its floating implementation retains an analytic ledger.
5 The next part supplies the stricter contract in which finite arithmetic and
6 output serialization are enclosed as well.}
7 \section{Adaptive K-COS algorithm}
8 
9 The packet planner accepts a finite positive spectrum, an upper-tail query
10 $q>\sum_j\lambda_j$, and a requested relative tolerance $\tau>0$.
11 Its initial support parameter satisfies $L>0$, and its mode count is a
12 positive integer.
13 
14 \begin{enumerate}[leftmargin=2em]
15 \item Solve $\kappa'(\theta_*)=q$.
16 \item Initialize an upper interval $b=q+L\sqrt{\kappa''(\theta_*)+\sqrt{\kappa^{(4)}(\theta_*)}}$ and a mode count $N$.
17 \item Retain the largest spectral spikes exactly and place the remaining sorted eigenvalues into coarse packets.
18 \item Evaluate $\rho_P(\theta_*+\ii u_k)$ and the packet remainder bound on the actual COS grid. Split packets until the propagated packet contribution is within its budget.
19 \item Evaluate the support/alias certificate from \eqref{eq:eps-support}--\eqref{eq:eta}.
20 \item Evaluate the omitted-mode certificate \eqref{eq:eps-cos}.
21 \item If the combined relative certificate exceeds $\tau$, refine whichever analytic error source dominates: split packets, increase $b$, or increase $N$.
22 \item Return a certified analytic result only after the combined bound meets
23 $\tau$. Return the tail estimate, the compiled spectral representation,
24 and its error ledger together. If resource limits are reached first,
25 report failure to certify rather than accepting the estimate.
26 \end{enumerate}
27 
28 The resulting object is query dependent. Schematically,
29 \begin{equation}
30 (\Lambda,q,\tau)
31 \longmapsto
32 \mathcal P_{\Lambda,q,\tau}
33 \longmapsto
34 (\widehat p,\text{certificate}),
35 \label{eq:compiler-map}
36 \end{equation}
37 where $\mathcal P_{\Lambda,q,\tau}$ stores exact spikes, packet centers, centered moments, packet radii, and the selected COS parameters.
38 
39 
40 \section{Numerical interfaces and log-domain evaluation}\label{sec:final-25}
41 
42 The preceding mathematics is exposed through a domain-neutral engine rather
43 than through a SKAT-only entry point.  The central positive engine accepts:
44 
45 \begin{itemize}
46 \item an explicit nonnegative spectrum.
47 \item a positive semidefinite matrix.
48 \item a dense factor \(A\).
49 \item a replayable streamed column-factor source.
50 \item or a covariance/quadratic-matrix pair
51 \((\Sigma,M)\).
52 \end{itemize}
53 
54 A signed central engine accepts a signed spectrum, a symmetric operator, or
55 \[
56 (\Sigma,M),\qquad M=M^\top,
57 \]
58 and performs the exact central-indefinite reduction proved in Chapter~\ref{ch:gaussian}.  A
59 separate noncentral positive engine accepts
60 \[
61 (\mu,\Sigma,M),\qquad M\succeq0,
62 \]
63 and performs the corresponding noncentral reduction.
64 
65 \subsection{Log-domain packet error accumulation}
66 
67 After separating the likelihood-ratio prefactor, the packet contribution
68 contains sums of the form
69 \[
70 \frac{2}{b}
71 \sum_k
72 |J_k|
73 \left(
74 e^{\varepsilon_k}-1
75 \right).
76 \]
77 Direct evaluation can overflow even when the candidate is destined to be
78 rejected by the adaptive planner.  The implementation instead
79 computes
80 \[
81 \log\left(
82 \frac{2}{b}
83 \sum_k
84 |J_k|
85 \left(
86 e^{\varepsilon_k}-1
87 \right)
88 \right)
89 \]
90 by log-sum-exp arithmetic, and compares this quantity with the logarithm of
91 the requested tolerance before converting a final accepted bound back to
92 float64.
93 
94 This change does not weaken the mathematical bound. It changes only its
95 floating-point representation.
96 
97 \subsection{Reference convergence is part of verification}
98 
99 An independently evaluated reference is useful only if its own numerical
100 resolution has converged.  In a rank-350 deep-tail audit, an initial fixed-grid
101 reference appeared to disagree with the adaptive answer.  Increasing the reference COS grid gave absolute discrepancies of approximately
102 \[
103 1.88\times10^{-2},
104 \quad
105 2.6\times10^{-3}\text{--}4.0\times10^{-3},
106 \quad
107 1.39\times10^{-4},
108 \quad
109 2.60\times10^{-8}
110 \]
111 decades as the grid was refined through
112 \[
113 N=4096,\ 8192,\ 16384,\ 32768.
114 \]
115 
116 \begin{figure}[htbp]
117 \centering
118 \includegraphics[width=\linewidth]{figures_production/figure_21_reference_convergence.pdf}
119 \caption{The adaptive result is compared with progressively refined full-spectrum references. The reference discrepancy is not monotone across the intermediate grids. Its final recorded value is approximately $-2.60\times10^{-8}$ decades, illustrating why a reference needs its own convergence check.}
120 \label{fig:reference-convergence}
121 \end{figure}
122 
123 The numerical verification rule is consequently two-sided: the adaptive
124 solver must satisfy its own certificate, and any external or fixed-grid
125 reference used for comparison must demonstrate numerical convergence.
126 
127 
128 

Back to source controls

Back to COS Method