×

Eignets for function approximation on manifolds. (English) Zbl 1201.41003

From the abstract: Let \(\mathbb{X}\) be a compact, smooth connected, Riemannian manifold without boundary, \(G:\mathbb{X}\to \mathbb{X}\to\mathbb{R}\) be a kernel. Analogous to a radial basis function network, an eignet is an expression of the form \(\sum^M_{j=1} \alpha_jG(\circ,y_j)\), where \(a_j\in \mathbb{R}\), \(y_j\in\mathbb{X}\), \(1\leq j\leq M\). A deterministic, universal algorithm for constructing an eignet for approximating functions in \(L^p(\mu;\mathbb{X})\) for a general class of measures \(\mu\) and kernels \(G\) is described. The algorithm yields linear operators. Using the minimal separation among the centers \(y_j\) as the cost of approximation, the modulus of smoothness estimates for the degree of approximation by our eignets is given and it’s shown by means of a converse theorem that these are the best possible for every individual function. The estimates on the coefficients \(a_j\) in terms of the norm of the eignet are given also. Finally, it’s demonstrated that if any sequence of eignets satisfies the optimal estimates for the degree of approximation of a smooth function, measured in terms of the minimal separation, then the derivatives of the eignets also approximate the corresponding derivatives of the target function in an optimal manner.

MSC:

41A30 Approximation by other special function classes
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Belkin, M.; Matveeva, I.; Niyogi, P., Regularization and regression on large graphs, (Proc. of Computational Learning Theory (2004), Banff: Banff Canada)
[3] Belkin, M.; Niyogi, P., Towards a theoretical foundation for Laplacian-based manifold methods, J. Comput. System Sci., 74, 8, 1289-1308 (2008) · Zbl 1157.68056
[4] Belkin, M.; Niyogi, P., Convergence of Laplacian eigenmaps
[5] Bergh, J.; Löfström, J., Interpolation Spaces, an Introduction (1976), Springer-Verlag: Springer-Verlag Berlin · Zbl 0344.46071
[6] Chui, C. K.; Donoho, D. L., Special Issue: Diffusion Maps and Wavelets. Special Issue: Diffusion Maps and Wavelets, Appl. Comput. Harmon. Anal., 21, 1 (2006)
[7] Coifman, R. R.; Maggioni, M., Diffusion wavelets, Appl. Comput. Harmon. Anal., 21, 53-94 (2006) · Zbl 1095.94007
[8] DeVore, R. A.; Lorentz, G. G., Constructive Approximation (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0797.41016
[9] Damelin, S. B., On bounds for diffusion, discrepancy and fill distance metrics. Principal manifolds for data visualization and dimension reduction, (Lect. Notes Comput. Sci. Eng., vol. 58 (2008), Springer: Springer Berlin), 261-270
[10] Damelin, S. B., A walk through energy, discrepancy, numerical integration and group invariant measures on measurable subsets of Euclidean space, Numer. Algorithms, 48, 1-3, 213-235 (2008) · Zbl 1152.41017
[11] Damelin, S. B.; Devaney, A. J., Local Paley Wiener theorems for analytic functions on the unit sphere, Inverse Problems, 23, 1-12 (2007) · Zbl 1120.42013
[12] Donoho, D. L.; Grimes, C., Image manifolds which are isometric to Euclidean space · Zbl 1478.62186
[13] Donoho, D. L.; Levi, O.; Starck, J.-L.; Martinez, V. J., Multiscale Geometric analysis for 3-D catalogues
[15] Filbir, F.; Themistoclakis, W., Polynomial approximation on the sphere using scattered data, Math. Nachr., 281, 5, 650-668 (2008) · Zbl 1147.41001
[16] Grigorýan, A., Estimates of heat kernels on Riemannian manifolds, (Davies, E. B.; Safarov, Y., Spectral Theory and Geometry. Spectral Theory and Geometry, Edinburgh, 1998. Spectral Theory and Geometry. Spectral Theory and Geometry, Edinburgh, 1998, London Math. Soc. Lecture Note Ser., vol. 273 (1999), Cambridge University Press: Cambridge University Press Cambridge), 140-225
[18] He, X.; Yan, S.; Hu, Y.; Niyogi, P.; Zhang, H.-J., Face recognition using Laplacian faces, IEEE Trans. Pattern Anal. Mach. Intell., 27, 3, 328-340 (2005)
[19] Hörmander, L., The spectral function of an elliptic operator, Acta Math., 121, 193-218 (1968) · Zbl 0164.13201
[20] Jones, P. W.; Maggioni, M.; Schul, R., Universal local parametrizations via heat kernels and eigenfunctions of the Laplacian · Zbl 1194.58031
[21] Keiner, J.; Kunis, S.; Potts, D., Efficient reconstruction of functions on the sphere from scattered data, J. Fourier Anal. Appl., 13, 435-458 (2007) · Zbl 1125.65019
[22] Kordyukov, Yu. A., Lp-theory of elliptic differential operators on manifolds of bounded geometry, Acta Appl. Math., 23, 3, 223-260 (1991) · Zbl 0743.58030
[24] Le Gia, Q. T.; Mhaskar, H. N., Localized linear polynomial operators and quadrature formulas on the sphere, SIAM J. Numer. Anal., 47, 1, 440-466 (2008/2009) · Zbl 1190.65039
[25] Maggioni, M.; Mhaskar, H. N., Diffusion polynomial frames on metric measure spaces, Appl. Comput. Harmon. Anal., 24, 3, 329-353 (2008) · Zbl 1242.42027
[26] Mhaskar, H. N., Introduction to the Theory of Weighted Polynomial Approximation (1996), World Scientific: World Scientific Singapore · Zbl 0948.41500
[27] Mhaskar, H. N., When is approximation by Gaussian networks necessarily a linear process?, Neural Networks, 17, 989-1001 (2004) · Zbl 1084.68104
[28] Mhaskar, H. N.; Prestin, J., Polynomial frames: A fast tour, (Chui, C. K.; Neamtu, M.; Schumaker, L., Approximation Theory XI. Approximation Theory XI, Gatlinburg, 2004 (2005), Nashboro Press: Nashboro Press Brentwood), 287-318 · Zbl 1077.42028
[29] Minakshisundaram, S.; Pleijel, A., Some properties of eigenfunctions of the Laplace operator on Riemannian manifolds, Canad. J. Math., 1, 242-256 (1949) · Zbl 0041.42701
[30] Saito, N., Data analysis and representation on a general domain using eigenfunctions of Laplacian, Appl. Comput. Harmon. Anal., 25, 1, 68-97 (2008) · Zbl 1148.94005
[31] Singer, A., From graph to manifold Laplacian: The convergence rate, Appl. Comput. Harmon. Anal., 21, 1, 128-134 (2006) · Zbl 1095.68102
[32] Xu, B., Derivatives of the spectral function and Sobolev norms of eigenfunctions on a closed Riemannian manifold, Ann. Global Anal. Geom., 26, 231-252 (2004) · Zbl 1083.35072
[33] Xu, R.; Damelin, S. B.; Wunsch, D., Clustering of cancer tissues using diffusion maps and fuzzy ART with gene expression data, BME, 42-49 (2008)
[35] Zygmund, A., Trigonometric Series (1977), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0367.42001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.