Curve based approximation of measures on manifolds by discrepancy minimization

DOI10.1007/S10208-021-09491-2zbMATH Open1491.65048arXiv1910.06124OpenAlexW2980049123MaRDI QIDQ2067682FDOQ2067682

Authors: Martin Ehler, Manuel Gräf, Sebastian Neumayer, Gabriele Steidl 

Publication date: 18 January 2022

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: The approximation of probability measures on compact metric spaces and in particular on Riemannian manifoldsby atomic or empirical ones is a classical task in approximation and complexity theory with a wide range of applications. Instead of point measures we are concerned with the approximation by measures supported on Lipschitz curves. Special attention is paid to push-forward measures of Lebesgue measures on the interval by such curves. Using the discrepancy as distance between measures, we prove optimal approximation rates in terms of Lipschitz constants of curves. Having established the theoretical convergence rates, we are interested in the numerical minimization of the discrepancy between a given probability measure and the set of push-forward measures of Lebesgue measures on the interval by Lipschitz curves. We present numerical examples for measures on the 2- and 3-dimensional torus, the 2-sphere, the rotation group on $mathbb{R}^3$ and the Grassmannian of all 2-dimensional linear subspaces of $mathbb{R}^4$. Our algorithm of choice is a conjugate gradient method on these manifolds which incorporates second-oder information. For efficiently computing the gradients and the Hessians within the algorithm, we approximate the given measures by truncated Fourier series and use fast Fourier transform techniques on these manifolds.

Full work available at URL: https://arxiv.org/abs/1910.06124

Recommendations

• Approximating probability measures on manifolds via radial basis functions
• Approximation by finitely supported measures
• Families of well approximable measures
• A gradient-descent method for curve fitting on Riemannian manifolds
• scientific article; zbMATH DE number 1304969

zbMATH Keywords

non-convex optimizationmanifoldssampling theorycurvesquadrature rulesFourier methodsapproximation of measures

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26)

Cites Work

• Using NFFT 3 -- a software library for various nonequispaced fast Fourier transforms
• Title not available (Why is that?)
• Computational optimal transport. With applications to data sciences
• Title not available (Why is that?)
• Principal Curves
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization Techniques on Riemannian Manifolds
• On the mathematical foundations of learning
• Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs
• A course in metric geometry
• The Grand Tour: A Tool for Viewing Multidimensional Data
• Modern methods in the calculus of variations. \(L^p\) spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sobolev algebras on Lie groups and Riemannian manifolds
• Approximation by finitely supported measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization methods on Riemannian manifolds and their application to shape space
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Spherical harmonics
• Title not available (Why is that?)
• Consistency of variational continuous-domain quantization via kinetic theory
• Dithering by differences of convex functions
• Quadrature errors, discrepancies, and their relations to halftoning on the torus and the sphere
• Quadrature rules and distribution of points on manifolds
• On minimal trajectories for mobile sampling of bandlimited fields
• On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms
• Quadrature in Besov spaces on the Euclidean sphere
• The Conjugate Gradient Method for Linear and Nonlinear Operator Equations
• A unified approach to scattered data approximation on \(\mathbb{S}^{\mathbf {3}}\) and \(\mathrm{SO(3)}\)
• Scattered data interpolation on embedded submanifolds with restricted positive definite kernels: Sobolev error estimates
• Well-separated spherical designs
• On averaging sets
• Optimal asymptotic bounds for spherical designs
• Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces
• Linear programming bounds for codes in grassmannian spaces
• On means of distances on the surface of a sphere. II: Upper bounds
• Extremal properties of principal curves in the plane
• Title not available (Why is that?)
• Generalized Jacobi Polynomials as Spherical Functions of the Grassmann Manifold
• Eignets for function approximation on manifolds
• Marcinkiewicz-Zygmund measures on manifolds
• Bounds for codes and designs in complex subspaces
• A projection method on measures sets
• Variable density sampling with continuous trajectories
• Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces
• On the generation of sampling schemes for magnetic resonance imaging
• Sampling Sets and Quadrature Formulae on the Rotation Group
• On Estimates for the Weights in Gaussian Quadrature in the Ultraspherical Case
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• Codes and designs in Grassmannian spaces.
• Designs in Grassmannian spaces and lattices
• Quasi Monte Carlo Integration and Kernel-Based Function Approximation on Grassmannians
• Numerical Fourier analysis
• Approximate Quadrature Measures on Data-Defined Spaces
• Optimal Transport Approximation of 2-Dimensional Measures
• Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure
• Uniform decomposition of probability measures: quantization, clustering and rate of convergence
• Reproducing kernels for the irreducible components of polynomial spaces on unions of Grassmannians

Cited In (10)

• Approximation properties of the double Fourier sphere method
• A discrete framework to find the optimal matching between manifold-valued curves
• Mathematical imaging and surface processing. Abstracts from the workshop held August 21--27, 2022
• t-Design Curves and Mobile Sampling on the Sphere
• Unbalanced multi-marginal optimal transport
• Approximating probability measures on manifolds via radial basis functions
• Approximation and interpolation of singular measures by trigonometric polynomials
• One-dimensional approximation of measures in Wasserstein distance
• Wasserstein steepest descent flows of discrepancies with Riesz kernels
• Minimax properties of Fréchet means of discretely sampled curves

Uses Software

• NFFT3

This page was built for publication: Curve based approximation of measures on manifolds by discrepancy minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067682)