Manifold learning in Wasserstein space
- URL: http://arxiv.org/abs/2311.08549v1
- Date: Tue, 14 Nov 2023 21:21:35 GMT
- Title: Manifold learning in Wasserstein space
- Authors: Keaton Hamm, Caroline Moosm\"uller, Bernhard Schmitzer, Matthew Thorpe
- Abstract summary: We show that the metric space $(Lambda,W_Lambda)$ can be recovered in the sense of Gromov--Wasserstein from a graph with nodes $lambda_i_i=1N$ and edge weights $W(lambda_i,lambda_j)$.
In particular, we show that the metric space $(Lambda,W_Lambda)$ can be recovered in the sense of Gromov--Wasserstein from a graph with nodes $lambda_i_
- Score: 3.2315169215372443
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper aims at building the theoretical foundations for manifold learning
algorithms in the space of absolutely continuous probability measures on a
compact and convex subset of $\mathbb{R}^d$, metrized with the Wasserstein-2
distance $W$. We begin by introducing a natural construction of submanifolds
$\Lambda$ of probability measures equipped with metric $W_\Lambda$, the
geodesic restriction of $W$ to $\Lambda$. In contrast to other constructions,
these submanifolds are not necessarily flat, but still allow for local
linearizations in a similar fashion to Riemannian submanifolds of
$\mathbb{R}^d$. We then show how the latent manifold structure of
$(\Lambda,W_{\Lambda})$ can be learned from samples $\{\lambda_i\}_{i=1}^N$ of
$\Lambda$ and pairwise extrinsic Wasserstein distances $W$ only. In particular,
we show that the metric space $(\Lambda,W_{\Lambda})$ can be asymptotically
recovered in the sense of Gromov--Wasserstein from a graph with nodes
$\{\lambda_i\}_{i=1}^N$ and edge weights $W(\lambda_i,\lambda_j)$. In addition,
we demonstrate how the tangent space at a sample $\lambda$ can be
asymptotically recovered via spectral analysis of a suitable "covariance
operator" using optimal transport maps from $\lambda$ to sufficiently close and
diverse samples $\{\lambda_i\}_{i=1}^N$. The paper closes with some explicit
constructions of submanifolds $\Lambda$ and numerical examples on the recovery
of tangent spaces through spectral analysis.
Related papers
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Exact Fractional Inference via Re-Parametrization & Interpolation
between Tree-Re-Weighted- and Belief Propagation- Algorithms [0.5348370085388683]
Inference efforts -- required to compute partition function, $Z$, of an Ising model over a graph of $N$ spins" -- are most likely exponential in $N$.
We show how to express $Z$ as a product, $forall lambda: Z=Z(lambda)cal Z(lambda)$, where the multiplicative correction, $cal Z(lambda)$, is an expectation over a node-independent probability distribution built from node-wise fractional marginals.
arXiv Detail & Related papers (2023-01-25T00:50:28Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
We consider the problem of estimating a $d$ dimensional sub-manifold of $mathbbRD$ from a finite set of noisy samples.
We show that the estimation yields rates of convergence of $n-frack2k + d$ for the point estimation and $n-frack-12k + d$ for the estimation of tangent space.
arXiv Detail & Related papers (2021-05-11T02:29:33Z) - Asymptotic Theory of $\ell_1$-Regularized PDE Identification from a
Single Noisy Trajectory [2.0299248281970956]
We prove the support recovery for a general class of linear and nonlinear evolutionary partial differential equation (PDE) identification from a single noisy trajectory.
We provide a set of sufficient conditions which guarantee that, from a single trajectory data denoised by a Local-Polynomial filter, the support of $mathbfc(lambda)$ally converges to the true signed-support associated with the underlying PDE.
arXiv Detail & Related papers (2021-03-12T02:23:04Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation.
We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
arXiv Detail & Related papers (2020-08-06T09:50:29Z) - Approximating the Riemannian Metric from Point Clouds via Manifold
Moving Least Squares [2.2774471443318753]
We present a naive algorithm that yields approximate geodesic distances with a rate of convergence $ O(h) $ provable approximations.
We show the potential and the robustness to noise of the proposed method on some numerical simulations.
arXiv Detail & Related papers (2020-07-20T04:42:17Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector.
We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
arXiv Detail & Related papers (2020-06-12T10:21:40Z) - Learning Theory for Estimation of Animal Motion Submanifolds [0.0]
This paper describes the formulation and experimental testing of a novel method for the estimation and approximation of submanifold models of animal motion.
Experiments generate a finite sets $(s_i,x_i)_i=1msubset mathbbZm$ of samples that are generated according to an unknown probability density.
arXiv Detail & Related papers (2020-03-30T20:54:51Z)
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.