Metric entropy, n-widths, and sampling of functions on manifolds
Provides theoretical foundations and optimal algorithms for approximating functions on manifolds, relevant to approximation theory and machine learning on geometric data.
The paper derives asymptotics of metric entropy and nonlinear n-widths for function classes on manifolds, and develops constructive algorithms for function representation that are asymptotically optimal in terms of n-widths and near-optimal in terms of metric entropy.
We first investigate on the asymptotics of the Kolmogorov metric entropy and nonlinear n-widths of approximation spaces on some function classes on manifolds and quasi-metric measure spaces. Secondly, we develop constructive algorithms to represent those functions within a prescribed accuracy. The constructions can be based on either spectral information or scattered samples of the target function. Our algorithmic scheme is asymptotically optimal in the sense of nonlinear n-widths and asymptotically optimal up to a logarithmic factor with respect to the metric entropy.