×

Instances of computational optimal recovery: refined approximability models. (English) Zbl 1460.65068

Summary: Models based on approximation capabilities have recently been studied in the context of Optimal Recovery. These models, however, are not compatible with overparametrization, since model- and data-consistent functions could then be unbounded. This drawback motivates the introduction of refined approximability models featuring an added boundedness condition. Thus, two new models are proposed in this article: one where the boundedness applies to the target functions (first type) and one where the boundedness applies to the approximants (second type). For both types of models, optimal maps for the recovery of linear functionals are first described on an abstract level before their efficient constructions are addressed. By exploiting techniques from semidefinite programming, these constructions are explicitly carried out on a common example involving polynomial subspaces of \(\mathcal{C}[-1,1]\).

MSC:

65K05 Numerical mathematical programming methods
90C22 Semidefinite programming

Software:

Basc

References:

[1] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton University Press · Zbl 1221.90001
[2] Binev, P.; Cohen, A.; Dahmen, W.; DeVore, R.; Petrova, G.; Wojtaszczyk, P., Data assimilation in reduced modeling, SIAM/ASA J. Uncertain. Quantif., 5, 1, 1-29 (2017) · Zbl 06736493
[3] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[4] DeVore, R.; Foucart, S.; Petrova, G.; Wojtaszczyk, P., Computing a quantity of interest from observational data, Constr. Approx., 49, 3, 461-508 (2019) · Zbl 1414.41019
[5] M. Ettehad, S. Foucart, Instances of computational optimal recovery: dealing with observation errors. Preprint. · Zbl 1436.93031
[6] Foucart, S., Computation of minimal projections and extensions, Numer. Funct. Anal. Optim., 37, 2, 159-185 (2016) · Zbl 1348.46013
[7] Foucart, S.; Lasserre, J. B., Computation of Chebyshev polynomials for union of intervals, Comput. Methods Funct. Theory, 19, 4, 625-641 (2019) · Zbl 1436.30004
[8] Foucart, S.; Powers, V., BASC: constrained approximation by semidefinite programming, IMA J. Numer. Anal., 37, 2, 1066-1085 (2017) · Zbl 1433.41001
[9] Lasserre, J., Moments, Positive Polynomials and their Applications. Vol. 1 (2009), Imperial College Press
[10] Novak, E.; Woźniakowski, H., Tractability of Multivariate Problems: Linear Information. Vol. 6 (2008), European Mathematical Society · Zbl 1156.65001
[11] Rudin, W., (Functional Analysis. Functional Analysis, International Series in Pure and Applied Mathematics (1991), McGraw-Hill) · Zbl 0867.46001
[12] Sloan, I. H.; Woźniakowski, H., When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. Complexity, 14, 1, 1-33 (1998) · Zbl 1032.65011
[13] Smolyak, S. A., On Optimal Restoration of Functions and Functionals of them (1965), Moscow State University, (Candidate dissertation)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.