betaFeedback

WorksMathematics

On the power of adaption and randomization 2: Non-symmetric convex sets

Abstract

Let S:X→YS:X\to Y be a bounded linear operator between real Banach spaces, and let F⊂XF\subset X be nonempty, bounded and convex. We prove a2n−1(S,F)≤27nmin⁡{enran(S,F),enada(S,F)}.a_{2n-1}(S,F)\le 27n\min \{ e^{\rm ran}_n (S,F), e^{\rm ada}_n (S,F)\}. Here aka_k is the minimal worst-case error of continuous affine algorithms of rank at most kk, and enrane_n^{\rm ran} and enadae_n^{\rm ada} are the minimal errors of adaptive randomized and deterministic algorithms using at most nn continuous linear measurements. This shows that the gain of adaption and randomization, and even nonlinearity, is limited by a factor 27n27n for approximation in convex sets. We discuss the optimality of the result by examples.

Paper details

vlnc:W_mbqdsvy8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…