Safe Screening for ℓ2-penalized Unbalanced Optimal Transport Problem

Optimal Transport (OT) has emerged as an effective metric in machine learning. However, its application to large-scale problems remains limited due to stringent usage conditions and significant computational complexity. Unbalanced Optimal Transport (UOT) is rapidly gaining attention by expanding the scope of its use through the relaxation of the original problem. Observing a recent connection between the UOT problem and the Lasso problem, this paper introduces safe screening—a technique prevalent in the Lasso community—to the UOT domain. Safe screening can significantly reduce computational time by identifying and disregarding zero elements in the sparse solution of the UOT problem. This represents the first successful application of the safe screening technique to the ℓ
2
penalized UOT problem. Addressing the specific structure of the constraint matrix in the UOT problem, a new projection method, and a cruciform two-hyperplane safe region construction method are proposed. Numerical evaluations of synthetic and real-world datasets demonstrate the extraordinary effectiveness of our proposed safe screening method without markedly increasing the computational burden.