Wasserstein Archetypal Analysis

• URL: http://arxiv.org/abs/2210.14298v1
• Date: Tue, 25 Oct 2022 19:50:09 GMT
• Title: Wasserstein Archetypal Analysis
• Authors: Katy Craig, Braxton Osting, Dong Wang, and Yiming Xu
• Abstract summary: Archetypal analysis is an unsupervised machine learning method that summarizes data using a convex polytope. We consider an alternative formulation of archetypal analysis based on the Wasserstein metric.
• Score: 9.54262011088777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Archetypal analysis is an unsupervised machine learning method that summarizes data using a convex polytope. In its original formulation, for fixed k, the method finds a convex polytope with k vertices, called archetype points, such that the polytope is contained in the convex hull of the data and the mean squared Euclidean distance between the data and the polytope is minimal. In the present work, we consider an alternative formulation of archetypal analysis based on the Wasserstein metric, which we call Wasserstein archetypal analysis (WAA). In one dimension, there exists a unique solution of WAA and, in two dimensions, we prove existence of a solution, as long as the data distribution is absolutely continuous with respect to Lebesgue measure. We discuss obstacles to extending our result to higher dimensions and general data distributions. We then introduce an appropriate regularization of the problem, via a Renyi entropy, which allows us to obtain existence of solutions of the regularized problem for general data distributions, in arbitrary dimensions. We prove a consistency result for the regularized problem, ensuring that if the data are iid samples from a probability measure, then as the number of samples is increased, a subsequence of the archetype points converges to the archetype points for the limiting data distribution, almost surely. Finally, we develop and implement a gradient-based computational approach for the two-dimensional problem, based on the semi-discrete formulation of the Wasserstein metric. Our analysis is supported by detailed computational experiments.

Related papers

• Extracting Manifold Information from Point Clouds [0.0]
  A kernel based method is proposed for the construction of signature functions of subsets of $mathbbRd$. The analytical and analysis of point clouds are the main application.
  arXiv  Detail & Related papers  (2024-03-30T17:21:07Z)
• Randomized Physics-Informed Machine Learning for Uncertainty Quantification in High-Dimensional Inverse Problems [49.1574468325115]
  We propose a physics-informed machine learning method for uncertainty quantification in high-dimensional inverse problems. We show analytically and through comparison with Hamiltonian Monte Carlo that the rPICKLE posterior converges to the true posterior given by the Bayes rule.
  arXiv  Detail & Related papers  (2023-12-11T07:33:16Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Nonlinear Sufficient Dimension Reduction for Distribution-on-Distribution Regression [9.086237593805173]
  We introduce a new approach to nonlinear sufficient dimension reduction in cases where both the predictor and the response are distributional data. Our key step is to build universal kernels (cc-universal) on the metric spaces.
  arXiv  Detail & Related papers  (2022-07-11T04:11:36Z)
• Tangent Space and Dimension Estimation with the Wasserstein Distance [10.118241139691952]
  Consider a set of points sampled independently near a smooth compact submanifold of Euclidean space. We provide mathematically rigorous bounds on the number of sample points required to estimate both the dimension and the tangent spaces of that manifold.
  arXiv  Detail & Related papers  (2021-10-12T21:02:06Z)
• Local versions of sum-of-norms clustering [77.34726150561087]
  We show that our method can separate arbitrarily close balls in the ball model. We prove a quantitative bound on the error incurred in the clustering of disjoint connected sets.
  arXiv  Detail & Related papers  (2021-09-20T14:45:29Z)
• Probabilistic methods for approximate archetypal analysis [8.829245587252435]
  Archetypal analysis is an unsupervised learning method for exploratory data analysis. We introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets.
  arXiv  Detail & Related papers  (2021-08-12T14:27:11Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLE is a dimensionality-reduction post-processing step that corrects an initial embedding by minimizing a loss functional with both a local, metric term and a global, topological term. We observe that DIPOLE outperforms popular methods like UMAP, t-SNE, and Isomap on a number of popular datasets.
  arXiv  Detail & Related papers  (2021-06-14T17:19:44Z)
• 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)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Consistency of archetypal analysis [10.424626933990272]
  Archetypal analysis is an unsupervised learning method that uses a convex polytope to summarize multivariate data. In this paper, we prove a consistency result that shows if the data is independently sampled from a probability measure with bounded support. We also obtain the convergence rate of the optimal objective values under appropriate assumptions on the distribution.
  arXiv  Detail & Related papers  (2020-10-16T04:07:26Z)

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.