MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Return to Question

2 added 56 characters in body; added 17 characters in body

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 obtain derive such bounds for functions with bounded first $n$-th derivative . as discussed below from bounds on $\epsilon_\infty(n)$. How to find literature specifically on this topic, bounds on $\epsilon_{1}(n)$, if it exists?

For example, 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

Approximation theory under $L_1$-error

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 obtain such bounds for functions with bounded first derivative. How to find literature on this topic, if it exists?

For example, 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.