ICASSP2022 “Block-coordinate Frank-Wolfe algorithm for semi-relaxed OT”
5月22日から27日にシンガポールで開催される信号処理分野・トップ会議 IEEE 47th International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2022 に1件の研究論文が採択されました．
Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed OT problem
- Authors: T. Fukunaga (M1, 1st-year graduate student) and HK
- Abstract: Optimal transport (OT), which provides a distance between two probability distributions by considering their spatial locations, has been applied to widely diverse applications. Computing an OT problem requires a solution of linear programming with tight mass-conservation constraints. This requirement hinders its application to large-scale problems. To alleviate this issue, the recently proposed relaxed-OT approach uses a faster algorithm by relaxing such constraints. Its effectiveness for practical applications has been demonstrated. Nevertheless, it still exhibits slow convergence. To this end, addressing a convex semi-relaxed OT, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm, which gives sparse solutions. Specifically, we provide their upper bounds of the worst convergence iterations and equivalence between the linearization duality gap and the Lagrangian duality gap. Three fast variants of the proposed BCFW are also proposed. Numerical evaluations in the color transfer problem demonstrate that the proposed algorithms outperform state-of-the-art algorithms across different settings.
- Paper: Publisher’s website, arXiv preprint arXiv:2205.13766
- Code: GitHub.
Conference information: IEEE ICASSP
- Google Scholar Metric H5-index: 96（checked on Jan. 25, 2022)