Komorebi Space

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 \chap{The attainable residual at a fixed correction budget}\label{sec:budget-frontier}
2 The unrestricted floor $\dist(r,\ran T)$ forgets how large a correction must be. To retain that information, fix a nonnegative budget $M$ and define
3 \[
4  \beta_{T,r}(M)=\inf_{\norm a\le M}\norm{r-Ta}.
5 \]
6 The norm is the actual correction norm in $H=\ker p$. It is not the norm of arbitrary coordinates used to represent that kernel. The function $\beta$ describes the smallest residual compatible with a declared amount of allowed change.
7 
8 \subsection{At every finite budget the residual minimum exists}
9 \begin{theorem}[Attainment and shape of the budget profile]\label{WR03}
10 For a bounded linear map between real Hilbert spaces, the infimum defining $\beta(M)$ is attained for every $M\ge0$. The profile is nonincreasing and convex. For $0\le M_1\le M_2$,
11 \[
12  0\le\beta(M_1)-\beta(M_2)\le\norm T(M_2-M_1).
13 \]
14 Writing $C=\overline{\ran T}$, $b=P_Cr$, and $q=\norm{r-b}$, one has
15 \[
16  \lim_{M\to\infty}\beta(M)=q.
17 \]
18 The equality $\beta(M)=q$ at a finite budget is equivalent to the existence of $a$ with $Ta=b$ and $\norm a\le M$. In particular,
19 \[
20  \beta(M)=0\quad\Longleftrightarrow\quad
21  \exists a\in H:\ Ta=r,\ \norm a\le M.
22 \]
23 \end{theorem}
24 \begin{proof}
25 The feasible ball is nonempty because it contains zero, and the infimum lies between zero and $\norm r$. Choose $a_n$ in that ball with $\norm{r-Ta_n}\to\beta(M)$. A weakly convergent subsequence has limit $a$ with $\norm a\le M$. Bounded linearity makes $r-Ta_{n_k}$ converge weakly to $r-Ta$. Applying weak lower semicontinuity in the target gives
26 \[
27  \norm{r-Ta}\le\liminf_k\norm{r-Ta_{n_k}}=\beta(M).
28 \]
29 The reverse inequality holds by the definition of the infimum, so $a$ attains it. When $M=0$ the only feasible correction is zero, and the same conclusion reads $\beta(0)=\norm r$.
30 
31 For convexity, take minimizers $a_1,a_2$ at budgets $M_1,M_2$ and $t\in[0,1]$. The candidate $a_t=ta_1+(1-t)a_2$ satisfies
32 \[
33  \norm{a_t}\le tM_1+(1-t)M_2,
34 \]
35 and its residual is $t(r-Ta_1)+(1-t)(r-Ta_2)$. The triangle inequality therefore gives
36 \[
37  \beta(tM_1+(1-t)M_2)\le t\beta(M_1)+(1-t)\beta(M_2).
38 \]
39 Monotonicity follows from inclusion of balls. If $0\le M_1\le M_2$ and $M_2>0$, choose a minimizer $a_2$ at $M_2$ and put $a_1'=(M_1/M_2)a_2$. Then $\norm{a_1'}\le M_1$ and $\norm{a_2-a_1'}\le M_2-M_1$, so
40 \[
41  \beta(M_1)\le\norm{r-Ta_1'}
42  \le\beta(M_2)+\norm T(M_2-M_1).
43 \]
44 Together with monotonicity this proves the Lipschitz estimate. The omitted case $M_2=0$ has $M_1=0$ and is equality.
45 
46 Since $r-b$ is orthogonal to $C$ and $b-Ta\in C$, every correction satisfies
47 \begin{equation}\label{eq:range-decomposition}
48  \norm{r-Ta}^2=q^2+\norm{b-Ta}^2.
49 \end{equation}
50 Thus $\beta(M)\ge q$. Given $\epsilon>0$, range density in $C$ supplies one correction $a$ with $\norm{b-Ta}<\epsilon$. For every $M\ge\norm a$ it follows that
51 \[
52  q\le\beta(M)\le\sqrt{q^2+\epsilon^2}.
53 \]
54 First letting the budget increase and then letting $\epsilon\downarrow0$ proves the limit.
55 
56 Finally, if $\beta(M)=q$, choose an attaining correction in that ball. The orthogonal identity forces $\norm{b-Ta}^2=0$, hence $Ta=b$. Conversely such a correction attains residual $q$. Setting $q=0$ proves the exact-feasibility criterion. Attainment at fixed budget is essential to the forward implication: a zero unrestricted infimum would not itself supply a preimage.
57 \end{proof}
58 \written{WR03}
59 
60 Although $\ran T$ may not be closed, the image $T(\{a:\norm a\le M\})$ of each closed budget ball is closed and convex. To see closedness, take a convergent sequence in that image, lift it to the bounded ball, and apply the weak limit argument. The full range is the increasing union of these closed images. Passing to an unlimited budget can therefore lose closedness even though every fixed-budget optimization is well posed.
61 
62 The nearest reachable image $y_M=P_{T(\{a:\norm a\le M\})}r$ is unique, so the best residual vector $r-y_M$ is unique as well. Corrections mapping to $y_M$ can differ by vectors in $\ker T$. Among those corrections there is a unique least norm correction. These two uniqueness statements should not be confused with injectivity of $T$.
63 
64 \subsection{A dual witness can rule out every correction in the budget}
65 \begin{theorem}[A sharp budget certificate]\label{WR04}
66 For every $M\ge0$,
67 \begin{equation}\label{eq:budget-dual}
68  \beta_{T,r}(M)=
69  \max_{\norm z\le1}\bigl(\langle r,z\rangle-M\norm{T^*z}\bigr).
70 \end{equation}
71 Thus any single $z$ with $\norm z\le1$ and
72 \[
73  \langle r,z\rangle-M\norm{T^*z}>\varepsilon
74 \]
75 certifies that no correction of norm at most $M$ has residual at most $\varepsilon$.
76 \end{theorem}
77 \begin{proof}
78 For every $\norm a\le M$ and $\norm z\le1$, the adjoint identity and Cauchy--Schwarz give
79 \[
80 \begin{aligned}
81  \langle r,z\rangle-M\norm{T^*z}
82  &=\langle r-Ta,z\rangle+\langle a,T^*z\rangle-M\norm{T^*z}\\
83  &\le\langle r-Ta,z\rangle
84  \le\norm{r-Ta}.
85 \end{aligned}
86 \]
87 Taking the infimum over corrections proves that every proposed dual value is at most $\beta(M)$. This part alone already proves the impossibility certificate.
88 
89 To prove sharpness, let $a_M$ be an attaining correction from Theorem~\ref{WR03} and put $v=r-Ta_M$. If $v=0$, then $\beta(M)=0$ and $z=0$ attains the dual bound. Assume henceforth $v\ne0$ and set $z=v/\norm v$.
90 
91 Fix any feasible $a$ and put $h=a-a_M$. The segment $a_M+th$ is feasible for $0\le t\le1$. Minimality gives, for $t>0$,
92 \[
93  0\le\norm{v-tTh}^2-\norm v^2
94    =-2t\langle v,Th\rangle+t^2\norm{Th}^2.
95 \]
96 Divide by $t$ and let $t\downarrow0$. It follows that $\langle v,T(a-a_M)\rangle\le0$, hence
97 \[
98  \langle T^*z,a\rangle\le\langle T^*z,a_M\rangle
99  \quad(\norm a\le M).
100 \]
101 The support value of a Hilbert ball can be computed directly. If $T^*z\ne0$ and $M>0$, it is attained at $a=M T^*z/\norm{T^*z}$ and equals $M\norm{T^*z}$. If either factor is zero, every feasible pairing is zero and the same formula holds. Thus
102 \[
103  \langle T^*z,a_M\rangle=M\norm{T^*z}.
104 \]
105 Substituting this equality gives
106 \[
107  \langle r,z\rangle-M\norm{T^*z}
108  =\langle r-Ta_M,z\rangle=\norm v=\beta(M).
109 \]
110 We have constructed an attaining witness and thereby justified the word ``maximum.'' The proof uses one-sided variations in a convex ball, not an unproved exchange of an infimum and a supremum.
111 \end{proof}
112 \written{WR04}
113 
114 In finite dimensions this is a checkable inequality, not merely an optimization prescription. A program may propose the correction or the witness. The displayed inequality can be verified independently of the proposal procedure. In a protected ambient calculation, use the restricted adjoint, not $d^*$ without projection onto $\ker p$.
115 
116 \subsection{A two-dimensional calculation of the supporting witness}
117 Take
118 \[
119  T=\begin{pmatrix}1&0\\0&1/2\end{pmatrix},\qquad r=(1,1),\qquad
120  a=(1/2,2/5),\qquad v=r-Ta=(1/2,4/5).
121 \]
122 Then $T^*v=a$. At the budget $M=\norm a=\sqrt{41}/10$, the normalized vector $z=v/\norm v$ gives
123 \[
124  \langle r,v\rangle-\norm a\norm{T^*v}
125  =\frac{13}{10}-\frac{41}{100}=\frac{89}{100}=\norm v^2.
126 \]
127 Consequently $a$ is a globally optimal budgeted correction and $\beta(M)=\sqrt{89}/10$. It is not necessary to compare it with a dense numerical grid of competing vectors. The supporting witness proves optimality over the entire ball.
128 
129 \fixedplate{32_budget_certificate}{The image of a Euclidean correction ball is an ellipse. The nearest reachable point has a residual normal to a supporting line. That same residual, normalized, is the dual witness in the exact budget formula. The plotted point and budget are the rational example in the text.}{fig:budget-certificate}
130 
131 \subsection{How measurement and model uncertainty affect the budget}
132 \begin{theorem}[A robust budget profile]\label{WR05}
133 Suppose the bounded linear map $\widetilde T:H\to Y$ and the datum $\widetilde r\in Y$ satisfy
134 \[
135  \norm{T-\widetilde T}\le\eta,\qquad
136  \norm{r-\widetilde r}\le\delta,\qquad\eta,\delta\ge0.
137 \]
138 For every $M\ge0$,
139 \[
140  \abs{\beta_{T,r}(M)-\beta_{\widetilde T,\widetilde r}(M)}
141  \le\delta+\eta M.
142 \]
143 In particular, for $\norm z\le1$,
144 \[
145  \beta_{T,r}(M)\ge
146  \langle\widetilde r,z\rangle-M\norm{\widetilde T^*z}
147        -\delta-\eta M.
148 \]
149 \end{theorem}
150 \begin{proof}
151 Fix a feasible correction $a$. The two residual vectors have difference
152 \[
153  (r-Ta)-(\widetilde r-\widetilde Ta)
154  =(r-\widetilde r)-(T-\widetilde T)a,
155 \]
156 whose norm is at most $c=\delta+\eta M$. The reverse triangle inequality therefore gives both inequalities
157 \[
158  \norm{r-Ta}\le\norm{\widetilde r-\widetilde Ta}+c,
159  \qquad
160  \norm{\widetilde r-\widetilde Ta}\le\norm{r-Ta}+c.
161 \]
162 The domain of feasible corrections is identical in the two problems. Taking the infimum of each inequality over that common domain yields
163 \[
164  \beta_{T,r}(M)\le\beta_{\widetilde T,\widetilde r}(M)+c,
165  \qquad
166  \beta_{\widetilde T,\widetilde r}(M)\le\beta_{T,r}(M)+c.
167 \]
168 These are precisely the absolute-value bound. One could equivalently evaluate at the two attained minimizers, but no relation between those minimizers is needed.
169 
170 For any admissible $z$, Theorem~\ref{WR04} for the nominal problem gives
171 \[
172  \beta_{\widetilde T,\widetilde r}(M)
173  \ge\langle\widetilde r,z\rangle-M\norm{\widetilde T^*z}.
174 \]
175 Combine this with the lower half of the preceding comparison. The result is a certificate against every correction in the original fixed ball, reduced by the explicit uncertainty allowance. If the correction space itself changed, the common-domain step would fail and this proof would no longer apply.
176 \end{proof}
177 \written{WR05}
178 
179 This estimate identifies a practical boundary of increasingly large corrections. A model error $\eta$ is amplified by the correction budget even if the measured residual is tiny. The candidate-level inequality is
180 \[
181  \norm{r-Ta}\le\norm{\widetilde r-\widetilde Ta}+\delta+\eta\norm a.
182 \]
183 The theorem compares maps on one fixed correction space. It does not cover an uncertain preservation map whose kernel itself changes.
184 
185 \fixedplate{33_budget_uncertainty}{The nominal budget profile is surrounded by the rigorous uncertainty band $\delta+\eta M$. A large budget can improve the nominal fit while enlarging the uncertainty in that conclusion. The example uses $T=1$, $r=1$, $\delta=1/20$, and $\eta=1/10$.}{fig:budget-uncertainty}

Back to source controls

Back to Komorebi Space