Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error?

Formal definitions for functions of one variable are below.

Let $C$ be a class of functions $f \colon [0,1] \rightarrow [0,1]$. For $n > 0$ and $f \in C$ let $A_n$ be a class of all deterministic (or randomized) rules $r_n$ which map $n$ values of $f$ (possibly chosen adaptively, i.e. $f(x_1), f(x_2(f(x_1))), \dots, f(x_n(f(x_{n - 1}(\dots f(x_1))))$) to a function $r_n(f) \colon [0,1] \rightarrow [0,1]$. For $p \ge 1$ let $\epsilon_p(n)$ be the best worst-case $L_p$-error of a rule $r_n \in A_n$ taken over all functions $f \in C$, i.e. $\epsilon_p(n) = \min_{r_n \in A_n} \sup_{f \in C} ||f - r_n(f)||_p$.

Under which conditions on $C$ non-trivial bounds on $\epsilon_1(n)$ exist? Same question for functions of multiple variables. E.g., one can derive such bounds for functions with bounded $n$-th derivative as discussed below from bounds on $\epsilon_\infty(n)$. How to find literature specifically on bounds on $\epsilon_{1}(n)$, if it exists?

For $L_\infty$-error $\epsilon_{\infty}(n)$ non-trivial such bounds can be achieved for the class of functions with bounded $n$-th derivative by using Chebyshev polynomials.

P.S. Similar results in theoretical computer science are known as ``learning of $C$ under $L_1$-error'', but the focus there is mostly on discrete domains.


Is this what you have in mind???

J.B. Leite, Approximation in [L1] Norm, University of Oxford, 1982

Teeradache Viangteeravat, Discrete Signal Approximation Using L1 Norm Techniques, Vanderbilt University, 2000

  • $\begingroup$ Thank you, did you have a chance to look at these sources? Unfortunately, I can't find any preview online and my university library doesn't have them as well. $\endgroup$ Jan 21 '13 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.