On the computation of Fortet-Mourier and Dudley distances between measures: Functional analytic expressions and algorithms

This master thesis is dedicated to the computation of Fortet-Mourier and Dudley norms of finite signed Borel measures on metric spaces and concepts related to it. Both norms are defined as the supremum of a convex functional on a closed unit ball in a space of bounded Lipschitz functions. Since this supremum is attained at an extreme point, we first study extreme points. We characterize a dense subset of the extreme points of the closed unit ball in the space of bounded Lipschitz functions equipped with the norm k · kBL := k · k? + | · |L, for any underlying connected metric space S. This is a novel result. Until now, a characterization was only known for the norm k · kFM := max(k · k?, | · |L) or for the very specific space S = [0, 1]. After that, we derive expressions for Fortet-Mourier distances between finite positive measures ? and µ, with ? a positive linear combination of Dirac measures. We give an explicit expression for the Fortet-Mourier distance between a Dirac measure...Show moreThis master thesis is dedicated to the computation of Fortet-Mourier and Dudley norms of finite signed Borel measures on metric spaces and concepts related to it. Both norms are defined as the supremum of a convex functional on a closed unit ball in a space of bounded Lipschitz functions. Since this supremum is attained at an extreme point, we first study extreme points. We characterize a dense subset of the extreme points of the closed unit ball in the space of bounded Lipschitz functions equipped with the norm k · kBL := k · k? + | · |L, for any underlying connected metric space S. This is a novel result. Until now, a characterization was only known for the norm k · kFM := max(k · k?, | · |L) or for the very specific space S = [0, 1]. After that, we derive expressions for Fortet-Mourier distances between finite positive measures ? and µ, with ? a positive linear combination of Dirac measures. We give an explicit expression for the Fortet-Mourier distance between a Dirac measure and any finite positive measure µ. Such an expression was not known in the field before, except for the distance between two Dirac measures. For ? a general positive linear combination of Dirac measures, we prove that the distance to a finite positive measure can be obtained by minimizing a convex functional over a convex and compact subset of R n , where n equals the number of points in the support of ?. We propose efficient numerical methods to approximate the norm. Next, we consider the case in which ? and µ are both a linear combination of Dirac measures. We present highly efficient, exact algorithms to compute the distance between µ and ? in both the Fortet-Mourier and Dudley norm, using linear programming. Up till now, algorithms that achieve this were only known for specific cases: S ? R for the Fortet-Mourier norm, or ?, µ both empirical probability measures for the Dudley norm. Our algorithms generalize substantially: they enable us to compute the distance between any two linear combinations of Dirac measures on any metric space S, in both the Fortet-Mourier and Dudley norm. Finally, we touch upon the topic of approximation theory in a context of measures. We study approximations of finite positive measures by positive measures with a finite support consisting of at most N points. We prove an existence result for the case in which the underlying metric space is compact. For non-compact settings, we study examples and pose a conjectureShow less

Leiden University Student Repository

Documents

In Collections

On the computation of Fortet-Mourier and Dudley distances between measures: Functional analytic expressions and algorithms