Randomized complexity of vector-valued approximation

DOI10.1007/978-3-031-59762-6_17MaRDI QIDQ7012111zbMATH OpenFDO

Authors Stefan Heinrich

Publication date 17 March 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59762-6_17

zbMATH Keywords

adaptivealgorithmapproximationinformation-based complexitynon-adaptiverandomized

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Analysis of algorithms and problem complexity (68Q25)

Review text

This interesting paper deals with the subject of random complexity of vector-valued approximation. A well known and very difficult problem in this circle of problems asks if there exists a constant \(c>0\) such for all linear problems, the randomized non-adaptive and adapative \(n,\, n\geq 1\) minimal errors (and hence complexity) can deviate by at most a factor of \(c\). This problem was solved in [\textit{S. Heinrich}, J. Complexity 82, Article ID 101823, 31 p. (2024; Zbl 1535.65009)] in which it was shown that there are instances where the gap between non-adaptive and adapt randomized minimial errors can be up to log factors, of the order \(n^{1/8}\). For maximal possible deviation, the author shows in this paper that the gap is up to log terms \(\sqrt{n}\) for certain situations in vector valued approximation.\N\NFor the entire collection see [Zbl 1552.65006].

Cites work

• Complexity of stochastic integration in Sobolev classes
• Deterministic and stochastic error bounds in numerical analysis
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• Monte Carlo approximation of weakly singular integral operators
• On the complexity of computing the \(L_q\) norm
• On the power of adaption
• Optimal sequential and non-sequential procedures for evaluating a functional
• Quantum summation with an application to integration.
• Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case
• The randomized information complexity of elliptic PDE
• Tractability of multivariate problems. Volume I: Linear information

Cited in

(2)

• Uniform approximation of vectors using adaptive randomized information
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors

This page was built for publication: Randomized complexity of vector-valued approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7012111)