Quantization-based Bounds on the Wasserstein Metric

• URL: http://arxiv.org/abs/2506.00976v1
• Date: Sun, 01 Jun 2025 12:06:31 GMT
• Title: Quantization-based Bounds on the Wasserstein Metric
• Authors: Jonathan Bobrutsky, Amit Moscovich,
• Abstract summary: The Wasserstein metric has become increasingly important in many machine learning applications.<n>Despite its appeal, it is often too costly to compute.<n>We consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds.
• Score: 0.7550566004119158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Wasserstein metric has become increasingly important in many machine learning applications such as generative modeling, image retrieval and domain adaptation. Despite its appeal, it is often too costly to compute. This has motivated approximation methods like entropy-regularized optimal transport, downsampling, and subsampling, which trade accuracy for computational efficiency. In this paper, we consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds. Focusing on discrete measures on regular grids, our approach involves formulating and exactly solving a Kantorovich problem on a coarse grid using a quantized measure and specially designed cost matrix, followed by an upscaling and correction stage. This is done either in the primal or dual space to obtain valid upper and lower bounds on the Wasserstein metric of the full-resolution inputs. We evaluate our methods on the DOTmark optimal transport images benchmark, demonstrating a 10x-100x speedup compared to entropy-regularized OT while keeping the approximation error below 2%.

Related papers

• Determination of Particle-Size Distributions from Light-Scattering Measurement Using Constrained Gaussian Process Regression [7.5715377940231114]
  We propose a novel methodology for robustly estimating particle size distributions from optical scattering measurements.<n>The proposed constrained Gaussian process regression framework accurately reconstructs particle size distributions.
  arXiv  Detail & Related papers  (2025-07-04T17:56:16Z)
• Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows [1.8109081066789847]
  We present a novel method for efficiently computing optimal transport maps and Wasserstein barycenters in high-dimensional spaces.<n>Our approach uses conditional normalizing flows to approximate the input distributions as invertible pushforward transformations from a common latent space.<n>We show how this approach can be extended to compute Wasserstein barycenters by solving a conditional variance minimization problem.
  arXiv  Detail & Related papers  (2025-05-28T13:46:07Z)
• Slicing the Gaussian Mixture Wasserstein Distance [1.534667887016089]
  Key challenge in working with GMMs is defining a computationally efficient and geometrically meaningful metric.<n>We propose novel slicing-based approximations to the Wasserstein distance that significantly reduce computational complexity.
  arXiv  Detail & Related papers  (2025-04-11T13:57:09Z)
• Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms [10.022615790746466]
  We derive non-asymptotic functional approximation error bounds between the algorithm sample paths and the Ornstein-Uhlenbeck approximation.<n>We use our main result to construct error bounds in terms of two common metrics: the L'evy-Prokhorov and bounded Wasserstein distances.
  arXiv  Detail & Related papers  (2025-01-21T15:29:11Z)
• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  Pathwise methods allow to efficiently compute the full path for penalized estimators.<n>We apply these algorithms to the penalized estimation of processes observed at discrete times.
  arXiv  Detail & Related papers  (2024-12-05T10:38:29Z)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
  We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration. The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
  arXiv  Detail & Related papers  (2024-05-30T15:55:04Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  We present a model inversion algorithm, CKLEMAP, for data assimilation and parameter estimation in partial differential equation models. The CKLEMAP method provides better scalability compared to the standard MAP method.
  arXiv  Detail & Related papers  (2023-01-26T18:14:12Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport. We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
  arXiv  Detail & Related papers  (2021-02-02T21:01:13Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)
• Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
  We introduce an algorithm to solve a regularized version of the problem of Wasserstein estimators gradient, with a time per step which is sublinear in the natural dimensions. We show that this algorithm can be extended to other tasks, including estimation of Wasserstein barycenters.
  arXiv  Detail & Related papers  (2020-02-20T12:04:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.