- A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport(arXiv)
Author : Tianyi Lin, Marco Cuturi, Michael I. Jordan
Abstract : Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. Recent works suggest that these estimators are more statistically efficient than plug-in (linear programming-based) OT estimators when comparing probability measures in high-dimensions~citep{Vacher-2021-Dimension}. Unfortunately, that statistical benefit comes at a very steep computational price: because their computation relies on the short-step interior-point method (SSIPM), which comes with a large iteration count in practice, these estimators quickly become intractable w.r.t. sample size n. To scale these estimators to larger n, we propose a nonsmooth fixed-point model for the kernel-based OT problem, and show that it can be efficiently solved via a specialized semismooth Newton (SSN) method: We show, exploring the problem’s structure, that the per-iteration cost of performing one SSN step can be significantly reduced in practice. We prove that our SSN method achieves a global convergence rate of O(1/k−−√), and a local quadratic convergence rate under standard regularity conditions. We show substantial speedups over SSIPM on both synthetic and real datasets
2.A novel Newton method for inverse elastic scattering problems (arXiv)
Author : Yan Chang, Yukun Guo, Hongyu Liu, Deyue Zhang
Abstract : This work is concerned with an inverse elastic scattering problem of identifying the unknown rigid obstacle embedded in an open space filled with a homogeneous and isotropic elastic medium. A Newton-type iteration method relying on the boundary condition is designed to identify the boundary curve of the obstacle. Based on the Helmholtz decomposition and the Fourier-Bessel expansion, we explicitly derive the approximate scattered field and its derivative on each iterative curve. Rigorous mathematical justifications for the proposed method are provided. Numerical examples are presented to verify the effectiveness of the proposed method.
