Approximating Optimal Transport via Low-rank and Sparse Factorization
arXiv:2111.06546
Abstract
Optimal transport (OT) naturally arises in a wide range of machine learning applications but may often become the computational bottleneck. Recently, one line of works propose to solve OT approximately by searching the \emph{transport plan} in a low-rank subspace. However, the optimal transport plan is often not low-rank, which tends to yield large approximation errors. For example, when Monge's \emph{transport map} exists, the transport plan is full rank. This paper concerns the computation of the OT distance with adequate accuracy and efficiency. A novel approximation for OT is proposed, in which the transport plan can be decomposed into the sum of a low-rank matrix and a sparse one. We theoretically analyze the approximation error. An augmented Lagrangian method is then designed to efficiently calculate the transport plan.
References in corpus (5)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Gromov-Wasserstein Learning for Graph Matching and Node Embedding
- Statistical Optimal Transport via Factored Couplings
- Massively scalable Sinkhorn distances via the Nyström method
- Linear Time Sinkhorn Divergences using Positive Features