Constructive quantization: approximation by empirical measures

DOI10.1214/12-AIHP489zbMATH Open1283.60063arXiv1108.5346MaRDI QIDQ376699FDOQ376699

Authors: Steffen Dereich, Reik Schottstedt, Michael Scheutzow 

Publication date: 19 November 2013

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: In this article, we study the approximation of a probability measure $mu$ on $mathbb{R}^d$ by its empirical measure $hat{mu}_N$ interpreted as a random quantization. As error criterion we consider an averaged $p$-th moment Wasserstein metric. In the case where $2p<d$, we establish refined upper and lower bounds for the error, a high-resolution formula. Moreover, we provide a universal estimate based on moments, a so-called Pierce type estimate. In particular, we show that quantization by empirical measures is of optimal order under weak assumptions.

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

Recommendations

• Quantization for probability measures in the Prokhorov metric
• Foundations of quantization for probability distributions
• Approximation rate in Wasserstein distance of probability measures on the real line by deterministic empirical measures
• Quantization of probability distributions under norm-based distortion measures
• Optimal approximation and quantisation

zbMATH Keywords

Wasserstein metrictransportation problemconstructive quantizationPierce's lemmarandom quantizationZador's theorem

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) (L^p)-limit theorems (60F25)

Cites Work

• On optimal matchings
• Asymptotics for transportation cost in high dimensions
• Combinatorial Optimization Over Two Random Point Sets
• Foundations of quantization for probability distributions
• Title not available (Why is that?)
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Title not available (Why is that?)
• On the mean speed of convergence of empirical and occupation measures in Wasserstein distance
• A space quantization method for numerical integration
• Optimal transport from Lebesgue to Poisson
• Multidimensional asymptotic quantization theory with&lt;tex&gt;r&lt;/tex&gt;th power distortion measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal quadratic quantization for numerics: the Gaussian case
• Mean rates of convergence of empirical measures in the Wasserstein metric
• Optimal Delaunay and Voronoi quantization schemes for pricing American style options
• Quantization of probability distributions under norm-based distortion measures
• Asymptotically optimal quantization schemes for Gaussian processes on Hilbert spaces
• Asymptotic formulae for coding problems and intermediate optimization problems: a review
• Derandomization of the Euler scheme for scalar stochastic differential equations
• The high resolution vector quantization problem with Orlicz norm distortion

Cited In (67)

• Randomized Wasserstein barycenter computation: resampling with statistical guarantees
• On optimal matching of Gaussian samples. III
• Convex order, quantization and monotone approximations of ARCH models
• A simple Fourier analytic proof of the AKT optimal matching theorem
• A measure theoretical approach to the mean-field maximum principle for training NeurODEs
• Asymptotics for semidiscrete entropic optimal transport
• On the rate of convergence in Wasserstein distance of the empirical measure
• Mini-Batch Risk Forms
• Rate of convergence of the Nanbu particle system for hard potentials and Maxwell molecules
• The Vlasov-Poisson dynamics as the mean field limit of extended charges
• Posterior asymptotics in Wasserstein metrics on the real line
• Wasserstein upper bounds of the total variation for smooth densities
• Convergence rates for empirical measures of Markov chains in dual and Wasserstein distances
• Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences
• Asymptotics of one-dimensional Lévy approximations
• Best finite constrained approximations of one-dimensional probabilities
• Behavior of the empirical Wasserstein distance in \({\mathbb R}^d\) under moment conditions
• A consistency estimate for Kac's model of elastic collisions in a dilute gas
• Convergence of asymptotic costs for random Euclidean matching problems
• A fluctuation result for the displacement in the optimal matching problem
• On optimal matching of Gaussian samples
• \(k\)-variance: a clustered notion of variance
• Finer estimates on the \(2\)-dimensional matching problem
• Consistency of probability measure quantization by means of power repulsion-attraction potentials
• Rates of convergence for robust geometric inference
• A gradient flow perspective on the quantization problem
• On the quadratic random matching problem in two-dimensional domains
• Random bit quadrature and approximation of distributions on Hilbert spaces
• Measure estimation on manifolds: an optimal transport approach
• On quantitative stability in infinite-dimensional optimization under uncertainty
• Some results on the optimal matching problem for the Jacobi model
• Learning finite-dimensional coding schemes with nonlinear reconstruction maps
• The Convergence Problem in Mean Field Games with Neumann Boundary Conditions
• Dynamics of data-driven ambiguity sets for hyperbolic conservation laws with uncertain inputs
• Inferring interaction rules from observations of evolutive systems I: The variational approach
• Deviation inequalities for separately Lipschitz functionals of iterated random functions
• Uniform decomposition of probability measures: quantization, clustering and rate of convergence
• A local refinement strategy for constructive quantization of scalar SDEs
• Optimal approximation and quantisation
• Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces
• Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
• Estimation of Wasserstein distances in the spiked transport model
• Quantization for probability measures in the Prokhorov metric
• Empirical measures: regularity is a counter-curse to dimensionality
• Improved rates for Wasserstein deconvolution with ordinary smooth error in dimension one
• Transport inequalities on Euclidean spaces for non-Euclidean metrics
• Geometrical Insights for Implicit Generative Modeling
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
• Derandomization of the Euler scheme for scalar stochastic differential equations
• Antithetic multilevel sampling method for nonlinear functionals of measure
• Weak quantitative propagation of chaos via differential calculus on the space of measures
• Characterization of probability distribution convergence in Wasserstein distance by \(L^p\)-quantization error function
• Distribution dependent SDEs driven by additive continuous noise
• Wasserstein upper bounds of \(L^p\)-norms for multivariate densities in Besov spaces
• An Integrated Transportation Distance between Kernels and Approximate Dynamic Risk Evaluation in Markov Systems
• Master Bellman equation in the Wasserstein space: Uniqueness of viscosity solutions
• The Wasserstein distance to the circular law
• Limit distribution theory for smooth \(p\)-Wasserstein distances
• Empirical optimal transport between different measures adapts to lower complexity
• Learning the random variables in Monte Carlo simulations with stochastic gradient descent: Machine learning for parametric PDEs and financial derivative pricing
• Convergence of adapted empirical measures on \(\mathbb{R}^d\)
• Gromov-Wasserstein distances: entropic regularization, duality and sample complexity
• On concentration of the empirical measure for radial transport costs
• Optimal transport methods for combinatorial optimization over two random point sets
• Asymptotic properties of Monte Carlo methods in elliptic PDE-constrained optimization under uncertainty
• On the optimal rate for the convergence problem in mean field control

Uses Software

• Wavelet and Multiscale Library

This page was built for publication: Constructive quantization: approximation by empirical measures

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