On combinatorial properties of greedy Wasserstein minimization

From MaRDI portal
(Redirected from Publication:6140904)

DOI10.1016/J.JMAA.2023.127940MaRDI QIDQ6140904zbMATH OpenOpenAlexFDO

Authors Stefan Steinerberger

Publication date 2 January 2024

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

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


zbMATH Keywords

greedy sequencesirregularities of distributionKritzingerKroneckervan der CorputWasserstein distance

Mathematics Subject Classification ID

General theory of distribution modulo (1) (11K06) Irregularities of distribution, discrepancy (11K38) Manifolds and measure-geometric topics (49Q99)


Abstract: We discuss a phenomenon where Optimal Transport leads to a remarkable amount of combinatorial regularity. Consider infinite sequences (xk)k=1infty in [0,1] constructed in a greedy manner: given x1,dots,xn, the new point xn+1 is chosen so as to minimize the Wasserstein distance W2 between the empirical measure of the n+1 points and the Lebesgue measure, x_{n+1} = argmin_x ~W_2left( frac{1}{n+1} sum_{k=1}^{n} delta_{x_k} + frac{delta_{x}}{n+1}, dx ight). This leads to fascinating sequences (for example: xn+1=(2k+1)/(2n+2) for some kinmathbbZ) which coincide with sequences recently introduced by Ralph Kritzinger in a different setting. Numerically, the regularity of these sequences rival the best known constructions from Combinatorics or Number Theory. We prove a regularity result below the square root barrier.


Review text

The theory of irregularities of distribution investigates how regular the distribution of the first \(n\) points of an infinite sequence can be. Classical examples of \textit{low discrepancy} sequences are known to be more regularly distributed than sequences of i.i.d. uniformly distributed random points. While sequences in \([0,1]\) are very well understood by now, the problem of irregularities of distribution in dimensions \(d \geq 2\) is challenging. Motivated by this the author initiated [\textit{S. Steinerberger}, Monatsh. Math. 191, No. 3, 639--655 (2020; Zbl 1471.11222)] the study of new constructions of sequences with very regular distribution, i.e., given \(x_1, \ldots, x_n\), the next point, \(x_{n+1}\), is chosen so as to minimize a particular energy functional. In the reviewed paper, the greedy construction is based on minimizing the Wasserstein distance between the empirical measure of the first \(n\) points and the Lebesgue measure. The author points out several astonishing properties of such sequences, and, in particular, shows (Theorem 1) that this general construction can reproduce a sequence introduced by \textit{R. Kritzinger} [Mosc. J. Comb. Number Theory 11, No. 3, 215--236 (2022; Zbl 1511.11069)]. This connection is interesting in two ways. First, the Kritzinger sequence is a greedy sequence that chooses its next point with the aim of minimizing the \(L_2\)-discrepancy, which is one of the main measures for the irregularity of distribution of sequences. Second, the author derives a new regularity statement for Kritzinger sequences in Theorem 2 breaking, what is known to be, the \textit{square-root barrier}. In other words, it shows that Kritzinger sequences are more regular than i.i.d. uniformly distributed random variables.


Recommendations


Cites work









This page was built for publication: On combinatorial properties of greedy Wasserstein minimization

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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=On_combinatorial_properties_of_greedy_Wasserstein_minimization&oldid=102401654"
Powered by MediaWiki