Scattered manifold-valued data approximation

Philipp Grohs, Markus Sprecher, Thomas YuNumerische Mathematik 2017 · DOI

TL;DR

This paper introduces a novel framework for approximating functions that map Euclidean domains to curved manifolds using scattered, non-grid data. By combining Moving Least Squares (MLS) with the Karcher mean (and more efficient retraction-based alternatives), the authors prove that these nonlinear approximants retain the same high-order accuracy and smoothness as their classical linear counterparts.

What Problem Does This Paper Address?

In many engineering and scientific fields—ranging from medical imaging (diffusion tensor MRI) to aeronautics (predicting aerodynamic flutter)—data doesn't live in a flat Euclidean space. Instead, it lives on a manifold, such as a sphere, a set of rotation matrices, or symmetric positive definite (SPD) matrices.

Traditional approximation methods (like splines or radial basis functions) are designed for linear spaces. A common workaround is the "push-interpolate-pull" technique: map data to a tangent space (flatten it), interpolate there, and map it back. However, this only works if all data points are very close together. If data is scattered across a manifold with non-trivial topology, this local approach fails. The challenge is creating a method that "acts locally but thinks globally"—one that is well-defined for scattered data across the whole manifold while maintaining the theoretical guarantees (like $O(h^k)$ accuracy) we expect from linear math.

Methods

The authors propose a Riemannian Moving Least Squares (MLS) approach.

  1. Linear Foundation: They start with classical MLS, which uses a set of basis functions $\phi_i(x)$ that can reproduce polynomials up to degree $k$.
  2. Nonlinear Extension: In a linear space, an approximant is a weighted sum: $Qf(x) = \sum \phi_i(x) f(\xi_i)$. On a manifold, you can't simply "add" points. The authors replace this sum with the Karcher mean (or Riemannian average), defined as the point that minimizes the weighted sum of squared geodesic distances to the data points.
  3. Retraction Pairs: Recognizing that computing Karcher means (which involve logs and exps) is computationally expensive, they generalize the theory to retraction pairs. This allows the use of more efficient, first-order approximations of the manifold's geometry without sacrificing the order of accuracy.
  4. Proximity Analysis: They use a "smoothness descriptor" for manifold-valued functions to prove that the error of their nonlinear scheme is bounded by the error of the underlying linear scheme plus terms related to the manifold's curvature.

Datasets

The paper evaluates the method using synthetic numerical experiments rather than large-scale public datasets:

  • Sphere-valued functions ($S^2$): Approximating a function mapping $[0, 1]$ to a unit sphere.
  • SPD Matrix-valued functions: Interpolating between randomly chosen Symmetric Positive Definite matrices using the Frobenius norm-based geodesic distance.
  • Reduced Order Models (ROMs): A practical application involving the interpolation of matrices for linear time-invariant systems, effectively working on the Stiefel manifold and Grassmannian.

Key Insights and Ideas

  • Smoothness Equivalence: The most significant theoretical "aha moment" is that the nonlinear approximant inherits the exact same accuracy order ($O(h^k)$) and smoothness ($C^m$) as the linear basis functions used to build it.
  • Geometry Independence: The error estimate "decouples" the contribution of the function's smoothness from the manifold's geometry. The geometric influence is captured entirely by the derivatives of the logarithm mapping (or retraction).
  • Objectivity: Because the construction is purely geometric, it is invariant under isometries. In physics and mechanics, this ensures the approximation doesn't change just because you rotated your coordinate system.
  • Retractions Suffice: You don't need the "perfect" Riemannian metric (Karcher mean) to get high-order convergence; any valid retraction pair will do, which is a huge win for computational efficiency.

Key Results

  • Theoretical Convergence: The authors prove Theorem 3.5, showing that the approximation error is $d(Q^M f(x), f(x)) \leq C \cdot h(x)^k$, where $h$ is the local meshwidth and $k$ is the polynomial reproduction degree.
  • Numerical Validation: Experiments on the sphere and SPD matrices confirm the $O(h^2)$ convergence rate when using linear "hat" functions (which reproduce degree 1 polynomials).
  • Superiority over "Push-Interpolate-Pull": In the ROM application, the authors show that their method avoids the massive errors (spikes) seen in previous methods (like Amsallem & Farhat 2011) when data points are spread far apart on the manifold.

Limitations and Future Work

  • Local Closeness: While the method handles globally scattered data, the data sites $(\xi_i)$ must still be "locally" close enough for the Karcher mean (or retraction-based mean) to be uniquely defined and well-behaved.
  • Computational Cost: Even with retractions, finding the "center of mass" is an iterative process (Newton-like methods), which is more demanding than a simple linear sum.
  • High Dimensions: While the theory holds for any dimension $s$, the numerical examples are relatively low-dimensional. Exploring the "curse of dimensionality" in the context of manifold-valued scattered data remains an open area.

Summary updated

BibTeX
@article{grohs2017scattered,
  author = {Philipp Grohs and Markus Sprecher and Thomas Yu},
  title = {{Scattered manifold-valued data approximation}},
  journal = {Numerische Mathematik},
  year = {2017},
  doi = {10.1007/s00211-016-0823-0},
}
Figure