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

arXiv (Cornell University)

Abstract

We prove lower bounds for the randomized approximation of the embedding $\ell_1^m \rightarrow \ell_\infty^m$ based on algorithms that use arbitrary linear (hence non-adaptive) information provided by a (randomized) measurement matrix $N \in \mathbb{R}^{n \times m}$. These lower bounds reflect the increasing difficulty of the problem for $m \to \infty$, namely, a term $\sqrt{\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 $(\log\log 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}$.

Authors 2

1. Robert J. Kunsch Aachen at the Chair of Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , at the Chair of Mathematics of Information Processing , Pont- driesch 10 , 52062 Aachen ,

2. Erich Novak

   Friedrich Schiller University Jena

   Affiliation as printed

   FSU Jena , Ernst-Abbe-Platz 2 , 03641 Jena ,