{'fraction_non_alphanumeric': 0.05884619831207368, 'fraction_numerical': 0.018343674130024277, 'mean_word_length': 3.8824082784571967, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bernstein-type approximation of set-valued functions in the symmetric difference metric

We study the approximation of univariate and multivariate set-valued functions (SVFs) by the adaptation to SVFs of positive samples-based approximation operators for real-valued functions. To this end, we introduce a new weighted average of several sets and study its properties. The approximation results are obtained in the space of Lebesgue measurable sets with the symmetric difference metric. In particular, we apply the new average of sets to adapt to SVFs the classical Bernstein approximation operators, and obtain a set-valued analog of the Weierstrass approximation theorem. The rate of approximation of H\"older continuous SVFs by Bernstein operators is studied and shown to be asymptotically equal to that for real-valued functions. Finally, the results obtained in the metric space of sets are generalized to metric spaces endowed with an average satisfying certain properties.

In order to adapt to SVFs sample-based approximation methods known for real-valued functions, it is required to define linear combinations of two or more sets. For most approximation methods it is sufficient to consider linear combinations with weights summing up to one, while for positive approximation operators only convex combinations (non-negative weights summing up to one) are considered. We term convex linear combinations as weighted averages.
In case of data sampled from a SVF mapping real-numbers to convex sets, methods based on the classical Minkowski sum of sets can be used for the approximation [8,27]. In this approach, sums of numbers in positive operators for real-valued approximation are replaced by Minkowski sums of sets. A generalization to sets which are either convex or differences of convex sets is done in [2], where convex sets are embedded into the Banach space of directed sets. This approach allows to apply existing methods for the approximation in Banach spaces [3].
Approximation of set-valued functions mapping real-numbers to general sets is a more challenging task. In this case, methods based on Minkowski sum of sets fail to approximate the sampled function [27,10], and other weighted averages of sets are needed.
Artstein [1] introduced a weighted average of two sets with the property that the Hausdorff metric between the average and any of the averaged sets changes linearly with the weight of the average. This average was later termed as the metric average of sets. An extension of the metric average to the weighted average of several sets, named the metric linear combination, is given in [12]. The metric linear combinations were used in [12] to adapt to sets positive and non-positive approximation operators, with the approximation error measured in the Hausdorff metric. However, the metric linear combination is applicable only to ordered sequences of sets, which limits its usage to the approximation of univariate SVFs.
As it is noticed in [1], the particular choice of a metric is crucial to the construction and analysis of set-valued approximation methods. While previous works develop and analyze set-valued approximation methods in the metric space of compact sets endowed with the Hausdorff metric, we consider here the approximation problem in the metric space of Lebesgue measurable sets with the symmetric difference metric 1 . The symmetric difference metric allows to obtain approximation results for a wider class of functions, as is demonstrated in [19], where set-valued subdivision techniques are investigated.
In this work, we consider the adaptation of positive sample-based approximation operators to univariate and multivariate SVFs . The adaptation is based on a new weighted average of several sets, termed the partition average, which is studied in details.
As it is very well known, the concept of the weighted average of numbers is closely related to that of the mathematical expectation of a discrete random variable. Similarly, a weighted average of several sets may be interpreted as the expectation of a random set [23]. We use tools from the theory of random sets to prove properties of the partition average of sets.
First, we adapt to SVFs the classical Bernstein operators, and show that these operators approximate continuous SVFs. Furthermore, we consider the rate of approximation of Hölder continuous SVFs by setvalued Bernstein operators, and obtain a result for SVFs analogous to that of Kac [17,18] for real-valued functions. Moreover, we show that the adaptation to SVFs of the classical de Casteljau's algorithm (see, e.g. [14], Chapter 4) yields another sequence of adapted operators having the same rate of approximation as that for the adapted Bernstein operators.
The results for Bernstein operators are then extended to general positive sample-based operators. Moreover, we study the application of positive sample-based operators to monotone SVFs, and show that the adapted operator is monotonicity preserving if and only if the corresponding operator for real-valued functions is monotonicity preserving.
Due to the commutativity of the partition average of sets, the results are easily generalized to approximation operators for multivariate SVFs. Finally, we generalize the approximation results to functions with values in metric spaces endowed with a weighted average, with properties similar to those of the partition average of sets.
The structure of this work is as follows. In Section 2, we survey definitions and results relevant to our work. In Section 3, we introduce the partition average of sets and study its properties. In Section 4, we adapt to sets the Bernstein approximation operators. In section 5, we study another type of set-valued Bernstein operators, obtained by adapting to sets of the de Casteljau's algorithm . In Section 6, we consider the adaptation to SVFs of positive sample-based operators. In Section 7, we discuss the approximation of monotone SVFs. The approximation of multi-variate SVFs is the subject of Section 8. Finally in Section 9, we generalize the results to functions with values in general metric spaces.

Sets and the symmetric difference metric
We denote by µ the m-dimensional Lebesgue measure and by L the collection of Lebesgue measurable subsets of R m having finite measure. The set difference of two sets A, B is and the symmetric difference is defined by The measure of the symmetric difference of A, B ∈ L, induces a pseudo-metric on L, and (L, d µ ) is a complete metric space by regarding any two sets A, B such that µ (A∆B) = 0 as equal ( [16], Chapter 8). For A, B ∈ L, such that B ⊆ A, it is easy to observe that (2.1) We use the notation ci (A) for the closure of the interior of A. A bounded set A, such that A = ci (A) is called regular compact. Regular compact sets are closed under finite unions, but not under finite intersections, yet for A, B regular compact sets such that B ⊂ A, We recall that a set A ∈ L is Jordan measurable if and only if its boundary has zero Lebesgue measure. Jordan measurable sets are denoted by J. We recall that J is closed under finite unions and finite intersections.
We denote by J the subset of J consisting of regular compact sets. Notice that for any A, B ∈ J, d µ (A, B) = 0 implies A = B, therefore d µ is a metric on J. In particular, the empty set φ is in J, and it is the only set in J having zero measure. Note that by its definition J is closed under finite unions.

Real-valued Bernstein approximation
For a function f : [0, 1] → R, the Bernstein polynomial of degree n is The mapping f (·) → B n (f, ·) is called the Bernstein operator. An extensive exposition of Bernstein polynomials is given in [7]. Obviously one can interpret (2.5) as the weighted arithmetic average of the values f j n . The probabilistic nature of the Bernstein polynomials is also well known. It can be recognized by interpreting the weights, as point probabilities of a binomial distribution with parameters n and x. The polynomials B n (f, ·) are the basis of Bernstein's proof of the Weierstrass Approximation Theorem ( [4], see [20] for a modern presentation). Using Bernstein polynomials the theorem can be formulated as A stronger version of the above theorem for Hölder continuous functions is due to Mark Kac ( [17,18], see [21] for a modern presentation). We denote by Lip (L, ν) the class of Hölder continuous functions with exponent ν and constant L, defined on [0, 1], namely functions satisfying, Our adaptation of Bernstein operators to SVFs is based on the new average of sets introduced in Section 3. To obtain the relevant properties of the new average of sets, we give it a probabilistic interpretation using the notion of a random closed set, which is discussed together with basic relevant results in the next subsection. 3

Random sets
We proceed with a few definitions regarding random sets. The following definitions and results are adapted from [23], which provides a thorough account of random sets theory.
Here we denote by F the collection of closed subsets of R m .
In the sequel we assume that X is discretely distributed, namely, X(ω) ∈ {A 0 , ..., A n }, with Pr {X = A i } = α i ≥ 0 and n i=0 α i = 1. Moreover, we assume that A i ∈ J, i = 0, ...n. Note that for any f : F → R and any random set X, f (X) defines a real-valued random variable. Random closed sets X 1 , ..., X n are said to be independent if, Notice that for discretely distributed random set X, The following relation is useful, where E denotes the expectation of a real-valued random variable. Clearly, for a discretely distributed X accepting values {A 0 , ..., A n } the integral in (2.12) can be taken over .., n one obtains from (2.9) that for independent X 1 , ...X n , Pr {u ∈ X 1 , ..., u ∈ X n } = p X1 (u) · · · p Xn (u) . (2.13) In the next section we define a new average of sets, with which we adapt the Bernstein operators to SVFs and obtain results analogous to Theorems 2.1 and 2.2.

The partition average of sets
The construction of our average of sets is built upon several definitions. We begin with The function Ψ is called the subset-generating function.
Note that since A ∈ J and Ψ (A, t) ∈ J, For any collection of sets in J, we consider a special partition of their union to mutually disjoint sets, For a fixed collection of sets {A 0 , ..., A n } we use the shorthand notation Ω χ . The collection of sets where 2 {n} denotes all subsets of the set of integers {0, ..., n}, is termed the partition of the union of A 0 , ..., A n . The sets Ω χ are termed elements of the partition.
An example of the partition of the union of three subsets on R 2 is given in Figure 1.
Here we state several properties of the partition of the union, that follow easily from Definition 3.2.
Next observation connects the notion of the partition of union with random sets. The proof of this observation follows from Definition 3.2 and (2.11).
is constant over each element Ω χ of the partition of the union of A 0 , ..., A n , and We are now in a position to define a new weighted average of sets in J, which is based on the partition of the union of the averaged sets.
where Ψ is a subset-generating function in Definition 3.1.
Using the partition average, we can define expectation of a discretely distributed random set as Remark 3.7. In view of Lemma 3.4, the partition expectation is related to the coverage function through Next we state relevant properties of the partition average of sets.
Theorem 3.8. In the notation of Definition 3.5, Proof. To obtain Property 1, observe that by Definition 3.1, Ψ (Ω χ , t) ∈ J for any χ ∈ 2 {n} , t ∈ [0, 1], and recall that J is closed under finite unions. Properties 2,3, follow immediately from the definition of the partition average. Next we prove Property 4. Letχ = {j ∈ {0, ..., n} : α j > 0}. Since Therefore, from (3.1), (2.4) and Property 4 in Lemma 3.3, The other part of Property 4, follows from the observation that Property 5 is an immediate consequence of Property 4. Next we prove Property 6. From the definition of the partition average, from the fact that the sets Ω χ : χ ∈ 2 {n} are pairwise disjoint and from the 6 properties of the subset-generating function, we obtain that To proceed with the proof of Property 6, we interpret n ⊗ i=0 α i A i as the partition expectation of a random set X, such that Pr (X = A i ) = α i , i = 0, ..., n. Now by Lemma 3.4 and by Properties 2, 5 of Lemma 3.3, Finally, we apply (2.12) to obtain that Remark 3.9. The above properties of the partition average are analogous to those of weighted averages between non-negative numbers. In this analogy, the measure of a set replaces the absolute value of a number, the measure of the symmetric difference of two sets (d µ (·; ·)) replaces the absolute value of the difference between two numbers. Moreover, the intersection and union of sets replace the minimum and the maximum of numbers, and finally the relation ⊆ between sets replaces the relation ≤ between numbers.
The next theorem treats the distance between the partition expectations of two independent random sets distributed over the same collection of sets {A 0 , ..., A n }.
Theorem 3.10. Let X 1 ,X 2 be independent random sets, Proof. It follows from the definition of the partition expectation, and by the fact that the partition elements are disjoint sets with their union equal to By the properties of the subset-generating function, for any χ ∈ 2 {n} one of the two sets Ψ Ω χ , i∈χ α i , Ψ Ω χ , i∈χ β i is necessarily contained in the other, and we get from (2.1), On the other hand, Since X 1 , X 2 are independent, and we obtain from (2.12), Using similar observations for E (µ (X 2 \X 1 )), we arrive at It is easy to obtain the claim of the theorem, by inspecting the relations (3.8) and (3.9), since From the above theorem we obtain, Corollary 3.11. Let X be a random set, Pr {X = A i } = α i , i = 0, ..., n. Then
Proof. Consider the random set X, Pr X = A i = δ ij , i = 0, .., n with δ ij = 1 for i = j and δ ij = 0 otherwise. By Property 5 of Theorem 3.8, E P X = A j , thus from Theorem 3.9, Since p X (u) ∈ {0, 1}, if follows from (3.10), that there is an equality in (3.12). Approximation results in the next section are based upon the following corollary, which is derived from Corollary 3.11. (3.13) Namely, the distance to the partition average from any of the averaged sets is equal to the average of the distances from this set to all the averaged sets. where r, p i , i = 0, ..., n are numbers. However, notice that there is equality in (3.13) versus inequality in (3.14). Moreover, observe that (3.13) applies only to the sets participating in the partition average, while (3.14) applies to any r ∈ R. This limitation has implications to the approximation power of methods based on the partition average.
The partition average of two sets possesses also the metric property [9] relative to d µ (·, ·).
Proof. Let X 1 , X 2 be random sets such that Pr ( To complete the construction of the partition average of sets, we need to provide a concrete example of a subset-generating function in Definition 3.1. We denote by Bl (p, r) a ball of radius r about p ∈ R m , namely where r A,t is chosen so that µ (Ψ (A, t)) = tµ (A). The existence of r A,t as above for any t ∈ [0, 1] follows from the continuity of the volume of the ball as a function of its radius. An example of the partition average with a such defined subset-generating function Ψ is shown in Figure 2. In this example, p is the centroid of the union of the averaged sets. Although there is a significant resemblance between the partition average of sets and the weighted average of numbers as is noticed in Remarks 3.9 and 3.13, the partition average of sets lacks several important properties of the weighted average of numbers.
Remark 3.15. The partition average is generally not associative, Remark 3.16. Zero-weighted sets in (3.3) affect the partition average by affecting the partition of the union of all the sets, namely,

Set-valued Bernstein approximation based on the partition average
Using the partition average of sets defined in the previous section, we can now define a set-valued operator analogous to (2.5), Definition 4.1. The the set-valued Bernstein operator is the mapping F (·) → B n (F, ·) given by  The proof of Theorem 4.2 is based on the following two lemmas.
Proof. By the triangle inequality, We obtain from Corollary 3.12 that and by the triangle inequality, This together with (4.4) and (4.5) completes the proof.
It is easy to observe that due to the continuity of F , the family of functions {g x (·) : x ∈ [0, 1]} is uniformly equicontinuous and uniformly bounded.
Next we note that By continuity of F , there exists a positive integer N 2 s.t. for |x − y| < 1 N2 , x, y ∈ [0, 1], d µ (F (x) , F (y)) < ε 4 . We set N = max {N 1 , N 2 } and apply Lemma 4.3 to obtain the claim of the theorem.
Next we consider the rate of approximation of Hölder continuous SVFs by the set-valued Bernstein operator. The class of Hölder continuous SVFs, Lip (L, ν), is defined as in (2.7), using d µ (·, ·) instead of the distance between numbers.
Note that for a fixed x ∈ (0, 1), the term L , so the results obtained in Theorem 2.2 and Theorem 4.5 are asymptotically equivalent.

Set-valued Bernstein approximation with the de Casteljau's algorithm
A widely used method for the evaluation of the real-valued Bernstein operators B n (f, x) is the de Casteljau's algorithm (see, e.g. [14], Chapter 4). The algorithm evaluates B n (f, x) through a sequence of averages of two numbers (binary averages) and is based on the following recurrence relation, where b (n, x; i) are given in (2.6). B n (f, x) in (2.5) can be represented using (5.1) as, with F n i = F i n , andB n (F, x) is set to be F 0 0 . Note that by Remark 3.15, this adaptation yields a setvalued operator which is different from that in (4.1). The above construction is similar to that in [13] with the metric average. Similarly to [13], we do not expect that for a general SVF F,B n (F, x) converges to F (x) as n → ∞.
We now alter the adaptation and apply Corollary 3.12, to obtain approximation results similar to Theorems 4.2 and 4.5 also in the case of the de Casteljau's representation of the Bernstein operators. To this end we use a binary average, based on the partition determined by F i n , i = 0, ..., n, of the form where E i = F i , i = 0, ..., n, E n+1 = A, E n+2 = B and β i = 0, i = 0, ..., n, β n+1 = λ, β n+2 = 1 − λ. Then we apply the de Casteljau's algorithm with this average, namely and set, Since F i n , i = 0, ..., n, is in the partition behind⊗, we get from (5.7) and Corollary 3.12, that Continuing the recursion we finally obtain the real-valued de Casteljau's algorithm for the function g i n defined in (4.7), namely with the initial data Therefore by (5.8) we have for i = 0, ..., n, The equality (5.9) is the same as (4.5), and therefore Theorems 4.2 and 4.5 also apply to the set-valued Bernstein operators defined by the de Casteljau's algorithm with the binary average (5.6).

Approximation of SVFs by positive sample-based operators
We consider the adaptation to SVFs of families of positive sample-based operators for real-valued functions, defined for n ∈ N as Other examples are the piecewise linear interpolation operator and the Schoenberg spline operators [26].
In analogy to the adaptation of the Bernstein operators to SVFs, we define for F : [0, 1] → J, The first result is obtained immediately due to Property 6 in Theorem 3.8 of the partition average, Then, sup Approximation of continuous functions by positive operators are discussed in ( [15], Chapter VII, §1) in the context of probability theory, while approximation results for Hölder continuous real-valued functions are the subject of [22].

Approximation of monotone SVFs
Next we obtain several results specific to the approximation of monotone SVFs by positive sample-based operators. We begin with a simple condition for the monotonicity preservation by positive sample-based operators for real-valued functions. β i = 1, such that for any integer k, The condition (7.1) is necessary and sufficient for the inequality, to hold for any monotone non-decreasing sequence of numbers r 0 , ..., r n ∈ R.
Proof. The necessity follows by considering sequences of the form r 0 = r 1 = ... = r k < r k+1 = r k+2 ... = r n . The sufficiency can be obtained by setting, .., n, and considering the contribution of each ∆ i in (7.2). In case r 0 , ..., r n is monotone non-increasing, condition (7.1) implies by symmetry, that Corollary 7.2. LetÕ n (F, x) be a positive sample-based operator defined as in (6.2), such that for any x, y ∈ [0, 1],x ≤ y, the weights α i = c n,i (x), β i = c n,i (y) satisfy (7.1). ThenÕ n is monotonicity preserving.
Next we show that similar conditions are necessary and sufficient for the monotonicity preservation by positive sample-based operators for SVFs. A sequence of sets {F i } i∈Z is termed monotone non-decreasing (non-increasing), if for all i, F i ⊆ F i+1 (F i ⊇ F i+1 ). Monotone non-decreasing (non-increasing) SVFs are defined in a similar way. Lemma 7.3. Let α 0 , ..., α n , β 0 , ..., β n be as in Lemma 7.1, then condition (7.1) is necessary and sufficient for the relation, to hold for any monotone non-decreasing sequence of sets A 0 , ..., A n ∈ J.
Proof. In view of Property 3 of Theorem 3.8, the necessity follows by considering sequences of the form To obtain the sufficiency, assume that A 0 , ..., A n is monotone non-decreasing and let Ω χ be as in Definition 3.2. We observe that due to the monotonicity of the sequence A 0 , ..., A n , if Ω χ = φ then necessarily χ = {k, k + 1, ..., n} for some integer k, 0 ≤ k ≤ n. Using (7.1) and Definition 3.1 we obtain that for Ω χ as above, which in view of Definition 3.5 of the partition average completes the proof of the lemma.
In case A 0 , ..., A n is monotone non-increasing, condition (7.1) implies by symmetry, that To obtain from (7.1) that the Bernstein approximation operators are monotonicity preserving, we need to show that for 0 ≤ x 1 ≤ x 2 ≤ 1, 0 ≤ k < n, This can be observed from the properties of the cumulative binomial distribution [28], which is clearly monotone non-increasing in x and thus leads to (7.3).
To continue the discussion, we recall the notion of the speed of a curve in a metric space (see e.g. [5], Chapter 2), which indicates the "smoothness" of a set-valued function. For a real-valued f the speed at a point whenever the limit exists. For differentiable f , v f is the absolute value of the derivative of f . The speed of a SVF F is defined as Using relation (2.1) and Corollary 6.1, we obtain Corollary 7.6. Let O n and O n be monotonicity preserving operators defined as above. Then for a monotone SVF F, the speed of O n (F, ·) equals that of O n (µ (F ) , ·).
In particular, for the Bernstein set-valued operators applied to a monotone SVF F, the speed of B n (F, ·) is a polynomial, since B n (µ (F ) , ·) is a monotone polynomial and therefore its speed is a polynomial too.

Approximation of multivariate SVFs
The results of Section 6 can be generalized to SVFs defined on a compact subset K of R d . In this case we adapt to SVFs families of positive sample-based operators of the form, Chapter XVII) and multivariate Bernstein polynomials on simplices (see e.g. [22]). Similarly to the univariate case, we define for F : K → J, With definitions (8.1)-(8.3), the analogs of Corollaries 6.1, 6.2 and 6.3 for multivariate SVFs are easily derived.
As an example of the application of (8.3), we consider the adaptation to SVFs of the piecewise linear interpolation over triangulations (see, e.g. [14], Chapter 3). We briefly recall that for a collection of points P = {p 1 , ..., p l } ⊂ R 2 , the triangulation Γ of P is a collection of triangles such that • The vertices of the triangles consist of points in P .
• The interiors of any two triangles do not intersect.
• If two triangles are not disjoint, then they share either a vertex or an edge.
• No edge can be added between points in P without intersecting an edge of one of the triangles in Γ.
In the notation of (8.1), let P 0 = {p 0,1 ....p 0.l0 } ⊂ R 2 , and let K be the convex hull of the points in P 0 . Assume that the sequence {P n } n∈N is nested, P 0 ⊂ P 1 ⊂ P 2 .... Let Γ n be a triangulation of P n , such that lim n→∞ ∆ n = 0 , where ∆ n = max T ∈Γn diam (T ) and diam (T ) is the diameter of the circumscribed circle of T . Note that for such a sequence of triangulations condition (8.2) is satisfied.
Let the triangle ∆ = p n,k1 , p n,k2 , p n,k3 be in Γ n and let p ∈ ∆. The piecewise linear interpolantL n (f, p) is defined as in (8.1) with the weights c n,i (p) given by c n,k1 (p) = area(p,p n,k 2 ,p n,k 3 ) area(p n,k 1 ,p n,k 2 ,p n,k 3 ) , c n,k2 (p) = area(p n,k 1 ,p,p n,k 3 ) area(p n,k 1 ,p n,k 2 ,p n,k 3 ) , c n,k3 (p) = area(p n,k 1 ,p n,k 2 ,p) area(p n,k 1 ,p n,k 2 ,p n,k 3 ) , Similarly, for a SVF F , the piecewise interpolant L n (F, p) is defined as in (8.3), with the weights c n,i (p) given by (8.4)-(8.5). Using Corollaries 6.2 and 6.3 extended to multivariate SVFs, we obtain that for a continuous Moreover, while L n (F, p) is continuous by its definition,L n (F, p) is discontinuous in view of Remark 3.16.

Approximation of functions with values in general metric spaces
Finally, we extend the approximation results for functions with values in the metric space {J, d µ } and the partition average to functions with values in general metric spaces endowed with an average satisfying certain properties. Let {X, d X } be a metric space, and let be an average on elements of X defined for non-negative weights. Assume that the average satisfies the conditions, that for any Λ 0 , ..., Λ n ∈ X and α 0 , ..., α n ∈ [0, 1], With these definitions, it is straightforwardly to obtain approximation results similar to Corollaries 6.2 and 6.3.