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

DOI10.1007/S00041-021-09838-XMaRDI QIDQ829888zbMATH OpenOpenAlexFDO

Authors Louis Brown

Publication date 6 May 2021

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

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

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)

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.

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

Cites work

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

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)