Smooth function extension based on high dimensional unstructured data

• Published in: Mathematics of computation 2014-11, Vol.83 (290), p.2865-2891
• Main Authors: Chui, Charles K., Mhaskar, H. N.
• Format: Article
• Language: English
• Subjects: Approximation; Eigenvalues; Integers; Interpolation; Mathematical functions; Mathematical manifolds; Mathematical theorems; Objective functions; Polynomials; Research article; Riemann manifold
• ISSN: 0025-5718; 1088-6842
• DOI: 10.1090/S0025-5718-2014-02819-6

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 P{\mathcal P} in some high dimensional Euclidean space Rs{\mathbb R}^{s}. Then the problem is to extend a desirable objective function ff from a certain relatively smaller training subset C⊂P\mathcal {C}\subset {\mathcal P} to some continuous manifold X⊂Rs{\mathbb X}\subset {\mathbb R}^{s} that contains P{\mathcal P}, at least approximately. More precisely, when the point cloud P{\mathcal P} of the given data–set is modeled in the abstract by some unknown compact manifold embedded in the ambient Euclidean space Rs{\mathbb R}^{s}, the extension problem can be considered as the interpolation problem of seeking the objective function on the manifold X{\mathbb X} that agrees with ff on C\mathcal {C} under certain desirable specifications. For instance, by considering groups of cardinality ss of data values as points in a point-cloud in Rs{\mathbb R}^{s}, such groups that are far apart in the original spatial data domain in R1{\mathbb R}^{1} or R2{\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.