Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 2 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Iterative regularization and early stopping

1 · Prerequisites

2 · Summary

Landweber iteration is given with an explicit discrepancy and finite-budget status; its spectral-filter identities yield exact-data convergence, source bias and noise bounds, then a source-conditioned discrepancy-stopping rate. The page also defines exact-arithmetic Golub–Kahan LSQR and proves its residual-minimization property on the generated Krylov space. For nonlinear inverse problems it defines the assigned unanchored regularized Gauss–Newton step and proves a local derivative-remainder estimate and one-step error recurrence. These unanchored local claims are retained separately from the anchored convergence theorem.

The nonlinear source/discrepancy theorem now applies to the separately defined anchored IRGNM method under explicit reference-factorization, source-smallness and discrepancy-factor conditions. It covers every source exponent between zero and one half, over real and complex Hilbert spaces, without a full-rank or finite-dimensional restriction. The unanchored LM procedure and its one-step identity/example remain valid separately; no unanchored stopped-convergence theorem is inferred from the anchored proof.

3 · Logical flowchart

4 · Definitions, theorems and proofs

AlgorithmAlgorithm: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Landweber iteration with discrepancy and budget statuses

Definition

Assume Countable Choice, as required for the Hilbert-space adjoint in the iteration.

Let $X, Y$ be real or complex Hilbert spaces, let $A : X \to Y$ be a nonzero compact linear operator, and let $ω$ satisfy $0 < ω < 2 / ∥ A ∥^{2}$ . The input consists of data $y_{δ} \in Y$ , a noise bound $δ \geq 0$ , a discrepancy factor $τ > 1$ , and a finite iteration budget $N \in N$ . Define the associated infinite mathematical path by $x_{0} = 0$ and $x_{k + 1} = x_{k} + ω A^{*} (y_{δ} - A x_{k}), k \geq 0.$ For the finite procedure, evaluate only the prefix through index $N$ , in increasing order, and return at its first stopping condition. Values of the mathematical path after an earlier return remain defined by the recurrence but need not be computed by an implementation.

For $k = 0, \dots, N$ in increasing order, compute $r_{k} = y_{δ} - A x_{k}$ . If $∥ r_{k} ∥ \leq τ δ$ , return $(x_{k}, k, discrepancy)$ . If $k = N$ , return $(x_{k}, k, budget-exhausted)$ . Otherwise set $x_{k + 1} = x_{k} + ω A^{*} (y_{δ} - A x_{k}) .$

The procedure uses exact Hilbert-space operations. It reports a finite-budget failure to cross as inconclusive; that status is not a convergence conclusion.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses

Definition

Let $A \in R^{m \times n}$ , $b \in R^{m}$ , $x_{0} \in R^{n}$ , $δ \geq 0$ , $τ > 1$ , and a budget $N \in N$ be given. All operations are exact. In the projected matrices and vectors, use local one-based labels: entry $(i, k)$ means the underlying zero-based entry $(i - 1, k - 1)$ , and vector entry $i$ means entry $i - 1$ . Put $r_{0} = b - A x_{0}$ . If $∥ r_{0} ∥_{2} = 0$ , return $(x_{0}, 0, zero-residual)$ . If $∥ r_{0} ∥_{2} \leq τ δ$ , return $(x_{0}, 0, discrepancy)$ . If $N = 0$ , return $(x_{0}, 0, budget-exhausted)$ . Otherwise initialize $β_{1} = ∥ r_{0} ∥_{2}$ , $u_{1} = r_{0} / β_{1}$ , and $α_{1} = ∥ A^{T} u_{1} ∥_{2}$ . If $α_{1} = 0$ , return $(x_{0}, 0, stationary-nonzero-residual)$ . Otherwise set $v_{1} = A^{T} u_{1} / α_{1}$ .

Initialize the current best iterate and index to $(x_{b e s t}, j_{b e s t}) = (x_{0}, 0)$ . If a Givens rotation is undefined, return $(x_{b e s t}, j_{b e s t}, small-QR-breakdown)$ .

For $j = 1, \dots, N$ , perform these steps.

Compute $p_{j} = A v_{j} - α_{j} u_{j}$ and $β_{j + 1} = ∥ p_{j} ∥_{2}$ . If $β_{j + 1} > 0$ , set $u_{j + 1} = p_{j} / β_{j + 1}$ .
If $β_{j + 1} > 0$ , compute $q_{j} = A^{T} u_{j + 1} - β_{j + 1} v_{j}$ and $α_{j + 1} = ∥ q_{j} ∥_{2}$ . If $α_{j + 1} > 0$ , set $v_{j + 1} = q_{j} / α_{j + 1}$ . A zero $β_{j + 1}$ or $α_{j + 1}$ marks bidiagonalization breakdown.
Put $V_{j} = [v_{1}, \dots, v_{j}]$ . Form the $(j + 1) \times j$ lower-bidiagonal matrix $B_{j}$ with diagonal $α_{1}, \dots, α_{j}$ and subdiagonal $β_{2}, \dots, β_{j + 1}$ , using $β_{j + 1} = 0$ if step 1 broke down. Let $e_{1} = (1, 0, \dots, 0)^{T} \in R^{j + 1}$ and $c = β_{1} e_{1}$ . For $i = 1, \dots, j$ , let $a, b$ be the current entries at positions $(i, i), (i + 1, i)$ of the rotated matrix and put $ρ = (a^{2} + b^{2})^{1 / 2}$ . If $ρ = 0$ , return the current best output with status small-QR-breakdown. Otherwise put $c_{i} = a / ρ$ , $s_{i} = b / ρ$ and apply $(\begin{array}{cc} c_{i} & s_{i} \\ - s_{i} & c_{i} \end{array})$ to rows $i, i + 1$ of the full matrix and right-hand side. After these $j$ rotations, let $R_{j}$ be the first $j$ rows of the rotated matrix and $d_{j}$ the first $j$ entries of the rotated right-hand side. Solve $R_{j} z_{j} = d_{j}$ by back substitution. Update $(x_{b e s t}, j_{b e s t}) = (x_{0} + V_{j} z_{j}, j)$ .
Put $x_{j} = x_{0} + V_{j} z_{j}$ . Compute the physical residual $∥ A x_{j} - b ∥_{2}$ . If it is at most $τ δ$ , return $(x_{j}, j, discrepancy)$ . If bidiagonalization broke down, return $(x_{j}, j, bidiagonalization-breakdown)$ . If $j = N$ , return $(x_{j}, j, budget-exhausted)$ ; otherwise continue.

The procedure makes no claim that a finite-budget status is a successful regularized approximation. Its exact-arithmetic residual-minimization property is a separate theorem.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

A Lipschitz Fréchet derivative gives a quadratic linearization remainder

Statement

Assume Countable Choice. Let $F \in {R, C}$ and let $X, Y$ be Banach spaces over the same field $F$ . Let $U \subseteq X$ be open and let $F : U \to Y$ be continuously Fréchet differentiable over $F$ . Thus $F^{'} (u)$ is bounded $F$ -linear for each $u \in U$ and $\lim_{\begin{array}{c} h \to 0, h \neq 0 \\ u + h \in U \end{array}} \frac{∥ F (u + h) - F (u) - F^{'} (u) h ∥}{∥ h ∥} = 0.$ In particular, in the complex case $F^{'} (u)$ is complex-linear and the limit ranges over complex increments. Let $K \subseteq U$ be convex and let $x, z \in K$ . If $∥ F^{'} (u) - F^{'} (v) ∥ \leq L ∥ u - v ∥$ for all $u, v \in K$ , where $L \geq 0$ , then $∥ F (x) - F (z) - F^{'} (z) (x - z) ∥ \leq \frac{L}{2} ∥ x - z ∥^{2} .$

Facts & Assumptions

Given: Countable Choice, the Banach spaces and map in the Statement, the convex set $K$ , points $x, z \in K$ , and the Lipschitz constant $L$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is the choice assumption used by the Banach-valued integral supplier.

[F1]

Taylor expansion with integral remainder for Banach-valued curves: For a $C^{1}$ Banach-valued curve $γ$ on $[0, 1]$ , $γ (1) - γ (0) = \int_{0}^{1} γ^{'} (t) d t$ .

[F2]

Linearity of the Bochner integral: The Bochner integral is linear.

[F6]

For a constant vector $v$ on $[0, 1]$ with Lebesgue measure, the one-cell simple-function formula Banach-valued simple function and integral gives $\int_{0}^{1} v d t = λ_{1} ([0, 1]) v = v$ , since A box in $R^{n}$ with parameters $a_{i} \leq b_{i}$ is Lebesgue measurable of measure $\prod_{i < n} (b_{i} - a_{i})$ , whichever of its faces are included gives $λ_{1} ([0, 1]) = 1$ .

[F3]

Bochner integral norm inequality: The norm of a Bochner integral is at most the integral of the norm of its integrand.

[F4]

Fréchet derivative between Banach spaces: In the real case the Fréchet derivative is bounded real-linear. In the complex case the same-field convention in the Statement makes it bounded complex-linear. In either case it is real-linear along real-parameter increments.

Proof

Given: The assumptions and facts above. Put $h = x - z$ and $γ (t) = F (z + t h)$ for $0 \leq t \leq 1$ .

1.1A1F1F2F6F4givenconstructalgebra

Convexity gives $z + t h \in K \subseteq U$ for $0 \leq t \leq 1$ . If $h \neq 0$ and $0 < t < 1$ , put $u = z + t h$ . For real $s \to 0$ with $t + s \in [0, 1]$ , Fréchet differentiability at $u$ gives $∥ \frac{F (u + s h) - F (u)}{s} - F^{'} (u) h ∥ = \frac{∥ F (u + s h) - F (u) - F^{'} (u) (s h) ∥}{∣ s ∣} ⟶ 0,$ because $F^{'} (u)$ is linear over the common field and hence over real scalars. Thus $γ^{'} (t) = F^{'} (z + t h) h$ . If $h = 0$ , $γ$ is constant and the same formula holds. Differentiability at every point of $U$ also makes $F$ and hence $γ$ continuous on the segment, directly from the Fréchet remainder definition. In either case this derivative is continuous in $t$ and extends to the endpoints, since $F^{'}$ is Lipschitz on $K$ . The Banach-valued fundamental theorem [F1] therefore gives $F (x) - F (z) = \int_{0}^{1} F^{'} (z + t h) h d t$ . The constant vector function $t \mapsto F^{'} (z) h$ has integral $F^{'} (z) h$ by [F6]. Subtracting that integral and using linearity [F2] gives $F (x) - F (z) - F^{'} (z) h = \int_{0}^{1} (F^{'} (z + t h) - F^{'} (z)) h d t$ .

2.1A1step 1.1F3F4algebra∎

For each $t \in [0, 1]$ , the Lipschitz hypothesis and bounded linearity give $∥ (F^{'} (z + t h) - F^{'} (z)) h ∥ \leq L t ∥ h ∥^{2}$ . Therefore [F3] and scalar integration give $∥ F (x) - F (z) - F^{'} (z) h ∥ \leq \int_{0}^{1} L t ∥ h ∥^{2} d t = (L / 2) ∥ h ∥^{2}$ .

Remarks

[F5] Bochner-integrable function: A Bochner integral is defined as the norm limit of integrals of simple-function approximants for a Bochner-integrable function.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Unanchored Levenberg–Marquardt step with explicit early stopping

Definition

Assume Countable Choice, as required for the Hilbert-space adjoints in the normal equation.

Let $X, Y$ be Hilbert spaces over the same field $F \in {R, C}$ , let $U \subseteq X$ be open, and let $F : U \to Y$ be continuously Fréchet differentiable over $F$ . In the complex case, each $F^{'} (x)$ is a bounded complex-linear operator and the Fréchet remainder is measured over complex increments, so $\lim_{\begin{array}{c} h \to 0, h \neq 0 \\ x + h \in U \end{array}} \frac{∥ F (x + h) - F (x) - F^{'} (x) h ∥}{∥ h ∥} = 0.$ Inputs are $x_{0} \in U$ , noisy data $y_{δ} \in Y$ , a bound $δ \geq 0$ , a discrepancy factor $τ > 1$ , a finite budget $N \in N$ , and parameters $α_{0} > 0$ and $q \in (0, 1)$ . The output is a tuple $(x_{k}, k, status)$ . Starting with $k = 0$ , repeat the following checks and update. If $x_{k} \notin U$ return $(x_{k}, k, domain-failure)$ . Otherwise put $A_{k} = F^{'} (x_{k})$ and $α_{k} = α_{0} q^{k}$ . Before computing an update, if $∥ F (x_{k}) - y_{δ} ∥ \leq τ δ$ , return $(x_{k}, k, discrepancy)$ . If $k = N$ , return $(x_{k}, k, budget-exhausted)$ .

For $k < N$ , solve the unique Hilbert-space Tikhonov normal equation $(A_{k}^{*} A_{k} + α_{k} I_{X}) s_{k} = A_{k}^{*} (y_{δ} - F (x_{k}))$ and set $x_{k + 1} = x_{k} + s_{k}$ , then replace $k$ by $k + 1$ and repeat the checks. The shifted normal operator is invertible by The shifted Hilbert-space normal operator is invertible with inverse norm at most $1 / λ$ . If the new iterate leaves $U$ , the next check returns domain-failure. The procedure asserts no convergence theorem; its prescribed step is the unanchored Levenberg–Marquardt form used in the assigned contract.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

A nonbreakdown LSQR iterate minimizes residual on its Krylov space

Statement

Let $A \in R^{m \times n}$ , $b \in R^{m}$ , $x_{0} \in R^{n}$ , and $r_{0} = b - A x_{0}$ . Consider a $k$ -step run of Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses with nonzero initial residual and no bidiagonalization or small-QR breakdown through step $k$ . Then its iterate $x_{k}$ minimizes $∥ A x - b ∥_{2}$ over $x_{0} + K_{k} (A^{T} A, A^{T} r_{0}),$ where $K_{k} (M, v) = span {v, M v, \dots, M^{k - 1} v}$ is the Krylov subspace of The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ . The assertion is exact-arithmetic residual minimization; it is not a convergence or noise-stability theorem.

Facts & Assumptions

Given: The real matrix $A$ , vectors $b, x_{0}$ , and a nonbreakdown $k$ -step run of the LSQR algorithm.

[F1]

Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses: The recurrences are $β_{j + 1} u_{j + 1} = A v_{j} - α_{j} u_{j}$ and $α_{j + 1} v_{j + 1} = A^{T} u_{j + 1} - β_{j + 1} v_{j}$ . The procedure rotates the lower-bidiagonal $B_{j}$ and $β_{1} e_{1}$ , solves $R_{j} z_{j} = d_{j}$ by back substitution, and sets $x_{j} = x_{0} + V_{j} z_{j}$ .

[F2]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{0} (M, v) = {0}$ ; for $k \geq 1$ , a square matrix $M$ and vector $v$ , $K_{k} (M, v) = span {v, M v, \dots, M^{k - 1} v}$ .

[F3]

The Krylov subspace consists exactly of the vectors $p (A) b$ for zero polynomials or polynomials of degree less than $m$ : $K_{k} (M, v) = {p (M) v : p = 0 or \deg p < k}$ .

[F4]

For a linear map $T : V \to W$ between finite-dimensional inner-product spaces, $x$ minimises $∥ T x - b ∥$ if and only if $T^{*} (T x - b) = 0$ , equivalently $T^{*} T x = T^{*} b$ ; minimisers exist and any two differ by an element of $\ker T$ : A minimizer of a finite-dimensional least-squares residual exists; a full-column-rank coefficient matrix makes it unique.

[F5]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $⟨ u, v ⟩ = u^{T} v = \sum_{i} u_{i} v_{i}$ on each real coordinate space.

[F6]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: Matrix multiplication uses the finite row-coordinate sums.

[F7]

The transpose $A^{T}$ of a matrix: $(A^{T})_{j i} = a_{i j}$ , so $⟨ A v, u ⟩ = ⟨ v, A^{T} u ⟩$ by interchanging the two finite sums.

Proof

Given: The hypotheses above, and write $V_{j} = [v_{1}, \dots, v_{j}]$ and $U_{j + 1} = [u_{1}, \dots, u_{j + 1}]$ .

1.1givenF1F2F5F6F7inductionalgebra

If $k = 0$ , [F2] gives $K_{0} (A^{T} A, A^{T} r_{0}) = {0}$ , so the feasible set is ${x_{0}}$ and $x_{0}$ is its residual minimizer. Henceforth assume $k \geq 1$ , so the stated nonbreakdown run initializes $u_{1}, v_{1}$ . The initial vector $u_{1} = r_{0} / ∥ r_{0} ∥_{2}$ is unit. Suppose $u_{1}, \dots, u_{j}$ and $v_{1}, \dots, v_{j}$ are orthonormal and satisfy the earlier Golub–Kahan recurrences. For $i < j$ , $⟨ A v_{j}, u_{i} ⟩ = ⟨ v_{j}, A^{T} u_{i} ⟩ = 0$ by [F5]–[F7], because $A^{T} u_{i}$ lies in $span {v_{i - 1}, v_{i}}$ ; for $i = j$ , $⟨ A v_{j}, u_{j} ⟩ = α_{j}$ by the definition of $α_{j}$ . Therefore $A v_{j} - α_{j} u_{j}$ is orthogonal to $u_{1}, \dots, u_{j}$ , and division by the nonzero $β_{j + 1}$ gives a unit $u_{j + 1}$ orthogonal to them. For $i < j$ , $⟨ A^{T} u_{j + 1}, v_{i} ⟩ = ⟨ u_{j + 1}, A v_{i} ⟩ = 0$ by [F5]–[F7], since $A v_{i} = α_{i} u_{i} + β_{i + 1} u_{i + 1}$ lies in $span {u_{1}, \dots, u_{j}}$ ; for $i = j$ the inner product equals $β_{j + 1}$ . Thus $A^{T} u_{j + 1} - β_{j + 1} v_{j}$ is orthogonal to $v_{1}, \dots, v_{j}$ , and division by the nonzero $α_{j + 1}$ gives a unit $v_{j + 1}$ orthogonal to them. Induction proves both orthonormality relations through step $k$ .

2.1step 1.1F1F5F6algebra

The column recurrences in [F1] assemble as $A V_{k} = U_{k + 1} B_{k}$ . Also $r_{0} = β_{1} u_{1} = β_{1} U_{k + 1} e_{1}$ . Hence for every $z \in R^{k}$ , $b - A (x_{0} + V_{k} z) = r_{0} - A V_{k} z = U_{k + 1} (β_{1} e_{1} - B_{k} z) .$ Orthonormality from [step 1.1] and the Euclidean norm definition [F5] imply $∥ b - A (x_{0} + V_{k} z) ∥_{2} = ∥ β_{1} e_{1} - B_{k} z ∥_{2}$ .

3.1F1F4F5F6step 2.1inductionalgebra

Each Givens rotation in [F1] is orthogonal because $(a / ρ)^{2} + (b / ρ)^{2} = 1$ when $ρ = (a^{2} + b^{2})^{1 / 2} > 0$ . Number the rows and columns here from one. Since $B_{k}$ is lower-bidiagonal, rotation $i$ annihilates its entry in row $i + 1$ , column $i$ , while preserving the zeros in earlier columns; induction gives $Q B_{k} = (\binom{R_{k}}{0})$ for the product $Q$ of all $k$ rotations, with $R_{k}$ upper triangular. Its diagonal entries are the nonzero rotation pivots $ρ$ , so back substitution returns $z_{k}$ with $R_{k} z_{k} = d_{k}$ . Write $Q β_{1} e_{1} = (\binom{d_{k}}{η_{k}})$ . Orthogonality gives, for every $z$ , $∥ β_{1} e_{1} - B_{k} z ∥_{2}^{2} = ∥ d_{k} - R_{k} z ∥_{2}^{2} + ∣ η_{k} ∣^{2}$ . The computed $z_{k}$ attains the lower bound $∣ η_{k} ∣^{2}$ , proving its minimizing property directly from the instructions; it is unique by [F4], since the nonzero diagonal of $B_{k}$ makes it full column rank. Thus $x_{k} = x_{0} + V_{k} z_{k}$ minimizes the true residual over $x_{0} + span {v_{1}, \dots, v_{k}}$ by [step 2.1].

4.1F1F2F3F6F7step 3.1inductionalgebra∎

The recurrence gives, for $j \geq 1$ , $A^{T} A v_{j} = α_{j} β_{j} v_{j - 1} + (α_{j}^{2} + β_{j + 1}^{2}) v_{j} + α_{j + 1} β_{j + 1} v_{j + 1},$ with the first term omitted at $j = 1$ . Every coefficient $α_{j + 1} β_{j + 1}$ is nonzero in a nonbreakdown run, so induction shows $span {v_{1}, \dots, v_{k}} = span {v_{1}, A^{T} A v_{1}, \dots, (A^{T} A)^{k - 1} v_{1}}$ . Since $v_{1} = A^{T} r_{0} / (β_{1} α_{1})$ , [F2]–[F3] identify this span with $K_{k} (A^{T} A, A^{T} r_{0})$ . Substitution into [step 3.1] proves the Statement.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Landweber iterates and residuals are spectral-filter iterates

Statement

Assume Countable Choice. Let $A : X \to Y$ and $ω$ satisfy the hypotheses of Landweber iteration with discrepancy and budget statuses and put $T = A^{*} A$ . For each integer $k \geq 0$ , define $g_{0} (t) = 0$ and $g_{k} (t) = ω \sum_{j = 0}^{k - 1} (1 - ω t)^{j}$ for $k \geq 1$ , with $r_{k} (t) = (1 - ω t)^{k}$ . For the associated infinite mathematical path, $x_{k} = g_{k} (T) A^{*} y_{δ}, y_{δ} - A x_{k} = r_{k} (A A^{*}) y_{δ} .$ If $y_{δ} = A x^{†}$ , then $x^{†} - x_{k} = r_{k} (T) x^{†} .$ Here $g_{k} (T)$ and $r_{k} (T)$ are the compact spectral multipliers defined in Compact spectral filters, source conditions, and qualification; $r_{k} (A A^{*})$ is the multiplier with scalar function $t \mapsto (1 - ω t)^{k}$ on the compact self-adjoint operator $A A^{*}$ , as supplied by Bounded multipliers on compact self-adjoint eigenspaces define bounded operators.

Facts & Assumptions

Given: Countable Choice, compact nonzero $A : X \to Y$ , $0 < ω < 2 / ∥ A ∥^{2}$ , the algorithm's initial value $x_{0} = 0$ , and $T = A^{*} A$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is assumed by the Hilbert-adjoint and compact spectral multiplier suppliers used here.

[F1]

Landweber iteration with discrepancy and budget statuses: Its associated infinite path is defined for every $j \geq 0$ by $x_{j + 1} = x_{j} + ω A^{*} (y_{δ} - A x_{j})$ ; a finite run computes only a prefix.

[F2]

A compact Hilbert-space Gram operator is positive and has the forward kernel: Both $A^{*} A$ and $A A^{*}$ are compact, positive, and self-adjoint, with $\ker (A^{*} A) = \ker A$ .

[F3]

Bounded multipliers on compact self-adjoint eigenspaces define bounded operators: Every bounded scalar function on the nonzero eigenspaces of a compact self-adjoint operator defines a bounded spectral multiplier.

[F4]

Compact spectral filters, source conditions, and qualification: For $T = A^{*} A$ , compact spectral multipliers include the residual filter $r_{k} (t) = (1 - ω t)^{k}$ .

[F5]

The Hilbert-space adjoint of a bounded operator: $⟨ A x, y ⟩_{Y} = ⟨ x, A^{*} y ⟩_{X}$ .

Proof

Given: The hypotheses above and the exact recurrence [F1].

1.1A1givenF1F5inductionalgebra

The adjoint identity [F5] gives $A^{*} A = T$ . Thus [F1] rewrites each update before stopping as $x_{j + 1} = (I - ω T) x_{j} + ω A^{*} y_{δ}$ . Starting from $x_{0} = 0$ , induction gives $x_{k} = ω \sum_{j = 0}^{k - 1} (I - ω T)^{j} A^{*} y_{δ}$ : the sum is empty for $k = 0$ , and multiplying the $k$ -term sum by $I - ω T$ and adding $ω A^{*} y_{δ}$ produces the $(k + 1)$ -term sum.

2.1A1F1F2F3step 1.1inductionalgebra

Put $ρ_{k} = y_{δ} - A x_{k}$ . Substitution of [F1] gives $ρ_{k + 1} = ρ_{k} - ω A A^{*} ρ_{k} = (I - ω A A^{*}) ρ_{k}$ . Induction from $ρ_{0} = y_{δ}$ yields $ρ_{k} = (I - ω A A^{*})^{k} y_{δ}$ . By [F2], $A A^{*}$ is compact positive self-adjoint, and [F3] therefore interprets this polynomial as the stated compact spectral multiplier. The scalar geometric identity $1 - (1 - ω t)^{k} = ω t \sum_{j = 0}^{k - 1} (1 - ω t)^{j}$ also identifies the vector expression from step 1.1 with $g_{k} (T) A^{*} y_{δ}$ .

3.1A1F2F4step 1.1algebra∎

If $y_{δ} = A x^{†}$ , then [step 1.1] and $A^{*} y_{δ} = T x^{†}$ give $x_{k} = ω \sum_{j = 0}^{k - 1} (I - ω T)^{j} T x^{†} = [I - (I - ω T)^{k}] x^{†}$ by the same polynomial identity. Since [F2] makes $T$ compact positive self-adjoint, [F4] interprets $r_{k} (T)$ as its residual multiplier; hence $x^{†} - x_{k} = (I - ω T)^{k} x^{†} = r_{k} (T) x^{†}$ .

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

One-step error recurrence for the assigned nonlinear regularized Gauss–Newton step

Statement

Assume Countable Choice. Let $X, Y$ be real or complex Hilbert spaces over the same scalar field and let $U \subseteq X$ be open. Let $F : U \to Y$ be continuously Fréchet differentiable over that field, with bounded complex-linear derivatives in the complex case. Let $x^{†} \in U$ satisfy $F (x^{†}) = y$ , and suppose $x_{k}, x^{†}$ lie in a convex subset of $U$ on which $F^{'}$ is $L$ -Lipschitz. Let $y_{δ}$ satisfy $∥ y_{δ} - y ∥ \leq δ$ , put $e_{k} = x_{k} - x^{†}$ and $A_{k} = F^{'} (x_{k})$ , and use the step of Unanchored Levenberg–Marquardt step with explicit early stopping with $α_{k} > 0$ . Define $R_{k} : = y - F (x_{k}) + A_{k} e_{k} .$ Then $e_{k + 1} = α_{k} (A_{k}^{*} A_{k} + α_{k} I)^{- 1} e_{k} + (A_{k}^{*} A_{k} + α_{k} I)^{- 1} A_{k}^{*} (y_{δ} - y + R_{k}),$ and $∥ e_{k + 1} ∥ \leq ∥ e_{k} ∥ + \frac{δ + (L / 2) ∥ e_{k} ∥^{2}}{2 \sqrt{α_{k}}} .$ If in addition the tangential-cone condition $∥ F (x) - F (z) - F^{'} (z) (x - z) ∥ \leq η ∥ F (x) - F (z) ∥$ holds for all $x, z$ in that subset, then also $∥ R_{k} ∥ \leq η (∥ F (x_{k}) - y_{δ} ∥ + δ)$ , which may replace $(L / 2) ∥ e_{k} ∥^{2}$ in the recurrence bound. This lemma alone does not assert contraction or discrepancy-stopped convergence.

Facts & Assumptions

Given: The Hilbert-space data and iterates above, $α_{k} > 0$ , the Lipschitz derivative bound, and, for the final bound, the stated tangential cone condition.

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is assumed by the Hilbert adjoint and shifted-normal-operator suppliers.

[F1]

Unanchored Levenberg–Marquardt step with explicit early stopping: $e_{k + 1} = e_{k} + s_{k}$ and $(A_{k}^{*} A_{k} + α_{k} I) s_{k} = A_{k}^{*} (y_{δ} - F (x_{k}))$ .

[F2]

The shifted Hilbert-space normal operator is invertible with inverse norm at most $1 / λ$ : $B_{k} = A_{k}^{*} A_{k} + α_{k} I$ is invertible with $∥ B_{k}^{- 1} ∥ \leq 1 / α_{k}$ .

[F3]

Hilbert-space Tikhonov amplifies data by at most $1 / (2 \sqrt{λ})$ : $∥ B_{k}^{- 1} A_{k}^{*} v ∥ \leq ∥ v ∥ / (2 \sqrt{α_{k}})$ for bounded $A_{k}$ .

[F4]

A Lipschitz Fréchet derivative gives a quadratic linearization remainder: $∥ F (x) - F (z) - F^{'} (z) (x - z) ∥ \leq (L / 2) ∥ x - z ∥^{2}$ on the convex subset.

Proof

Given: The assumptions and facts above. Put $B_{k} = A_{k}^{*} A_{k} + α_{k} I$ .

1.1A1F1F2algebra

From [F1], $e_{k + 1} = e_{k} + B_{k}^{- 1} A_{k}^{*} (y_{δ} - F (x_{k}))$ . Multiplying by $B_{k}$ and using $B_{k} e_{k} = A_{k}^{*} A_{k} e_{k} + α_{k} e_{k}$ gives $B_{k} e_{k + 1} = α_{k} e_{k} + A_{k}^{*} (A_{k} e_{k} + y_{δ} - F (x_{k})) .$ Since $A_{k} e_{k} + y - F (x_{k}) = R_{k}$ , the term in parentheses is $y_{δ} - y + R_{k}$ . Applying [F2] to invert $B_{k}$ proves the stated identity.

2.1A1F2F3F4step 1.1algebra

By [F2], $∥ α_{k} B_{k}^{- 1} e_{k} ∥ \leq ∥ e_{k} ∥$ . By [F3], $∥ B_{k}^{- 1} A_{k}^{*} (y_{δ} - y + R_{k}) ∥ \leq (δ + ∥ R_{k} ∥) / (2 \sqrt{α_{k}})$ . The triangle inequality and [F4] give the quadratic-error recurrence.

3.1A1givenstep 2.1algebra∎

For the tangential-cone bound, substitute $x = x^{†}$ and $z = x_{k}$ . Its left side is $∥ y - F (x_{k}) + A_{k} (x_{k} - x^{†}) ∥ = ∥ R_{k} ∥$ , so $∥ R_{k} ∥ \leq η ∥ y - F (x_{k}) ∥ \leq η (∥ y - y_{δ} ∥ + ∥ y_{δ} - F (x_{k}) ∥) \leq η (δ + ∥ y_{δ} - F (x_{k}) ∥)$ . Inserting this estimate into the bound from [step 2.1] proves the optional residual form.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Real and complex Hilbert source powers and fixed-reference Tikhonov filter bounds

Statement

Assume AC. Let $A : X \to Y$ be bounded between real or complex Hilbert spaces, and set $S = A^{*} A$ . For $ν > 0$ , define $S^{ν}$ by the continuous calculus of $t \mapsto t^{ν}$ in the complex case; in the real case use the Hilbert complexification and restrict to the real copy, as constructed below. On a zero space or for $S = 0$ , this power is zero. It is bounded self-adjoint, and $S^{ν} h = 0$ for $h \in \ker A$ , so $S^{ν} w ⊥ \ker A$ . For $α > 0$ put $T_{α} = (S + α I)^{- 1}$ . Then $∥ α T_{α} S^{ν} ∥ \leq α^{ν} (0 < ν \leq 1), ∥ A α T_{α} S^{ν} ∥ \leq α^{ν + 1 / 2} (0 < ν \leq 1 / 2),$ $∥ T_{α} A^{*} ∥ \leq \frac{1}{2 \sqrt{α}}, ∥ A T_{α} A^{*} ∥ \leq 1, ∥ S^{ν} ∥ \leq ∥ A ∥^{2 ν} .$ No compactness or lower singular-value bound is assumed.

Facts & Assumptions

Given: The bounded operator, Hilbert spaces, positive exponents and shift in the Statement.

[A1]

The Axiom of Choice: AC is assumed for the complex calculus, and implies the Countable Choice needed by Hilbert adjoints.

[F1]

Continuous functional calculus for bounded self adjoint operators: on a nonzero complex Hilbert space a bounded self-adjoint operator has an isometric unital star-homomorphism from continuous functions on its spectrum.

[F2]

Spectrum of a positive operator is nonnegative and Spectrum is nonempty compact and norm bounded: for a bounded positive operator on a nonzero complex Hilbert space, its spectrum is contained in $[0, ∥ S ∥]$ .

[F3]

Polynomials are uniformly dense in $C ([a, b], R)$ for every closed interval: continuous real functions on a closed interval have uniform real-polynomial approximants.

[F4]

Hilbert-adjoint identities: adjoints preserve the reversed product, $∥ T^{*} ∥ = ∥ T ∥$ , and $∥ T^{*} T ∥ = ∥ T ∥^{2}$ .

[F5]

Real and complex inner-product spaces and their induced length and Hilbert space: the pairing is linear in the first argument, conjugate symmetric, and its norm is complete in a Hilbert space.

[F6]

Real powers for positive bases, with the zero-base positive-exponent convention, The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents and Continuity and derivatives of positive-base real powers: positive real powers obey the exponent laws and are continuous with positive derivative on positive bases for positive exponents; $0^{ν} = 0$ for $ν > 0$ .

[F7]

The shifted Hilbert-space normal operator is invertible with inverse norm at most $1 / λ$ : the shifted normal inverse exists in either field; Hilbert-space Tikhonov amplifies data by at most $1 / (2 \sqrt{λ})$ gives $∥ (S + α I)^{- 1} A^{*} ∥ \leq 1 / (2 \sqrt{α})$ .

[F8]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a positive derivative on an interval implies that endpoint increments are positive, hence the real power function is increasing.

Proof

1.1A1F4F5F7givenalgebra

If $X = {0}$ or $A = 0$ , all asserted powers and products involving $A$ are zero, and the bounds and kernel conclusions follow directly. In the remaining case $S = A^{*} A$ is positive self-adjoint and $∥ S ∥ = ∥ A ∥^{2} > 0$ by the adjoint identities.

2.1F4F5step 1.1givenconstructalgebra

For real $X$ , construct $X_{c} = X \times X$ with $(a + i b) (x, y) = (a x - b y, b x + a y)$ and $⟨ (x, y), (u, v) ⟩_{c} = ⟨ x, u ⟩ + ⟨ y, v ⟩ + i (⟨ y, u ⟩ - ⟨ x, v ⟩)$ . Expansion verifies conjugate symmetry, complex linearity in the first argument and norm squared $∥ x ∥^{2} + ∥ y ∥^{2}$ ; completeness follows by taking the two component limits of a Cauchy sequence. Thus this is a complex Hilbert space. Construct $Y_{c}$ similarly. The extensions $A_{c} (x, y) = (A x, A y)$ and $S_{c} (x, y) = (S x, S y)$ have the same operator norms as $A, S$ : the upper bound follows by summing squared component bounds, and real vectors give the reverse inequality. The inner-product identity gives $A_{c}^{*} = (A^{*})_{c}$ and $S_{c} = A_{c}^{*} A_{c}$ . This construction uses the Hilbert sum norm, not a rotation-supremum Banach norm.

3.1A1F1F2F3F6F8step 2.1givenconstructalgebra

In the nonzero complex space, or in step 2.1's complexification, apply [F1]–[F2]. For $ν > 0$ , $t^{ν}$ extends continuously to zero: for $0 < t < ε^{1 / ν}$ , the positive derivative and [F8], followed by the power laws, give $t^{ν} < ε$ . Hence [F3] supplies real polynomials converging uniformly to $t^{ν}$ on $[0, ∥ S ∥]$ . The calculus maps them to a norm-convergent sequence of self-adjoint operators. In the real case each polynomial in $S_{c}$ preserves $j (X) = {(x, 0)}$ , a closed real subspace, so the limit preserves it too. Restriction defines $S^{ν}$ over the real field, independent of approximants by the norm estimate from [F1]. Polynomial identities and norm bounds pass to these restrictions.

4.1F1F4F5step 3.1algebra

For $h \in \ker A$ , $S h = 0$ , so every polynomial satisfies $p (S) h = p (0) h$ . Taking step 3.1's approximants gives $S^{ν} h = 0$ . Self-adjointness then gives $⟨ S^{ν} w, h ⟩ = ⟨ w, S^{ν} h ⟩ = 0$ . Also the calculus norm gives $∥ S^{ν} ∥ \leq ∥ S ∥^{ν} = ∥ A ∥^{2 ν}$ .

4.2F1F6F7step 3.1algebra

The calculus identifies $T_{α}$ with $(t + α)^{- 1}$ : multiplying this function by $t + α$ gives the identity, so uniqueness of the inverse in [F7] applies. For $0 < γ \leq 1$ and $u \geq 0$ , $u^{γ} \leq 1 + u$ (use $u \leq 1$ and $u \geq 1$ separately). Scaling $t = α u$ therefore gives $α t^{ν} / (t + α) \leq α^{ν}$ for $0 < ν \leq 1$ . Applying the isometric calculus and its real restriction proves the first filter bound.

5.1A1F1F2F4F7step 3.1step 4.2algebra∎

Put $Q = α T_{α} S^{ν}$ . By [F4], $∥ A Q ∥^{2} = ∥ Q^{*} S Q ∥$ . Its scalar function is $[α t^{ν + 1 / 2} / (t + α)]^{2}$ . Since $ν + 1 / 2 \leq 1$ , the same scalar estimate as step 4.2 bounds this by $α^{2 ν + 1}$ , proving the second bound. The noise bound is [F7]. Finally $(A A^{*} + α I) A = A (S + α I)$ yields $A T_{α} A^{*} = (A A^{*} + α I)^{- 1} A A^{*}$ . Apply the calculus to $A A^{*}$ on $Y$ , or directly use zero if $Y = {0}$ : its function $t / (t + α)$ is at most one. This proves the last bound in either field.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Anchored iteratively regularized Gauss-Newton with finite discrepancy stopping

Definition

Assume Countable Choice. Let $X, Y$ be Hilbert spaces over the same field $F \in {R, C}$ , let $U \subseteq X$ be open, and let $F : U \to Y$ be continuously Fréchet differentiable over $F$ : for each $x \in U$ , $F^{'} (x)$ is bounded $F$ -linear, the map $x \mapsto F^{'} (x)$ is operator-norm continuous, and $\lim_{\begin{array}{c} h \to 0, h \neq 0 \\ x + h \in U \end{array}} \frac{∥ F (x + h) - F (x) - F^{'} (x) h ∥}{∥ h ∥} = 0,$ where $h$ ranges over increments in $F$ . In the complex case the derivative is complex-linear and the limit uses complex increments. Inputs are anchor and initial point $x_{0} \in U$ , datum $y_{δ}$ , noise bound $δ \geq 0$ , discrepancy factor $τ > 1$ , finite update cap $N \in N_{0}$ , $α_{0} > 0$ and $q \in (0, 1)$ . For $k = 0, \dots, N$ , first check $x_{k} \in U$ ; otherwise return $(x_{k}, k, domain-failure)$ . The output of every return is a tuple $(x_{k}, k, status)$ . Use an exact-call interface with these outcomes: an evaluation call returns either $ok (v_{k})$ with the exact value $v_{k} = F (x_{k})$ or $failure$ ; a normal-solve call returns either $ok (s_{k})$ with the exact solution of the displayed equation or $unverified$ . The interface never returns an incorrect value. If the evaluation call returns $failure$ , return $(x_{k}, k, evaluation-failure)$ . If the evaluation returns $ok (v_{k})$ and $∥ v_{k} - y_{δ} ∥ \leq τ δ$ , return $(x_{k}, k, discrepancy)$ . If $k = N$ , return $(x_{k}, k, budget-exhausted)$ . Otherwise set $A_{k} = F^{'} (x_{k})$ , $α_{k} = α_{0} q^{k}$ , and call the normal solver on $(A_{k}^{*} A_{k} + α_{k} I) s_{k} = A_{k}^{*} (y_{δ} - v_{k}) + α_{k} (x_{0} - x_{k}),$ whose exact solution exists uniquely by The shifted Hilbert-space normal operator is invertible with inverse norm at most $1 / λ$ . If the solve call returns $unverified$ , return $(x_{k}, k, solve-unverified)$ ; otherwise set $x_{k + 1} = x_{k} + s_{k}$ . The mathematical evaluation and solve succeed because $F$ is defined on $U$ and the shifted normal equation has a unique solution; the failure outcomes record only a finite implementation's inability to return the exact value or certify the exact solve. No success or convergence claim is attached to these failure statuses.

The mathematical extended recurrence means the same exact updates with the discrepancy and finite-cap tests suppressed, for as long as the states lie in $U$ . It is used only for comparison in proofs. A finite actual run follows its prefix and stops at its first test crossing. This anchored update is distinct from the retained unanchored Levenberg-Marquardt step; its extra term is $α_{k} (x_{0} - x_{k})$ .

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Anchored IRGNM error identity and fixed-reference residual inequality

Statement

Assume AC. Let $X, Y$ be real or complex Hilbert spaces over the same scalar field, let $U \subseteq X$ be open, and let $B = \overline{B} (x^{†}, ρ) \subseteq U$ be convex. Let $F : U \to Y$ continuously Fréchet differentiable over that field (bounded complex-linear derivatives in the complex case). Set $A = F^{'} (x^{†})$ , $S = A^{*} A$ and $y = F (x^{†})$ . Suppose for each $x \in B$ that $F^{'} (x) = (I + R_{x}) A$ for a bounded linear $R_{x} : Y \to Y$ with $∥ R_{x} ∥ \leq κ < 1$ , taking $R_{x^{†}} = 0$ . Let $x \in B$ , $e = x - x^{†}$ , $e_{0} = x_{0} - x^{†} = S^{ν} w$ , $0 < ν \leq 1 / 2$ , $∥ w ∥ \leq W$ , and $∥ y_{δ} - y ∥ \leq δ$ . For a single exact anchored update with shift $α > 0$ , define $e_{+} = x_{+} - x^{†}$ , $v = ∥ A e ∥$ , $v_{+} = ∥ A e_{+} ∥$ , $R = R_{x}$ , $H = R + R^{*} + R^{*} R$ , $θ = 2 κ + κ^{2}$ , $d_{0} = 2 κ (1 + κ)$ , and $c_{0} = 1 + κ$ . Then $t = F^{'} (x) e - (F (x) - y), z = (I + R)^{*} (y_{δ} - y + t) - H A e_{+},$ $(S + α I) e_{+} = α e_{0} + A^{*} z, ∥ z ∥ \leq c_{0} δ + d_{0} v + θ v_{+} .$ Consequently $(1 - θ) v_{+} \leq W α^{ν + 1 / 2} + d_{0} v + c_{0} δ, ∥ e_{+} ∥ \leq W α^{ν} + \frac{c_{0} δ + d_{0} v + θ v_{+}}{2 \sqrt{α}} .$ Also for $x, u \in B$ , $(1 - κ) ∥ A (x - u) ∥ \leq ∥ F (x) - F (u) ∥ \leq (1 + κ) ∥ A (x - u) ∥,$ and the tangential-cone condition holds with constant $2 κ / (1 - κ)$ . The conclusions require only the current state and segment in $B$ , not the next state in $B$ .

Facts & Assumptions

Given: The objects, source condition, current admissible state and exact anchored step in the Statement.

[A1]

The Axiom of Choice: AC supplies the field-complete functional calculus and the inherited Countable Choice for adjoints and the segment integral.

[F1]

Anchored iteratively regularized Gauss-Newton with finite discrepancy stopping specifies the anchored correction equation. Here a single exact anchored update means $x_{+} = x + s$ , where $(F^{'} (x)^{*} F^{'} (x) + α I) s = F^{'} (x)^{*} (y_{δ} - F (x)) + α (x_{0} - x)$ . This is a standalone step at the specified $x \in B$ with anchor $x_{0} \in X$ , not a run initialized at $x_{0}$ .

[F2]

Real and complex Hilbert source powers and fixed-reference Tikhonov filter bounds: source bias, source residual, normal-noise and pushed residual bounds hold in both fields.

[F3]

Taylor expansion with integral remainder for Banach-valued curves, Linearity of the Bochner integral and Bochner integral norm inequality: a continuously differentiable segment curve has increment the integral of its derivative, and the integral norm is bounded by the integral of the norm.

[F4]

Hilbert-adjoint identities: adjoints reverse products, preserve the norm and satisfy the conjugate-linear sum identities.

Proof

1.1A1F3givenalgebra

For $h = x - u$ , let $γ (s) = F (u + s h)$ . The segment lies in $B$ . If $h \neq 0$ and $0 < s < 1$ , then for real $r \to 0$ with $s + r \in [0, 1]$ , same-field Fréchet differentiability gives $∥ \frac{F (u + (s + r) h) - F (u + s h)}{r} - F^{'} (u + s h) h ∥ = \frac{∥ F (u + (s + r) h) - F (u + s h) - F^{'} (u + s h) (r h) ∥}{∣ r ∣} ⟶ 0.$ Thus $γ^{'} (s) = F^{'} (u + s h) h$ . For $h = 0$ the curve is constant. In either case differentiability makes $γ$ continuous by the Fréchet remainder definition, and this derivative is continuous on the segment with endpoint extensions because the assumed continuous Fréchet differentiability makes $s \mapsto F^{'} (u + s h)$ continuous in operator norm, including at $s = 0, 1$ , and evaluation at the fixed vector $h$ is continuous. Applying the Banach-valued fundamental theorem [F3] and subtracting the constant integral of $A h$ gives $F (x) - F (u) - A h = \int_{0}^{1} (F^{'} (u + s h) - A) h d s .$ Linearity of $R_{u + s h}$ and its norm bound make the integrand norm at most $κ ∥ A h ∥$ , so the integral has that bound. The triangle and reverse triangle inequalities give the two-sided estimate. Subtracting $(F^{'} (u) - A) h$ bounds the linearization remainder by $2 κ ∥ A h ∥$ , proving the cone constant. This integrates the continuous vector $F^{'} (u + s h) h$ , not a possibly unmeasurable choice of the operators $R_{u + s h}$ . Taking $u = x^{†}$ also gives $∥ t ∥ \leq 2 κ v$ .

1.2A1F1F2F4givenalgebra

Let $A_{x} = F^{'} (x)$ . Since $A_{x}$ is bounded and $α > 0$ , [F2] applied to $A_{x}$ supplies the inverse defining the unique correction in [F1] for every anchor $x_{0} \in X$ ; no evaluation at $x_{0}$ is required. Adding $(A_{x}^{*} A_{x} + α I) e$ to that correction equation gives $(A_{x}^{*} A_{x} + α I) e_{+} = α e_{0} + A_{x}^{*} (y_{δ} - y + t)$ . By factorization and [F4], $A_{x}^{*} A_{x} = S + A^{*} H A$ and $A_{x}^{*} = A^{*} (I + R)^{*}$ . Moving $A^{*} H A e_{+}$ to the right gives the fixed-reference identity with $z$ in the Statement. The inverse used here exists independently of where $x_{+}$ lies.

2.1F4step 1.1step 1.2algebra

By [F4], $∥ H ∥ \leq 2 κ + κ^{2} = θ$ and $∥ (I + R)^{*} ∥ \leq 1 + κ$ . Combining these bounds with $∥ t ∥ \leq 2 κ v$ proves $∥ z ∥ \leq c_{0} δ + d_{0} v + θ v_{+}$ .

3.1A1F2step 1.2step 2.1algebra∎

Apply $A (S + α I)^{- 1}$ to step 1.2 and use [F2] with $e_{0} = S^{ν} w$ . Then $v_{+} \leq W α^{ν + 1 / 2} + ∥ z ∥$ ; moving $θ v_{+}$ to the left gives the residual inequality. Applying $(S + α I)^{- 1}$ without $A$ instead gives $∥ e_{+} ∥ \leq W α^{ν} + ∥ z ∥ / (2 \sqrt{α})$ , proving the error bound. This controls the fixed source term through its spectral filter, not through a crude $α^{- 1} ∥ e_{0} ∥$ estimate.

TheoremStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Anchored IRGNM local source-condition convergence with ordinary discrepancy stopping

Statement

Assume AC. Let $X, Y$ be Hilbert spaces over the same field $F \in {R, C}$ and let $F : U \to Y$ be continuously Fréchet differentiable over $F$ on open $U \subseteq X$ . In the complex case, each $F^{'} (x)$ is a bounded complex-linear operator and the Fréchet remainder is measured over complex increments. Let $B = \overline{B} (x^{†}, ρ) \subseteq U$ , with $ρ > 0$ , and $y = F (x^{†})$ . Set $A = F^{'} (x^{†})$ , $S = A^{*} A$ . Suppose $F^{'}$ is Lipschitz on $B$ and, for every $x \in B$ , $F^{'} (x) = (I + R_{x}) A, ∥ R_{x} ∥ \leq κ < 1 / 5, κ \geq 0,$ with bounded linear $R_{x} : Y \to Y$ and $R_{x^{†}} = 0$ . This is an explicit additional weak-nonlinearity hypothesis; it is not inferred from the original tangential-cone/Lipschitz assumptions alone.

Suppose $e_{0} = x_{0} - x^{†} = S^{ν} w$ , $0 < ν \leq 1 / 2$ , $∥ w ∥ \leq W$ , where $W > 0$ ; changing the sign of $w$ gives the original opposite-sign source convention. Let $α_{0} > 0$ , $α_{0} \geq ∥ A ∥^{2}$ , $0 < q < 1$ , and $α_{k} = α_{0} q^{k}$ . Define $β = ν + 1 / 2, θ = 2 κ + κ^{2}, d_{0} = 2 κ (1 + κ), c_{0} = 1 + κ,$ $a = (1 - θ)^{- 1}, b = d_{0} / (1 - θ), c = c_{0} / (1 - θ), b < q^{β},$ $D = \max {1, a / (q^{β} - b)}, E = c / (1 - b), C_{e} = 1 + D (d_{0} + θ q^{β}) / 2, N_{e} = [c_{0} + (d_{0} + θ) E] / 2.$ Require the source-smallness and discrepancy conditions $(C_{e} + N_{e}) W α_{0}^{ν} < ρ, τ > (1 + κ) (D + E) + 1.$ For each $0 < δ < W α_{0}^{β}$ and datum $∥ y_{δ} - y ∥ \leq δ$ , use the anchored recurrence of Anchored iteratively regularized Gauss-Newton with finite discrepancy stopping. Its theoretical exact extension, ignoring the stopping tests, is well-defined and lies in $B$ through $K_{δ} = \min {k \geq 0 : W α_{k}^{β} \leq δ} .$ Its first ordinary discrepancy crossing $k_{δ} = \min {k : ∥ F (x_{k}^{δ}) - y_{δ} ∥ \leq τ δ}$ is finite and $k_{δ} \leq K_{δ}$ . For the theoretical extension through this comparison index, $∥ A (x_{k}^{δ} - x^{†}) ∥ \leq D W α_{k}^{β} + E δ, ∥ x_{k + 1}^{δ} - x^{†} ∥ \leq C_{e} W α_{k}^{ν} + N_{e} δ / \sqrt{α_{k}} (0 \leq k < K_{δ}) .$ As $δ ↓ 0$ , $x_{k_{δ}}^{δ} \to x^{†}$ in norm for every admissible noise sequence. For exact data the extended recurrence converges to $x^{†}$ as well. A finite actual algorithm returns this first-crossing iterate only if its cap reaches $k_{δ}$ and exact calls succeed; shorter caps and uncertified calls retain their explicit failure statuses. No nonlinear rate is asserted, and no injectivity, closed range or finite-dimensional restriction on $A$ is imposed. The retained unanchored LM algorithm is not claimed to satisfy this anchored theorem.

Facts & Assumptions

Given: The field, spaces, ball, nonlinear map, source, constants and noise in the Statement. The extension suppresses algorithmic stopping tests only for proof comparison.

[A1]

The Axiom of Choice: AC supplies the source-power calculus and inherited Countable Choice used by Hilbert adjoints and integrals.

[F1]

Anchored iteratively regularized Gauss-Newton with finite discrepancy stopping: the anchored normal equation, initial state and first-crossing/budget semantics.

[F2]

Anchored IRGNM error identity and fixed-reference residual inequality: factorization gives the two-sided reference residual bound, the fixed-reference identity and the one-step residual/error inequalities without assuming the next iterate lies in the ball.

[F3]

Real and complex Hilbert source powers and fixed-reference Tikhonov filter bounds: the stated source powers and filter bounds hold over either field; $S^{ν} w ⊥ \ker A$ .

[F4]

The shifted Hilbert-space normal operator is invertible with inverse norm at most $1 / λ$ : each positive-shift normal equation has a unique inverse of norm at most $1 / α$ .

[F5]

Hilbert-adjoint identities: operator products and adjoints are norm-continuous by the adjoint/product norm laws.

[F6]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : powers of a scalar of modulus less than one tend to zero.

Proof

1.1A1F1F3givenalgebra

The hypotheses give $θ < 1$ , $0 \leq b < q^{β} < 1$ , so all constants are finite and positive except possibly $b, d_{0}, θ$ . By [F3], $∥ e_{0} ∥ \leq W ∥ A ∥^{2 ν} \leq W α_{0}^{ν} < ρ$ and $v_{0} : = ∥ A e_{0} ∥ \leq W α_{0}^{β}$ . If $X = {0}$ , or $A = 0$ , the source condition gives $e_{0} = 0$ ; more generally whenever $e_{0} = 0$ the actual noisy algorithm stops at index zero since its residual is at most $δ$ . Its conclusion is exact. The extended recurrence is still treated by the estimates below, including in these cases, rather than assumed to stop.

1.2A1F1F2F4givenalgebra

Suppose a theoretical current iterate lies in $B$ and $v_{k} \leq D W α_{k}^{β} + E δ$ . The inverse [F4] defines its next exact step in $X$ before any next-domain assertion. The residual inequality [F2] yields $v_{k + 1} \leq a W α_{k}^{β} + b v_{k} + c δ \leq (a + b D) W α_{k}^{β} + (b E + c) δ \leq D W α_{k + 1}^{β} + E δ$ , since $D (q^{β} - b) \geq a$ and $E (1 - b) = c$ . Here $v_{k + 1} = ∥ A (x_{k + 1} - x^{†}) ∥$ is defined even before proving the next state lies in $B$ .

2.1A1F2step 1.2algebra

Under step 1.2's conditions, substitute its bounds for $v_{k}, v_{k + 1}$ into [F2]'s error inequality. As $β - 1 / 2 = ν$ , this gives $∥ e_{k + 1} ∥ \leq [1 + D (d_{0} + θ q^{β}) / 2] W α_{k}^{ν} + [c_{0} + (d_{0} + θ) E] δ / (2 \sqrt{α_{k}}) = C_{e} W α_{k}^{ν} + N_{e} δ / \sqrt{α_{k}}$ . Thus the source term has its actual filtered power, not an inverse-shift estimate of the initial norm.

3.1A1F3F4F6step 1.1step 1.2step 2.1giveninductionalgebra

By [F6], $K_{δ}$ exists and is positive. For every $j < K_{δ}$ , $δ < W α_{j}^{β}$ , so step 2.1 gives $∥ e_{j + 1} ∥ \leq (C_{e} + N_{e}) W α_{j}^{ν} \leq (C_{e} + N_{e}) W α_{0}^{ν} < ρ$ . Start at step 1.1 and induct: at stage $j$ the current state is already in $B$ , so [F4] and step 1.2 define the next state and its residual bound, and the displayed estimate places it in $B$ . This proves the extension, ball preservation and both stated estimates through $K_{δ}$ without any future-ball assumption. For exact data the same induction runs for every $j$ with noise zero, and the error estimate with [F6] gives convergence of the exact extension to $x^{†}$ .

4.1F1F2step 3.1givenalgebra

The upper residual comparison in [F2] and step 3.1 give $∥ F (x_{K_{δ}}^{δ}) - y_{δ} ∥ \leq (1 + κ) v_{K_{δ}} + δ \leq [(1 + κ) (D + E) + 1] δ < τ δ$ . Thus the first crossing exists by $K_{δ}$ . Until its first crossing the actual finite algorithm uses exactly the extended recurrence, so with a sufficient cap and successful exact calls its return equals this crossing. No property of an arbitrary budget-final iterate follows.

5.1F6step 3.1step 4.1givenalgebra

For $1 \leq k_{δ} \leq K_{δ}$ , minimality of $K_{δ}$ gives $W α_{K_{δ} - 1}^{β} > δ$ and hence $δ / \sqrt{α_{k_{δ} - 1}} \leq δ / \sqrt{α_{K_{δ} - 1}} < W^{1 / (2 β)} δ^{1 - 1 / (2 β)} \to 0$ , since $β > 1 / 2$ . Along any sequence with $k_{δ} \to \infty$ , also $α_{k_{δ} - 1}^{ν} \to 0$ by [F6]. The error bound in step 3.1 therefore proves stopped convergence along such sequences.

5.2A1F1F2F4F5step 3.1step 4.1giveninductionalgebra

For each fixed index $j$ , the extended iterates depend continuously on the datum near $y$ . Indeed, the exact states for data $y$ lie strictly inside $B$ by step 3.1. Inductively $F, F^{'}$ and the adjoint/product laws [F5] are continuous there; for fixed positive $α_{j}$ , the inverse identity $B_{1}^{- 1} - B_{2}^{- 1} = B_{1}^{- 1} (B_{2} - B_{1}) B_{2}^{- 1}$ and [F4]'s $1 / α_{j}$ bounds prove continuity of each normal inverse. Thus $x_{j}^{δ} \to x_{j}^{0}$ . If a stopping subsequence has fixed index $j$ , its discrepancy bound implies $F (x_{j}^{0}) = y$ . The lower residual comparison in [F2] then gives $A (x_{j}^{0} - x^{†}) = 0$ .

6.1A1F2F3step 5.2giveninductionalgebra

By [F3], $e_{0} ⊥ \ker A$ . Testing the anchored error equation $(A_{k}^{*} A_{k} + α_{k} I) e_{k + 1} = α_{k} e_{0} + A_{k}^{*} (y_{δ} - y + t_{k})$ against $h \in \ker A$ gives $⟨ e_{k + 1}, h ⟩ = ⟨ e_{0}, h ⟩ = 0$ , because factorization gives $A_{k} h = 0$ . Hence every exact error lies in $(\ker A)^{⊥}$ . The exact error in step 5.2 also lies in $\ker A$ , so it is zero. This includes $j = 0$ and proves convergence along every bounded-index stopping subsequence by taking a constant-index further subsequence.

7.1step 5.1step 6.1givenalgebra∎

If stopped convergence failed for some admissible noise sequence, take a sequence of errors bounded away from zero. Its stopping indices have either an unbounded subsequence, along which a further strictly increasing subsequence contradicts step 5.1, or a bounded subsequence, with a constant-index further subsequence contradicting step 6.1. Thus stopped convergence holds for every admissible noise family. This proof never assumes $k_{δ} \to \infty$ in all cases.

Remarks

The original target coupled the unanchored update to an unmatched source-condition argument and had no proof. This theorem instead uses the separately defined anchored method and the explicit additional factorization/smallness/discrepancy conditions above; it does not assert the original unmatched contract proved or false. The factorization implies the original tangential-cone condition with $2 κ / (1 - κ) < 1 / 2$ by [F2], while no closed-range, finite-dimensional or compactness hypothesis was introduced. The original unanchored algorithm, one-step identity and scalar example retain their own valid claims.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Landweber converges for exact data and balances source bias with noise

Statement

Assume Countable Choice. Let $A : X \to Y$ be a nonzero compact operator between real or complex Hilbert spaces, set $T = A^{*} A$ , choose $0 < ω < 2 / ∥ A ∥^{2}$ , and let $y = A x^{†}$ with $x^{†} \in (\ker A)^{⊥}$ . Let $x_{k}$ be the exact-data Landweber iterates in the infinite recurrence-defined path of Landweber iteration with discrepancy and budget statuses for datum $y$ ; this path depends on $A, ω, y$ and not on a finite cap or stopping test. Put $r_{k} (t) = (1 - ω t)^{k}$ . Then $∥ x_{k} - x^{†} ∥$ is nonincreasing and $x_{k} \to x^{†}$ in norm. For every $s > 0$ , if $x^{†} = T^{s} w$ with $w \in X$ , then for $k \geq 1$ , $∥ x_{k} - x^{†} ∥ \leq C_{s, A, ω} ∥ w ∥ k^{- s} .$ The scalar filter also satisfies $\sup_{t \in Σ} t^{s} ∣ r_{k} (t) ∣ \leq C_{s, A, ω} k^{- s},$ where $Σ$ is the set of nonzero eigenvalues of $T$ . For noisy data $y_{δ}$ with $∥ y_{δ} - y ∥ \leq δ$ , let $x_{k}^{δ}$ be the infinite recurrence-defined path for datum $y_{δ}$ . It satisfies $∥ x_{k}^{δ} - x_{k} ∥ \leq \sqrt{2 ω k} δ .$ Consequently, under the source condition $x^{†} = T^{ν} w$ , $0 < ν \leq 1$ , the total error obeys $∥ x_{k}^{δ} - x^{†} ∥ \leq C_{ν, A, ω} ∥ w ∥ k^{- ν} + \sqrt{2 ω k} δ .$

Facts & Assumptions

Given: Countable Choice; the stated $A, ω, y, x^{†}$ ; and $T = A^{*} A$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is assumed by the Hilbert-adjoint and compact spectral theorem suppliers used in this proof.

[F1]

Landweber iterates and residuals are spectral-filter iterates: For the infinite mathematical path, $x_{k} = g_{k} (T) A^{*} y_{δ}$ and, for exact data, $x^{†} - x_{k} = r_{k} (T) x^{†}$ .

[F2]

Compact spectral filters, source conditions, and qualification: $T^{ν}$ and the filters are defined by their scalar values on the nonzero eigenvalues of the compact positive operator $T$ .

[F3]

A compact Hilbert-space Gram operator is positive and has the forward kernel: $T$ is compact positive self-adjoint and $\ker T = \ker A$ .

[F4]

Hilbert-adjoint identities: $∥ A^{*} A ∥ = ∥ A ∥^{2}$ and $∥ Q ∥^{2} = ∥ Q Q^{*} ∥$ for bounded Hilbert-space operators.

[F5]

Orthogonality and the orthogonal complement: $x^{†} \in (\ker A)^{⊥}$ means it has no component in the zero eigenspace of $T$ .

[F6]

Spectral theorem for compact self adjoint operators: The nonzero eigenspaces of compact self-adjoint $T$ are mutually orthogonal, at most countably many, and together with $\ker T$ have dense span in $X$ .

[F7]

Bounded multipliers on compact self-adjoint eigenspaces define bounded operators: A bounded scalar multiplier on these eigenspaces defines an operator whose norm is at most the supremum of the multiplier's absolute value.

Proof

Given: The hypotheses and facts above. Write $M = ∥ A ∥^{2}$ .

1.1A1F1F3F4F5F6givenchoose

For every nonzero eigenvalue $t$ of $T$ , [F3]–[F4] give $0 < t \leq M$ , so $0 < ω t < 2$ and $∣ 1 - ω t ∣ < 1$ . Therefore $∣ r_{k} (t) ∣$ decreases with $k$ and tends to $0$ . Since $x^{†} ⊥ \ker T$ by [F3] and [F5], [F6] expands it using only positive-eigenvalue components. By [F1], each component of $x_{k} - x^{†}$ is multiplied by $- r_{k} (t)$ ; its magnitude decreases to zero and is bounded by the corresponding component of $x^{†}$ . Given $ϵ > 0$ , choose a finite set of eigenvalues whose omitted squared components of $x^{†}$ sum to less than $ϵ$ ; on the chosen finite set every component tends to zero. The squared error sum therefore tends to at most $ϵ$ , and arbitrariness of $ϵ$ proves norm convergence. The componentwise decrease also proves monotonicity of the norm.

1.2A1F2F3F4givenalgebra

Choose an integer $m > s$ . For $v \geq 0$ and an integer $n \geq 0$ , $(1 + v)^{n} \geq 1 + n v$ : induction proves this, since multiplying the bound at $n$ by $1 + v$ gives $1 + (n + 1) v + n v^{2} \geq 1 + (n + 1) v$ . For $k \geq 2 m$ , let $n = ⌊ k / m ⌋$ , so $m n \leq k$ and $n \geq k / (2 m)$ . If $0 < t \leq \min {M, ω^{- 1}}$ , put $u = ω t \in (0, 1]$ . At $u = 1$ the filter is zero. If $0 < u \leq 1 / k$ , then $u^{s} (1 - u)^{k} \leq k^{- s}$ . If $k \geq 2 m$ and $1 / k < u < 1$ , the identity $(1 - u) (1 + u) = 1 - u^{2} \leq 1$ gives $(1 - u)^{- k} \geq (1 + u)^{k} \geq (1 + u)^{m n} = ((1 + u)^{n})^{m} \geq (n u)^{m}$ . Consequently $u^{s} (1 - u)^{k} \leq n^{- m} u^{s - m} \leq n^{- m} k^{m - s} \leq (2 m)^{m} k^{- s} .$ For $k < 2 m$ the same product is at most $1 \leq (2 m)^{s} k^{- s}$ . Thus on this range $t^{s} ∣ r_{k} (t) ∣ = ω^{- s} u^{s} (1 - u)^{k} \leq C_{s, ω} k^{- s}$ . If $ω^{- 1} < t \leq M$ , a range that exists only when $ω M > 1$ , then $∣ 1 - ω t ∣ = ω t - 1 \leq ω M - 1 = : q \in (0, 1)$ . Put $a = q^{- 1} - 1 > 0$ . For $k \geq 2 m$ and the same $n$ , $q^{- k} = (1 + a)^{k} \geq (1 + a)^{m n} = ((1 + a)^{n})^{m} \geq (n a)^{m},$ so $k^{s} q^{k} \leq (2 m)^{m} a^{- m} k^{s - m} \leq (2 m)^{m} a^{- m}$ . For $k < 2 m$ , $k^{s} q^{k} \leq (2 m)^{s}$ . Hence $\sup_{k \geq 1} k^{s} q^{k} < \infty$ and $t^{s} ∣ r_{k} (t) ∣ \leq M^{s} q^{k} \leq C_{s, M, ω} k^{- s}$ . Combining the two ranges proves $\sup_{t \in σ (T) ∖ {0}} t^{s} ∣ r_{k} (t) ∣ \leq C_{s, A, ω} k^{- s}$ .

1.3A1F1F4F7givenalgebra

For $k \geq 1$ , the scalar geometric identity gives $g_{k} (t) = [1 - (1 - ω t)^{k}] / t$ for $t > 0$ . Since $∣ 1 - ω t ∣ \leq 1$ , both the bound by $2$ and the finite-sum bound by $k ω t$ hold for its numerator. Hence $\sqrt{t} ∣ g_{k} (t) ∣ \leq \min {2 / \sqrt{t}, ω k \sqrt{t}} \leq \sqrt{2 ω k} .$ The last inequality follows by splitting at $t = 2 / (ω k)$ . For $Q_{k} = g_{k} (T) A^{*}$ , adjoint multiplication gives $Q_{k} Q_{k}^{*} = g_{k} (T) T g_{k} (T)^{*}$ , the compact spectral multiplier with scalar values $t ∣ g_{k} (t) ∣^{2}$ and value zero on $\ker T$ . [F7] bounds its norm by the supremum of these values; [F4] and $∥ Q_{k} ∥^{2} = ∥ Q_{k} Q_{k}^{*} ∥$ then give $∥ Q_{k} ∥ \leq \sqrt{2 ω k}$ . Applying [F1] to $y_{δ} - y$ gives $∥ x_{k}^{δ} - x_{k} ∥ = ∥ Q_{k} (y_{δ} - y) ∥ \leq \sqrt{2 ω k} δ$ .

2.1A1F1F2F7step 1.2algebra

Under $x^{†} = T^{s} w$ , [F1] gives $x_{k} - x^{†} = - r_{k} (T) T^{s} w$ . On every eigenspace the product multiplier is $t^{s} r_{k} (t)$ , bounded by [step 1.2]; [F7] therefore yields $∥ x_{k} - x^{†} ∥ \leq \sup_{t > 0} t^{s} ∣ r_{k} (t) ∣ ∥ w ∥$ . Substituting the bound in [step 1.2] proves the source-bias estimate.

3.1step 2.1step 1.3algebra∎

The triangle inequality gives $∥ x_{k}^{δ} - x^{†} ∥ \leq ∥ x_{k}^{δ} - x_{k} ∥ + ∥ x_{k} - x^{†} ∥$ ; substituting the bounds from [step 2.1] and [step 1.3] proves the final estimate.

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck pendingjudge pass (gpt-6-luna)Open item page →

Landweber discrepancy stopping converges under a source condition

Statement

Assume Countable Choice and the hypotheses of Landweber converges for exact data and balances source bias with noise. Let $x^{†} = T^{ν} w$ with $0 < ν \leq 1$ and $R = ∥ w ∥ \geq 0$ . Fix $τ > 1$ and $δ > 0$ with $∥ y_{δ} - A x^{†} ∥ \leq δ$ . Let $k_{δ}$ be the first index on the associated infinite mathematical path satisfying $∥ A x_{k_{δ}}^{δ} - y_{δ} ∥ \leq τ δ$ , where $x_{k}^{δ}$ is the corresponding noisy-data path. If a finite budget is used, assume it is at least the upper bound $K_{δ}$ constructed in the proof when $R > 0$ . If $R = 0$ , the initial iterate is the first crossing and any finite budget suffices. For all sufficiently small $δ$ , $∥ x_{k_{δ}}^{δ} - x^{†} ∥ \leq C_{ν, A, ω, τ} R^{1 / (2 ν + 1)} δ^{2 ν / (2 ν + 1)} .$ The conclusion is conditional on an actual discrepancy crossing; a budget exhaustion status is inconclusive.

Facts & Assumptions

Given: The stated compact operator, Landweber parameter, source condition, noise bound, $τ > 1$ , and the first discrepancy index.

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is assumed by the compact spectral and Hilbert-adjoint suppliers used in the proof.

[F1]

Landweber converges for exact data and balances source bias with noise: For every $s > 0$ , $\sup_{t \in Σ} t^{s} ∣ r_{k} (t) ∣ \leq C_{s, A, ω} k^{- s}$ ; the noise amplification is at most $\sqrt{2 ω k} δ$ .

[F2]

Landweber iterates and residuals are spectral-filter iterates: $y_{δ} - A x_{k}^{δ} = r_{k} (A A^{*}) y_{δ}$ and $x^{†} - x_{k} = r_{k} (T) x^{†}$ .

[F3]

Compact spectral filters, source conditions, and qualification: $T^{ν}$ and $r_{k} (T)$ act by their scalar multipliers on each nonzero eigenspace.

[F4]

Hilbert-adjoint identities: $∥ A v ∥^{2} = ⟨ A^{*} A v, v ⟩$ , $∥ A^{*} ∥ = ∥ A ∥$ , and $∥ Q ∥^{2} = ∥ Q Q^{*} ∥$ for bounded Hilbert-space operators.

[F5]

Bounded multipliers on compact self-adjoint eigenspaces define bounded operators: A compact spectral multiplier has operator norm at most the supremum of the absolute values of its scalar multipliers.

[F6]

Spectral theorem for compact self adjoint operators: The eigenspaces of compact self-adjoint $T$ are mutually orthogonal and, together with $\ker T$ , have dense span.

[F7]

A compact Hilbert-space Gram operator is positive and has the forward kernel: Both $A^{*} A$ and $A A^{*}$ are compact, positive, and self-adjoint; $\ker (A^{*} A) = \ker A$ .

Proof

Given: The hypotheses above, with $R \geq 0$ .

If $R = 0$ , then $w = 0$ , so $x^{†} = 0$ and $y = A x^{†} = 0$ . The initial iterate $x_{0}^{δ} = 0$ has residual $∥ A x_{0}^{δ} - y_{δ} ∥ = ∥ y_{δ} ∥ \leq δ \leq τ δ$ . Therefore $k_{δ} = 0$ and the stopped error is zero, which is the stated estimate with $R = 0$ since $0^{a} = 0$ for every $a > 0$ . For the rest of the proof assume $R > 0$ . [given, algebra]

1.1A1F1F2F3F4F5F6F7givenconstructalgebra

Put $p = ν + \frac{1}{2}$ . By [F2], $x_{k} - x^{†} = - r_{k} (T) T^{ν} w$ . The compact spectral expansion [F6], the power convention [F3], and $∥ A z ∥^{2} = ⟨ A^{*} A z, z ⟩$ from [F4] give $∥ A x_{k} - y ∥ = ∥ T^{p} r_{k} (T) w ∥$ . The scalar filter bound [F1] therefore gives $∥ A x_{k} - y ∥ \leq C_{p, A, ω} R k^{- p}$ . Choose $K_{δ} = \max ⁣ {1, ⌈ {(\frac{C_{p, A, ω} R}{(τ - 1) δ})}^{1 / p} ⌉} .$ Then $∥ A x_{K_{δ}} - y ∥ \leq (τ - 1) δ$ . By [F2], the noisy residual differs from the exact-data residual by $r_{K_{δ}} (A A^{*}) (y_{δ} - y)$ . [F7] makes $A A^{*}$ compact positive self-adjoint, and [F4] gives $∥ A A^{*} ∥ = ∥ A ∥^{2}$ . Every eigenvalue $t$ of $A A^{*}$ therefore satisfies $0 \leq t \leq ∥ A ∥^{2}$ , so $∣ 1 - ω t ∣ \leq 1$ by the step-size hypothesis. [F5] bounds the noise residual by $δ$ . Hence $∥ A x_{K_{δ}}^{δ} - y_{δ} ∥ \leq τ δ$ , so the first crossing exists and $k_{δ} \leq K_{δ}$ (provided the finite budget reaches $K_{δ}$ ).

1.2A1F2F5givenalgebra

At the crossing, [F2] and the same multiplier estimate [F5] give $∥ A x_{k_{δ}} - y ∥ \leq ∥ A x_{k_{δ}}^{δ} - y_{δ} ∥ + δ \leq (τ + 1) δ$ .

2.1A1F2F3F4F6step 1.2algebra

Let $v = r_{k_{δ}} (T) w$ and $θ = 2 ν / (2 ν + 1)$ . For a finite set $E \subseteq Σ$ , put $a_{t} = t^{2 ν + 1} ∥ P_{t} v ∥^{2}$ and $b_{t} = ∥ P_{t} v ∥^{2}$ . Then $t^{2 ν} ∥ P_{t} v ∥^{2} = a_{t}^{θ} b_{t}^{1 - θ}$ . If either $\sum_{E} a_{t}$ or $\sum_{E} b_{t}$ is zero, every summand on the left is zero. Otherwise normalize ${\tilde{a}}_{t} = a_{t} / (\sum_{E} a_{t})$ and ${\tilde{b}}_{t} = b_{t} / (\sum_{E} b_{t})$ . The scalar inequality $u^{θ} v^{1 - θ} \leq θ u + (1 - θ) v$ follows by minimizing $f (s) = θ s + (1 - θ) - s^{θ}$ : $f^{'} (s) = θ (1 - s^{θ - 1})$ is negative for $0 < s < 1$ and positive for $s > 1$ , so $f (s) \geq f (1) = 0$ . Thus the sum of the normalized products is at most $1$ , and $∥ T^{ν} v ∥ \leq ∥ T^{ν + 1 / 2} v ∥^{2 ν / (2 ν + 1)} ∥ v ∥^{1 / (2 ν + 1)} .$ Since [F6] gives the norm-convergent spectral expansion, increasing finite sets $E$ to $Σ$ passes this inequality to the full sums. Also $∥ v ∥ \leq R$ because $∣ r_{k_{δ}} (t) ∣ \leq 1$ . Finally [F2], [F3], [F4], [F6], and [step 1.2] give $x^{†} - x_{k_{δ}} = T^{ν} v$ . For every $z \in X$ , $∥ A z ∥^{2} = ⟨ T z, z ⟩ = \sum_{t \in Σ} t ∥ P_{t} z ∥^{2} = ∥ T^{1 / 2} z ∥^{2}$ , so $∥ T^{ν + 1 / 2} v ∥ = ∥ A T^{ν} v ∥ = ∥ A x_{k_{δ}} - y ∥ \leq (τ + 1) δ$ . Hence $∥ x_{k_{δ}} - x^{†} ∥ = ∥ T^{ν} v ∥ \leq ((τ + 1) δ)^{2 ν / (2 ν + 1)} R^{1 / (2 ν + 1)} .$

3.1A1F1step 1.1step 2.1algebra∎

From [F1], $∥ x_{k_{δ}}^{δ} - x_{k_{δ}} ∥ \leq \sqrt{2 ω K_{δ}} δ$ . Put $B = C_{p, A, ω} R / (τ - 1)$ , choosing $C_{p, A, ω} > 0$ . For sufficiently small $δ$ , $B / δ \geq 1$ , so $K_{δ} = ⌈ (B / δ)^{1 / p} ⌉ \leq 2 (B / δ)^{1 / p}$ . Therefore $\sqrt{2 ω K_{δ}} δ \leq 2 \sqrt{ω} B^{1 / (2 p)} δ^{1 - 1 / (2 p)} = C^{'} R^{1 / (2 ν + 1)} δ^{2 ν / (2 ν + 1)},$ because $2 p = 2 ν + 1$ . Combining this with [step 2.1] by the triangle inequality proves the claim.

5 · Examples, counterexamples and false statements

None yet.

Iterative regularization and early stopping

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Landweber iteration with discrepancy and budget statuses

Definition

Exact-arithmetic LSQR with Golub–Kahan bidiagonalization and explicit statuses

Definition

A Lipschitz Fréchet derivative gives a quadratic linearization remainder

Statement

Facts & Assumptions

Proof

Remarks

Unanchored Levenberg–Marquardt step with explicit early stopping

Definition

A nonbreakdown LSQR iterate minimizes residual on its Krylov space

Statement

Facts & Assumptions

Proof

Landweber iterates and residuals are spectral-filter iterates

Statement

Facts & Assumptions

Proof

One-step error recurrence for the assigned nonlinear regularized Gauss–Newton step

Statement

Facts & Assumptions

Proof

Real and complex Hilbert source powers and fixed-reference Tikhonov filter bounds

Statement

Facts & Assumptions

Proof

Anchored iteratively regularized Gauss-Newton with finite discrepancy stopping

Definition

Anchored IRGNM error identity and fixed-reference residual inequality

Statement

Facts & Assumptions

Proof

Anchored IRGNM local source-condition convergence with ordinary discrepancy stopping

Statement

Facts & Assumptions

Proof

Remarks

Landweber converges for exact data and balances source bias with noise

Statement

Facts & Assumptions

Proof

Landweber discrepancy stopping converges under a source condition

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources