# On Robust Optimal Transport: Computational Complexity and Barycenter Computation

Source: [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](<https://www.sota2.com/research/paper/68fa58a61e209131ce9b0175>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T15:27:32.438Z

Authors: Khang Le, Huy Nguyen, Quang Nguyen, Tung Pham, Hung Bui, Nhat Ho

Published: 2021-02-13T03:55:52.000Z

## Abstract

We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibler divergence. We show that Sinkhorn-based algorithms can approximate the optimal cost of robust optimal transport in $\\widetilde{\\mathcal{O}}(\\frac{n^2}{\\varepsilon})$ time, in which $n$ is the number of supports of the probability distributions and $\\varepsilon$ is the desired error. Furthermore, we investigate a fixed-support robust barycenter problem between $m$ discrete probability distributions with at most $n$ number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case $m = 2$, we show that this algorithm can approximate the optimal barycenter value in $\\widetilde{\\mathcal{O}}(\\frac{mn^2}{\\varepsilon})$ time, thus being better than the previous complexity $\\widetilde{\\mathcal{O}}(\\frac{mn^2}{\\varepsilon^2})$ of the IBP algorithm for approximating the Wasserstein barycenter.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [ED Time Point Prediction on Echocardiogram 100 videos](<https://www.sota2.com/research/sota/ed-time-point-prediction-on-echocardiogram-100-videos.md>): ED time point prediction; Echocardiogram 100 videos; Prediction Error: 43.

- [ED time point prediction on Echocardiogram videos 100 randomly selected (test)](<https://www.sota2.com/research/sota/ed-time-point-prediction-on-echocardiogram-videos-100-randomly-selected-test.md>): ED time point prediction; Echocardiogram videos 100 randomly selected (test); Error: 0.33.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2102.06857>)

[PDF](<https://arxiv.org/pdf/2102.06857.pdf>)