×

Approximation of functions over manifolds: a moving least-squares approach. (English) Zbl 1458.62327

Summary: We present an algorithm for approximating a function defined over a \(d\)-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require knowledge about the local geometry of the manifold or its local parameterizations. We do require, however, knowledge regarding the manifold’s intrinsic dimension \(d\). We use the Manifold Moving Least-Squares approach of B. Sober and D. Levin [Constr. Approx. 52, No. 3, 433–478 (2020; Zbl 1455.65042)] to reconstruct the atlas of charts and the approximation is built on top of those charts. The resulting approximant is shown to be a function defined over a neighborhood of a manifold, approximating the originally sampled manifold. In other words, given a new point, located near the manifold, the approximation can be evaluated directly on that point. We prove that our construction yields a smooth function, and in case of noiseless samples the approximation order is \(\mathcal{O} (h^{m + 1})\), where \(h\) is a local density of sample parameter (i.e., the fill distance) and \(m\) is the degree of a local polynomial approximation, used in our algorithm. In addition, the proposed algorithm has linear time complexity with respect to the ambient space’s dimension. Thus, we are able to avoid the computational complexity, commonly encountered in high dimensional approximations, without having to perform non-linear dimension reduction, which inevitably introduces distortions to the geometry of the data. Additionally, we show numerically that our approach compares favorably to some well-known approaches for regression over manifolds.

MSC:

62R30 Statistics on manifolds
41A58 Series expansions (e.g., Taylor, Lidstone series, but not Fourier series)
65D15 Algorithms for approximation of functions
62-08 Computational methods for problems pertaining to statistics

Citations:

Zbl 1455.65042

Software:

COIL-20
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bellman, R., Dynamic Programming (1957), Princeton University Press: Princeton University Press Princeton, NJ, USA, URL http://books.google.com/books?id=fyVtp3EMxasC&pg=PR5&dq=dynamic+programming+richard+e+bellman&client=firefox-a#v=onepage&q=dynamic · Zbl 0077.13605
[2] Donoho, D. L., High-dimensional data analysis: The curses and blessings of dimensionality, AMS Math. Chall. Lect., 1-32 (2000)
[3] Hughes, G., On the mean accuracy of statistical pattern recognizers, IEEE Trans. Inf. Theory, 14, 1, 55-63 (1968)
[4] Stone, C. J., Optimal rates of convergence for nonparametric estimators, Ann. Statist., 1348-1360 (1980) · Zbl 0451.62033
[5] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 6, 1373-1396 (2003) · Zbl 1085.68119
[6] Coifman, R. R.; Lafon, S., Diffusion maps, Appl. Comput. Harmon. Anal., 21, 1, 5-30 (2006) · Zbl 1095.68094
[7] Jolliffe, I., Principal Component Analysis (2002), Wiley Online Library · Zbl 1011.62064
[8] Jones, P. W.; Maggioni, M.; Schul, R., Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels, Proc. Natl. Acad. Sci., 105, 6, 1803-1808 (2008) · Zbl 1215.58012
[9] Kohonen, T., Self-Organizing Maps, Vol. 30 (2001), Springer Science & Business Media
[10] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[11] Saul, L. K.; Roweis, S. T., Think globally, fit locally: unsupervised learning of low dimensional manifolds, J. Mach. Learn. Res., 4, 119-155 (2003) · Zbl 1093.68089
[12] Tenenbaum, J. B.; De Silva, V.; Langford, J. C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 5500, 2319-2323 (2000)
[13] Lee, J. A.; Verleysen, M., Nonlinear Dimensionality Reduction (2007), Springer Science & Business Media · Zbl 1128.68024
[14] Aizenbud, Y.; Bermanis, A.; Averbuch, A., PCA-based out-of-sample extension for dimensionality reduction (2015), arXiv preprint arXiv:1511.00831
[15] Bengio, Y.; Paiement, J.-f.; Vincent, P.; Delalleau, O.; Roux, N. L.; Ouimet, M., Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering, (Advances in Neural Information Processing Systems (2004)), 177-184
[16] Coifman, R. R.; Lafon, S., Geometric harmonics: a novel tool for multiscale out-of-sample extension of empirical functions, Appl. Comput. Harmon. Anal., 21, 1, 31-52 (2006) · Zbl 1095.68095
[17] Pavan, M.; Pelillo, M., Efficient out-of-sample extension of dominant-set clusters, (Advances in Neural Information Processing Systems (2005)), 1057-1064
[18] Smola, A. J.; Schölkopf, B., A tutorial on support vector regression, Statist. Comput., 14, 3, 199-222 (2004)
[19] Schölkopf, B.; Smola, A.; Müller, K.-R., Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 10, 5, 1299-1319 (1998)
[20] Allard, W. K.; Chen, G.; Maggioni, M., Multi-scale geometric methods for data sets II: Geometric multi-resolution analysis, Appl. Comput. Harmon. Anal., 32, 3, 435-462 (2012) · Zbl 1242.42038
[21] Chen, G.; Little, A. V.; Maggioni, M., Multi-resolution geometric analysis for data in high dimensions, (Excursions in Harmonic Analysis, Vol. 1 (2013), Springer), 259-285 · Zbl 1320.62086
[22] Little, A. V.; Maggioni, M.; Rosasco, L., Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature, Appl. Comput. Harmon. Anal., 43, 3, 504-567 (2017) · Zbl 06770640
[23] Maggioni, M.; Minsker, S.; Strawn, N., Geometric multi-resolution analysis for dictionary learning, (Wavelets and Sparsity XVI, Vol. 9597 (2015), International Society for Optics and Photonics), 95971C
[24] Wang, Y.; Chen, G.; Maggioni, M., High-dimensional data modeling techniques for detection of chemical plumes and anomalies in hyperspectral images and movies, IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens., 9, 9, 4316-4324 (2016)
[25] Binev, P.; Dahmen, W.; Lamby, P., Fast high-dimensional approximation with sparse occupancy trees, J. Comput. Appl. Math., 235, 8, 2063-2076 (2011) · Zbl 1209.65018
[26] Binev, P.; Cohen, A.; Dahmen, W.; DeVore, R.; Temlyakov, V., Universal algorithms for learning theory part i: piecewise constant functions, J. Mach. Learn. Res., 6, Sep, 1297-1321 (2005) · Zbl 1191.62068
[27] Binev, P.; Cohen, A.; Dahmen, W.; DeVore, R., Universal algorithms for learning theory. part ii: Piecewise polynomial functions, Constr. Approx., 26, 2, 127-152 (2007) · Zbl 1191.62067
[28] Kpotufe, S., K-NN regression adapts to local intrinsic dimension, (Shawe-Taylor, J.; Zemel, R. S.; Bartlett, P. L.; Pereira, F.; Weinberger, K. Q., Advances in Neural Information Processing Systems 24 (2011), Curran Associates, Inc.), 729-737, URL http://papers.nips.cc/paper/4455-k-nn-regression-adapts-to-local-intrinsic-dimension.pdf
[29] Kpotufe, S.; Garg, V., Adaptivity to local smoothness and dimension in kernel regression, (Burges, C. J.C.; Bottou, L.; Welling, M.; Ghahramani, Z.; Weinberger, K. Q., Advances in Neural Information Processing Systems 26 (2013), Curran Associates, Inc.), 3075-3083, URL http://papers.nips.cc/paper/5103-adaptivity-to-local-smoothness-and-dimension-in-kernel-regression.pdf
[30] Bickel, P. J.; Li, B., Local polynomial regression on unknown manifolds, (Complex Datasets and Inverse Problems (2007), Institute of Mathematical Statistics), 177-186
[31] Ruppert, D.; Wand, M. P., Multivariate locally weighted least squares regression, Ann. Statist., 1346-1370 (1994) · Zbl 0821.62020
[32] Cheng, M.-Y.; Wu, H.-t., Local linear regression on manifolds and its geometric interpretation, J. Amer. Statist. Assoc., 108, 504, 1421-1434 (2013) · Zbl 1426.62402
[33] Aswani, A.; Bickel, P.; Tomlin, C., Regression on manifolds: Estimation of the exterior derivative, Ann. Statist., 48-81 (2011) · Zbl 1209.62063
[34] Lancaster, P.; Salkauskas, K., Surfaces generated by moving least squares methods, Math. Comput., 37, 155, 141-158 (1981) · Zbl 0469.41005
[35] Levin, D., The approximation power of moving least-squares, Math. Comput. Amer. Math. Soc., 67, 224, 1517-1531 (1998) · Zbl 0911.41016
[36] McLain, D. H., Drawing contours from arbitrary data points, Comput. J., 17, 4, 318-324 (1974)
[37] Alexa, M.; Behr, J.; Cohen-Or, D.; Fleishman, S.; Levin, D.; Silva, C. T., Computing and rendering point set surfaces, IEEE Trans. Vis. Comput. Graphics, 9, 1, 3-15 (2003)
[38] Levin, D., Mesh-independent surface interpolation, (Geometric Modeling for Scientific Visualization (2004), Springer), 37-49
[39] Sober, B.; Levin, D., Manifold approximation by moving least-squares projection (MMLS), Constr. Approx. (2019)
[40] Federer, H., Curvature measures, Trans. Amer. Math. Soc., 93, 3, 418-491 (1959) · Zbl 0089.38402
[41] Bos, L.; Salkauskas, K., Moving least-squares are Backus-Gilbert optimal, J. Approx. Theory, 59, 3, 267-275 (1989) · Zbl 0729.41008
[42] Backus, G. E.; Gilbert, J., Numerical applications of a formalism for geophysical inverse problems, Geophys. J. Int., 13, 1-3, 247-276 (1967)
[43] Backus, G.; Gilbert, F., The resolving power of gross earth data, Geophys. J. Int., 16, 2, 169-205 (1968) · Zbl 0177.54102
[44] Aizenbud, Y.; Sober, B., Approximating the span of principal components via iterative least-squares (2019), arXiv preprint arXiv:1907.12159
[45] Aizenbud, Y.; Averbuch, A., Matrix decompositions using sub-Gaussian random matrices, Inf. Inference: J. IMA (2018), arXiv:http://oup.prod.sis.lan/imaiai/advance-article-pdf/doi/10.1093/imaiai/iay017/25882669/iay017.pdf
[46] Camastra, F.; Vinciarelli, A., Estimating the intrinsic dimension of data with a fractal-based method, IEEE Trans. Pattern Anal. Mach. Intell., 24, 10, 1404-1407 (2002)
[47] Kégl, B., Intrinsic dimension estimation using packing numbers, (Advances in Neural Information Processing Systems (2003)), 697-704
[48] Costa, J. A.; Hero, A. O., Geodesic entropic graphs for dimension and entropy estimation in manifold learning, IEEE Trans. Signal Process., 52, 8, 2210-2221 (2004) · Zbl 1369.68278
[49] Levina, E.; Bickel, P. J., Maximum likelihood estimation of intrinsic dimension, (Advances in Neural Information Processing Systems (2005)), 777-784
[50] Nene, S. A.; Nayar, S. K.; Murase, H., Columbia Object Image Library (coil-20)Technical report CUCS-005-96 (1996)
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.