(ProQuest: ... denotes non-US-ASCII text omitted.)
Martin Ehler 1 and Frank Filbir 2, 3
Academic Editor:Carlo Cattani
1, Department of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria
2, Faculty of Mathematics, Technische Universität München, Boltzmannstraße 3, 85748 Garching, Germany
3, Helmholtz Zentrum München, Ingolstädter Landstraße 1, 85764 Neuherberg, Germany
Received 13 February 2014; Accepted 19 May 2014; 17 June 2014
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
Data processing in the digital era often deals with finitely many high-dimensional data chunks stemming from measurements that obey some continuous physical model. The implementation and numerical evaluation require estimates on the accuracy of the discretization with respect to the underlying model. As an elementary tool providing accuracy guarantees, we will address [varepsilon] -coverings of some function spaces related to information theory and machine learning.
As a standard concept in discrete mathematics, the [varepsilon] -covering number n [varepsilon] ( Y ) is the minimal number of balls of radius [varepsilon] that cover a compact metric space Y . An arbitrary element in Y can be represented by a nearby center preserving precision up to [varepsilon] . As such, [varepsilon] -coverings are also an integral part of approximation theory, especially if Y is some function space. Covering numbers capture the complexity of Y and the approximation aspects are used in many fields such as information theory, statistics, nonparametric density estimation, and machine learning. There are estimates on the asymtotics of the [varepsilon] -covering numbers of the standard function spaces (cf. [1, 2]), but some fields such as machine learning involve data lying on some manifold, so that target functions are naturally defined on this manifold. To clarify the terminology, we consider smoothness spaces on manifolds as somewhat nonstandard function spaces. It may be possible that the covering number of a function space on some compact Riemannian manifold can be assembled by covering numbers of standard function spaces on Euclidian spaces derived from the charts. However, it is also important to derive explicit [varepsilon] -coverings whose cardinality is near the benchmark given by the [varepsilon] -covering number. We believe that explicit coverings may be harder to construct using the charts due to interface problems, and therefore we will not pursue this direction and, instead, we will follow a more global approach.
In general, there is still demand for computing coverings of many discrete and continuous spaces [3]. As an important additional requirement, any covering of a function space needs to come with an algorithmic scheme to determine some function's nearby center in an effective manner. At first sight, the latter seems simple enough as we can take the center whose distance is minimal. However, determining the distance between two functions is eventually a continuous operation, and one is particularly interested in finite methods.
In this paper, we first determine the asymtotics of the [varepsilon] -covering number for the unit ball of some Hölder-Zygmund type space Y = C s ( X ) on an underlying smooth compact Riemannian manifold X (without boundary and with nonnegative Ricci curvature). In fact, we determine the asymtotics of the metric entropy log ... 2 ( n [varepsilon] ( Y ) ) , which is the number of bits needed to enumerate the [varepsilon] -covering (cf. [1]). Moreover, we compute an explicit [varepsilon] -covering, such that [figure omitted; refer to PDF] where n ^ [varepsilon] is the cardinality of the constructed covering and [<, ~] means that the left-hand side can be bounded by a generic constant times the right-hand side. Hence, our covering is optimal up to a logarithmic factor by means of the metric entropy. We allow the underlying manifold to be unknown in our scheme and, instead, to be represented through a finite sampling. This sampling must be chosen carefully and is the key to obtaining a finite scheme. The centers of our [varepsilon] -covering can then be determined through a finite process, and we can measure any function's distance to these centers in a finite manner.
For constructions of [varepsilon] -coverings on periodic smoothness spaces, for instance, we refer to [4, 5]. The concept of [varepsilon] -entropy is also closely related to entropy numbers; see [6-8].
The outline of this paper is as follows. In Section 2 we introduce the setting, define the Hölder-Zygmund type space C s ( X ) , and determine the metric entropy for its unit ball. An explicit covering is computed in Section 3.
2. Covering Numbers for Hölder-Zygmund Type Spaces
We first fix the setting and list some technical assumptions used throughout the paper. Let X ⊂ R d be an α -dimensional compact and connected Riemannian manifold without boundary and with nonnegative Ricci curvature, geodesic distance ρ , and μ being the normalized Riemannian volume measure on X ; { [straight phi] k } k = 0 ∞ are the eigenfunctions of the Laplacian on X , and { - λ k 2 } k = 0 ∞ are the corresponding eigenvalues arranged in nonincreasing order, so that 0 = λ 0 ...4; λ 1 ...4; ... . Readers who are not familiar with some terms from differential geometry that are used here may simply think of a "nice" manifold without boundary, such as the sphere, the real projective space, the (real) Grassmann manifold, or more generally compact homogeneous spaces. The above properties ensure certain estimates on the heat kernel on X (see [9, 10]), which were used in a series of papers [9, 11-13] to develop approximation schemes for smooth functions on the manifold. Here, we will make use of those approximation schemes, but we will keep the technical details at a minimum level.
Let N be a positive integer and most of the time we will restrict ourselves to N = 2 j , where j is some nonnegative integer. The space of diffusion polynomials up to degree N is [figure omitted; refer to PDF] Later, we will use the fact that the above conditions imply the following estimate on the Christoffel function: [figure omitted; refer to PDF] (cf. [9-11]), so that integration and orthonormality yield dim ... ( Π N ) [asymptotically =] N α . Here, the symbol [asymptotically =] indicates that each side is bounded by a generic positive constant times the other side.
In traditional scenarios, the accuracy of approximation by polynomials is closely related to the smoothness of the function. Therefore, the accuracy of approximation itself is nowadays considered to be a measurement of smoothness. This viewpoint is particularly useful in our setting because defining smoothness in a classical manner would require more technical details. Here, we define the Hölder-Zygmund type space of order s > 0 by C s ( X ) = { f ∈ L ∞ ( X ) : || f || C s ( X ) < ∞ } , where its norm is given by [figure omitted; refer to PDF] with E ( f , Π N , L ∞ ( X ) ) ... = inf ... g ∈ Π N || f - g || L ∞ ( X ) . Hence, f ∈ L ∞ ( X ) is contained in the Hölder-Zygmund type space if and only if it can be approximated by Π N at rate N - s . Since the eigenfunctions { [straight phi] k } k = 0 ∞ are known to be smooth and we consider the L ∞ -norm, each function in C s ( X ) has a continuous representative and point evaluation makes sense. The unit ball in C s ( X ) is denoted by C s ¯ ( X ) ... = { f ∈ L ∞ ( X ) : || f || C s ( X ) ...4; 1 } . To compute its covering number, we first establish compactness. Since C s ( X ) is not finite-dimensional, C s ¯ ( X ) is not compact in the Hölder-Zygmund type space, but we consider it as a subspace of L ∞ ( X ) .
Lemma 1.
The set C s ¯ ( X ) is compact in L ∞ ( X ) .
The compactness of this embedding can be derived from (4) by abstract arguments involving Kolmogorov numbers (cf. [6]). Here, we provide a simple elementary proof for the sake of completeness.
Proof.
We aim to verify that any sequence ( f j ) j = 1 ∞ ⊂ C s ¯ ( X ) must have an accumulation point in this set. Since each space Π N is finite-dimensional, there are g j , N ∈ Π N , such that || f j || L ∞ ( X ) + sup ... N ...5; 1 N s || f j - g j , N || L ∞ ( X ) ...4; 1 . The latter implies that || g j , N || L ∞ ( X ) is bounded for all j and N . Thus, there is g 1 ∈ Π 1 such that the subsequence ( g π 1 ( j ) , 1 ) j = 1 ∞ converges towards g 1 . For any N = 1,2 , ... , we can recursively construct g N ∈ Π N such that [figure omitted; refer to PDF] and ( g π N ( j ) , k ) n = 1 ∞ is a subsequence of ( g π N - 1 ( j ) , k ) n = 1 ∞ . For N [variant prime] ...5; N , this construction yields that ( g π N [variant prime] ( j ) , N ) j = 1 ∞ is a subsequence of ( g π N ( j ) , N ) j = 1 ∞ , so that we derive [figure omitted; refer to PDF] Therefore, ( g N ) N = 1 ∞ is a Cauchy sequence and, hence, converges towards some g ∈ L ∞ ( X ) . Standard calculations reveal that g is an accumulation point of ( f j ) j = 1 ∞ and is contained in C s ¯ ( X ) , which concludes the proof.
We can now derive the asymptotes of the [varepsilon] -covering number of C s ¯ ( X ) in L ∞ ( X ) .
Theorem 2.
If s > 0 is fixed and 0 < [varepsilon] ...4; 1 , then [figure omitted; refer to PDF] holds, where the generic constants do not depend on [varepsilon] .
Analogous results can be derived for similar concepts such as different types of n -widths of functions spaces (cf. [14-16]). Theorem 2 and its proof are rather classical and can be derived from [17]. To guide the interested reader, we will provide the outline of the proof that is based on a general Banach space result and is also used in [18, Theorem 4.1]. Let X be a Banach space and let { [varphi] k } k = 1 ∞ ⊂ X be a sequence of linearly independent elements whose linear span is dense in X , and define X k ... = span ... { [varphi] 1 , ... , [varphi] k } with X 0 = { 0 } . Let { δ k } k = 0 ∞ be a nonincreasing sequence of positive numbers with lim ... k [arrow right] ∞ δ k = 0 . The full approximation space is [figure omitted; refer to PDF] A proof similar to Lemma 1 yields that this space is compact, and we can formulate the result from Banach space theory that goes back to Lorentz in [17].
Theorem 3 (see [19, Theorem 3.3]).
Let { δ k } k = 0 ∞ be a nonincreasing sequence of positive numbers such that δ 2 k ...4; c δ k , for k = 1,2 , ... and some constant c ∈ ( 0,1 ) . For l ...5; 0 , let M l : = min ... { k : δ k ...4; e - l } . If n [varepsilon] denotes the [varepsilon] -covering number of A ( X ; { δ k } k = 0 ∞ , { [varphi] k } k = 1 ∞ ) in X , then one has, for 0 < [varepsilon] ...4; 1 , [figure omitted; refer to PDF] where L : = 2 + [left floor] log ... ( 1 / [varepsilon] ) [right floor] .
At this point our preparations are complete.
Proof of Theorem 2.
We aim to apply Theorem 3 with the function system { [straight phi] k } k = 0 ∞ and with X being the closure of ... N = 1 ∞ ... Π N in L ∞ ( X ) . There, the index set is supposed to start with k = 1 , so we set [varphi] k = [straight phi] k - 1 , k = 1,2 , ... . To define the sequence { δ k } k = 0 ∞ , we need some preparations. As pointed out before, integrating (3) over X yields dim ... ( Π N ) [asymptotically =] N α . By using X k ... = span ... { [straight phi] 0 , ... , [straight phi] k - 1 } , we derive, for N α ...4; k ...4; ( 2 N ) α , [figure omitted; refer to PDF] Therefore, there are constants C i ...5; 1 , for i = 1,2 , such that the definitions δ 1 ; 0 = 1 / 2 , δ 1 ; k ... = ( 2 C 1 ) - 1 k - s / α , and δ 2 ; 0 = C 2 , δ 2 ; k ... = C 2 k - s / α , lead to [figure omitted; refer to PDF] which also yields [figure omitted; refer to PDF] Since δ i ; 2 k ...4; c δ i ; k , for c : = 2 - s / α ∈ ( 0,1 ) , we can apply Theorem 3. According to [18, Lemma 4.1], ∑ l = 1 L ... M l [asymptotically =] e L α / s , so that the choice of L in (9) implies (7).
Remark 4.
The proof of Theorem 2 discovers that (7) also holds under much weaker conditions, and we have only used the fact that there is a sequence of linearly independent functions { [straight phi] k } k = 0 ∞ , so that the polynomial spaces in (2) satisfy dim ... ( Π N ) [asymptotically =] N α .
3. Near Optimal Covering
This section is dedicated to constructing our covering of the unit ball in the Hölder-Zygmund type space, which is based on localized summation kernels as developed in a series of papers [9, 11-13]. We first need some preparations. A Borel probability measure ν on X is called a quadrature measure of order N if [figure omitted; refer to PDF] Note that our setting yields that there is a constant a > 0 such that f · g ∈ Π a N for all f , g ∈ Π N and all N (cf. [11, Theorem A . 1 ]); see also [20] for homogeneous spaces. The existence of quadrature measures with finite support is proved for fairly general smooth Riemannian manifolds in [11], where a construction procedure is outlined. In fact, the support of ν can be chosen to be contained in any sufficiently dense finite sampling { x l } l = 1 m of X , so that ν can be identified with { x l } l = 1 m and nonnegative weights { ω l } l = 1 m satisfying ν ( { x l } ) = ω l . Examples on the sphere, for instance, are given in [21].
The results in [11] yield that we can even choose a sequence ( ν N ) N = 1 ∞ of quadrature measures of order N , respectively, such that # supp ... ( ν N ) [<, ~] N α . For the remaining part of the paper, we will suppose that this estimate holds and we define, for N = 2 j , [figure omitted; refer to PDF] where h : R ...5; 0 [arrow right] R is an infinitely often differentiable and nonincreasing function with h ( t ) = 1 for t ...4; 1 / 2 and h ( t ) = 0 for t ...5; 1 . Although we will not explicitly use it in the present paper, we want to point out that many advantageous properties of σ N are steered by the so-called localization of the kernel K N ; that is, for fixed S > α and all x ...0; y with N = 1,2 , ... , [figure omitted; refer to PDF] See [12, 13]. Later, we will apply [figure omitted; refer to PDF] (cf. [11]). Those estimates are used in [12, 13] to characterize the Hölder-Zygmund type smoothness by means of σ N .
Theorem 5.
Assume that ( ν N ) N = 1 ∞ is a family of quadrature measures of order N , respectively. Then, for all f ∈ C s ( X ) , one has [figure omitted; refer to PDF] where the generic constants do not depend on N or f . On the other hand, if, for f ∈ L p ( X ) , there are generic constants not depending on N such that || f - σ N ( f ) || L ∞ ( X ) [<, ~] N - s holds, then f ∈ C s ( X ) .
Next, by using h ( λ k / N ) h ( λ k / 2 N ) = h ( λ k / N ) and applying the quadrature property of ν N , a straightforward calculation yields [figure omitted; refer to PDF] For some fixed S > 1 , we define the actual approximation by [figure omitted; refer to PDF] In other words, we replace σ N ( f , y ) in (18) with a number on the grid ( 1 / N S ) Z . We define the following collection: [figure omitted; refer to PDF] which induces a covering of C s ¯ ( X ) in L ∞ ( X ) .
Theorem 6.
For fixed s > 0 and S > max ... ( 1 , s ) , one applies the discretization (19). Then, there is a constant c > 0 such that, for all f ∈ C s ¯ ( X ) , || f - σ N [composite function] ( f ) || L ∞ ( X ) ...4; c N - s holds. Thus, for c N - s = [varepsilon] ...4; 1 , the collection M S , N induces an [varepsilon] -covering of C s ¯ ( X ) in L ∞ ( X ) . Its cardinality n ^ [varepsilon] satisfies [figure omitted; refer to PDF] where the generic constant does not depend on [varepsilon] .
Proof of Theorem 6.
The triangle inequality yields [figure omitted; refer to PDF] Since Theorem 5 implies || f - σ N ( f ) || L ∞ ( X ) [<, ~] N - s || f || C s ( X ) = N - s , we only need to take care of the term on the farmost right. The quantization (19) immediately yields [figure omitted; refer to PDF] so that (18) and (16) imply [figure omitted; refer to PDF] Hence, we have derived the estimate on || f - σ N [composite function] ( f ) || L ∞ ( X ) .
To tackle (21), we apply (23), which yields [figure omitted; refer to PDF] According to [13, Theorem 5.1], || σ N ( f ) || L ∞ ( X ) [<, ~] || f || L ∞ ( X ) holds. Since f is contained in the ball of radius 1, we see that [figure omitted; refer to PDF] Thus, the number of possible values of I N ( f , y ) for fixed y is at most c 1 N S , where c 1 ...5; 1 is a positive constant. Note that we can assume that c 1 N S ...5; 1 because, otherwise, I N ( f , y ) would be zero. Since # supp ... ( ν N ) [<, ~] N α , we have # { I N ( f , y ) : y ∈ supp ... ( ν N ) } [<, ~] N α . Therefore, we have n ^ [varepsilon] ...4; ( c 1 N S ) c 2 N α , for some positive constant c 2 . By using c N - s = [varepsilon] ...4; 1 , we obtain [figure omitted; refer to PDF] which concludes the proof.
According to Theorems 2 and 6, the [varepsilon] -covering number n [varepsilon] of C s ¯ ( X ) and the number n ^ [varepsilon] of [varepsilon] -balls induced by M S , N satisfy [figure omitted; refer to PDF] Therefore, our scheme is optimal up to a logarithmic factor by means of the metric entropy.
Our results are also related to the field of manifold learning, in which a function must be reconstructed from finite training data (cf. [22-25]). When actually applying our scheme, we first acquire a set of samples { x l } l = 1 m sufficiently well covering X and we also need the function values { f ( x l ) } l = 1 m , which altogether build the training data. Next, we compute a quadrature measure ν N for some maximal N such that supp ... ( ν N ) ⊂ { x l } l = 1 m ; see [11, 21] for an algorithm. Here, we need that the sample points { x l } l = 1 m are well distributed and larger N require more samples. An element in M S , N that is [varepsilon] -close to f is simply given by σ N [composite function] ( f ) , whose computation only requires knowledge of f and { [straight phi] k : λ k ...4; N } on the finite set supp ... ( ν N ) ; see (14) and (19). In other words, we do not need to know the entire manifold but only the finite sampling of the training data { x l } l = 1 m , the sampling of the target function { f ( x l ) } l = 1 m , and, more delicately, the sampling of the eigenfunctions { [straight phi] k ( x l ) : λ k ...4; N , l = 1 , ... , m } of the Laplacian. Those eigenfunctions, however, are not explicitly known except for few special cases, such as the sphere, projective space, the Grassmann manifold, and few more. Fortunately, approximation of those eigenfunctions is a common procedure in manifold learning. Computational schemes are based on the graph Laplacian to be built from the training data and, at least under suitable assumptions, converging towards the Laplacian on the manifold when the cardinality of the data increases (cf. [26-28] and references therein). Those schemes approximately sample the first few eigenfunctions on the training data. Thus, our proposed approach is indeed fully discrete and computationally feasible even if the eigenfunctions { [straight phi] k } k = 0 ∞ are not explicitly known. In fact, the manifold itself can be unknown. As long as X satisfies the theoretical assumptions, it is simply represented by means of a finite sample.
Remark 7.
The technical assumptions on the manifold X and the function system { [straight phi] k } k = 0 ∞ imply certain estimates on the heat kernel on X (see [9, 10]), mainly used to ensure that the localization property (15) holds (cf. [12, 13]). Our assumptions also imply the existence of quadrature measures ν N and that f · g ∈ Π a N for all f , g ∈ Π N and some constant a > 0 . These items lead to the characterization of the Hölder-Zygmund type space by means of σ N in Theorem 5. Moreover, the family ( ν N ) N = 1 ∞ can be chosen with finite support, in fact with # supp ... ( ν N ) [<, ~] N α (cf. [11]). Theorem 5 and # supp ... ( ν N ) [<, ~] N α are indeed the two main ingredients of the poof of our results in Theorem 6.
Remark 8.
The reader familiar with the approximation scheme developed in [9, 11-13] may expect that the presented results can be generalized to a wider class of Besov spaces on metric spaces. This is indeed true but requires more technical details and does not lead to a fully discrete scheme in the end. Here, we intended to emphasize the main ideas by keeping technical details at a minimum level and to focus on the development of a fully discrete covering algorithm. The more general approach will be described elsewhere.
Acknowledgments
Martin Ehler has been funded by the Vienna Science and Technology Fund (WWTF) through Project VRG12-009. The research of Frank Filbir was partially funded by the Deutsche Forschungsgemeinschaft Grant FI 883/3-1. Both authors thank H. N. Mhaskar for many fruitful discussions.
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
[1] A. N. Kolmogorov, V. M. Tihomirov, " [straight epsilon] -entropy and [straight epsilon] -capacity of sets in function spaces," English translation in American Mathematical Society, vol. 17, pp. 277-364, 1961 Uspekhi Matematicheskikh Nauk , vol. 14, no. 2, pp. 3-86, 1959.
[2] A. G. Vituskin Theory of the Transmission and Processing of Information , pp. xvi+206, Pergamon, 1961.
[3] A. Schürmann, F. Vallentin, "Computational approaches to lattice packing and covering problems," Discrete & Computational Geometry , vol. 35, no. 1, pp. 73-116, 2006.
[4] D. Dung, "Non-linear approximations using sets of finite cardinality or finite pseudo-dimension," Journal of Complexity , vol. 17, no. 2, pp. 467-492, 2001.
[5] V. N. Temlyakov, "Estimates for the asymptotic characteristics of classes of functions with bounded mixed derivative or difference," Proceedings of the Steklov Institute of Mathematics , vol. 189, pp. 161-197, 1990.
[6] B. Carl, I. Stephani Entropy, Compactness and the Approximation of Operators , Cambridge University Press, Cambridge, UK, 1990.
[7] D. E. Edmunds, H. Triebel Function Spaces, Entropy Numbers, Differential Operators , vol. 120, pp. xii+252, Cambridge University Press, Cambridge, UK, 1996.
[8] D. D. Haroske, H. Triebel Distributions, Sobolev Spaces, Elliptic Equations , pp. x+294, European Mathematical Society, 2008.
[9] C. K. Chui, H. N. Mhaskar, "Smooth function extension based on high dimensional unstructured data," Mathematics of Computation , 2013.
[10] E. B. Davies, " L p spectral theory of higher-order elliptic differential operators," The Bulletin of the London Mathematical Society , vol. 29, no. 5, pp. 513-546, 1997.
[11] F. Filbir, H. N. Mhaskar, "Marcinkiewicz-Zygmund measures on manifolds," Journal of Complexity , vol. 27, no. 6, pp. 568-596, 2011.
[12] M. Maggioni, H. N. Mhaskar, "Diffusion polynomial frames on metric measure spaces," Applied and Computational Harmonic Analysis , vol. 24, no. 3, pp. 329-353, 2008.
[13] H. N. Mhaskar, "Eignets for function approximation on manifolds," Applied and Computational Harmonic Analysis , vol. 29, no. 1, pp. 63-87, 2010.
[14] D. Dung, T. Ullrich, " n -widths and [straight epsilon] -dimensions for high-dimensional approximations," Foundations of Computational Mathematics , vol. 13, no. 6, pp. 965-1003, 2013.
[15] E. Novak, "Optimal recovery and n -widths for convex classes of functions," Journal of Approximation Theory , vol. 80, no. 3, pp. 390-408, 1995.
[16] A. Pinkus n-Widths in Approximation Theory , Springer, Berlin, Germany, 1985.
[17] G. G. Lorentz, "Metric entropy and approximation," Bulletin of the American Mathematical Society , vol. 72, pp. 903-937, 1966.
[18] H. N. Mhaskar, "On the representation of smooth functions on the sphere using finitely many bits," Applied and Computational Harmonic Analysis , vol. 18, no. 3, pp. 215-233, 2005.
[19] G. G. Lorentz, M. V. Golitschek, Y. Makovoz Constructive Approximation, Advanced Problems , pp. xii+649, Springer, New York, NY, USA, 1996.
[20] D. Geller, I. Z. Pesenson, "Band-limited localized Parseval frames and Besov spaces on compact homogeneous manifolds," Journal of Geometric Analysis , vol. 21, no. 2, pp. 334-371, 2011.
[21] Q. T. Le Gia, H. N. Mhaskar, "Localized linear polynomial operators and quadrature formulas on the sphere," SIAM Journal on Numerical Analysis , vol. 47, no. 1, pp. 440-466, 2009.
[22] M. Belkin, P. Niyogi, "Semi-supervised learning on riemannian manifolds," Machine Learning , vol. 56, no. 1-3, pp. 209-239, 2004.
[23] M. Belkin, P. Niyogi, V. Sindhwani, "Manifold regularization: a geometric framework for learning from labeled and unlabeled examples," Journal of Machine Learning Research , vol. 7, pp. 2399-2434, 2006.
[24] M. Gavish, B. Nadler, R. R. Coifman, "Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning," in Proceedings of the 27th International Conference on Machine Learning (ICML '10), pp. 367-374, June 2010.
[25] A. D. Szlam, M. Maggioni, R. R. Coifman, "Regularization on graphs with function-adapted diffusion processes," Journal of Machine Learning Research , vol. 9, pp. 1711-1739, 2008.
[26] M. Belkin, P. Niyogi, B. Schölkopf, J. C. Platt, T. Hoffman, "Convergence of Laplacian eigenmaps," in Proceedings of the NIPS, pp. 129-136, MIT Press, 2006.
[27] B. Nadler, S. Lafon, R. R. Coifman, I. G. Kevrekidis, Y. Weiss, B. Schölkopf, J. Platt, "Diffusion maps, spectral clustering and Eigen functions of Fokker-Planck operators," Advances in Neural Information Processing Systems , vol. 18, MIT Press, Cambridge, Mass, USA, 2006.
[28] U. von Luxburg, M. Belkin, O. Bousquet, "Consistency of spectral clustering," The Annals of Statistics , vol. 36, no. 2, pp. 555-586, 2008.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Copyright © 2014 Martin Ehler and Frank Filbir. Martin Ehler et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
We first determine the asymptotes of the [straight epsilon] -covering numbers of Hölder-Zygmund type spaces on data-defined manifolds. Secondly, a fully discrete and finite algorithmic scheme is developed providing explicit [straight epsilon] -coverings whose cardinality is asymptotically near the [straight epsilon] -covering number. Given an arbitrary Hölder-Zygmund type function, the nearby center of a ball in the [straight epsilon] -covering can also be computed in a discrete finite fashion.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer