FoCM 2014 conference
Workshop B5 - Information Based Complexity
December 17, 18:00 ~ 18:30 - Room B23
Approximation of piecewise Hölder classes from inexact information
Leszek Plaskota
University of Warsaw, Poland - leszekp@mimuw.edu.pl
We study algorithms for $L^p$-approximation ($1\le p<\infty$) of functions $f:[a,b]\to{\mathbb R}$ that are piecewise $r$-times continuously differentiable and $f^{(r)}$ are piecewise Hölder continuous with exponent $\rho\in(0,1]$. The singular points of $f$ are unknown. Available information is blurred and given as $y_i=f(x_i)+e_i$, $1\le i\le n$, where $|e_i|\le\delta$. We show that a necessary and sufficient condition for the error of approximation to be at most $\varepsilon$ is that $n\asymp\varepsilon^{-1/(r+\rho)}$ and $\delta\asymp\varepsilon$. The optimal algorithms use adaptive information. This generalizes previous results where information was exact and we had $\rho=1$.
Joint work with Pawel Morkisz (AGH Krakow, Poland).