COS Method

Download original file

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

Included manuscript sections

• worked_packet_table.tex

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Exponential tilting and spectral packets}\label{ch:packets}
2 \chapterlead{The operator stage ends at a spectrum. The probability stage begins with a
3 threshold and an accuracy requirement. Exponential tilting places the query
4 in a better-conditioned region of the transformed law. Centered packets
5 compress repeated transform evaluations on the grid that the query uses,
6 without replacing the distribution by a moment-matched surrogate.}
7 \label{sec:packets}
8 Storage blocks partition a factor before eigendecomposition. Spectral packets
9 group the coefficients after a spectrum is available. They act on different
10 objects. The packet expansion approximates the transform on a specified
11 complex grid and supplies a remainder bound on that grid.
12 
13 The written packet bounds concern exact arithmetic. A directed packet implementation would also have to enclose its centers, moments, and transform evaluations. The positive interval backend in Chapter~\ref{ch:intervals} instead evaluates the supplied spectrum directly. The two routes share the inversion analysis, but their arithmetic guarantees must not be conflated.
14 
15 \section{Quadratic-form transform and saddlepoint tilt}
16 
17 Let
18 \begin{equation}
19 Q=\sum_{j=1}^{r}\lambda_j Z_j^2,
20 \qquad \lambda_j>0,\quad r\ge1.
21 \label{eq:Q}
22 \end{equation}
23 The variables $Z_j$ are independent standard normal variables.
24 The moment generating function exists for
25 \[
26 \Re s < \frac{1}{2\lambda_{\max}},
27 \qquad
28 \lambda_{\max}=\max_j\lambda_j,
29 \]
30 and its cumulant generating function is
31 \begin{equation}
32 \kappa(s)=\log \E e^{sQ}
33 =-\frac12\sum_{j=1}^{r}\log(1-2s\lambda_j).
34 \label{eq:cgf}
35 \end{equation}
36 For complex $s$, $\kappa$ denotes the analytic logarithm normalized by
37 $\kappa(0)=0$. Each factor $1-2s\lambda_j$ has positive real part on this
38 domain, so its logarithm in the sum is principal. The sum need not equal the
39 principal logarithm of the product, whose argument can wrap by $2\pi$.
40 For real $\theta<1/(2\lambda_{\max})$,
41 \begin{equation}
42 \kappa^{(m)}(\theta)
43 =2^{m-1}(m-1)!\sum_{j=1}^{r}
44 \frac{\lambda_j^m}{(1-2\theta\lambda_j)^m},
45 \qquad m\ge1.
46 \label{eq:derivatives}
47 \end{equation}
48 At $\theta=0$, this recovers the standard cumulant identity
49 \[
50 \operatorname{cum}_m(Q)=2^{m-1}(m-1)!\sum_j\lambda_j^m.
51 \]
52 
53 \begin{theorem}[Unique upper-tail saddlepoint]
54 \label{thm:saddle}
55 If $q>\E Q=\sum_j\lambda_j$, there exists a unique
56 \[
57 \theta_*=\theta(q)\in\left(0,\frac{1}{2\lambda_{\max}}\right)
58 \]
59 satisfying
60 \begin{equation}
61 \kappa'(\theta_*)=q.
62 \label{eq:saddle}
63 \end{equation}
64 \end{theorem}
65 
66 \begin{proof}
67 By \eqref{eq:derivatives},
68 \[
69 \kappa'(\theta)=\sum_j\frac{\lambda_j}{1-2\theta\lambda_j}
70 \]
71 is continuous and strictly increasing on the stated interval. It equals $\E Q$ at $\theta=0$ and diverges as $\theta\uparrow1/(2\lambda_{\max})$. The intermediate value theorem and strict monotonicity give existence and uniqueness.
72 \end{proof}
73 
74 Define the exponentially tilted law by
75 \begin{equation}
76 f_{\theta}(x)=e^{\theta x-\kappa(\theta)}f(x).
77 \label{eq:tilt-density}
78 \end{equation}
79 Its characteristic function is
80 \begin{equation}
81 \phi_{\theta}(t)
82 =\exp\{\kappa(\theta+\ii t)-\kappa(\theta)\},
83 \label{eq:tilt-cf}
84 \end{equation}
85 and $\E_{\theta}Q=\kappa'(\theta)$. Therefore the choice \eqref{eq:saddle} moves the query $q$ to the mean of the tilted law.
86 
87 For any $\theta>0$ in the transform domain,
88 \begin{equation}
89 \Pp(Q\ge q)
90 =e^{\kappa(\theta)-\theta q}
91 \E_{\theta}\!\left[e^{-\theta(Q-q)}\mathbf 1_{\{Q\ge q\}}\right].
92 \label{eq:tilt-tail}
93 \end{equation}
94 This classical exponential-tilting identity lets K-COS evaluate the upper tail
95 without subtracting a cumulative distribution function (CDF) value close to one.
96 
97 \section{Centered spectral packets}
98 
99 Let a nonempty packet $P\subset\{1,\ldots,r\}$ contain $n_P\ge1$ eigenvalues. Define its center
100 \[
101 \mu_P=\frac{1}{n_P}\sum_{j\in P}\lambda_j,
102 \qquad
103 \delta_j=\lambda_j-\mu_P,
104 \]
105 and centered moments
106 \begin{equation}
107 M_{P,m}=\sum_{j\in P}\delta_j^m,
108 \qquad m\ge0.
109 \label{eq:centeredmoments}
110 \end{equation}
111 Thus $M_{P,0}=n_P$ and $M_{P,1}=0$.
112 
113 \begin{theorem}[Centered packet expansion]
114 \label{thm:packet}
115 Fix $s\in\C$ with $\Re s<1/(2\lambda_{\max})$, use the principal logarithm, and define
116 \begin{equation}
117 \alpha_P(s)=\frac{2s}{1-2s\mu_P},
118 \qquad
119 \rho_P(s)=|\alpha_P(s)|\max_{j\in P}|\delta_j|.
120 \label{eq:alpha-rho}
121 \end{equation}
122 For a nonnegative integer expansion order $p$, if $\rho_P(s)<1$, then the packet contribution to \eqref{eq:cgf} is
123 \begin{align}
124 \kappa_P(s)
125 &=-\frac{n_P}{2}\log(1-2s\mu_P)
126 +\frac12\sum_{m=1}^{p}
127 \frac{\alpha_P(s)^m}{m}M_{P,m}
128 +R_{P,p}(s),
129 \label{eq:packet-expansion}
130 \end{align}
131 where
132 \begin{equation}
133 |R_{P,p}(s)|
134 \le
135 \frac{n_P}{2}
136 \frac{\rho_P(s)^{p+1}}{(p+1)(1-\rho_P(s))}.
137 \label{eq:packet-remainder}
138 \end{equation}
139 \end{theorem}
140 
141 \begin{proof}
142 For $j\in P$,
143 \[
144 1-2s\lambda_j
145 =(1-2s\mu_P)(1-\alpha_P(s)\delta_j).
146 \]
147 The transform-domain condition gives positive real part for each
148 \(1-2s\lambda_j\) and for \(1-2s\mu_P\).  The disk condition gives
149 positive real part for \(1-\alpha_P\delta_j\).  The two factor arguments
150 therefore sum inside \((-\pi,\pi)\), so their principal logarithms add
151 without a branch ambiguity.  Hence
152 \[
153 -\frac12\log(1-2s\lambda_j)
154 =-\frac12\log(1-2s\mu_P)
155 -\frac12\log(1-\alpha_P\delta_j).
156 \]
157 When $|\alpha_P\delta_j|<1$,
158 \[
159 -\log(1-z)=\sum_{m\ge1}\frac{z^m}{m}.
160 \]
161 Summing over $j\in P$ gives \eqref{eq:packet-expansion}. The remainder satisfies
162 \[
163 \left|\sum_{m\ge p+1}\frac{z^m}{m}\right|
164 \le
165 \sum_{m\ge p+1}\frac{|z|^m}{p+1}
166 =\frac{|z|^{p+1}}{(p+1)(1-|z|)}.
167 \]
168 Using $|z|\le\rho_P(s)$ and summing $n_P$ terms yields \eqref{eq:packet-remainder}.
169 \end{proof}
170 
171 \begin{remark}[What is compressed]\label{claim:final-26-3}
172 A packet of $n_P$ eigenvalues is replaced by its center and $p$ centered moments. Large spectral spikes may be retained exactly. If the representation contains $s$ exact eigenvalues and $R$ packets of order $p$, evaluation of the CGF on $N$ frequencies costs $O(N(s+R(p+1)))$ arithmetic operations after compilation, instead of $O(Nr)$ direct eigenvalue-transform evaluations.
173 \end{remark}
174 
175 \begin{remark}[Query dependence]\label{claim:final-26-4}
176 The relevant packet condition is not merely geometric closeness of eigenvalues. It is the complex-grid quantity $\rho_P(\theta_*+\ii u_k)$. Thus a partition suitable for one tail query or one COS grid need not be suitable for another.
177 \end{remark}
178 
179 
180 
181 \section{The running example under an exponential tilt}\label{sec:worked-tilt}
182 For spectrum $(1,1,2,2)$, the cumulant generator is
183 $\kappa(s)=-\log(1-2s)-\log(1-4s)$ on $\Re s<1/4$.
184 At $q=40$, the saddlepoint equation reduces to
185 $160\theta^2-112\theta+17=0$, with
186 \[
187 \frac{2}{1-2\theta}+\frac{4}{1-4\theta}=40,
188 \qquad
189 \theta_* = \frac{14-\sqrt{26}}{40}\approx0.2225245122.
190 \]
191 The other root lies outside the transform domain. The tilted mean is $40$,
192 while the likelihood-ratio identity restores the original tail probability.
193 
194 \begin{figure}[!htbp]
195 \centering\includegraphics[width=\linewidth]{figures_production/worked_tilt.pdf}
196 \caption{The running example before and after exponential tilting. The original mean is $6$, while the reweighted mean is the query $q=40$. Shading identifies the tail under the tilted law. Both curves are point evaluations of explicit densities, not numerical enclosures.}
197 \label{fig:worked-tilt}
198 \end{figure}
199 
200 The two copies of $1$ form one exact packet, and the two copies of $2$ form another. All centered deviations vanish, so the packet remainder is zero on every admissible grid. The numerical enclosure still has support, Fourier-mode, and arithmetic errors.
201 
202 \clearpage
203 \section{A packet with a nonzero remainder}\label{sec:worked-packet}
204 To see the approximation itself, take a separate declared packet
205 \[
206 \{1.96,1.98,2.02,2.04\},\qquad \mu=2,
207 \]
208 and evaluate its contribution at $s=0.1+0.4\,\mathrm i$. The deviations are $-0.04,-0.02,0.02,0.04$. In particular,
209 \[
210 M_1=M_3=0,\quad M_2=0.004,\quad M_4=0.00000544.
211 \]
212 The factor $\alpha=2s/(1-4s)$ gives $\rho=0.04|\alpha|<1$, so Theorem~\ref{thm:packet} applies. Retaining successive even moment orders gives the values below. Both columns are rounded point evaluations. The theorem, not these rounded comparisons, is the reason the remainder is bounded.
213 
214 \begin{center}\small\input{worked_packet_table.tex}\end{center}
215 
216 \begin{figure}[!htbp]
217 \centering\includegraphics[width=\linewidth]{figures_production/worked_packet_error.pdf}
218 \caption{Pointwise transform error and its geometric remainder for the declared packet $(1.96,1.98,2.02,2.04)$ at $s=0.1+0.4i$. Increasing the retained moment order contracts both quantities. The shaded gap separates the observed discrepancy from the analytic bound.}
219 \label{fig:spectral-packets}
220 \end{figure}
221 
222 

Back to source controls

Back to COS Method