Randomized Complexity of Vector-Valued Approximation

2023/06/23 by Stefan Heinrich, Heinrich, Stefan
Mathematics · Computer Science · #Mathematical Approximation and Integration #Topological and Geometric Data Analysis #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2306.13697

Abstract

We study the randomized n-th minimal errors (and hence the complexity) of vector valued approximation. In a recent paper by the author [Randomized complexity of parametric integration and the role of adaption I. Finite dimensional case (preprint)] a long-standing problem of Information-Based Complexity was solved: Is there a constant c>0 such that for all linear problems P the randomized non-adaptive and adaptive n-th minimal errors can deviate at most by a factor of c? That is, does the following hold for all linear P and n∈ \mathbb N e_n^{\rm ran-non} (P)≤ ce_n^{\rm ran} (P) \bf ? The analysis of vector-valued mean computation showed that the answer is negative. More precisely, there are instances of this problem where the gap between non-adaptive and adaptive randomized minimal errors can be (up to log factors) of the order n^1/8. This raises the question about the maximal possible deviation. In this paper we show that for certain instances of vector valued approximation the gap is n^1/2 (again, up to log factors).

Related

• Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case
• Randomized Complexity of Mean Computation and the Adaption Problem
• Uniform approximation of vectors using adaptive randomized information
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors
• Randomized Complexity of Parametric Integration and the Role of Adaption II. Sobolev Spaces