Abstract
Abstract. Consider approximating functions based on a finite number of their samples. We show that adaptive algorithms are much more powerful than nonadaptive ones when dealing with piecewise smooth functions. More specifically, let F 1 r be the class of scalar functions f : [0, T ] → R whose derivatives of order up to r are continuous at any point except for one unknown singular point. We provide an adaptive algorithm A ad n that uses at most n samples of f and whose worst case L p error (1 ≤ p < ∞) with respect to 'reasonable' function classes F 1 r ⊂ F 1 r is proportional to n −r . On the other hand, the worst case error of any nonadaptive algorithm that uses n samples is at best proportional to n −1/p .
Abstract
The restriction to only one singularity is necessary for superiority of adaption in the worst case setting. Fortunately, adaption regains its power in the asymptotic setting even for a very general class F ∞ r consisting of piecewise C r -smooth functions, each having a finite number of singular points. For any f ∈ F ∞ r our adaptive algorithm approximates f with error converging to zero at least as fast as n −r . We also prove that the rate of convergence for nonadaptive methods cannot be better than n −1/p , i.e., is much slower.
Abstract
The results mentioned above do not hold if the errors are measured in the L ∞ norm, since no algorithm produces small L ∞ errors for functions with unknown discontinuities. However, we strongly believe that the L ∞ norm is inappropriate when dealing with singular functions and that the Skorohod metric should be used instead. We show that our adaptive algorithm retains its positive properties when the approximation error is measured in the Skorohod metric. That is, the worst case error with respect to F 1 r equals Θ(n −r ), and the convergence in the asymptotic setting for F ∞ r is n −r . Numerical results confirm the theoretical properties of our algorithms.
THE POWER OF ADAPTION FOR APPROXIMATING FUNCTIONS WITH SINGULARITIES
LESZEK PLASKOTA, GRZEGORZ W. WASILKOWSKI, AND YAXI ZHAO Abstract. Consider approximating functions based on a finite number of their samples. We show that adaptive algorithms are much more powerful than nonadaptive ones when dealing with piecewise smooth functions. More specifically, let F 1 r be the class of scalar functions f : [0, T ] → R whose derivatives of order up to r are continuous at any point except for one unknown singular point. We provide an adaptive algorithm A ad n that uses at most n samples of f and whose worst case L p error (1 ≤ p < ∞) with respect to 'reasonable' function classes F 1 r ⊂ F 1 r is proportional to n −r . On the other hand, the worst case error of any nonadaptive algorithm that uses n samples is at best proportional to n −1/p .
THE POWER OF ADAPTION FOR APPROXIMATING FUNCTIONS WITH SINGULARITIES
The restriction to only one singularity is necessary for superiority of adaption in the worst case setting. Fortunately, adaption regains its power in the asymptotic setting even for a very general class F ∞ r consisting of piecewise C r -smooth functions, each having a finite number of singular points. For any f ∈ F ∞ r our adaptive algorithm approximates f with error converging to zero at least as fast as n −r . We also prove that the rate of convergence for nonadaptive methods cannot be better than n −1/p , i.e., is much slower.
THE POWER OF ADAPTION FOR APPROXIMATING FUNCTIONS WITH SINGULARITIES
The results mentioned above do not hold if the errors are measured in the L ∞ norm, since no algorithm produces small L ∞ errors for functions with unknown discontinuities. However, we strongly believe that the L ∞ norm is inappropriate when dealing with singular functions and that the Skorohod metric should be used instead. We show that our adaptive algorithm retains its positive properties when the approximation error is measured in the Skorohod metric. That is, the worst case error with respect to F 1 r equals Θ(n −r ), and the convergence in the asymptotic setting for F ∞ r is n −r . Numerical results confirm the theoretical properties of our algorithms.
Introduction
In traditional studies of function approximation one usually assumes that the functions under consideration are smooth in some sense, e.g., they are r-times continuously differentiable, and that they form a separable linear space. On the other hand, functions appearing in practice are very often only piecewise smooth, and their collection is more complicated than a linear space. An important example is provided by image representation. Here edges correspond to discontinuities of the underlying function, and the linear combination of two images need not be any image of practical interest.
Introduction
Much attention has been recently devoted to wavelets that are now considered a universal tool to deal with images and signals. A given function f (image, signal) is represented by a few of the largest coefficients of its expansion in a suitable wavelet basis (or curvelet basis in 2-D); see, e.g., [5, 8, 9, 15] . It is also believed that adaptive methods, that rely on adjusting the choice of the basis to the underlying function and its discontinuities (edges), are much more efficient than nonadaptive methods where the basis is fixed for all f 's. Note that the wavelet approach is based on the paradigm that one has at his disposal all wavelet coefficients of f corresponding to a given basis. This actually means that complete information about f is available.
Introduction
In the present paper, we take an information-based approach. It follows the paradigm that only partial information about f is available, and that the only source of information is an oracle; see, e.g., [16, 20, 24, 25, 28, 29, 30, 32, 33] . This seems to be more suitable for numerical computations where the oracle calls usually correspond to function evaluations. In this approach the term adaption means adjusting the selection of successive oracle calls to the results of previous calls. Note that superiority of adaptive methods is here far less obvious since so far adaptive methods have been mainly developed for integration (and not approximation) problems; see, e.g., [2, 6, 7, 12, 13, 14, 19, 22, 23] . Moreover, there are theoretical results showing that adaption does not help for linear problems such as function approximation. This holds in different settings, including the worst case setting with convex classes, and the asymptotic setting with Banach function spaces; see, e.g., [3, 17, 10, 30, 31] . Observe that singular functions of practical interest form neither convex classes nor Banach spaces. Therefore the results mentioned above do not contradict the common belief that adaptive methods should be used when dealing with singularities.
Introduction
The information-based approach to the approximation of singular functions was presented in a recent paper [1] . The scalar function f to be approximated is assumed to be globally continuous, and C r -smooth except for exactly one (unknown) point at which f has nontrivial discontinuity. The authors use the uniform mesh of size h to construct a nonadaptive approximation which converges to f with error proportional to h r in the uniform norm. This result means that for singular but globally continuous functions, adaption does not help in the asymptotic setting, i.e., nonadaptive methods are optimal.
Introduction
We consider a class F ∞ r of functions with more general singularities. We assume that f : [0, T ] → R and allow discontinuity of the function itself and/or of its derivatives starting at order perhaps higher than one, as assumed in [1] . That is, f may be, say, twice differentiable on [0, T ], and f (3) (s) may not exist at some point s. Moreover, f may have more than just one (but finitely many) singular points; their location and number are unknown. We want to approximate functions f ∈ F ∞ r by algorithms A n f that use function values at some n points x 1 , . . . , x n as the only available information. We allow adaptive algorithms, in which case the choice of x j depends on previously obtained values of f (x 1 ), . . . , f(x j−1 ).
Introduction
An interesting feature of discontinuous functions is that it is impossible to approximate them with small errors measured in the L ∞ norm. This should not be surprising after realizing how inappropriate the L ∞ norm is for such functions. To see this, let us consider perhaps the simplest discontinuous functions from our class 
Introduction
Since f a − f b L ∞ = 1 whenever a = b, the sequence {f a+1/n } does not converge to f a in the L ∞ norm even though both functions are almost identical. In particular, the function f a cannot be represented with error smaller than 1 (in the L ∞ norm) in a floating point arithmetic of finite precision, unless a is a machine number. In other words, one would like to use a distance (metric) that enjoys all the good properties of the uniform norm, yet is also appropriate for discontinuous functions. Fortunately, the Skorohod metric dist S (·, ·), see (3), enjoys the desiderata above. Roughly speaking, the distance between two functions f and g is small iff the graph of one of them, say f , can be viewed as a slightly perturbed graph of g, i.e., f is close to g • λ for some homeomorphism λ that is close to the identity function id(x) = x, both in the L ∞ norm. Following our example, note that dist S (f a , f fl(a) ) = |a − fl(a)| is small, as it should be. Moreover, for continuous functions from our class F ∞ r (e.g., with discontinuity of derivatives but not of the function itself), the Skorohod distance is equivalent to the uniform norm. Hence, one could say that it has the good and practical properties of the uniform norm without the drawbacks that the norm induces for discontinuous functions. We refer again to Section 3 for some relations between the Skorohod metric and L p norms. In our paper, we seek optimal nonadaptive and adaptive algorithms in the worst case and asymptotic settings, assuming that the error of approximation is measured in the L p norm (1 ≤ p < ∞) or in the Skorohod metric. We are ready to discuss the main results of the paper. Since they strongly depend on the number of singular points, we begin with the class F 1 r ⊂ F ∞ r that consists of functions with at most one singular point. In Section 4 we prove that the best nonadaptive algorithms using n function values have the rather poor convergence rate n −1/p when the L p norms are used, and n −1 when the Skorohod metric is used; see Theorem 2 and Proposition 3. These negative results should be contrasted with the case of globally C r -smooth functions (having no singularities), where nonadaptive piecewise polynomial approximation yields the error bounded
Introduction
L ∞ n −r in the uniform norm, for any f and n ≥ r. Can we do better by using adaptive algorithms? Definitely YES. In Section 5 we construct an adaptive algorithm A ad n that achieves the optimal convergence rate of n −r for both the L p norms and the Skorohod metric. Moreover, the error asymptotically behaves as though there were no singularities, i.e., for any f ∈ F 1 r we have (1) lim
Introduction
where γ depends only on r and the metric used; see Theorems 3 and 4. We stress that (1) and (2) are only asymptotic results. If we switch to the worst case setting, then the situation is more complicated. For the worst case error to be of order n −r it is not enough to assume that the rth derivative is uniformly bounded, which is the case for functions with no singularities. Actually, we prove in Section 5.4 that for any (possibly adaptive) algorithm A n its worst case error with respect to the class
Introduction
is infinite, independent of whether the L p norm or the Skorohod metric is considered. Hence, for positive worst case results we have to put more restrictions on f . Indeed, we show that for our adaptive algorithm A ad n we have
Introduction
where L r , L 1 , and D 0 are finite, and ∆
Introduction
is the discontinuity jump of f . For the details, see again Theorems 3 and 4, as well as Section 5.4.
Introduction
Our algorithm A ad n consists of two steps. First, an adaptive (bisection-like) mechanism is used to detect and localize singularities; next, a piecewise polynomial interpolation of degree r − 1 is applied. The detection mechanism is based on ideas already developed in [21] , where numerical integration of piecewise smooth functions is considered, and relies on getting some quantitative information about the singularity by computing rth order divided differences. Roughly speaking, singularities with big discontinuity jumps are easily detected and localized with small errors, and those not detected have small enough jumps not to influence the approximation error.
Introduction
Next, in Section 6, we consider the general case of functions with multiple singularities. We show in Section 6.1 that, unfortunately, the worst case errors of any algorithm with respect to any reasonable function class from F ∞ r are bounded away from zero, independent of the number n of function evaluations used; see Proposition 4. In other words, the worst case errors of even optimal algorithms do not converge to zero. This is because two or more singularity points can be arbitrarily close to one another, which makes it impossible to distinguish them using a fixed number n of function evaluations.
Introduction
Fortunately, the lack of convergence in the worst case setting can be reversed in the asymptotic setting, as considered in Section 6.2. Indeed, a modification of A ad n leads to an algorithm A ad n that replicates the asymptotic properties (1) and (2); see Theorem 5. Finally, in Section 7, we report on numerical results that confirm the theoretical properties of A 
Basic definitions
We say that a function g :
Basic definitions
The set of all r-smooth functions defined on [a, b] will be denoted by W r (a, b) .
Basic definitions
For given T > 0 and r ≥ 1 we consider the space
Basic definitions
The points s i , 1 ≤ i ≤ k, are singularities of f . The corresponding discontinuity jumps are denoted by
Basic definitions
Observe that any f ∈ F ∞ r admits the useful representation
Basic definitions
where g ∈ W r (0, T ) and
Basic definitions
Here and elsewhere, A denotes the indicator function of the set A. We distinguish in F ∞ r the classes F r of functions with no more than singular points,
Basic definitions
For fixed (finite or infinite) our aim is to construct efficient algorithms for approximating functions f ∈ F r in a given metric (distance), choices of which will be discussed later. We assume that the only a priori information about f is that f ∈ F r . In particular, the locations of singularities are unknown; when = ∞, we also assume that we do not have an upper bound on the number of singularities. However, together with this a priori information, the algorithms also use some a posteriori information that consists of finitely many evaluations of f at certain points x i . For instance, the algorithm may be given as
Basic definitions
for some x i ∈ [0, T ] and functions f i . These include (piecewise) polynomial or trigonometric interpolation, splines, etc. More generally, by an algorithm we mean a mapping of the form
Basic definitions
If the points x i are chosen independently of f , then the algorithm is nonadaptive. An important particular case is provided by the equispaced sampling
Basic definitions
We also consider adaptive algorithms in which the choice of the successive x i 's and their number n = n(f ) depend on previously obtained information about f . That is, x 1 is fixed and
Basic definitions
The index n of A n means that for any f ∈ F r the algorithm uses no more than n function evaluations, i.e., n(f ) ≤ n for all f . Note that our problem is determined by the parameters T , r, , and the metric with respect to which the error of approximation is measured. Hence the results will also depend on them.
Basic definitions
Throughout this paper we denote by
Basic definitions
The same applies to the space C of continuous functions and the uniform (Chebyshev) norm.
Basic definitions
We will also say that an x is in [a, b] with respect to f (or w.r.t. f in the sequel), and write
L p norms versus the Skorohod metric
It would be desirable to have algorithms that converge fast in the most conservative uniform L ∞ norm. Unfortunately, L ∞ approximation is an ill-posed problem when dealing with discontinuous functions. Indeed, we have the following negative result.
L p norms versus the Skorohod metric
For a given function f :
Lemma 1.
Let {A n } n≥1 be a sequence of (adaptive) algorithms. Then for any function f and ε = 0, the set of u ∈ [0, T ) for which
Lemma 1.
n values of u. Consequently, the error converges to zero with n → ∞ for at most countably many f ε,u 's.
Lemma 1.
The lack of convergence for the L ∞ approximation can be remedied by using a weaker metric. The first and straightforward choice is L p with 1 ≤ p < ∞. However, there is also another possibility -the Skorohod metric.
Lemma 1.
The Skorohod metric, see, e.g., [4, 11, 18, 26] , was introduced in statistics after it had been observed that the L ∞ norm is not adequate for piecewise continuous functions (processes), since it makes the space of such functions nonseparable, i.e., too large. To explain this from a layman's perspective, let us consider for a moment functions f 1/2+1/n :
Lemma 1.
/n in spite of the fact that f 1/2 and f * are so different. The L p norms (with p < ∞) do not have these bad properties; however, they ignore singular points, characteristics that might be important to preserve in some applications, e.g., in signal/image processing.
Lemma 1.
As we shall see, the Skorohod metric is free of all the problems above, and therefore turns out to be a suitable tool for working with discontinuous functions. It is defined as follows. Let f, g be two functions from L ∞ . Their Skorohod distance is given by 
Lemma 1.
We believe that the Skorohod metric is an important way of measuring errors for a host of applications including image analysis/processing, where preserving discontinuities is essential. There f (λ(·)) would correspond to a slightly distorted image of f .
Lemma 1.
Even though f − g L ∞ and dist S (f, g) differ so much, it is possible to show some relations. Obviously, we always have
Lemma 1.
The following proposition might be known; however, we have not seen it in the literature.
Lemma 1.
Now taking the ess sup with respect to x and the inf with respect to λ completes the proof.
Lemma 1.
Here is another property showing a relation between the Skorohod metric and the
Lemma 1.
where k is the number of discontinuities of f and ∆ (0) j , 1 ≤ j ≤ k, are the corresponding discontinuity jumps.
Proposition 2. For any
f, g ∈ F ∞ 1 we have f − g L 1 ≤ min (c(f ), c(g)) · T · dist S (f, g).
Proof. Without loss of generality, let c(f ) ≤ c(g) and the infimum in the definition
of dist S (f, g) be attained for λ, so that dist S (f, g) = λ − id L ∞ + f • λ − g L ∞ (otherwise we would do the standard δ-trick). Then T 0 |f (x) − g(x)| dx ≤ T 0 |f (λ(x)) − f (x)| dx + T 0 |f (λ(x)) − g(x)| dx.
The latter integral is upper bounded by
To bound the former integral, we represent f (up to the finite set of discontinuity points s j ) as
The latter integral is upper bounded by
where
The latter integral is upper bounded by
which completes the proof.
The latter integral is upper bounded by
Thus, in the Skorohod metric, any sequence of approximations converges at least as fast as it does in the L ∞ norm, and no faster than in the L 1 norm. There are no such relations between the Skorohod distance and the L p norms
Nonadaptive algorithms
It is well known that, in the space of r-smooth functions W r = F 0 r , piecewise polynomial interpolation of degree r − 1 based on equidistant sampling leads to a nonadaptive algorithm with error bounded from above by C f (r)
Nonadaptive algorithms
−r with C > 0 independent of f and n. Moreover, n −r is the best rate of convergence among all (including adaptive) algorithms. It turns out that the presence of discontinuities causes all nonadaptive algorithms to have their errors bounded from below by n −1/p . The purpose of this section is to show this fact.
Nonadaptive algorithms
We first show the following rather simple bounds.
Nonadaptive algorithms
1 | ≤ ∆ and
Nonadaptive algorithms
Moreover, there exists a piecewise constant function
Nonadaptive algorithms
Proof. Suppose that A n computes f at points x 1 < · · · < x n . Let x 0 = 0 and
Nonadaptive algorithms
. Since g 1 and g 2 share the same information (i.e., g 1 (
Nonadaptive algorithms
1/p , the algorithm error cannot be smaller than ∆(T/(n + 1)) 1/p /2 for at least one of the functions g i . This proves (4). Similarly, (5) follows from the fact that for the same functions dist
Nonadaptive algorithms
To show (6), we choose a, b as before and define g 1 ≡ 0 and
Nonadaptive algorithms
, and (6) follows.
Nonadaptive algorithms
Theorem 1 is in the spirit of the worst case setting, since a single 'bad' function is selected depending on n. The following theorem shows that also asymptotically the L p error of nonadaptive algorithms cannot decrease faster than n −1/p . However, we have the lower bound n −1 for the asymptotic convergence in the Skorohod metric, independently of the number of singularities. As we shall see later, these lower bounds are sharp. Hence for nonadaptive algorithms, the switch from the worst case to the asymptotic setting only benefits the convergence in the Skorohod metric.
Nonadaptive algorithms
Let f ε,u be defined as in Lemma 1. 
Nonadaptive algorithms
Proof. We first show the theorem for the L p norm. In view of Lemma 1 it suffices to consider 1 ≤ p < ∞.
Nonadaptive algorithms
Note that for any function g the set of u
Nonadaptive algorithms
The proof is similar to the proof of Lemma 4 in [21] . That is, for c > 0, we define the sets B
Nonadaptive algorithms
Since the information takes no more than n + 1 different values for functions f ε,u , the algorithm A n also takes at most n+1 different values for these functions. Hence
Nonadaptive algorithms
Since c can be arbitrarily small, L(A) = 0. To show the theorem for the Skorohod metric, observe first that
Nonadaptive algorithms
which shows (7). The proof then proceeds as for the L p norm by noting that for a < (1/2)|ε|/ (1 + f L ∞ ) the set of u for which dist S (f ε,u , g) ≤ a is of measure at most 2a.
Nonadaptive algorithms
To complete this section, we now show that the estimates of Theorems 1 and 2 are sharp. For n ≥ 2, consider the piecewise constant approximation
Nonadaptive algorithms
Proof. We first prove (8) . Consider an arbitrary interval [x i , c i ], where 1 ≤ i ≤ n−1. Let P i be the set of all indices j such that
Nonadaptive algorithms
where Q i is the set of all indices j such that s j ∈ f [c i , x i+1 ]. Observe that any s j is in exactly one of the sets P i or Q i . It now follows that the error can be bounded from above by the sum of two functions: a saw-like function
Nonadaptive algorithms
and the piecewise constant function
Straightforward calculations give
The bound (8) 
Straightforward calculations give
On the other hand, consider the homeomorphism λ defined as the piecewise linear function interpolating the following data:
Straightforward calculations give
.
Straightforward calculations give
(where c 0 = s 0 = 0 and c n = s n = T ), for any x ∈ (c j , c j+1 ) we have
Straightforward calculations give
Combining (11) and (12) we get (10).
Adaptive algorithms: Single discontinuity
In this section, we provide an adaptive algorithm whose worst case error is proportional to n −r . Clearly, this is a significant improvement over the convergence of nonadaptive methods. We stress that this result holds true because we have restricted the function class to F 1 r . As shown in the next section, adaption loses its superiority in the worst case setting for classes of functions with possibly more than one singular point.
Adaptive algorithms: Single discontinuity
Our adaptive algorithm consists of two stages. First, it tries to detect/localize the discontinuity using adaptive sampling, and next it approximates the function by piecewise polynomial interpolation at points that depend on the location of the singularity.
Adaptive algorithms: Single discontinuity
5.1. Detection mechanism. Our mechanism for detecting the singular point s f in (0, T ) with 'large' discontinuity jumps is based on the one already developed in [21] . A theoretical justification of that mechanism is based on Lemma 2 and Lemma 3 that are basically taken from [21] ; however, the formulation of Lemma 2 is slightly different than the one in [21] . For completeness, we provide a proof in the Appendix.
Adaptive algorithms: Single discontinuity
For m ≥ 1, let h = T/m and t i := ih for all (not necessarily integer) i. Denote by f [t i , t i+1 , . . . , t i+j ] the jth order divided difference of f with respect to t i , . . . , t i+j . We also define the constant
Adaptive algorithms: Single discontinuity
then the discontinuity jumps are bounded by (14) |∆
Adaptive algorithms: Single discontinuity
Otherwise, if the largest |d (15) |∆
In addition, if (16) holds, then f is r-smooth on [0, t q/2 κ ] and on [t (q+r)/2 κ , T ].
Obviously, for fixed f ∈ F 1 r with nontrivial discontinuity of one of the derivatives f (j) , where 0 ≤ j ≤ r − 1, condition (13) is satisfied for the mesh-size h sufficiently small (or m sufficiently large). Even more, if D < ∞, then for h small enough the largest |d 0 i | exceeds D so that we only have (15) or (16) . However, we aim at stronger, nonasymptotic results and therefore have to extend applicability of the detection mechanism to the intervals (t (r−1)/2 κ , t r−1 ] and [t m−r+1 , t m−(r−1)/2 κ ). As we shall see, this is sufficient to construct an algorithm with small worst case error.
In addition, if (16) holds, then f is r-smooth on [0, t q/2 κ ] and on [t (q+r)/2 κ , T ].
The extension works for m ≥ 2(r−1) and is done by computing additional divided differences with decreasing mesh-size in the vicinities of 0 and T . Specifically, for 1 ≤ j ≤ κ, 0 ≤ i ≤ 2(r − 1), and Before providing a corresponding pseudocode, we comment on the choice of the threshold D. Observe that if (14), one can take D = 0. Then (17) holds for any f ; however, the detection part is triggered regardless of whether f has a singularity or not.
In addition, if (16) holds, then f is r-smooth on [0, t q/2 κ ] and on [t (q+r)/2 κ , T ].
In the following procedure the parameters are: the smoothness r, a positive integer sequence {κ m } m≥1 , and a threshold D. 
. , t i+r ]; 05
for j := 1 to κ do 06 begin 07 For fixed points τ i satisfying
. , t i+r ]; 05
let P r (f ; a, b) be the polynomial of degree at most r − 1 interpolating f at a + τ j (b−a), with 1 ≤ j ≤ r. Further, for any collection U of points u 0 < u 1 < u 2 < · · · < u k , let P r (f ; U ) be the piecewise polynomial interpolation of f determined by U , i.e.,
. , t i+r ]; 05
Fix a threshold D ≥ 0 and an integer sequence {κ m } m≥1 satisfying κ m ≥ log 2 (r−1), so that
. , t i+r ]; 05
Our algorithm A ad n is determined by r, {κ m } m , and D, and is defined as follows. We choose m ≥ 2(r − 1) and run DETECT. If the procedure returns ∅, then we let
. , t i+r ]; 05
Otherwise, the procedure produces an interval
, and construct our algorithm as
That is, A 
, and construct our algorithm as
.
, and construct our algorithm as
(Here and later we adopt the convention that 1/p = 0 when p = ∞.) Inequality (18) can be easily generalized to the case of functions with one singularity as follows. For 0 ≤ j ≤ r − 1, let
, and construct our algorithm as
Then we have the following bound, the proof of which is in the Appendix.
, and construct our algorithm as
We are now ready to state and prove the main result about the L p error of our adaptive algorithm. Let 
, and construct our algorithm as
where the three successive components of the sum are: the L p error outside of the 'small' subintervals derived from (18) , the error on the two (or one) 'small' subintervals not containing s f (which follows from (8) of Proposition 3 with n = 2 and T replaced by δ m ), and the error on the 'small' subinterval containing s f (which again follows from (8)). Now consider the second, opposite case when s f is w.r.t. f in one of the 'large' subintervals of length at most h. This is possible only when all the divided differences computed in lines 04 to 09 of DETECT are not larger than D f and, consequently, the jumps |∆
, and construct our algorithm as
Hence in this case, the error can be bounded by
, and construct our algorithm as
where the last component of the sum is the error on the 'large' interval containing s f , derived from Lemma 4 and inequalities (14) and (15 ., except for 3 or 4 intervals) , the approximation (A ad n f )(x) = P r (f ; t i−1 , t i )(x). Hence for any such interval the error can be bounded by
, and construct our algorithm as
Since by (20) the error on the 'small' subintervals is asymptotically negligible, it follows that
, and construct our algorithm as
can be asymptotically bounded from below and from above by Riemann sums 
, and construct our algorithm as
Proof. First consider the case when s f is in one of the three 'small' intervals of length δ m . We can assume without loss of generality that
, and construct our algorithm as
On the other hand, define the homeomorphism λ as the piecewise linear interpolation of the data:
, and construct our algorithm as
For x ∈ (v l , v r ) we show, similar to the proof of (10) , that the error is at most δ m f L ∞ . Thus, in this case we also have
, and construct our algorithm as
Now consider the case when s f is not in any of the 'small' intervals. Then we have (14) or (15) and
, and construct our algorithm as
Inequality (22) is obtained by combining both cases.
, and construct our algorithm as
To show (23) we use arguments similar to those in the proof of (21).
Worst case setting.
The bound (19) in Theorem 3 establishes the following result in the worst case setting. Let F f | and first and rth derivatives of f , i.e.,
Worst case setting.
where C is independent of n and f (but it depends on L r , L 1 , D 0 ). Similarly, for the Skorohod metric we have
Worst case setting.
with respect to the clasŝ
Worst case setting.
Note that F 
Worst case setting.
where dependence on the successive discontinuity jumps |∆
Worst case setting.
f | rapidly decreases (e.g., if κ m = m, then δ 1/p m vanishes at an exponential rate). Consequently, we have the corresponding worst case results for the classes
Worst case setting.
We chose to work with s = 1 for a number of reasons. First, dependence of the error on quantities other than f (r) is practically negligible. Second, if κ m increases faster than log 2 m and slower than m, then the same algorithm A ad n (i.e., with the same set of parameters) satisfies the estimates of Theorems 3 and 4. Third, in the Skorohod metric, the algorithm A ad n does not work well for s = 0, and taking s ≥ 2 is useless because in this way dependence on f cannot be removed from the error formula, due to the L ∞ norm of the homeomorphism λ.
Lower bounds. It is well known that for functions with no singularities (f
is of order n −r with respect to the class of functions with uniformly bounded f (r) L ∞ . Moreover, this convergence cannot be improved, and uniform boundeness of the rth derivative is crucial.
Lower bounds. It is well known that for functions with no singularities (f
One can ask if a similar result holds true in F 1 r . That is, if it is possible to construct an algorithm with the worst case error of order n −r in the class
Lower bounds. It is well known that for functions with no singularities (f
r . Unfortunately, the answer to this question is negative since any algorithm has an infinite worst case error even for the subclass F 1 r (0, ∞, ∞). To show this, let g 1 and g 2 be two r-smooth functions that will be specified later. Consider the following functions dependent on g i 's and parameterized by s ∈ (0, T ):
Lower bounds. It is well known that for functions with no singularities (f
Of course, they belong to F 1 r . Let A n be an arbitrary adaptive algorithm that evaluates f at n points x j = x j (f (x 1 ), . . . , f(x j−1 )). To simplify the notation, we will write x j = x j (f ). Since the value of f s at x depends only on whether x < s or x ≥ s, we have that
Lower bounds. It is well known that for functions with no singularities (f
Therefore, there is an interval (a, b) ⊂ (0, T ) of length T 2 −n that contains no point
Lower bounds. It is well known that for functions with no singularities (f
This means that the algorithm A n cannot distinguish between the functions f a+δ and f b−δ (for sufficiently small δ), and its error is bounded from below by
Lower bounds. It is well known that for functions with no singularities (f
for any algorithm A n . The result above does not hold for the Skorohod distance since the class F 1 r (0, 0, ∞) admits an adaptive algorithm with its worst case error equal to T 2 −n . Therefore to get a meaningful lower bound, we use different functions g i . Namely, we take g 1 (x) = A 1 + Lx and g 2 (x) = A 2 + Lx for some − 2δ) ). Note that for both functions, |A 1 − A 2 | is the discontinuity, L is the norm of the first derivative, and the norm of the rth derivative is zero. Hence we conclude that Remark 2. The convergence rate n −r cannot be improved, not only in the worst case, but also in the asymptotic setting. This follows from the general results of Trojan [27] that can be rephrased as follows. Let {A n } n be an arbitrary sequence of algorithms and {γ n } n be any positive sequence converging to infinity (however slowly). Then the set of f ∈ C r for which lim sup n→∞ f − A n f L p n r /γ n < ∞ is nowhere dense. Although the results of [27] were proven for errors measured in norms of Banach spaces, due to Proposition 1, the same result holds for the approximation problem with the Skorohod metric.
Adaptive algorithms: Multiple discontinuities
In this section, we consider functions with possibly multiple singularities. Unlike the case of one singularity, the results now depend significantly on whether the problem is considered in the worst case setting or in the asymptotic setting.
Adaptive algorithms: Multiple discontinuities
6.1. Worst case setting. A natural generalization of the class F 1 r to the case of multiple discontinuities is
Adaptive algorithms: Multiple discontinuities
k f is the vector of all discontinuity jumps of f ,
Adaptive algorithms: Multiple discontinuities
and ∆
Adaptive algorithms: Multiple discontinuities
be the nonadaptive algorithm from Proposition 3. Due to (8) , for < ∞ the worst case error of A non n over F r,q is bounded as sup
Adaptive algorithms: Multiple discontinuities
Surprisingly, this error bound cannot be improved by any other (adaptive) algorithm. We also have that for the worst case approximation in the Skorohod metric with respect to the clasŝ 
Adaptive algorithms: Multiple discontinuities
(with the convention that ∞ a = ∞ for a > 0, and ∞ 0 = 1) and 
Adaptive algorithms: Multiple discontinuities
Observe that f 1 := f * and f −1 := −f * share the same information, and they are both in F r,q . Note also that f 1 (x) = ∆k for any x ∈ (a + δk, b − δk). Therefore, for any δ, the worst case L p error of A n is at least
Adaptive algorithms: Multiple discontinuities
The bounds for = ∞ are obtained by taking → ∞ above. For the result in the Skorohod metric it suffices to note that for arbitrary D 0 the worst case error is at least
Adaptive algorithms: Multiple discontinuities
Remark 3. Consider the classes 
Adaptive algorithms: Multiple discontinuities
The results of this section can be summarized as follows. In the worst case setting, adaption helps for the classes F r only when = 1. This is in agreement with the corresponding results for the integration problem; see [21] .
Adaptive algorithms: Multiple discontinuities
Fortunately, adaption regains its superiority in the asymptotic setting discussed below.
Adaptive algorithms: Multiple discontinuities
Formally, A ad n is defined as follows. Let
Adaptive algorithms: Multiple discontinuities
and
Adaptive algorithms: Multiple discontinuities
Observe that in the worst case, the number of function evaluations is now at most n = n(m) = (r + 1)m + r m (κ m + 1) + 1.
Adaptive algorithms: Multiple discontinuities
We have the following theorem, the proof of which follows from our discussion and the proofs of Theorems 3 and 4. 
Test results
We implemented and tested both A ad n and A ad n algorithms for regularity r = 2, 4 with errors measured both in the Skorohod metric and the L 2 norm. We report the test results for the following four functions:
Test results
The functions f 3 and f 4 have five singular points with the same discontinuity jumps given by ∆
Test results
3 , ∆
Test results
4 , ∆ For interpolations P r (·, a, b) we used points equidistributed over (a, b) (including the endpoints). All the tests are performed under the choice of κ m = 2r * (log 2 (m) − log 2 (T )) . The tables provide the total number of function evaluations used (denoted by n) as well as the estimated errors (denoted respectively by sko dist and l2 error).
Test results
We begin with the first four tables, where the results for r = 2 and r = 4 are provided, respectively, in the left and right parts. The function f 1 has only discontinuity at s f = π, with the discontinuity jump 0.2π. The function f 2 has only one singular point, s f = 1; however, this time |∆
Test results
1 | = 0 and |∆ (1) 1 | = 32. Also here, the errors are proportional to m −r , and n is close to m(r − 1); see Table 2 . In addition to the errors and the number of function evaluations, we provide the number of subintervals chosen by the algorithm in the detection process. This number is marked by n sin in the second and the sixth column. Since D = 0, it is not surprising that the number n sin of detected subintervals equals (m) . Tables 3 and 4 show that the errors are quite large unless m is large enough. For f 3 we have the errors not proportional to m −r until m = 150 for r = 2 and m = 400 for r = 4. The corresponding values of m are even much higher (in the thousands) for f 4 . This is because the singular points of f 4 are clustered and require a very small spacing h in order to be distinguished from each other during the detection stage. Nevertheless, both tables are consistent with our theoretical results on the worst case and asymptotic settings for functions with multiple singularities: the former setting does not work, but the latter does. In the rest of this section, we discuss how the choice of D and/or (m) affects the efficiency of the algorithm. This is illustrated by the errors of A ad n for the function f 3 ; see Tables 5 and 6 . We begin by discussing the choice of D.
Test results
As mentioned before, a good choice would be f
Test results
L ∞ /r! or its decent estimation, which in some cases might be impossible to get. In such cases one could use the most conservative choice D = 0 (as we have done above). However, then, too, L ∞ /r! ≤ 1). We report results only for errors measured in the Skorohod distance since they are identical to those with the L 2 norm.
Test results
When the value of D is too small (say D = 0), the choice of the function (m) can worsen this problem. Indeed, this is illustrated in the following tables, where we used two different choices: For instance, in Table 6 we have the following situation. When m = 400, the algorithm uses 2369 points when (m) = 1 (m) and over 5 times more when (m) = 2 (m), even though the errors are the same. However, the choice of (m) = 1 (m) is not good for smaller values of m, since 1 (m) < 5; recall that f 3 has five singular points.
Test results
Note that when D is properly chosen (D = 1 for f 3 ), the choice of (m) is not so important as long as (m) is not smaller than the number of singularities, since then the number n sin does not change and equals 5. However, if (m) < 5, then we have the same situation as for D = 0: the errors are too large, since n sin is smaller than 5 and some singular points are not detected/localized.
Test results
However, even for poor choices of D and (m), we always have n proportional to m and the error proportional to m −r , the latter holding when m is sufficiently large. 

{'paper_id': '11520472', 'title': 'The power of adaption for approximating functions with singularities', 's2_url': 'https://api.semanticscholar.org/CorpusID:11520472', 'source': 'S2ORC'}