For a linear system whose operator and right-hand side are known only with error, and whose exact solution is known to lie in an a priori set MM, the theory of optimal recovery seeks the linear method with the smallest worst-case error. Bayev (2007) applied the Lagrange principle to this problem in finite dimensions: the optimal method and its exact error are obtained from an extremal x^\hat{x} of an associated maximization problem, the set II of constraints active at x^\hat{x}, and a nonnegative solution of a finite multiplier system. The paper made this fully algorithmic only for polyhedral data (polytope MM with box or polytope error neighborhoods, via the simplex method), assumed a solver oracle for ellipsoidal errors and for general MM given by mixed linear and quadratic (norm-bound) constraints, and derived sharp small-error formulas only for injective data operators. The open problem addressed here is the completion of this program: an efficient, certified numerical procedure that, for general mixed linear/quadratic MM and for the error-neighborhood classes the source treats (polyhedral, ellipsoidal, and intersections thereof), computes the extremal, certifies the active set, and produces the nonnegative multipliers yielding the optimal recovery functional and its exact worst-case error. (The source also excludes noninjective operators BB from its sharp small-error formulas and observes, without treating, nonuniqueness of the extremal and of the multipliers.)

Background

Optimal recovery is the worst-case branch of information-based complexity: one must approximate an unknown quantity from data known to be inexact, and the quality of a method is measured by its worst-case error over all possibilities consistent with the information. In the finite-dimensional setting of the source paper, the unknown is a vector x∈Rnx\in\mathbb{R}^n satisfying a linear system; the data is a vector y∈Rmy\in\mathbb{R}^m produced by a known linear operator B:Rn→RmB:\mathbb{R}^n\to\mathbb{R}^m corrupted by an error whose size is described by a convex balanced neighborhood Ω⊂Rm\Omega\subset\mathbb{R}^m (a set is balanced if tx∈Ωtx\in\Omega whenever x∈Ωx\in\Omega and ∣t∣≤1|t|\le 1; balanced convex sets are symmetric about the origin), so that y−Bx∈Ωy-Bx\in\Omega. Prior knowledge is encoded by an a priori set M⊂RnM\subset\mathbb{R}^n, likewise convex and balanced, containing the exact solution. A recovery method is a map φ\varphi producing an estimate of the value ⟨ξ,x⟩\langle\xi,x\rangle of a linear functional from the data; its error is the supremum of ∣⟨ξ,x⟩−φ(y)∣|\langle\xi,x\rangle-\varphi(y)| over all admissible pairs, and a method attaining the infimum of this error is optimal. For convex balanced MM and Ω\Omega an optimal method exists and may be taken linear, a fact from the general optimal recovery and extremum theory of Magaril-Il'yaev, Osipenko, and Tikhomirov.

The Lagrange principle for optimal recovery converts this minimax problem into convex duality: the optimal worst-case error equals the value of an associated extremal problem, namely maximizing the linear objective ⟨ξ,x⟩\langle\xi,x\rangle over the feasible set M∩(−B)−1(Ω)M\cap(-B)^{-1}(\Omega), and an optimal linear method is given by a Lagrange multiplier of that problem. Bayev (2007) turned this principle into an explicit scheme for recovering the components of xx (that is, for ξ=eq\xi=e_q, the qq-th coordinate functional). The scheme has three steps: solve the associated maximization to get an extremal x^\hat{x}; determine II, the set of constraints (from the description of MM and Ω\Omega) that are active at x^\hat{x}, i.e. satisfied with equality; and find nonnegative coefficients {ασ}σ∈I\{\alpha_\sigma\}_{\sigma\in I} solving a finite linear system (equation (3.7) of the paper), from which the optimal method and its exact error are assembled. The paper carried this out completely when MM is a polytope and Ω\Omega is a box or any polytope (the associated problem is a linear program solved by the simplex method, which also returns the active set), and, when Ω\Omega is a Euclidean ball or ellipsoid and MM a polytope, reduced the associated problem to maximizing a linear functional under linear inequalities plus one quadratic norm constraint — while assuming a solver that returns the extremal and the active set. Even in the polyhedral case, the paper asserts the existence of a nonnegative solution of the multiplier system but does not specify how to compute one. For the general case in which MM is given by finitely many two-sided linear inequalities and finitely many norm bounds ∥Gσx∥≤ρσ\|G_\sigma x\|\le\rho_\sigma with linear maps GσG_\sigma (the mixed linear/quadratic case covered by the paper's Theorem 3), the paper states that finding the extremal of the associated problem and the active set is the main difficulty of the algorithm. In the small-error regime — the error ball radius ε\varepsilon so small that the preimage P={x:∥Bx∥≤ε}P=\{x:\|Bx\|\le\varepsilon\} lies inside MM — the paper proves that pseudoinversion (recovery by the Moore-Penrose pseudoinverse matrix Λ=(B∗B)−1B∗\Lambda=(B^*B)^{-1}B^*, defined for injective BB; the componentwise functional for coordinate qq has coefficient vector B(B∗B)−1eqB(B^*B)^{-1}e_q) is the componentwise optimal method, with an explicit error formula in terms of the diagonal of (B∗B)−1(B^*B)^{-1}; this derivation requires BB to be injective, since for noninjective BB and bounded MM the inclusion P⊂MP\subset M fails for every ε>0\varepsilon>0. The paper also notes that the extremal x^\hat{x} and the nonnegative solution of the multiplier system need not be unique, without giving a selection principle or a stability analysis.

Modern convex optimization casts light on part of this: for the convex constraint classes treated by the paper, the associated maximization is a linear objective over a set describable by linear and second-order-cone constraints, solvable with duality certificates. Separately, the computational-optimal-recovery program of Ettehad and Foucart constructs optimal recovery maps by linear and semidefinite programming for linearly or semidefinitely describable models with bounded observation errors. Neither line, however, delivers the certified Lagrange-principle construction (extremal plus active set plus nonnegative multipliers) for the paper's general mixed-constraint class with polyhedral and ellipsoidal error neighborhoods, and neither touches the sharp small-error theory beyond injectivity.

Problem Statement

Within the Lagrange-principle framework of Bayev (2007) for optimal recovery of the components of the solution of a linear system from error-corrupted data, complete the program that the source leaves unfinished: make the scheme constructively total and general for the classes the source treats. The scheme is: solve the associated maximization to obtain an extremal x^\hat{x}, determine the active-constraint set II, and find a nonnegative multiplier solution from which the optimal recovery functional and its exact worst-case error are assembled. Specifically:

Certified general-case computation. For M⊂RnM\subset\mathbb{R}^n given by finitely many two-sided linear inequalities and finitely many norm bounds ∥Gσx∥≤ρσ\|G_\sigma x\|\le\rho_\sigma (with linear maps GσG_\sigma), and for a convex balanced error neighborhood Ω⊂Rm\Omega\subset\mathbb{R}^m of the classes treated by the source (polyhedral, ellipsoidal, or intersections thereof), give an efficient numerical procedure that, for any linear data operator BB and coordinate functional eqe_q (equivalently, any linear functional), (i) computes an extremal x^\hat{x} of the associated maximization problem ⟨eq,x⟩→max⁡\langle e_q,x\rangle\to\max over x∈Mx\in M, −Bx∈Ω-Bx\in\Omega; (ii) certifies the active-constraint index set II at x^\hat{x}; and (iii) computes nonnegative coefficients {ασ}σ∈I\{\alpha_\sigma\}_{\sigma\in I} solving the multiplier system (3.7) — a step for which even the source's polyhedral algorithms assert existence but give no computational procedure — thereby producing the optimal linear recovery functional and its exact worst-case error, with correctness guarantees (exactness or explicit certified tolerances) covering degenerate instances where several constraints are simultaneously active and the multiplier system is rank-deficient.

The objective is that the Lagrange-principle scheme becomes constructively complete for these classes rather than dependent on an assumed extremal-oracle.

References

  1. A. V. Bayev, 'The Lagrange principle in the problem of optimal inversion of linear operators in finite-dimensional spaces with a priori information about its solution', Computational Mathematics and Mathematical Physics 47:9 (2007) 1452–1463, DOI 10.1134/S0965542507090072, https://doi.org/10.1134/S0965542507090072 (Russian original: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki 47:9 (2007) 1512–1523, https://www.mathnet.ru/eng/zvmmf246)
  2. A. V. Bayev, 'Princip Lagranzha i konechnomernaya approksimatsiya v zadache optimal'nogo obrashcheniya lineinykh operatorov' [Lagrange Principle and Finite-Dimensional Approximation in Optimal Inversion of Linear Operators], Vychislitel'nye Metody i Programmirovanie (Numerical Methods and Programming) 7 (2006), No. 4, 323–336, https://num-meth.ru/index.php/journal/article/view/224 (Russian, no DOI)
  3. A. V. Bayev, 'Optimal recovery and finite-dimensional approximation in linear inverse problems', Sbornik: Mathematics 199:12 (2008) 1735–1750, DOI 10.1070/SM2008V199N12ABEH003979, https://doi.org/10.1070/SM2008V199N12ABEH003979 (https://www.mathnet.ru/eng/sm3930)
  4. A. V. Bayev, 'An optimal regularizing algorithm for the recovery of functionals in linear inverse problems with sourcewise represented solution', Computational Mathematics and Mathematical Physics 48:11 (2008) 1936–1944, DOI 10.1134/S0965542508110031, https://doi.org/10.1134/S0965542508110031
  5. A. V. Bayev and A. G. Yagola, 'Optimal recovery in problems of solving linear integral equations with a priori information', Journal of Inverse and Ill-Posed Problems 15:6 (2007) 569–586, DOI 10.1515/jiip.2007.031, https://doi.org/10.1515/jiip.2007.031
  6. G. G. Magaril-Il'yaev, K. Yu. Osipenko, and V. M. Tikhomirov, 'Optimal Recovery and Extremum Theory', Computational Methods and Function Theory 2:1 (2003) 87–112, DOI 10.1007/BF03321011, https://doi.org/10.1007/BF03321011
  7. Ye. Zhang, D. V. Lukyanenko, and A. G. Yagola, 'An optimal regularization method for convolution equations on the sourcewise represented set', Journal of Inverse and Ill-Posed Problems 23:5 (2015) 465–475, DOI 10.1515/jiip-2014-0047, https://doi.org/10.1515/jiip-2014-0047
  8. Y. Zhang, D. V. Lukyanenko, and A. G. Yagola, 'Using Lagrange principle for solving two-dimensional integral equation with a positive kernel', Inverse Problems in Science and Engineering 24:5 (2016) 811–831 (published online 2015), DOI 10.1080/17415977.2015.1077445, https://doi.org/10.1080/17415977.2015.1077445
  9. M. Ettehad and S. Foucart, 'Instances of Computational Optimal Recovery: Dealing with Observation Errors', SIAM/ASA Journal on Uncertainty Quantification 9:4 (2021) 1438–1456, DOI 10.1137/20M1328476, https://doi.org/10.1137/20M1328476 (preprint arXiv:2004.00192, https://arxiv.org/abs/2004.00192)
  10. S. Foucart, 'Instances of computational optimal recovery: Refined approximability models', Journal of Complexity 62 (2021) 101503, DOI 10.1016/j.jco.2020.101503, https://doi.org/10.1016/j.jco.2020.101503
  11. A. V. Arutyunov and K. Yu. Osipenko, 'Recovering Linear Operators and Lagrange Function Minimality Condition', Siberian Mathematical Journal 59:1 (2018) 11–21, DOI 10.1134/S0037446618010020, https://doi.org/10.1134/S0037446618010020