A diffusion-map-based algorithm for gradient computation on manifolds and applications
This provides a derivative-free optimization method for problems on manifolds, which is incremental but useful for domains like computational geometry and imaging.
The paper tackles the problem of computing Riemannian gradients on manifolds using only function evaluations, by leveraging diffusion-map estimates of the Laplace-Beltrami operator, and demonstrates applications such as tomographic reconstruction and sphere packing with validated results.
We recover the Riemannian gradient of a given function defined on interior points of a Riemannian submanifold in the Euclidean space based on a sample of function evaluations at points in the submanifold. This approach is based on the estimates of the Laplace-Beltrami operator proposed in the diffusion-maps theory. The Riemannian gradient estimates do not involve differential terms. Analytical convergence results of the Riemannian gradient expansion are proved. We apply the Riemannian gradient estimate in a gradient-based algorithm providing a derivative-free optimization method. We test and validate several applications, including tomographic reconstruction from an unknown random angle distribution, and the sphere packing problem in dimensions 2 and 3.