Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon

DOI10.1016/J.JCO.2020.101485MaRDI QIDQ1996877zbMATH OpenOpenAlexWikidataFDO

Authors Louis Brown, Stefan Steinerberger

Publication date 26 February 2021

Published in Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmGreen's functionlow-discrepancy sequencesWasserstein distance

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Dynamical systems involving maps of the interval (37E05) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Abstract: We describe a curious dynamical system that results in sequences of real numbers in $[0,1]$ with seemingly remarkable properties. Let the function $f:mathbbTightarrowmathbbR$ satisfy $hatf(k)geqc|k{|}^{-2}$ and define a sequence via ${\displaystyle }$ x_n = argmin_x sum_{k=1}^{n-1}{f(x-x_k)}.${\displaystyle }$ Such sequences $(x_n{)}_{n=1}^{infty}$ seem to be astonishingly regularly distributed in various ways (satisfying favorable exponential sum estimates; every interval $Jsubset[0,1]$ contains $sim|J|n$ elements). We prove ${\displaystyle }$ W_2left( frac{1}{n} sum_{k=1}^{n}{delta_{x_k}}, dx ight) leq frac{c}{sqrt{n}},${\displaystyle }$ where $W_2$ is the 2-Wasserstein distance. Much stronger results seem to be true and it seems like an interesting problem to understand this dynamical system better. We obtain optimal results in dimension $dgeq3$: using $G(x,y)$ to denote the Green's function of the Laplacian on a compact manifold, we show that ${\displaystyle }$ x_n = argmin_{x in M} sum_{k=1}^{n-1}{G(x,x_k)} quad mbox{satisfies} quad W_2left( frac{1}{n} sum_{k=1}^{n}{delta_{x_k}}, dx ight) lesssim frac{1}{n^{1/d}}.${\displaystyle }$

Recommendations

• scientific article; zbMATH DE number 3303288
• On an extremal problem for positive definite functions
• scientific article; zbMATH DE number 1033795
• On some positive definite functions
• On positive definiteness of some functions
• On positive definiteness of some functions
• On the exponential sum-product problem
• The extension problem for positive-definite functions
• On approximation of functions by exponential sums

Cites work

• A facility location formulation for stable polynomials and elliptic Fekete points
• An improved bound for the star discrepancy of sequences in the unit interval
• Comparison between \(W_2\) distance and \(\dot{H}^{-1}\) norm, and localization of Wasserstein distance
• Concentration for Coulomb gases and Coulomb transport inequalities
• Concentration for Coulomb gases on compact manifolds
• Connections between numerical integration, discrepancy, dispersion, and universal discretization
• Cubature formulas, discrepancy, and nonlinear approximation
• Discrete and continuous Green energy on compact manifolds
• Dynamically defined sequences with small discrepancy
• Equidistribution estimates for Fekete points on complex manifolds
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• General and refined Montgomery lemmata
• Greedy approximation
• Greedy approximation
• scientific article; zbMATH DE number 4130488 (Why is no real title available?)
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3654722 (Why is no real title available?)
• scientific article; zbMATH DE number 3555292 (Why is no real title available?)
• scientific article; zbMATH DE number 3565828 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 3997927 (Why is no real title available?)
• scientific article; zbMATH DE number 4000052 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 3048718 (Why is no real title available?)
• scientific article; zbMATH DE number 3049260 (Why is no real title available?)
• scientific article; zbMATH DE number 3096356 (Why is no real title available?)
• Irregularities of distribution, VII
• On irregularities of distribution
• On the diaphony of the van der Corput-Halton sequence
• On the small ball inequality in all dimensions
• On the small ball inequality in three dimensions
• On the star discrepancy of sequences in the unit interval
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Renormalized energy and asymptotic expansion of optimal logarithmic energy on the sphere
• Roth's orthogonal function method in discrepancy theory and some new connections
• Sequences, discrepancies and applications
• Some remarks on greedy algorithms

Cited in

(8)

• A Wasserstein inequality and minimal Green energy on compact manifolds
• Numerical integration and discrepancy under smoothness assumption and without it
• On the Wasserstein distance between classical sequences and the Lebesgue measure
• Sums of distances on graphs and embeddings into Euclidean space
• POLYNOMIALS WITH ZEROS ON THE UNIT CIRCLE: REGULARITY OF LEJA SEQUENCES
• On combinatorial properties of greedy Wasserstein minimization
• The rival coffee shop problem
• Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport

This page was built for publication: Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon

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