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{COS inversion and the analytic error budget}\label{ch:inversion}
2 \chapterlead{The tail functional has three distinct approximation errors: packet
3 compression on a finite grid, finite support with cosine folding, and omitted
4 Fourier modes. Each receives its own bound. Their sum yields an analytic
5 certificate, while a finite-refinement theorem shows that the mathematical
6 error can be made arbitrarily small for a fixed positive spectrum and an
7 upper-tail query.}
8 \section{Tilted COS tail functional}
9 
10 Because $Q\ge0$, K-COS uses the interval $[0,b]$.  Throughout the
11 following functional and packet-error results, assume $b>q\ge0$, $b>0$,
12 $0<\theta<1/(2\lambda_{\max})$, and an integer mode count $N\ge1$.  Let
13 \[
14 u_k=\frac{k\pi}{b},
15 \qquad k=0,1,\ldots,
16 \]
17 and define the exponentially weighted cosine integrals
18 \begin{equation}
19 J_k(q,b,\theta)
20 =\int_q^b e^{-\theta(x-q)}\cos(u_kx)\,dx.
21 \label{eq:J-def}
22 \end{equation}
23 They admit the closed form
24 \begin{equation}
25 J_k
26 =\Re\left[
27  e^{\ii u_k q}
28  \frac{1-e^{(-\theta+\ii u_k)(b-q)}}{\theta-\ii u_k}
29 \right].
30 \label{eq:J-formula}
31 \end{equation}
32 The prime on a cosine sum denotes half weight for $k=0$.
33 
34 If the exact tilted characteristic function is used, the $N$-mode finite-window expression is
35 \begin{equation}
36 T_{N,b}
37 =\frac{2}{b}\sum_{k=0}^{N-1}{}'
38 J_k\,
39 \Re\left[e^{\kappa(\theta+\ii u_k)-\theta q}\right].
40 \label{eq:tail-cos}
41 \end{equation}
42 The cancellation of $\kappa(\theta)$ in \eqref{eq:tail-cos} is useful numerically: the likelihood-ratio prefactor from \eqref{eq:tilt-tail} and the normalization in \eqref{eq:tilt-cf} do not need to be formed separately inside each mode.
43 
44 \section{Propagation of packet error}
45 
46 Let $\widehat\kappa(s_k)$ be the packet approximation at
47 \[
48 s_k=\theta+\ii u_k,
49 \]
50 and suppose
51 \begin{equation}
52 |\widehat\kappa(s_k)-\kappa(s_k)|\le B_k.
53 \label{eq:Bk}
54 \end{equation}
55 For disjoint packets, $B_k$ can be chosen as the sum of the packet bounds \eqref{eq:packet-remainder}.
56 
57 \begin{theorem}[Finite-grid packet-to-tail bound]
58 \label{thm:packet-tail}
59 Let $\widehat T_{N,b}$ be obtained from \eqref{eq:tail-cos} by replacing $\kappa(s_k)$ by $\widehat\kappa(s_k)$. Then
60 \begin{equation}
61 |\widehat T_{N,b}-T_{N,b}|
62 \le \eps_{\mathrm{pkt}},
63 \label{eq:packet-tail-bound}
64 \end{equation}
65 where
66 \begin{equation}
67 \eps_{\mathrm{pkt}}
68 =
69 \frac{2}{b}
70  e^{\kappa(\theta)-\theta q}
71 \sum_{k=0}^{N-1}{}'
72 |J_k|\bigl(e^{B_k}-1\bigr).
73 \label{eq:eps-pkt}
74 \end{equation}
75 \end{theorem}
76 
77 \begin{proof}
78 Write $\Delta_k=\widehat\kappa(s_k)-\kappa(s_k)$. Then
79 \[
80 |e^{\widehat\kappa(s_k)-\theta q}-e^{\kappa(s_k)-\theta q}|
81 \le
82 |e^{\kappa(s_k)-\theta q}|\,(e^{|\Delta_k|}-1).
83 \]
84 Moreover
85 \[
86 \Re\kappa(\theta+\ii u_k)-\kappa(\theta)
87 =\log|\phi_{\theta}(u_k)|\le0,
88 \]
89 so
90 \[
91 |e^{\kappa(s_k)-\theta q}|
92 \le e^{\kappa(\theta)-\theta q}.
93 \]
94 Substitute this into the finite cosine sum and apply the triangle inequality.
95 \end{proof}
96 
97 \section{Positive support, truncation, and cosine periodization}
98 
99 Using full characteristic-function coefficients on $[0,b]$ reconstructs the even $2b$-periodization of the tilted density rather than the strictly truncated density. For a nonnegative density supported on $[0,\infty)$, the total mass folded back into $[0,b]$ equals the tilted mass above $b$. This gives a clean error control for the positive quadratic-form setting.
100 
101 
102 \begin{lemma}[Integrated cosine identity by folding]
103 \label{lem:folding}
104 Let \(\nu_\theta\) be the tilted probability measure and let
105 \(F_b:[0,\infty)\to[0,b]\) fold each interval of length \(2b\) by
106 reflection.  Then
107 \(\cos(k\pi F_b(x)/b)=\cos(k\pi x/b)\).
108 For \(h(x)=e^{-\theta(x-q)}\mathbf1_{[q,b]}(x)\),
109 \[
110 \int h\,d(F_{b\#}\nu_\theta)
111 =\frac2b\sum_{k=0}^{\infty}{}'
112 J_k\,\Re\phi_\theta(k\pi/b).
113 \]
114 The series is absolutely convergent for every positive rank \(r\ge1\).
115 \end{lemma}
116 \begin{proof}
117 A positive weighted chi-square sum has an absolutely continuous law. Its
118 folded measure therefore has no atom at the jump of \(h\).  The even periodic
119 extension of \(h\) has bounded Fej\'er means, which converge at every continuity
120 point.  Dominated convergence identifies the integral of those means with
121 \(\int h\,d(F_{b\#}\nu_\theta)\).  Their cosine coefficients are the Ces\`aro
122 weighted coefficients \(2J_k/b\), and folding preserves the cosine moments
123 \(\Re\phi_\theta(k\pi/b)\).  Finally
124 \(J_k=O(k^{-1})\) and
125 \(|\phi_\theta(k\pi/b)|=O(k^{-r/2})\), as follows directly from the product
126 formula below.  Thus the coefficient products are
127 \(O(k^{-1-r/2})\). Their absolute sum converges.  The Ces\`aro sums and ordinary
128 sum have the same limit, proving the displayed identity.  This argument
129 justifies the weighted functional without requiring pointwise convergence of
130 the reconstructed density at every boundary.
131 \end{proof}
132 
133 \begin{proposition}[Support and periodization bound]
134 \label{prop:support}
135 Let the finite positive spectrum have rank \(r\ge1\), and let
136 \(b>q\ge0\), \(b>0\), and \(0<\theta<1/(2\lambda_{\max})\).  Let
137 \[
138 \tau_{\theta}(b)=\Pp_{\theta}(Q>b).
139 \]
140 Then the combined error from (i) replacing the tilted density on $[0,b]$ by its full-coefficient cosine periodization and (ii) omitting the original integral over $(b,\infty)$ is bounded by
141 \begin{equation}
142 \eps_{\mathrm{sup}}
143 \le
144 e^{\kappa(\theta)-\theta q}\,
145 \tau_{\theta}(b)
146 \left(1+e^{-\theta(b-q)}\right).
147 \label{eq:eps-support}
148 \end{equation}
149 \end{proposition}
150 
151 \begin{proof}
152 By Lemma~\ref{lem:folding}, the infinite cosine functional integrates
153 the folded measure.  The part of that measure originating from \((b,\infty)\)
154 is nonnegative and has total mass $\tau_{\theta}(b)$. On $[q,b]$, the weight $e^{-\theta(x-q)}$ is at most one, so its contribution to the weighted functional is at most $\tau_{\theta}(b)$. For the omitted original tail, $x\ge b$ implies
155 \[
156 e^{-\theta(x-q)}\le e^{-\theta(b-q)},
157 \]
158 so that term is at most $e^{-\theta(b-q)}\tau_{\theta}(b)$. Multiplication by the likelihood-ratio prefactor in \eqref{eq:tilt-tail} gives \eqref{eq:eps-support}.
159 \end{proof}
160 
161 The tilted tail probability itself can be bounded by Chernoff's inequality. For $\eta>\theta$ inside the transform domain,
162 \begin{equation}
163 \tau_{\theta}(b)
164 \le
165 \exp\left\{
166 \kappa(\eta)-\kappa(\theta)-(\eta-\theta)b
167 \right\}.
168 \label{eq:tilted-chernoff}
169 \end{equation}
170 When $b>\kappa'(\theta)$, the minimizing $\eta$ is the unique solution of
171 \begin{equation}
172 \kappa'(\eta)=b.
173 \label{eq:eta}
174 \end{equation}
175 For the saddlepoint tilt, $\kappa'(\theta_*)=q<b$, so such an $\eta$ exists.
176 
177 \section{A specialized omitted-mode bound}
178 
179 The tilted characteristic function has an especially transparent modulus.
180 
181 \begin{lemma}[Tilted characteristic-function modulus]
182 \label{lem:modulus}
183 Define
184 \begin{equation}
185 a_j=\frac{2\lambda_j}{1-2\theta\lambda_j}>0.
186 \label{eq:aj}
187 \end{equation}
188 Then
189 \begin{equation}
190 |\phi_{\theta}(t)|
191 =\prod_{j=1}^{r}\left(1+(a_jt)^2\right)^{-1/4}.
192 \label{eq:phi-modulus}
193 \end{equation}
194 For $t>0$, define the logarithmic decay rate
195 \begin{equation}
196 \beta(t)
197 =-\frac{d\log|\phi_{\theta}(t)|}{d\log t}
198 =\frac12\sum_{j=1}^{r}
199 \frac{(a_jt)^2}{1+(a_jt)^2}.
200 \label{eq:beta}
201 \end{equation}
202 Set $\beta(0)=0$ by continuous extension. Then $\beta(t)$ is nondecreasing for $t\ge0$.
203 \end{lemma}
204 
205 \begin{proof}
206 Taking the modulus of each factor in \eqref{eq:tilt-cf} gives \eqref{eq:phi-modulus}. Differentiating its logarithm gives \eqref{eq:beta}. Each summand $x/(1+x)$ with $x=(a_jt)^2$ is nondecreasing in $t$.
207 \end{proof}
208 
209 \begin{corollary}[Power envelope from one frequency]
210 \label{cor:power-envelope}
211 For $t\ge t_0>0$,
212 \begin{equation}
213 |\phi_{\theta}(t)|
214 \le
215 |\phi_{\theta}(t_0)|
216 \left(\frac{t}{t_0}\right)^{-\beta(t_0)}.
217 \label{eq:power-envelope}
218 \end{equation}
219 \end{corollary}
220 
221 \begin{proof}
222 By Lemma \ref{lem:modulus},
223 \[
224 \frac{d\log|\phi_{\theta}(t)|}{d\log t}=-\beta(t)\le-\beta(t_0)
225 \]
226 for $t\ge t_0$. Integrating from $t_0$ to $t$ proves the claim.
227 \end{proof}
228 
229 For $k\ge1$, the exact integral \eqref{eq:J-formula} implies
230 \begin{equation}
231 |J_k|
232 \le \frac{2}{u_k}.
233 \label{eq:J-bound}
234 \end{equation}
235 
236 \begin{theorem}[Omitted COS-mode certificate]
237 \label{thm:cos-tail}
238 Let $N\ge1$ and $b>q\ge0$. Set $u_N=N\pi/b$ and
239 $\beta_N=\beta(u_N)$. If $\beta_N>0$, then the contribution of all exact tilted-COS modes $k\ge N$ to the weighted tail functional is bounded by
240 \begin{equation}
241 \eps_{\mathrm{COS}}
242 \le
243  e^{\kappa(\theta)-\theta q}
244 \frac{4|\phi_{\theta}(u_N)|}{\pi}
245 \left(\frac1N+\frac1{\beta_N}\right).
246 \label{eq:eps-cos}
247 \end{equation}
248 \end{theorem}
249 
250 \begin{proof}
251 Using the cosine coefficient magnitude $2|\phi_{\theta}(u_k)|/b$ and \eqref{eq:J-bound}, the omitted series is at most
252 \[
253 e^{\kappa(\theta)-\theta q}
254 \frac{4}{\pi}
255 \sum_{k=N}^{\infty}\frac{|\phi_{\theta}(u_k)|}{k}.
256 \]
257 By Corollary \ref{cor:power-envelope},
258 \[
259 |\phi_{\theta}(u_k)|
260 \le
261 |\phi_{\theta}(u_N)|\left(\frac{k}{N}\right)^{-\beta_N}.
262 \]
263 Therefore
264 \[
265 \sum_{k=N}^{\infty}\frac{|\phi_{\theta}(u_k)|}{k}
266 \le
267 |\phi_{\theta}(u_N)|N^{\beta_N}
268 \sum_{k=N}^{\infty}k^{-\beta_N-1}.
269 \]
270 Finally,
271 \[
272 \sum_{k=N}^{\infty}k^{-\beta_N-1}
273 \le N^{-\beta_N-1}+\int_N^{\infty}x^{-\beta_N-1}\,dx
274 =N^{-\beta_N-1}+\frac{N^{-\beta_N}}{\beta_N},
275 \]
276 which yields \eqref{eq:eps-cos}.
277 \end{proof}
278 
279 \section{Combined analytic certificate}
280 
281 \begin{theorem}[K-COS analytic error certificate]
282 \label{thm:combined}
283 Let $p=\Pp(Q\ge q)$, and let $\widehat p$ be the finite K-COS approximation formed with
284 \begin{enumerate}[label=(\roman*)]
285 \item an upper interval endpoint $b>q$,
286 \item an integer $N\ge1$ of cosine modes,
287 \item a packet approximation satisfying \eqref{eq:Bk} on the finite grid.
288 \end{enumerate}
289 Under the positive-spectrum and parameter hypotheses of Proposition \ref{prop:support},
290 \begin{equation}
291 |p-\widehat p|
292 \le
293 \eps_{\mathrm{an}}
294 :=\eps_{\mathrm{pkt}}+\eps_{\mathrm{sup}}+\eps_{\mathrm{COS}}.
295 \label{eq:combined}
296 \end{equation}
297 If $\eps_{\mathrm{an}}<|\widehat p|$, then
298 \begin{equation}
299 \frac{|p-\widehat p|}{|p|}
300 \le
301 \frac{\eps_{\mathrm{an}}}
302 {|\widehat p|-\eps_{\mathrm{an}}}.
303 \label{eq:relative-certificate}
304 \end{equation}
305 \end{theorem}
306 
307 \begin{proof}
308 Decompose the error into packet error on the retained grid, support and periodization error, and the exact omitted cosine series. The first is bounded by Theorem \ref{thm:packet-tail}, the second by Proposition \ref{prop:support}, and the third by Theorem \ref{thm:cos-tail}. This proves \eqref{eq:combined}. Also
309 \[
310 |p|\ge |\widehat p|-|p-\widehat p|
311 \ge |\widehat p|-\eps_{\mathrm{an}},
312 \]
313 which gives \eqref{eq:relative-certificate}.
314 \end{proof}
315 
316 \begin{remark}[Certificate boundary]\label{claim:final-26-12}
317 Theorem \ref{thm:combined} is an \emph{analytic approximation certificate}. It does not enclose IEEE floating-point rounding in complex logarithms, exponentials, root finding, or summation. A machine-level certificate would require directed rounding, interval arithmetic, or a comparable validated-numerics layer.
318 \end{remark}
319 
320 \section{Finite refinability}
321 
322 The combined error terms correspond to three distinct obstructions. Packet error is reduced by splitting spectral packets or raising packet order. Support error is reduced by increasing $b$. Cosine-series error is reduced by increasing $N$.
323 
324 \begin{proposition}[Existence of a finite analytic refinement]
325 \label{prop:finite-refinement}
326 Fix a finite positive spectrum $\{\lambda_j\}_{j=1}^{r}$, an upper-tail query $q>\E Q$, and $\eps>0$. There exist a finite interval endpoint $b>q$, a finite number of cosine modes $N$, and a finite packet partition (allowing singleton packets) for which the analytic error bound in \eqref{eq:combined} is below $\eps$.
327 \end{proposition}
328 
329 \begin{proof}
330 First choose $b$ sufficiently large that \eqref{eq:eps-support} is below $\eps/3$. This is possible because the tilted law has a moment generating function in a nontrivial right neighborhood of zero and hence its Chernoff bound tends to zero exponentially as $b\to\infty$. Hold this $b$ fixed. By \eqref{eq:phi-modulus}, $|\phi_{\theta}(t)|\to0$ polynomially as $t\to\infty$, while $\beta(t)\to r/2>0$. Therefore \eqref{eq:eps-cos} tends to zero as $N\to\infty$, so a finite $N$ makes it below $\eps/3$. Finally, split every packet to singletons if necessary. A singleton has $\delta_j=0$, so its packet remainder is exactly zero. Hence a finite partition makes $\eps_{\mathrm{pkt}}<\eps/3$. Summing the three terms proves the claim.
331 \end{proof}
332 
333 \begin{remark}\label{claim:final-26-14}
334 Proposition \ref{prop:finite-refinement} proves existence of a finite representation meeting any analytic tolerance. It proves neither termination of an arbitrary greedy schedule nor optimality of its resource use. A particular capped implementation can fail to certify even though a finite analytic refinement exists. The packet planner refines the largest currently certified obstruction and is evaluated in Chapter~\ref{ch:evidence}.
335 \end{remark}
336 
337 

Back to source controls

Back to COS Method