Constructive quantization: approximation by empirical measures

DOI10.1214/12-AIHP489MaRDI QIDQ376699zbMATHFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(67)

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

Describes a project that uses

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)