Approximating Optimal Transport via Low-rank and Sparse Factorization
This addresses the efficiency and accuracy challenges of optimal transport for machine learning practitioners, offering a method that balances computational speed with reduced approximation errors compared to purely low-rank approaches.
The paper tackles the computational bottleneck of optimal transport in machine learning by proposing a novel approximation that decomposes the transport plan into a low-rank matrix plus a sparse matrix, theoretically analyzing the error and designing an efficient augmented Lagrangian method for computation.
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.