\(\varepsilon\)-coverings of Hölder-Zygmund type spaces on data-defined manifolds. (English) Zbl 1470.41026

Summary: We first determine the asymptotes of the \(\varepsilon\)-covering numbers of Hölder-Zygmund type spaces on data-defined manifolds. Secondly, a fully discrete and finite algorithmic scheme is developed providing explicit \(\varepsilon\)-coverings whose cardinality is asymptotically near the \(\varepsilon\)-covering number. Given an arbitrary Hölder-Zygmund type function, the nearby center of a ball in the \(\varepsilon\)-covering can also be computed in a discrete finite fashion.


41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
41A30 Approximation by other special function classes
Full Text: DOI


[1] Kolmogorov, A. N.; Tihomirov, V. M., \(\varepsilon\)-entropy and \(\varepsilon\)-capacity of sets in function spaces, Uspekhi Matematicheskikh Nauk, 14, 2, 3-86, (1959) · Zbl 0090.33503
[2] Vituškin, A. G., Theory of the Transmission and Processing of Information, xvi+206, (1961), Pergamon
[3] Schürmann, A.; Vallentin, F., Computational approaches to lattice packing and covering problems, Discrete & Computational Geometry, 35, 1, 73-116, (2006) · Zbl 1091.52009
[4] Dung, D., Non-linear approximations using sets of finite cardinality or finite pseudo-dimension, Journal of Complexity, 17, 2, 467-492, (2001) · Zbl 0993.41013
[5] Temlyakov, V. N., Estimates for the asymptotic characteristics of classes of functions with bounded mixed derivative or difference, Proceedings of the Steklov Institute of Mathematics, 189, 161-197, (1990) · Zbl 0719.46021
[6] Carl, B.; Stephani, I., Entropy, Compactness and the Approximation of Operators, (1990), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 0705.47017
[7] Edmunds, D. E.; Triebel, H., Function Spaces, Entropy Numbers, Differential Operators, 120, xii+252, (1996), Cambridge, UK: Cambridge University Press, Cambridge, UK
[8] Haroske, D. D.; Triebel, H., Distributions, Sobolev Spaces, Elliptic Equations, x+294, (2008), European Mathematical Society
[9] Chui, C. K.; Mhaskar, H. N., Smooth function extension based on high dimensional unstructured data, Mathematics of Computation, (2013) · Zbl 1297.41002
[10] Davies, E. B., \(L^p\) spectral theory of higher-order elliptic differential operators, The Bulletin of the London Mathematical Society, 29, 5, 513-546, (1997) · Zbl 0955.35019
[11] Filbir, F.; Mhaskar, H. N., Marcinkiewicz-Zygmund measures on manifolds, Journal of Complexity, 27, 6, 568-596, (2011) · Zbl 1235.58007
[12] Maggioni, M.; Mhaskar, H. N., Diffusion polynomial frames on metric measure spaces, Applied and Computational Harmonic Analysis, 24, 3, 329-353, (2008) · Zbl 1242.42027
[13] Mhaskar, H. N., Eignets for function approximation on manifolds, Applied and Computational Harmonic Analysis, 29, 1, 63-87, (2010) · Zbl 1201.41003
[14] Dũng, D.; Ullrich, T., \(n\)-widths and \(\varepsilon\)-dimensions for high-dimensional approximations, Foundations of Computational Mathematics, 13, 6, 965-1003, (2013) · Zbl 1284.42001
[15] Novak, E., Optimal recovery and \(n\)-widths for convex classes of functions, Journal of Approximation Theory, 80, 3, 390-408, (1995) · Zbl 0841.65037
[16] Pinkus, A., n-Widths in Approximation Theory, (1985), Berlin, Germany: Springer, Berlin, Germany · Zbl 0551.41001
[17] Lorentz, G. G., Metric entropy and approximation, Bulletin of the American Mathematical Society, 72, 903-937, (1966) · Zbl 0158.13603
[18] Mhaskar, H. N., On the representation of smooth functions on the sphere using finitely many bits, Applied and Computational Harmonic Analysis, 18, 3, 215-233, (2005) · Zbl 1082.41020
[19] Lorentz, G. G.; Golitschek, M. V.; Makovoz, Y., Constructive Approximation, Advanced Problems, xii+649, (1996), New York, NY, USA: Springer, New York, NY, USA · Zbl 0910.41001
[20] Geller, D.; Pesenson, I. Z., Band-limited localized Parseval frames and Besov spaces on compact homogeneous manifolds, Journal of Geometric Analysis, 21, 2, 334-371, (2011) · Zbl 1216.43004
[21] Le Gia, Q. T.; Mhaskar, H. N., Localized linear polynomial operators and quadrature formulas on the sphere, SIAM Journal on Numerical Analysis, 47, 1, 440-466, (2009) · Zbl 1190.65039
[22] Belkin, M.; Niyogi, P., Semi-supervised learning on riemannian manifolds, Machine Learning, 56, 1–3, 209-239, (2004) · Zbl 1089.68086
[23] Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from labeled and unlabeled examples, Journal of Machine Learning Research, 7, 2399-2434, (2006) · Zbl 1222.68144
[24] Gavish, M.; Nadler, B.; Coifman, R. R., Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning, Proceedings of the 27th International Conference on Machine Learning (ICML ’10)
[25] Szlam, A. D.; Maggioni, M.; Coifman, R. R., Regularization on graphs with function-adapted diffusion processes, Journal of Machine Learning Research, 9, 1711-1739, (2008) · Zbl 1225.68217
[26] Belkin, M.; Niyogi, P.; Schölkopf, B.; Platt, J. C.; Hoffman, T., Convergence of Laplacian eigenmaps, Proceedings of the NIPS, MIT Press
[27] Nadler, B.; Lafon, S.; Coifman, R. R.; Kevrekidis, I. G.; Weiss, Y.; Schölkopf, B.; Platt, J., Diffusion maps, spectral clustering and Eigen functions of Fokker-Planck operators, Advances in Neural Information Processing Systems, 18, (2006), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA
[28] von Luxburg, U.; Belkin, M.; Bousquet, O., Consistency of spectral clustering, The Annals of Statistics, 36, 2, 555-586, (2008) · Zbl 1133.62045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.