Realization Calculus: twin edition

Download original file

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

1 \chap{Reading a stability certificate}\label{sec:certificate-reading}
2 A numerical residual becomes useful only after it is tied to an operator, a norm, and a conclusion. This section separates uncertainty in a measured residual from uncertainty in the operator itself. It also distinguishes closeness to a reference exact space from closeness to a changed one. All estimates below refer to the actual canonical Hilbert projection used earlier.
3 
4 \subsection{The statement carried by a certificate}
5 Let \(D:E\to R\) be bounded linear from a real Hilbert space into a real normed space. A residual certificate with gain \(C\ge0\) is the universally quantified estimate
6 \[
7  \norm{x-qx}\le C\norm{Dx}\quad\text{for every }x\in E,
8  \qquad q=P_{\ker D}.
9 \]
10 A reported number \(C\) is not a certificate unless this estimate has been justified in the stated model. A successful test at one input is likewise not the universally quantified estimate.
11 
12 Suppose the measured vector is \(y\), with a certified error radius \(\eta\) such that \(\norm{Dx-y}\le\eta\). The triangle inequality converts the measured ball into a bound for the true residual.
13 
14 \begin{proposition}[Measurement and operator uncertainty]\label{KS69}
15 With the reference certificate above,
16 \[
17  \norm{x-qx}\le C(\norm y+\eta)
18  \quad\text{if }\norm{Dx-y}\le\eta.
19 \]
20 More generally, let \(\widetilde D:E\to R\) be the bounded linear operator actually used in the measurement. If
21 \[
22  \norm{D-\widetilde D}\le\varepsilon,
23  \qquad\norm{\widetilde D x-y}\le\eta,
24 \]
25 then
26 \begin{equation}\label{eq:measured-reference}
27  \norm{x-qx}\le C(\norm y+\eta+\varepsilon\norm x).
28 \end{equation}
29 The projection in this conclusion is still the projection for the reference operator \(D\).
30 \end{proposition}
31 \begin{proof}
32 The first assertion follows from \(\norm{Dx}\le\norm y+\eta\). For the second, decompose
33 \[
34  Dx=(D-\widetilde D)x+(\widetilde D x-y)+y.
35 \]
36 Its norm is at most \(\varepsilon\norm x+\eta+\norm y\). Apply the reference residual certificate.
37 \end{proof}
38 \source{KS69}
39 The input-size term has a mathematical purpose. A small error in an operator can produce a large error on a large input. It cannot generally be replaced by a number depending only on the measured residual. Even a measurement of zero may reflect a difference between the measured kernel and the reference kernel.
40 
41 \subsection{A vanishing measured residual can still miss the reference space}
42 For a concrete family, take \(E=\R^2\) with the Euclidean norm and \(R=\R\), and define
43 \[
44  D(a,b)=a,\qquad \widetilde D(a,b)=a+tb.
45 \]
46 The reference projection is \(q(a,b)=(0,b)\), its least residual gain is one, and \(\norm{D-\widetilde D}\le|t|\). On the input \(x=(-tB,B)\), the measured operator returns exactly zero. Its distance to the reference kernel is nevertheless \(|tB|\).
47 
48 Setting \(\eta=0\) and \(y=0\) in \eqref{eq:measured-reference} gives the valid upper bound \(|t|\sqrt{1+t^2}|B|\). Deleting the input-size term would give zero and would be false whenever \(tB\ne0\). The input is exact for the changed model and not exact for the reference model. This is precisely the distinction that the estimate is designed to retain.
49 
50 There is no statistical assertion here. The error radii are mathematical inputs. Estimating them from noisy observations, unknown dynamics, or a fitted model is an additional task that requires its own assumptions and evidence.
51 
52 \subsection{A preserved kernel gives a stronger conclusion}
53 A useful regime occurs when the changed operator annihilates every old exact vector:
54 \[
55  \widetilde D q=0.
56 \]
57 This says that the old kernel is contained in the new kernel. Equality is not assumed. Let \(\norm{D-\widetilde D}\le\varepsilon\) and suppose the strict budget \(C\varepsilon<1\) holds.
58 
59 \begin{theorem}[Kernel preservation and a strict error budget]\label{KS70}
60 Under these hypotheses,
61 \[
62  \ker\widetilde D=\ker D,
63  \qquad
64  \norm{x-qx}\le\frac{C}{1-C\varepsilon}\norm{\widetilde D x}.
65 \]
66 For a measurement with \(\norm{\widetilde D x-y}\le\eta\), the bound becomes
67 \[
68  \norm{x-qx}\le\frac{C}{1-C\varepsilon}(\norm y+\eta).
69 \]
70 Thus the exact space is unchanged and the residual gain degrades by an explicit factor.
71 \end{theorem}
72 \begin{proof}
73 Let \(q=P_{\ker D}\), and write \(u=x-qx\). The stated kernel inclusion makes both \(Dqx\) and \(\widetilde Dqx\) zero. Hence \(Du=Dx\) and \(\widetilde Du=\widetilde Dx\). Applying the reference residual bound to \(u\), whose projection onto \(\ker D\) is zero, gives
74 \[
75  \begin{aligned}
76  \norm u&\le C\norm{Du}
77  \le C\norm{\widetilde Du}+C\norm{(D-\widetilde D)u}\\
78  &\le C\norm{\widetilde Dx}+C\varepsilon\norm u.
79  \end{aligned}
80 \]
81 Subtract the final term. The strict inequality \(C\varepsilon<1\) makes \(1-C\varepsilon\) positive, so division preserves the inequality and gives the claimed residual estimate. This also covers \(C=0\) without division by \(C\).
82 
83 If \(\widetilde Dx=0\), the same estimate forces \(u=0\), hence \(x=qx\in\ker D\). This is the inclusion not initially assumed. Combining it with the supplied inclusion proves \(\ker\widetilde D=\ker D\), and their orthogonal projections coincide in the fixed Hilbert geometry. Finally \(\norm{\widetilde Dx-y}\le\eta\) gives \(\norm{\widetilde Dx}\le\norm y+\eta\). Substitution proves the measured certificate. The kernel-preservation hypothesis is what removed \(qx\) before applying the perturbation estimate. Without it, one obtains a term proportional to \(\norm x\), not the absorbable term proportional to \(\norm u\).
84 \end{proof}
85 \source{KS70}
86 This result does not require the reference operator to be surjective. It is different from the split-surjective perturbation theorem, which allows the kernel to move and constructs an actual transport between the old and new kernels. Both theorems have a strict quantitative radius, but they retain different structural data.
87 
88 For \(D(a,b)=a\) and \(\widetilde D(a,b)=(1-t)a\), with \(0\le t<1\), the kernel is preserved and the exact gain is \(1/(1-t)\). The bound is attained on transverse inputs. At \(t=1\), the changed operator is zero and its kernel becomes all of \(\R^2\). This illustrates why the strict endpoint cannot simply be included.
89 
90 \plate{22_gain_budget}{For the kernel-preserving family \(\widetilde D_t(a,b)=(1-t)a\), the exact residual gain is \(1/(1-t)\). It deteriorates as the strict budget is exhausted. At the excluded endpoint the kernel changes, so the finite-radius estimate does not extend by substituting \(t=1\).}{fig:gain-budget}
91 
92 \subsection{Select the theorem by its conclusion}
93 The following distinctions organize the estimates without turning them into competing formulas.
94 \begin{center}
95 \begin{tabularx}{\linewidth}{@{}p{.29\linewidth}p{.32\linewidth}X@{}}
96 \toprule
97 Available information & Structural hypothesis & Certified conclusion\\
98 \midrule
99 Reference gain and measured error & None on a changed kernel & Distance to the reference kernel, with an input-size term\\
100 Reference gain and small operator change & Old kernel preserved & Same kernel and a degraded gain\\
101 Two residual gains & Same source Hilbert geometry & Distance between the two orthogonal projectors\\
102 A right inverse and a strict radius & Split surjectivity & A new right inverse and an equivalence of moving kernels\\
103 \bottomrule
104 \end{tabularx}
105 \end{center}
106 A claim about the new exact space cannot be obtained by silently replacing the reference projector in the first row. Conversely, a theorem that establishes equality of kernels under preservation need not be weakened to a moving-kernel estimate when the stronger hypothesis is actually available.
107 
108 \subsection{Norm conventions are part of the certificate}
109 On a finite family of real Hilbert fibers, the maximum norm and the Euclidean product norm satisfy
110 \[
111  \norm x_\infty\le\norm x_2\le\sqrt{n}\norm x_\infty,
112 \]
113 where \(n\) is the number of components. The first inequality follows because each squared component is one term in the sum. The second follows by bounding every component by the maximum. These inequalities transfer bounds with explicit dimension factors. They do not assert that the same numerical best constant remains optimal.
114 
115 The graph chapters use the maximum norm on vertex and directed-edge products unless a different geometry is declared. The nearest-point statements use a Hilbert source norm. In the worked graph calculations that follow, selecting one orientation and using a sum of squared residuals defines a different numerical operator model. It has the same edge-exactness equations for an isometric connection, but a different residual norm.
116 
117 A repair certificate should therefore identify its candidate space, residual map, preserved data, norms, gain, and error budgets. The exact equation alone does not specify these quantities. Explicitly retaining them is what makes a numerical conclusion transportable between examples.

Back to source controls

Back to Realization Calculus: twin edition