Importance Sparsification for Sinkhorn Algorithm
Mengyu Li, Jun Yu, Tao Li, Cheng Meng; 24(247):1−44, 2023.
Abstract
The Sinkhorn algorithm is widely used for approximating the solutions to optimal transport (OT) and unbalanced optimal transport (UOT) problems. However, its practical application is hindered by its high computational complexity. To address this issue, we propose a novel method called Spar-Sink, which utilizes importance sparsification to efficiently approximate entropy-regularized OT and UOT solutions. Spar-Sink establishes effective sampling probabilities using natural upper bounds for unknown optimal transport plans and constructs a sparse kernel matrix to accelerate Sinkhorn iterations. This reduces the computational cost of each iteration from $O(n^2)$ to $\\widetilde{O}(n)$ for a sample size of $n$. Theoretical analysis shows that our proposed estimators for regularized OT and UOT problems are consistent under mild regularity conditions. We conduct experiments on various synthetic data, which demonstrate that Spar-Sink outperforms mainstream competitors in terms of both estimation error and speed. Additionally, we apply Spar-Sink to analyze real-world echocardiogram data, effectively estimating and visualizing cardiac cycles. This enables the identification of heart failure and arrhythmia. To evaluate the numerical accuracy of cardiac cycle prediction, we consider the task of predicting the end-systole time point using the end-diastole one. Results show that Spar-Sink performs as well as the classical Sinkhorn algorithm while requiring significantly less computational time.
[abs]