Concept

Transportation theory (mathematics)

Related publications (22)

Reliable data-driven decision-making through optimal transport

Decision-making permeates every aspect of human and societal development, from individuals' daily choices to the complex decisions made by communities and institutions. Central to effective decision-making is the discipline of optimization, which seeks th ...

EPFL2024

On distributional autoregression and iterated transportation

Victor Panaretos, Laya Ghodrati

We consider the problem of defining and fitting models of autoregressive time series of probability distributions on a compact interval of Double-struck capital R. An order-1 autoregressive model in this context is to be understood as a Markov chain, where ...

Wiley2024

Multi-Frequency Tracking via Group-Sparse Optimal Transport

Isabel Haasler

In this letter, we introduce an optimal transport framework for inferring power distributions over both spatial location and temporal frequency. Recently, it has been shown that optimal transport is a powerful tool for estimating spatial spectra that chang ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport

Isabel Haasler

In this work, we develop a new framework for dynamic network flow pro-blems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where t ...

2023

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

Axel Elie Joseph Séguin

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

EPFL2023

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

SIAM Publications2023

Graph Representation Learning with Optimal Transport: Analysis and Applications

Effrosyni Simou

In several machine learning settings, the data of interest are well described by graphs. Examples include data pertaining to transportation networks or social networks. Further, biological data, such as proteins or molecules, lend themselves well to graph- ...

EPFL2022

Learning to Align Sequential Actions in the Wild

Pascal Fua, Bugra Tekin, Weizhe Liu

State-of-the-art methods for self-supervised sequential action alignment rely on deep networks that find correspon- dences across videos in time. They either learn frame-to- frame mapping across sequences, which does not leverage temporal information, or a ...

IEEE COMPUTER SOC2022

fGOT: Graph Distances Based on Filters and Optimal Transport

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, ...

2023

Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case

Valentin Hartmann

We consider the problem of finding an optimal transport plan between an absolutely continuous measure and a finitely supported measure of the same total mass when the transport cost is the unsquared Euclidean distance. We may think of this problem as close ...

SPRINGER HEIDELBERG2020

Forward-Backward Splitting for Optimal Transport Based Problems

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Guillermo Ortiz Jimenez, Effrosyni Simou

Optimal transport aims to estimate a transportation plan that minimizes a displacement cost. This is realized by optimizing the scalar product between the sought plan and the given cost, over the space of doubly stochastic matrices. When the entropy regula ...

IEEE2020

Procrustes Metrics and Optimal Transport for Covariance Operators

Valentina Masarotto

Covariance operators play a fundamental role in functional data analysis, providing the canonical means to analyse functional variation via the celebrated Karhunen-Loève expansion. These operators may themselves be subject to variation, for instance in con ...

EPFL2019

Procrustes Metrics on Covariance Operators and Optimal Transportation of Gaussian Processes

Victor Panaretos, Yoav Zemel, Valentina Masarotto

Covariance operators are fundamental in functional data analysis, providing the canonical means to analyse functional variation via the celebrated Karhunen-Loeve expansion. These operators may themselves be subject to variation, for instance in contexts wh ...

2019

GOT: An Optimal Transport framework for Graph comparison

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Fréchet means in Wasserstein space : theory and algorithms

Yoav Zemel

This work studies the problem of statistical inference for Fréchet means in the Wasserstein space of measures on Euclidean spaces,

\mathcal W_2 ( \mathbb R^d )

. This question arises naturally from the problem of separating amplitude and phase variation i ...

EPFL2017

An Alternating Trust Region Algorithm for Distributed Linearly Constrained Nonlinear Programs, Application to the Optimal Power Flow Problem

Colin Neil Jones, Jean-Hubert Hours

A novel trust region method for solving linearly constrained nonlinear programs is presented. The proposed technique is amenable to a distributed implementation, as its salient ingredient is an alternating projected gradient sweep in place of the Cauchy po ...

2017

Fabrication-Aware Design with Performative Criteria

Yuliy Gennadievich Schwartzburg

Artists and architects often need to handle multiple constraints during design of physical constructions. We define a performative constraint as any constraint on design that is tied to the performance of the model--either during fabrication, construction, ...

EPFL2015

Kantorovich distance in the martingale CLT and quantitative homogenization of parabolic equations with random coefficients

Jean-Christophe Mourrat

The article begins with a quantitative version of the martingale central limit theorem, in terms of the Kantorovich distance. This result is then used in the study of the homogenization of discrete parabolic equations with random i.i.d. coefficients. For s ...

Springer Heidelberg2014

High-contrast Computational Caustic Design

Mark Pauly, Yuliy Gennadievich Schwartzburg, Andrea Tagliasacchi, Romain Pierre Testuz

We present a new algorithm for computational caustic design. Our algorithm solves for the shape of a transparent object such that the refracted light paints a desired caustic image on a receiver screen. We introduce an optimal transport formulation to esta ...

ACM2014