Exact-residual Morozov discrepancy bracketing and bisection

Assume Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)). Input a compact operator $A:X\to Y$ between real or complex Hilbert spaces, data $g\in Y$, a declared noise level $\delta >0$, a discrepancy factor $\tau >1$, an initial parameter ${\lambda }_0>0$, integer budgets $M,N\ge 0$, an exact residual evaluator for $r_g(\lambda )=\mathrm{\parallel }A(A^{\ast }A+\lambda I{)}^{-1}{A}^{\ast }g-g\mathrm{\parallel }$, and exact certified endpoint inputs $d=\mathrm{dist}(g,\overline{\mathrm{Ran}A}),G=\mathrm{\parallel }g\mathrm{\parallel }\mathrm{.}$ The algorithm does not infer an infinite-dimensional range distance from a finite number of residual evaluations. If the supplied endpoint values fail $d<\tau \delta <G,$ return incompatible-endpoints.

Set $q=\tau \delta$, initialize ${\lambda }_{-}={\lambda }_{+}={\lambda }_0$, and evaluate $r_g({\lambda }_0)$. If it is below $q$, repeatedly double ${\lambda }_{+}$, at most $M$ times, evaluating the residual after each doubling until $r_g({\lambda }_{+})\ge q$. If the initial residual is at least $q$, repeatedly halve ${\lambda }_{-}$, at most $M$ times, evaluating the residual after each halving until $r_g({\lambda }_{-})<q$. If the selected search exhausts its budget without a bracket, return budget-exhausted; this status is inconclusive.

With a bracket satisfying $r_g({\lambda }_{-})<q\le r_g({\lambda }_{+})$, repeat $N$ times: set ${\lambda }_m=({\lambda }_{-}+{\lambda }_{+})\mathrm{/}2$; if $r_g({\lambda }_m)<q$, replace ${\lambda }_{-}$ by ${\lambda }_m$, and otherwise replace ${\lambda }_{+}$ by ${\lambda }_m$. Return the bracket $[{\lambda }_{-},{\lambda }_{+}]$. The algorithm returns a bracket, not a universal accuracy guarantee for a finite budget.