Abstract
One of the basic principles of Approximation Theory is that the quality of approximations increase with the smoothness of the function to be approximated. Functions that are smooth in certain subdomains will have good approximations in those subdomains, and these sub-approximations can possibly be calculated efficiently in parallel, as long as the subdomains do not overlap. This paper proposes a class of algorithms that first calculate sub-approximations on non-overlapping subdomains, then extend the subdomains as much as possible and finally produce a global solution on the given domain by letting the subdomains fill the whole domain. Consequently, there will be no Gibbs phenomenon along the boundaries of the subdomains. Throughout, the algorithm works for fixed scattered input data of the function itself, not on spectral data, and it does not resample.
Introduction
Assume that a large set {(x i , f i ), i = 1, . . . , N} of data is given, where the points x i are scattered in R d and form a set X . We want to find a function u that recovers the data on a domain Ω containing the points, i.e.
Introduction
We are particularly interested in situations where the data have smooth interpolants in certain non-overlapping subdomains Ω j , but not globally. The reason may be that there are discontinuities in the function itself or its derivatives. Thus a major goal is to identify subdomains Ω j ⊆ Ω, 1 ≤ j ≤ J and smooth functions u j , 1 ≤ j ≤ J such that u j : Ω j → R, u j (x i ) ≈ f i for all x i ∈ X ∩ Ω j .
Introduction
The solution to the problem is piecewise defined as u(x) := u j (x) for all x ∈ Ω j , 1 ≤ j ≤ J.
Introduction
Our motivation is the well-known fact that errors and convergence rates in Approximation Theory always improve with increasing smoothness. Thus on each subdomain we expect to get rather small errors, much smaller than if the problem would have been treated globally, where the non-smoothness is a serious limiting effect.
Introduction
From the viewpoint of Machine Learning [3, 8, 9] this is a mixture of classification and regression. The domain points have to be classified in such a way that on each class there is a good regression model. The given training data are used for both classification and regression, but in this case the classification is dependent on the regression, and the regression is dependent on the classification.
Introduction
Furthermore, there is a serious amount of geometry hidden behind the problem. The subdomains should be connected, their interiors should be disjoint, and the union of their closures should fill the domain completely. This is why a black-box machine learning approach is not pursued here. Instead, Geometry and Approximation Theory play a dominant part. For the same reason, we avoid to calculate edges or fault lines first, followed by local approximations later. The approximation properties should determine the domains and their boundaries, not the other way round.
Introduction
In particular, localized approximation will combine Geometry and Approximation Theory and provide a central tool, together with adaptivity. The basic idea is that in the interior of each subdomain, far away from its boundary, there should be a good and simple approximation to the data at each data point from the data of its neighbors.
An Adaptive Algorithm
Localized approximation will be used as the first phase of an adaptive algorithm, constructing disjoint localized subsets of the data that allow good and simple local approximations. Thus this "localization" phase produces a subset X g ⊆ X of "good" data points that is the union of disjoint sets X g 1 , . . . , X g J consisting of data points that allow good approximations u g j ∈ U, 1 ≤ j ≤ J using only the data points in X g j . In some sense, this is a rough classification already, but only of data points. The goal of the second phase is to reduce the number of unclassified points by enlarging the sets of classified points. It is tacitly assumed that the final number 3 of subdomains is already obtained by the number J of classes of "good" points after the first phase. The "blow-up" of the sets X g j should maintain locality by adding neighboring data points first, and adding them only if the local approximation u g j does not lose too much quality after adding that point and changing the approximation.
An Adaptive Algorithm
The second phase usually leaves a small number of "unsure" points that could not be clearly classified by blowing up the classified sets. While the blow-up phase focuses on each single set X g j in turn and tries to extend it by looking at all "unsure" points for good extension candidates, the third phase works the other way round. It focuses on each single "unsure" point x i in turn and looks at all sets X g j and the local approximations u j on these, and assigns the point x j to one of the sets X g j so that u j (x i ) is closest to f (x i ). It is a "final assignment" phase that should classify all data points and it should produce the final sets X Thus the determination of subdomain boundaries from a classification of data points could be the task of a fourth phase. It could, for instance, be handled by any machine learning program that uses the classification as training data and classifies each given point x accordingly. But this paper does not implement a fourth phase, being satisfied if each approximation u f j is good on each set X f j , and much better than any global approximation u * ∈ U to all data.
Implementation
The above description of a three-phase algorithm allows a large variation of different implementations that compete for efficiency and accuracy. We shall describe a basic implementation together with certain minor variants, and provide numerical examples demonstrating that the overall strategy works fine.
Implementation
We work on the unit square of R 2 for simplicity and take a trial space U spanned by translates of a fixed positive definite radial kernel K. In our examples, K may be a Gaussian or an inverse multiquadric. For details on kernels, readers are referred to standard texts [2, 10, 7, 4] , for example. When working on finite subsets of data points, we shall only use the translates with respect to this subset. Since the kernel K is fixed, also the Hilbert space H is fixed in which the kernel is reproducing, and we can evaluate the norm . K of trial functions 4 cheaply and exactly.
Implementation
To implement locality, we assume that we have a computationally cheap method that allows to calculate for each x ∈ R 2 its n nearest neighbors from X . This can, for instance, be done via a range query after an initialization of a kd-tree data structure [1] .
Phase 1: Localization
This is carried out by a first step picking all data points with good localized approximation properties, followed by a second step splitting the set X g of good points into J disjoint sets X g j .
Good Data Points
We assume that the global fill distance
Good Data Points
of the full set of data points with respect to the full domain Ω is roughly the same as the local fill distances h(X f j , Ω j ) of the final splitting. The basic idea is to loop over all N data points of X and to calculate for each data point x i , 1 ≤ i ≤ N a number σ i that is a reliable indicator for the quality of localized approximation. Using a threshold σ , this allows to determine the set X g ⊆ X of "good" data points, without splitting it into subsets.
Good Data Points
There are many ways to do this. The implementation of this paper fixes a number n of neighbors and loops over all N data points to calculate for each data point
Good Data Points
This loop can be executed with roughly O(Nn 3 ) complexity and O(N + n 3 ) storage, and with easy parallelization, if apham@example.org. A similar indicator would be the error obtained when predicting f (x i ) from the values at the n neighboring points.
Good Data Points
Practical experience shows that the numbers σ i are good indicators of locality, because adding outliers to a good interpolant usually increases the error norm dramatically. Many of the σ i can be expected to be small, and thus the threshold σ i < 2M σ will be used to determine "good" points within the next splitting step, see Section 3.1.2, where M σ is the median of all σ i . This is illustrated for a data set by Figure  1 : it represents, in base loglog scale, the sorted {σ i } and the constant line relevant to the value of the threshold. 
Splitting
The set X g of points with good localization must now be split into J disjoint subsets of points that are close to each other. We assume that the inner boundaries of the subdomains are everywhere clearly determined by large values of σ i .
Splitting
The implementation of this paper accomplishes the splitting by a variation of Kruskal's algorithm [5] for calculating minimal spanning trees in graphs.
Splitting
The Kruskal algorithm sorts the edges by increasing weight and starts with an output graph that has no edges and no vertices. When running, it keeps a number of disconnected graphs as the output graph. It gradually adds edges with 6 increasing weight that either connect two previously disconnected graphs or add an edge to an existing component or define a new connected component by that single edge.
Splitting
In the current implementation the edges that connect each x i with its n − 1 nearest neighbors are collected in an edge list. The edge list is sorted by increasing length of the edges and then, by n | X | comparisons, many repetitions of edges are removed, and these are all repetitions if any two different edges have different length.
Splitting
Then the thresholding of the {σ i } by
Splitting
is executed, and it is known which points are good and which are bad. All edges with one or two bad end points are removed from the edge list with cost n | X |.
Splitting
After the spanning tree algorithm is run, the list of the points of each tree is intersected with itself to avoid eventual repetitions that are left. At the end, each connected component is associated to its tree in exactly one way.
Splitting
In rare cases, the splitting step may return only one tree, but these cases are detected and repaired easily.
Phase 2: Blow-up
This is also an adaptive iterative process. It reduces the set X u := X \ ∪ J j=1 X g j of "unsure" data points gradually, moving points from X u to one of the nearest sets X g j . In order to deal with easy cases first, the points x i in X u are sorted by their locality quality such that points with better localization come first. We also assume that for each point x i ∈ X u we know its distance to all sets X g j , and we shall update this distance during the algorithm, when the sets X u and X g j change.
Phase 2: Blow-up
We also use the distances to the sets X g,0 j that are the output of the localization phase and serve as a start-up for the sets X g j . In an outer loop we run over all points x i ∈ X u with decreasing quality of local approximation. In our implementation, this means increasing values of σ i . The inner loop runs over the m sets X g j to which x i has shortest distance. In most cases, and in particular in R 2 , it will suffice to take m = 2. The basic idea is to find the nearby set X g j of "good" points for which the addition of x i does least damage to the local approximation quality. 
Phase 3: Final Assignment
The assignment of a point x i ∈ X u to a set X g j is done on the basis of how well the function value f (x i ) is predicted by u j (x i ). We loop over all points x i ∈ X u and first determine two sets X g j and X g k to which x i has shortest distance. This is done in order to make sure that x i is not assigned to a far-away X g j . We then could add
Phase 3: Final Assignment
in case that we have more than one unsure point, we want to make sure that under all unsure 8 points, x i fits better into X g j than into X g k . Therefore we calculate
Phase 3: Final Assignment
for all j and i beforehand, and assign
Examples
Some test functions are considered now, each of which is smooth on J = 2 subdomains of Ω. The algorithm constructs X . This is due to the fact that standard domain boundaries, even without any domain splittings, let the approximation quality decrease near the boundaries.
Examples
To be more precise, let Ω sa f e be the union of the circles of radius q := min 1≤i< j≤N
Examples
the separation distance of the data sites, centered at those points of X g j , j = 1, 2 such that the centered circles of radius 2q do not contain points of X g k with k = j. We then evaluate L sa f e
Examples
The chosen kernel for calculating the local kernel-based interpolants is the inverse multiquadric kernel φ (r) = (1 + 2r 2 /δ 2 ) −1/2 with parameter δ = 0.35. In all cases, N = 900 data locations are mildly scattered on a domain Ω that extends [0, 1] 2 a little, with q = 0.04. We shall restrict to [0, 1] 2 to evaluate the subapproximant, calculated by the basis in the Newton form. Such a basis is much more stable than the standard basis, see [6] . The error is computed on a grid with step 0.01. For comparison, the errors of the global interpolant are
Examples
The classification turns out to be correct. 890 out of 900 data points are correctly classified as output of phase 3.2, and then phase 3.3 completes the classification. The actual error L ∞ (u) = 6.0·10 −2 is not much affected if we omit Phase 3 and and ignore the remaining 10 "unsure" points after the blow-up phase. A similar effect is observed for the other examples to follow.
Examples
A zoomed area of Ω is considered in Figure 3 . The details are related to an iteration of the blow-up phase, where the "unsure" point x i (both squared and starred) is currently examined. Points of X For comparison, the errors of the global interpolant are
Examples
The classification turns out to be correct. 888 out of 900 data points are classified correctly as output of phase 3.2, and phase 3.3 completes the classification for the remaining 12 points. It might be that u f j is more accurate on the safe zone, and also globally. 
Examples
is regular but has a steep gradient. Our algorithm yields 
Examples
has a jump on the line x = 0.5 and a derivative singularity on it at (0.5, 0.5). It has rather a steep gradient too. One data point close to the singularity is not classified correctly. We get 11 Figure 5 shows the points of X f 1 as dotted and those of X g 2 as crossed. All examples show that the transition from a global to a properly segmented problem decreases the achievable error considerably. But the computational cost is serious, and it might be more efficient to implement a multiscale strategy that works on coarse data first, does the splitting of the domain coarsely, and then refines the solution on more data, without recalculating everything on the finer data. 

{'paper_id': '119233524', 'title': 'Adaptive Approximation of Functions with Discontinuities', 's2_url': 'https://api.semanticscholar.org/CorpusID:119233524', 'source': 'S2ORC'}