Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Smooth function extension based on high dimensional unstructured data


Authors: Charles K. Chui and H. N. Mhaskar
Journal: Math. Comp. 83 (2014), 2865-2891
MSC (2010): Primary 41A25, 42C15, 68Q32
DOI: https://doi.org/10.1090/S0025-5718-2014-02819-6
Published electronically: June 18, 2014
MathSciNet review: 3246813
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Many applications, including the image search engine, image inpainting, hyperspectral image dimensionality reduction, pattern recognition, and time series prediction, can be facilitated by considering the given discrete data-set as a point-cloud $ {\mathcal P}$ in some high dimensional Euclidean space $ {\mathbb{R}}^{s}$. Then the problem is to extend a desirable objective function $ f$ from a certain relatively smaller training subset $ \mathcal {C}\subset {\mathcal P}$ to some continuous manifold $ {\mathbb{X}}\subset {\mathbb{R}}^{s}$ that contains $ {\mathcal P}$, at least approximately. More precisely, when the point cloud $ {\mathcal P}$ of the given data-set is modeled in the abstract by some unknown compact manifold embedded in the ambient Euclidean space $ {\mathbb{R}}^{s}$, the extension problem can be considered as the interpolation problem of seeking the objective function on the manifold $ {\mathbb{X}}$ that agrees with $ f$ on $ \mathcal {C}$ under certain desirable specifications. For instance, by considering groups of cardinality $ s$ of data values as points in a point-cloud in $ {\mathbb{R}}^{s}$, such groups that are far apart in the original spatial data domain in $ {\mathbb{R}}^{1}$ or $ {\mathbb{R}}^{2}$, but have similar geometric properties, can be arranged to be close neighbors on the manifold. The objective of this paper is to incorporate the consideration of data geometry and spatial approximation, with immediate implications to the various directions of application areas. Our main result is a point-cloud interpolation formula that provides a near-optimal degree of approximation to the target objective function on the unknown manifold.


References [Enhancements On Off] (What's this?)

  • [1] M. Belkin and P. Niyogi, Semi-supervised learning on Riemannian manifolds, Machine Learning Journal 56 (2004), 209-239.
  • [2] Mikhail Belkin and Partha Niyogi, Towards a theoretical foundation for Laplacian-based manifold methods, J. Comput. System Sci. 74 (2008), no. 8, 1289-1308. MR 2460286 (2009m:68207), https://doi.org/10.1016/j.jcss.2007.08.006
  • [3] M. Belkin, P. Niyogi, Convergence of Laplacian Eigenmaps, Manuscript (http://www.
    cse.ohio-state.edu/ mbelkin/papers/CLEM_08.pdf).
  • [4] Charles K. Chui and Harvey Diamond, A general framework for local interpolation, Numer. Math. 58 (1991), no. 6, 569-581. MR 1083520 (92b:41005), https://doi.org/10.1007/BF01385640
  • [5] Charles K. Chui and H. N. Mhaskar, MRA contextual-recovery extension of smooth functions on manifolds, Appl. Comput. Harmon. Anal. 28 (2010), no. 1, 104-113. MR 2563262 (2011j:94010), https://doi.org/10.1016/j.acha.2009.04.004
  • [6] Charles K. Chui and Jianzhong Wang, PDE models associated with the bilateral filter, Adv. Comput. Math. 31 (2009), no. 1-3, 131-156. MR 2511577 (2010e:94028), https://doi.org/10.1007/s10444-008-9095-2
  • [7] C.K. Chui and J.Z. Wang, Dimensionality Reduction of Hyper-spectral Imagery Data for Feature Classification, in ``Handbook of Geomathematics'', pp. 1005-1049, Freeden, W., Nashed, Z., and Sonar, T. (eds.), Springer, 2010.
  • [8] Charles K. Chui and Jianzhong Wang, Randomized anisotropic transform for nonlinear dimensionality reduction, GEM Int. J. Geomath. 1 (2010), no. 1, 23-50. MR 2747641 (2012b:62012), https://doi.org/10.1007/s13137-010-0004-8
  • [9] Ronald R. Coifman and Stéphane Lafon, Diffusion maps, Appl. Comput. Harmon. Anal. 21 (2006), no. 1, 5-30. MR 2238665 (2008a:60210), https://doi.org/10.1016/j.acha.2006.04.006
  • [10] Ronald R. Coifman and Mauro Maggioni, Diffusion wavelets, Appl. Comput. Harmon. Anal. 21 (2006), no. 1, 53-94. MR 2238667 (2007d:42067), https://doi.org/10.1016/j.acha.2006.04.004
  • [11] W. Czaja and M. Ehler, Schrödinger eigenmaps for the analysis of bio-medical data, IEEE Trans. Pattern Anal. Mach. Intelligence, DOI:10.1109/TPAMI.2012.270.
  • [12] E. B. Davies, $ L^p$ spectral theory of higher-order elliptic differential operators, Bull. London Math. Soc. 29 (1997), no. 5, 513-546. MR 1458713 (98d:35164), https://doi.org/10.1112/S002460939700324X
  • [13] Ronald A. DeVore and George G. Lorentz, Constructive Approximation, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR 1261635 (95f:41001)
  • [14] M. Ehler, The multiresolution structure of pairs of dual wavelet frames for a pair of Sobolev spaces, Jaen J. Approx., 2 (2) (2010), 193-214.
  • [15] M. Ehler, F. Filbir, and H. N. Mhaskar, Locally learning biomedical data using diffusion frames, J. Comput. Biol. 19 (2012), no. 11, 1251-1264. MR 2994881, https://doi.org/10.1089/cmb.2012.0187
  • [16] Michael Elad, On the origin of the bilateral filter and ways to improve it, IEEE Trans. Image Process. 11 (2002), no. 10, 1141-1151. MR 1966043 (2004c:94042), https://doi.org/10.1109/TIP.2002.801126
  • [17] Charles Fefferman, Whitney's extension problem for $ C^m$, Ann. of Math. (2) 164 (2006), no. 1, 313-359. MR 2233850 (2007g:58013), https://doi.org/10.4007/annals.2006.164.313
  • [18] Charles Fefferman, The structure of linear extension operators for $ C^m$, Rev. Mat. Iberoam. 23 (2007), no. 1, 269-280. MR 2351135 (2009c:41003), https://doi.org/10.4171/RMI/495
  • [19] Charles Fefferman and Bo'az Klartag, Fitting a $ C^m$-smooth function to data. I, Ann. of Math. (2) 169 (2009), no. 1, 315-346. MR 2480607 (2011g:58011), https://doi.org/10.4007/annals.2009.169.315
  • [20] Charles Fefferman and Bo'az Klartag, Fitting a $ C^m$-smooth function to data. II, Rev. Mat. Iberoam. 25 (2009), no. 1, 49-273. MR 2514338 (2011f:58020), https://doi.org/10.4171/RMI/569
  • [21] Charles Fefferman, Fitting a $ C^m$-smooth function to data. III, Ann. of Math. (2) 170 (2009), no. 1, 427-441. MR 2521121 (2011e:58014), https://doi.org/10.4007/annals.2009.170.427
  • [22] F. Filbir and H. N. Mhaskar, A quadrature formula for diffusion polynomials corresponding to a generalized heat kernel, J. Fourier Anal. Appl. 16 (2010), no. 5, 629-657. MR 2673702 (2011j:41007), https://doi.org/10.1007/s00041-010-9119-4
  • [23] F. Filbir and H. N. Mhaskar, Marcinkiewicz-Zygmund measures on manifolds, J. Complexity 27 (2011), no. 6, 568-596. MR 2846706, https://doi.org/10.1016/j.jco.2011.03.002
  • [24] Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720 (97g:65006)
  • [25] Alexander Grigoryan, Estimates of heat kernels on Riemannian manifolds, Spectral theory and geometry (Edinburgh, 1998) London Math. Soc. Lecture Note Ser., vol. 273, Cambridge Univ. Press, Cambridge, 1999, pp. 140-225. MR 1736868 (2001b:58040), https://doi.org/10.1017/CBO9780511566165.008
  • [26] Alexander Grigoryan, Heat kernels on weighted manifolds and applications, The ubiquitous heat kernel, Contemp. Math., vol. 398, Amer. Math. Soc., Providence, RI, 2006, pp. 93-191. MR 2218016 (2007a:58028), https://doi.org/10.1090/conm/398/07486
  • [27] Alexander Grigor'yan, Heat kernels on metric measure spaces with regular volume growth, Handbook of geometric analysis, No. 2, Adv. Lect. Math. (ALM), vol. 13, Int. Press, Somerville, MA, 2010, pp. 1-60. MR 2743439 (2012d:58037)
  • [28] Yu. A. Kordyukov, $ L^p$-theory of elliptic differential operators on manifolds of bounded geometry, Acta Appl. Math. 23 (1991), no. 3, 223-260. MR 1120831 (92f:58164)
  • [29] M. Maggioni and H. N. Mhaskar, Diffusion polynomial frames on metric measure spaces, Appl. Comput. Harmon. Anal. 24 (2008), no. 3, 329-353. MR 2407008 (2010d:42052), https://doi.org/10.1016/j.acha.2007.07.001
  • [30] H. N. Mhaskar, Polynomial operators and local smoothness classes on the unit interval, J. Approx. Theory 131 (2004), no. 2, 243-267. MR 2106540 (2005k:41011), https://doi.org/10.1016/j.jat.2004.10.002
  • [31] H. N. Mhaskar, Eignets for function approximation on manifolds, Appl. Comput. Harmon. Anal. 29 (2010), no. 1, 63-87. MR 2647012 (2012c:41031), https://doi.org/10.1016/j.acha.2009.08.006
  • [32] H.N. Mhaskar, A generalized diffusion frame for parsimonious representation of functions on data defined manifolds, Neural Networks 24 (2011), 345-359.
  • [33] Naoki Saito, Data analysis and representation on a general domain using eigenfunctions of Laplacian, Appl. Comput. Harmon. Anal. 25 (2008), no. 1, 68-97. MR 2419705 (2009d:35038), https://doi.org/10.1016/j.acha.2007.09.005
  • [34] J.B. Tenenbaum, V. de Silva, and J.C. Langford, A global geometric framwork for nonlinear dimensionality reduction, Science 290 (2000), 2319-2323.
  • [35] C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, in ``Proc. 6$ ^{\rm }$th Int. Conf. Computer Vision'', New Delhi, India, 1998, pp. 839-846.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A25, 42C15, 68Q32

Retrieve articles in all journals with MSC (2010): 41A25, 42C15, 68Q32


Additional Information

Charles K. Chui
Affiliation: Department of Statistics, Stanford University, Stanford, California 94305
Email: ckchui@stanford.edu

H. N. Mhaskar
Affiliation: Department of Mathematics, California Institute of Technology, Pasadena, California 91125 — and — Institute of Mathematical Sciences, Claremont Graduate University, Claremont, California 91711
Email: hmhaska@gmail.com

DOI: https://doi.org/10.1090/S0025-5718-2014-02819-6
Received by editor(s): February 17, 2012
Received by editor(s) in revised form: February 23, 2013
Published electronically: June 18, 2014
Additional Notes: The first author’s research was supported by ARO Grants # W911NF-07-1-0525 and # W911NF-11-1-0426.
The second author’s research was supported, in part, by grant DMS-0908037 from the National Science Foundation and grant W911NF-09-1-0465 from the U.S. Army Research Office.
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society