Dimension reduction and the gradient flow of relative entropy

• URL: http://arxiv.org/abs/2409.16963v1
• Date: Wed, 25 Sep 2024 14:23:04 GMT
• Title: Dimension reduction and the gradient flow of relative entropy
• Authors: Ben Weinkove,
• Abstract summary: Dimension reduction, widely used in science, maps high-dimensional data into low-dimensional space. We investigate a basic mathematical model underlying the techniques of neighborhood embedding (SNE) and its popular variant t-SNE. The aim is to map these points to low dimensions in an optimal way so that similar points are closer together.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dimension reduction, widely used in science, maps high-dimensional data into low-dimensional space. We investigate a basic mathematical model underlying the techniques of stochastic neighborhood embedding (SNE) and its popular variant t-SNE. Distances between points in high dimensions are used to define a probability distribution on pairs of points, measuring how similar the points are. The aim is to map these points to low dimensions in an optimal way so that similar points are closer together. This is carried out by minimizing the relative entropy between two probability distributions. We consider the gradient flow of the relative entropy and analyze its long-time behavior. This is a self-contained mathematical problem about the behavior of a system of nonlinear ordinary differential equations. We find optimal bounds for the diameter of the evolving sets as time tends to infinity. In particular, the diameter may blow up for the t-SNE version, but remains bounded for SNE.

Related papers

• Learning Distances from Data with Normalizing Flows and Score Matching [9.605001452209867]
  Density-based distances offer an elegant solution to the problem of metric learning. We show that existing methods to estimate Fermat distances suffer from poor convergence in both low and high dimensions. Our work paves the way for practical use of density-based distances, especially in high-dimensional spaces.
  arXiv  Detail & Related papers  (2024-07-12T14:30:41Z)
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities [0.5592394503914488]
  We introduce a method for identifying and approximating a target measure $pi$ as a perturbation of a given reference measure $mu$. Our main contribution unveils a connection between the emphdimensional logarithmic Sobolev inequality (LSI) and approximations with this ansatz.
  arXiv  Detail & Related papers  (2024-06-18T20:02:44Z)
• A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction [0.0]
  Persistence diagrams (PDs) are used as signatures of point cloud data. Two clouds of points can be compared using the bottleneck distance d_B between their PDs. We define, and study properties of, a new scale-invariant distance between PDs termed normalized bottleneck distance, d_N.
  arXiv  Detail & Related papers  (2023-06-11T17:17:48Z)
• 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)
• Matching Normalizing Flows and Probability Paths on Manifolds [57.95251557443005]
  Continuous Normalizing Flows (CNFs) are generative models that transform a prior distribution to a model distribution by solving an ordinary differential equation (ODE) We propose to train CNFs by minimizing probability path divergence (PPD), a novel family of divergences between the probability density path generated by the CNF and a target probability density path. We show that CNFs learned by minimizing PPD achieve state-of-the-art results in likelihoods and sample quality on existing low-dimensional manifold benchmarks.
  arXiv  Detail & Related papers  (2022-07-11T08:50:19Z)
• Compressive Fourier collocation methods for high-dimensional diffusion equations with periodic boundary conditions [7.80387197350208]
  High-dimensional Partial Differential Equations (PDEs) are a popular mathematical modelling tool, with applications ranging from finance to computational chemistry. Standard numerical techniques for solving these PDEs are typically affected by the curse of dimensionality. Inspired by recent progress in sparse function approximation in high dimensions, we propose a new method called compressive Fourier collocation.
  arXiv  Detail & Related papers  (2022-06-02T19:11:27Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  This paper develops a dimensionality reduction method that allows us to move the optimization to a finite-dimensional setting with an explicit bound on the dimension. In order to make progress on the problem, we restrict ourselves to Bayesian risks induced by a relatively large class of loss functions, namely Bregman divergences.
  arXiv  Detail & Related papers  (2022-02-23T16:22:28Z)
• Entropic Optimal Transport in Random Graphs [8.7314407902481]
  In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes. We show that it is possible to consistently estimate distances between groups of nodes in the latent space.
  arXiv  Detail & Related papers  (2022-01-11T13:52:34Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• 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)

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.