Randomized approximation of summable sequences -- adaptive and non-adaptive

2023/08/03 by Robert J. Kunsch, Kunsch, Robert, Erich Novak +3 · 1 citation
Economics, Econometrics and Finance · Mathematics · #46 (secondary) #60 (secondary) #65C (primary) #65D (secondary) #FOS: Mathematics #Functional Analysis (math.FA) #Mathematical Approximation and Integration #Numerical Analysis (math.NA) #Probability (math.PR) #Statistical Methods and Inference #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2308.01705

openalex publication_date 2023/08/03 · openalex created_date 2023/08/18 · openalex updated_date 2026/07/28

Abstract

We prove lower bounds for the randomized approximation of the embedding ℓ₁^m → ℓ_∞^m based on algorithms that use arbitrary linear (hence non-adaptive) information provided by a (randomized) measurement matrix N ∈ ℝ^{n × m}. These lower bounds reflect the increasing difficulty of the problem for m → ∞, namely, a term √(log m) in the complexity n. This result implies that non-compact operators between arbitrary Banach spaces are not approximable using non-adaptive Monte Carlo methods. We also compare these lower bounds for non-adaptive methods with upper bounds based on adaptive, randomized methods for recovery for which the complexity n only exhibits a (loglog m)-dependence. In doing so we give an example of linear problems where the error for adaptive vs. non-adaptive Monte Carlo methods shows a gap of order n^1/2 ( log n)^-1/2.

Cited by

• Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors

Related

• Uniform approximation of vectors using adaptive randomized information
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors
• Randomized Complexity of Mean Computation and the Adaption Problem
• Randomized Complexity of Vector-Valued Approximation
• On the power of adaption and randomization