Mediane di Wasserstein: teoria e algoritmi.

The concepts of mean and median admit a very simple variational formulation: the weighted average of a sample of N points in Rd is the only point in Rd that minimizes the sum of the squared (weighted) distances with all the points in the sample. Minimizing the sum of the weighted distances we obtain a notion of weighted median, which in literature is commonly known as Torricelli point, Fermat-Weber point or Geometric median. These definitions can be generalized to any metric space (cf. Fréchet means) as noted in the pioneering work of G. Carlier and M. Agueh, where the concept of Wasserstein's mean is introduced for probability measures with respect to the metric W2 and the main properties of existence, uniqueness and regularity are discussed. In this thesis we introduce and discuss the concept of the Wasserstein median, that is a probability measure (with finite first moment) that minimizes the sum of the (weighted) W1 distances from a sample of N probability measures in P1(Rd). We show that the breakdown point of Wasserstein medians is 0.5, as for the geometric medians, providing a proof that works for any Fréchet median. This makes the Wasserstein median a location estimator robust to outliers. The gain in terms of robustness is however contrasted with important losses in terms of regularity and uniqueness, which however trigger new interesting challenges, such as: the selection of absolutely continuous medians or medians with good interpolation properties. We discuss this issues in dimension one, providing explicit constructions of medians that meet the above requirements. We also discuss further different formulations of the Wasserstein median problem. We prove the equivalence with a dual problem, from which we obtain a set of optimality conditions. The multi-marginal formulation, on the other hand, highlights a strong link with geometric medians, and allows us to find important consistency results. Furthermore, this formulation provides, in a discrete setting, a linear programming problem that can be easily implemented with generic linear optimization solvers. As a last equivalent formulation of the median problem we introduce and analyze the Beckmann Minimal flow formulation. This dynamic formulation of the problem allows to characterize the Wasserstein Medians, the optimal potentials of the dual problem, and the optimal solutions to the Beckmann problem as solutions of a Monge-Kantorovich PDE system. We also provide a variational approximation of the Monge-Kantorovich problem, whose solutions solve a system of PDEs with q-Laplacian operators with obstacle-like and Neumann constraints, and we prove that the solutions of the approximate problem converge when q tends to infinity to solutions of Beckmann's problem. In a discrete setting, this formulation takes the form of a minimum cost flow problem, which some numerical methods developed for this specific problem solve in a very efficient way. Finally, in order to meet the aforementioned selection requirements, we propose to select a Wasserstein median as a solution to a further variational problem. Which, in analogy with the classical transportation theory, we call the secondary variational problem. We provide a variational approximation of the secondary problem and prove a linear convergence rate. With a numerical example we show that the solutions of the secondary variational problem have good interpolation properties. Finally we present the numerical methods used in the examples illustrated in the thesis: Sinkhorn, Network Flow formulations of the problem, and a Lagrangian approach. We close with a practical example on a real dataset.

I concetti di media e mediana ammettono una formulazione variazionale molto semplice: la media ponderata di un campione di N punti in Rd e l'unico punto in Rd che minimizza la somma delle distanze al quadrato (pesate) con tutti i punti del campione. Minimizzando invece la somma delle distanze pesate si ottiene una nozione di mediana pesata, che in letteratura prende comunemente il nome di punto di Torricelli, punto di Fermat-Weber o Mediana Geometrica. Tali definizioni possono essere generalizzate su qualsiasi spazio metrico (cfr. medie di Fréchet) come osservato nel pionieristico lavoro di G. Carlier e M. Agueh, dove si introduce il concetto di Baricentro di Wasserstein per misure di probabilità rispetto la metrica W2 e sono discusse le principali proprietà di esistenza, unicità e regolarità. Nella tesi, seguito da G. Carlier e S. Gualandi, introduciamo e discutiamo il concetto di mediana di Wasserstein, ovvero una misura di probabilità a momento primo finito che minimizza la somma delle distanze W1 (pesate) da un campione di N misure in P1(Rd). Dimostriamo che il breakdown point delle Wasserstein Medians è di 0.5, come per le mediane geometriche, fornendo una prova che può adattarsi ad ogni mediana di Fréchet. Il che rende le mediane di Wasserstein uno stimatore di centralità robusto agli outliers. Il guadagno in termini di robustezza è tuttavia contrapposto a delle importanti perdite in termini di regolarità e unicità, che però offrono interessanti sfide da risolvere come la selezione di mediane assolutamente continue o di mediane con buone proprietà interpolatorie. Discutiamo il problema in dimensione uno, fornendo delle costruzioni esplicite di mediane che rispettano i requisiti suddetti. Discutiamo inoltre ulteriori diverse formulazioni del problema delle mediane di Wasserstein. Proviamo l'equivalenza con un problema duale, da cui otteniamo delle condizioni di ottimalità. La formulazione multi-marginale invece, mette in luce un forte legame con le mediane geometriche, e permette di trovare degli importanti risultati di consistenza con il problema delle mediane in Rd. Inoltre, tale formulazione fornisce, nel discreto, un problema di programmazione lineare facilmente implementabile con generici solver di ottimizzazione lineare. Come ultima formulazione equivalente del problema delle mediane abbiamo introdotto e analizzato la Beckmann Minimal flow formulation. Tale formulazione dinamica del problema permette di caratterizzare le Mediane di Wasserstein, i potenziali ottimali del problema duale, e le soluzioni ottimale del problema di Beckmann come soluzioni di un sistema di PDE di tipo Monge-Kantorovich. Abbiamo inoltre fornito un'approssimazione variazionale del problema di Monge-Kantorovich, le cui soluzioni risolvono un sistema di PDEs con operatori di tipo q-Laplaciano e vincoli di tipo ostacolo e Neumann e provato che le soluzioni del problema approssimato convergono al tendere di q all'infinito a soluzioni del problema di Beckmann. Nel discreto tale formulazione si declina in problema di flusso di costo minimo, che alcuni metodi numerici sviluppati per questo tipo di problema specifico risolvono in modo molto efficiente. Infine, per rispondere ai requisiti di selezione di mediane suddetti proponiamo di selezionare una mediana di Wasserstein come soluzione di un ulteriore problema variazionale. Che, in analogia con la teoria del trasporto classica, chiamiamo problema variazionale secondario. Forniamo un'approssimazione variazionale del problema secondario facile da computare e dimostriamo un tasso di convergenza lineare. Con un esempio numerico mostriamo che le soluzioni del problema secondario hanno buone proprietà di interpolazione. Infine presentiamo i metodi numerici utilizzati negli esempi illustrati nella tesi: Sinkhorn, formulazioni Network Flow del problema, e un approccio lagrangiano. Chiudiamo con un esempio pratico su un dataset reale.