2021/01/11 by Wanting Lu, Heping Wang, Lu, Wanting +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #41A63 #65C05 #65D15 #65Y20 #FOS: Mathematics #Mathematical Approximation and Integration #Mathematical functions and polynomials #Numerical Analysis (math.NA) #Probabilistic and Robust Engineering Design #cs.NA #math.NA #msc:41A63 #msc:65C05 #msc:65D15 #msc:65Y20
paper · pdf · doi:10.48550/arxiv.2101.03665
25 pages
arxiv created 2021/01/11 · openalex publication_date 2021/01/11 · arxiv updated 2021/01/12 · openalex created_date 2021/01/18 · openalex updated_date 2026/07/28
We study approximation of multivariate functions from a separable Hilbert space in the randomized setting with the error measured in the weighted L2 norm. We consider algorithms that use standard information Λ\rm std consisting of function values or general linear information Λ\rm all consisting of arbitrary linear functionals. We use the weighted least squares regression algorithm to obtain the upper estimates of the minimal randomized error using Λ\rm std. We investigate the equivalences of various notions of algebraic and exponential tractability for Λ\rm std and Λ\rm all for the normalized or absolute error criterion. We show that in the randomized setting for the normalized or absolute error criterion, the power of Λ\rm std is the same as that of Λ\rm all for all notions of exponential and algebraic tractability without any condition. Specifically, we solve four Open Problems 98, 100-102 as posed by E.Novak and H.Woźniakowski in the book: Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, Zürich, 2012.