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
- 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) - Physics-Informed Machine Learning Method for Large-Scale Data
Assimilation Problems [48.7576911714538]
We extend the physics-informed conditional Karhunen-Lo'eve expansion (PICKLE) method for modeling subsurface flow with unknown flux (Neumann) and varying head (Dirichlet) boundary conditions.
We demonstrate that the PICKLE method is comparable in accuracy with the standard maximum a posteriori (MAP) method, but is significantly faster than MAP for large-scale problems.
arXiv Detail & Related papers (2021-07-30T18:43:14Z) - 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.