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.


1 Answer 1


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, 2013 at 19:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .