The Equivalence of Fourier-based and Wasserstein Metrics on Imaging
Problems
- URL: http://arxiv.org/abs/2005.06530v1
- Date: Wed, 13 May 2020 19:01:00 GMT
- Title: The Equivalence of Fourier-based and Wasserstein Metrics on Imaging
Problems
- Authors: Gennaro Auricchio, Andrea Codegoni, Stefano Gualandi, Giuseppe
Toscani, Marco Veneroni
- Abstract summary: We investigate properties of some extensions of a class of Fourier-based probability metrics.
In benchmark problems of image processing, Fourier metrics provide a better runtime with respect to Wasserstein ones.
- Score: 1.1744028458220426
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate properties of some extensions of a class of Fourier-based
probability metrics, originally introduced to study convergence to equilibrium
for the solution to the spatially homogeneous Boltzmann equation. At difference
with the original one, the new Fourier-based metrics are well-defined also for
probability distributions with different centers of mass, and for discrete
probability measures supported over a regular grid. Among other properties, it
is shown that, in the discrete setting, these new Fourier-based metrics are
equivalent either to the Euclidean-Wasserstein distance $W_2$, or to the
Kantorovich-Wasserstein distance $W_1$, with explicit constants of equivalence.
Numerical results then show that in benchmark problems of image processing,
Fourier metrics provide a better runtime with respect to Wasserstein ones.
Related papers
- Computational Guarantees for Doubly Entropic Wasserstein Barycenters via
Damped Sinkhorn Iterations [0.0]
We propose and analyze an algorithm for computing doubly regularized Wasserstein barycenters.
An inexact variant of our algorithm, implementable using approximate Monte Carlo sampling, offers the first non-asymptotic convergence guarantees.
arXiv Detail & Related papers (2023-07-25T09:42:31Z) - Stochastic optimal transport in Banach Spaces for regularized estimation
of multivariate quantiles [0.0]
We introduce a new algorithm for solving entropic optimal transport (EOT) between two absolutely continuous probability measures $mu$ and $nu$.
We study the almost sure convergence of our algorithm that takes its values in an infinite-dimensional Banach space.
arXiv Detail & Related papers (2023-02-02T10:02:01Z) - Depth-based pseudo-metrics between probability distributions [1.1470070927586016]
We propose two new pseudo-metrics between continuous probability measures based on data depth and its associated central regions.
In contrast to the Wasserstein distance, the proposed pseudo-metrics do not suffer from the curse of dimensionality.
The regions-based pseudo-metric appears to be robust w.r.t. both outliers and heavy tails.
arXiv Detail & Related papers (2021-03-23T17:33:18Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining'
This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
arXiv Detail & Related papers (2021-01-16T17:11:02Z) - Wasserstein K-Means for Clustering Tomographic Projections [6.878995336760916]
We present a k-means algorithm based on a rotationally-invariant Wasserstein metric for images.
There is little computational overhead, thanks to the use of a fast linear-time approximation to the Wasserstein-1 metric, also known as the Earthmover's distance.
arXiv Detail & Related papers (2020-10-20T03:28:17Z) - Continuous Regularized Wasserstein Barycenters [51.620781112674024]
We introduce a new dual formulation for the regularized Wasserstein barycenter problem.
We establish strong duality and use the corresponding primal-dual relationship to parametrize the barycenter implicitly using the dual potentials of regularized transport problems.
arXiv Detail & Related papers (2020-08-28T08:28:06Z) - Scalable Computations of Wasserstein Barycenter via Input Convex Neural
Networks [15.171726731041055]
Wasserstein Barycenter is a principled approach to represent the weighted mean of a given set of probability distributions.
We present a novel scalable algorithm to approximate the Wasserstein Barycenters aiming at high-dimensional applications in machine learning.
arXiv Detail & Related papers (2020-07-08T22:41:18Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data.
We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem.
In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
arXiv Detail & Related papers (2020-06-11T19:40:38Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting.
We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$.
Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
arXiv Detail & Related papers (2020-05-13T16:44:12Z) - A diffusion approach to Stein's method on Riemannian manifolds [65.36007959755302]
We exploit the relationship between the generator of a diffusion on $mathbf M$ with target invariant measure and its characterising Stein operator.
We derive Stein factors, which bound the solution to the Stein equation and its derivatives.
We imply that the bounds for $mathbb Rm$ remain valid when $mathbf M$ is a flat manifold.
arXiv Detail & Related papers (2020-03-25T17:03:58Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations.
Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic.
We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
arXiv Detail & Related papers (2020-02-05T03:09:23Z)
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.