The Wasserstein barycenter is an important notion in the analysis of high dimensional data with a broad range of applications in applied probability, economics, statistics, and in particular to clustering and image processing. In this paper, we state a general version of the equivalence of the Wasserstein barycenter problem to the n-coupling problem. As a consequence, the coupling to the sum principle (characterizing solutions to the n-coupling problem) provides a novel criterion for the explicit characterization of barycenters. Based on this criterion, we provide as a main contribution the simple to implement iterative swapping algorithm (ISA) for computing barycenters. The ISA is a completely non-parametric algorithm which provides a sharp image of the support of the barycenter and has a quadratic time complexity which is comparable to other well established algorithms designed to compute barycenters. The algorithm can also be applied to more complex optimization problems like the k-barycenter problem.

On the computation of Wasserstein barycenters / G. Puccetti, L. Ruschendorf, S. Vanduffel. - In: JOURNAL OF MULTIVARIATE ANALYSIS. - ISSN 0047-259X. - 176(2020 Mar).

On the computation of Wasserstein barycenters

G. Puccetti
Primo
;
2020-03

Abstract

The Wasserstein barycenter is an important notion in the analysis of high dimensional data with a broad range of applications in applied probability, economics, statistics, and in particular to clustering and image processing. In this paper, we state a general version of the equivalence of the Wasserstein barycenter problem to the n-coupling problem. As a consequence, the coupling to the sum principle (characterizing solutions to the n-coupling problem) provides a novel criterion for the explicit characterization of barycenters. Based on this criterion, we provide as a main contribution the simple to implement iterative swapping algorithm (ISA) for computing barycenters. The ISA is a completely non-parametric algorithm which provides a sharp image of the support of the barycenter and has a quadratic time complexity which is comparable to other well established algorithms designed to compute barycenters. The algorithm can also be applied to more complex optimization problems like the k-barycenter problem.
Image processing; k-means clustering; Optimal transportation; Swapping algorithm; Wasserstein barycenter
Settore SECS-S/06 - Metodi mat. dell'economia e Scienze Attuariali e Finanziarie
Settore SECS-S/01 - Statistica
Settore MAT/06 - Probabilita' e Statistica Matematica
Article (author)
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0047259X19302544-main.pdf

accesso riservato

Descrizione: JMVA20 articolo finale
Tipologia: Publisher's version/PDF
Dimensione 3.66 MB
Formato Adobe PDF
3.66 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
SSRN-id3276147.pdf

accesso aperto

Descrizione: Preprint
Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 12.56 MB
Formato Adobe PDF
12.56 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/701763
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact