Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport

DOI10.1007/S00041-021-09838-XzbMATH Open1462.05192arXiv2008.11296OpenAlexW3156880283MaRDI QIDQ829888FDOQ829888

Authors: Louis Brown 

Publication date: 6 May 2021

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Abstract: Given a graph $G=(V,E)$, suppose we are interested in selecting a sequence of vertices $(x_j{)}_{j=1}^n$ such that $left{x}_1,dots,x_{k}ight$ is `well-distributed' uniformly in $k$. We describe a greedy algorithm motivated by potential theory and corresponding developments in the continuous setting. The algorithm performs nicely on graphs and may be of use for sampling problems. We can interpret the algorithm as trying to greedily minimize a negative Sobolev norm; we explain why this is related to Wasserstein distance by establishing a purely spectral bound on the Wasserstein distance on graphs that mirrors R. Peyre's estimate in the continuous setting. We illustrate this with many examples and discuss several open problems.

Full work available at URL: https://arxiv.org/abs/2008.11296

Recommendations

• Lazy random walks and optimal transport on graphs
• Geometry of graph partitions via optimal transport
• Optimal mass transport on metric graphs
• \(W_{1,+}\)-interpolation of probability measures on graphs
• Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon

zbMATH Keywords

samplingmanifoldpotential theoryinverse Laplacian

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Variational problems in a geometric measure-theoretic setting (49Q20) Extremal problems in graph theory (05C35) Integral representations, integral operators, integral equations methods in higher dimensions (31B10) Integral transforms, operational calculus (44A99)

Cites Work

• Title not available (Why is that?)
• Computational optimal transport. With applications to data sciences
• On mass transportation
• Quasi-Monte Carlo integration on manifolds with mapped low-discrepancy points and greedy minimal Riesz \(s\)-energy points
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Irregularities of distribution, VII
• Title not available (Why is that?)
• Optimal logarithmic energy points on the unit sphere
• Sampling in Paley-Wiener spaces on combinatorial graphs
• Title not available (Why is that?)
• Sampling, filtering and sparse approximations on combinatorial graphs
• An implicit restarted Lanczos method for large symmetric eigenvalue problems
• Sur certaines suites liées aux ensembles plans et leur application à la représentation conforme
• Pseudo Leja sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Newton interpolation at Leja points
• Two-point Taylor expansions and one-dimensional boundary value problems
• Title not available (Why is that?)
• The application of Leja points to Richardson iteration and polynomial preconditioning
• Introduction to analysis on graphs
• Discrete and continuous Green energy on compact manifolds
• Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon
• Wasserstein distance, Fourier series and applications
• Dynamically defined sequences with small discrepancy
• Greedy energy minimization can count in binary: point charges and the van der Corput sequence
• Numerical integration on graphs: Where to sample and how to weigh
• On the Wasserstein distance between classical sequences and the Lebesgue measure
• Comparison between \(W_2\) distance and \(\dot{H}^{-1}\) norm, and localization of Wasserstein distance
• Title not available (Why is that?)
• An enhanced uncertainty principle for the vaserstein distance

Cited In (4)

• A low discrepancy sequence on graphs
• Quadrature formulas on combinatorial graphs
• Sums of distances on graphs and embeddings into Euclidean space
• Overview of the topical collection: harmonic analysis on combinatorial graphs

This page was built for publication: Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q829888)