Wasserstein K-Means for Clustering Tomographic Projections

• URL: http://arxiv.org/abs/2010.09989v1
• Date: Tue, 20 Oct 2020 03:28:17 GMT
• Title: Wasserstein K-Means for Clustering Tomographic Projections
• Authors: Rohan Rao, Amit Moscovich, Amit Singer
• Abstract summary: 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.
• Score: 6.878995336760916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the 2D class averaging problem in single-particle cryo-electron microscopy (cryo-EM), we present a k-means algorithm based on a rotationally-invariant Wasserstein metric for images. Unlike existing methods that are based on Euclidean ($L_2$) distances, we prove that the Wasserstein metric better accommodates for the out-of-plane angular differences between different particle views. We demonstrate on a synthetic dataset that our method gives superior results compared to an $L_2$ baseline. Furthermore, 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.

Related papers

• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• 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)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Centered plug-in estimation of Wasserstein distances [0.0]
  The plug-in estimator of the squared Euclidean 2-Wasserstein distance is conservative, however due to its large positive bias it is often uninformative. We construct a pair of centered plug-in estimators that decrease with the true Wasserstein distance, and are therefore guaranteed to be informative, for any finite sample size.
  arXiv  Detail & Related papers  (2022-03-22T11:26:18Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• 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)
• Two-sample Test using Projected Wasserstein Distance [18.46110328123008]
  We develop a projected Wasserstein distance for the two-sample test, a fundamental problem in statistics and machine learning. A key contribution is to couple optimal projection to find the low dimensional linear mapping to maximize the Wasserstein distance between projected probability distributions.
  arXiv  Detail & Related papers  (2020-10-22T18:08:58Z)
• When OT meets MoM: Robust estimation of Wasserstein Distance [8.812837829361923]
  We consider the problem of estimating the Wasserstein distance between two probability distributions when observations are polluted by outliers. We introduce and discuss novel MoM-based robust estimators whose consistency is studied under a data contamination model. We propose a simple MoM-based re-weighting scheme that could be used in conjunction with the Sinkhorn algorithm.
  arXiv  Detail & Related papers  (2020-06-18T07:31:39Z)
• The Equivalence of Fourier-based and Wasserstein Metrics on Imaging Problems [1.1744028458220426]
  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.
  arXiv  Detail & Related papers  (2020-05-13T19:01:00Z)
• Wasserstein Exponential Kernels [13.136143245702915]
  We study the use of exponential kernels defined thanks to the regularized Wasserstein distance. We show that Wasserstein squared exponential kernels are shown to yield smaller classification errors on small training sets of shapes.
  arXiv  Detail & Related papers  (2020-02-05T17:31:56Z)

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.