Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

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

share|improve this answer
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. –  Grigory Yaroslavtsev Jan 21 '13 at 19:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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