Optimal transportation for electrical impedance tomography

Bao, Gang; Zhang, Yixuan

doi:10.1090/mcom/3919

Optimal transportation for electrical impedance tomography
HTML articles powered by AMS MathViewer

by Gang Bao and Yixuan Zhang

Math. Comp.

DOI: https://doi.org/10.1090/mcom/3919

Published electronically: November 13, 2023

HTML | PDF | Request permission

Abstract:

This work establishes a framework for solving inverse boundary problems with the geodesic-based quadratic Wasserstein distance ($W_{2}$). A general form of the Fréchet gradient is systematically derived from the optimal transportation (OT) theory. In addition, a fast algorithm based on the new formulation of OT on $\mathbb {S}^{1}$ is developed to solve the corresponding optimal transport problem. The computational complexity of the algorithm is reduced to $O(N)$ from $O(N^{3})$ of the traditional method. Combining with the adjoint-state method, this framework provides a new computational approach for solving the challenging electrical impedance tomography problem. Numerical examples are presented to illustrate the effectiveness of our method.

References

I. Abraham, R. Abraham, M. Bergounioux, and G. Carlier, Tomographic reconstruction from a few views: a multi-marginal optimal transport approach, Appl. Math. Optim. 75 (2017), no. 1, 55–73. MR 3600390, DOI 10.1007/s00245-015-9323-3
A. Adler and D. Holder, Electrical Impedance Tomography: Methods, History and Applications, CRC Press, 2021.
Luigi Ambrosio and Nicola Gigli, A user’s guide to optimal transport, Modelling and optimisation of flows on networks, Lecture Notes in Math., vol. 2062, Springer, Heidelberg, 2013, pp. 1–155. MR 3050280, DOI 10.1007/978-3-642-32160-3_{1}
Gang Bao, Peijun Li, Junshan Lin, and Faouzi Triki, Inverse scattering problems with multi-frequencies, Inverse Problems 31 (2015), no. 9, 093001, 21. MR 3401991, DOI 10.1088/0266-5611/31/9/093001
Gang Bao, Xiaojing Ye, Yaohua Zang, and Haomin Zhou, Numerical solution of inverse problems by weak adversarial networks, Inverse Problems 36 (2020), no. 11, 115003, 31. MR 4173578, DOI 10.1088/1361-6420/abb447
Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math. 84 (2000), no. 3, 375–393. MR 1738163, DOI 10.1007/s002110050002
Jean-David Benamou, Brittany D. Froese, and Adam M. Oberman, Numerical solution of the optimal transportation problem using the Monge-Ampère equation, J. Comput. Phys. 260 (2014), 107–126. MR 3151832, DOI 10.1016/j.jcp.2013.12.015
D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Vol. 6, Belmont, MA, Athena Scientific, 1997.
Liliana Borcea, Electrical impedance tomography, Inverse Problems 18 (2002), no. 6, R99–R136. MR 1955896, DOI 10.1088/0266-5611/18/6/201
Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575, DOI 10.1017/CBO9780511804441
Yann Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (1991), no. 4, 375–417. MR 1100809, DOI 10.1002/cpa.3160440402
Luis A. Caffarelli, Boundary regularity of maps with convex potentials. II, Ann. of Math. (2) 144 (1996), no. 3, 453–496. MR 1426885, DOI 10.2307/2118564
Alberto P. Calderón, On an inverse boundary value problem, Comput. Appl. Math. 25 (2006), no. 2-3, 133–138. MR 2321646, DOI 10.1590/S0101-82052006000200002
Jing Chen, Yifan Chen, Hao Wu, and Dinghui Yang, The quadratic Wasserstein metric for earthquake location, J. Comput. Phys. 373 (2018), 188–209. MR 3854142, DOI 10.1016/j.jcp.2018.06.066
Margaret Cheney, David Isaacson, and Jonathan C. Newell, Electrical impedance tomography, SIAM Rev. 41 (1999), no. 1, 85–101. MR 1669729, DOI 10.1137/S0036144598333613
M. Cheney, D. Isaacson, J. C. Newell, S. Simske, and J. Goble, NOSER: An algorithm for solving the inverse conductivity problem, Int. J. Imaging Syst. Technol. 2 (1990), no. 2, 66–75.
Eric T. Chung, Tony F. Chan, and Xue-Cheng Tai, Electrical impedance tomography using level set representation and total variational regularization, J. Comput. Phys. 205 (2005), no. 1, 357–372. MR 2132313, DOI 10.1016/j.jcp.2004.11.022
M. Cuturi, Sinkhorn distances: lightspeed computation of optimal transport, 26 (2013).
Julie Delon, Julien Salomon, and Andrei Sobolevski, Fast transport optimization for Monge costs on the circle, SIAM J. Appl. Math. 70 (2010), no. 7, 2239–2258. MR 2678036, DOI 10.1137/090772708
Björn Engquist and Brittany D. Froese, Application of the Wasserstein metric to seismic signals, Commun. Math. Sci. 12 (2014), no. 5, 979–988. MR 3187785, DOI 10.4310/CMS.2014.v12.n5.a7
Björn Engquist, Kui Ren, and Yunan Yang, The quadratic Wasserstein metric for inverse data matching, Inverse Problems 36 (2020), no. 5, 055001, 23. MR 4105314, DOI 10.1088/1361-6420/ab7e04
Björn Engquist and Yunan Yang, Optimal transport based seismic inversion: beyond cycle skipping, Comm. Pure Appl. Math. 75 (2022), no. 10, 2201–2244. MR 4491871, DOI 10.1002/cpa.21990
Yuwei Fan and Lexing Ying, Solving electrical impedance tomography with deep learning, J. Comput. Phys. 404 (2020), 109119, 19. MR 4044725, DOI 10.1016/j.jcp.2019.109119
Alessio Figalli and Cédric Villani, Optimal transport and curvature, Nonlinear PDE’s and applications, Lecture Notes in Math., vol. 2028, Springer, Heidelberg, 2011, pp. 171–217. MR 2883682, DOI 10.1007/978-3-642-21861-3_{4}
T. Glimm and V. Oliker, Optical design of single reflector systems and the Monge-Kantorovich mass transfer problem, J. Math. Sci. (N.Y.) 117 (2003), no. 3, 4096–4108. Nonlinear problems and function theory. MR 2027449, DOI 10.1023/A:1024856201493
Howard Heaton, Samy Wu Fung, Alex Tong Lin, Stanley Osher, and Wotao Yin, Wasserstein-based projections with applications to inverse problems, SIAM J. Math. Data Sci. 4 (2022), no. 2, 581–603. MR 4417000, DOI 10.1137/20M1376790
S. Haker, L. Zhu, A. Tannenbaum, et al, Optimal mass transport for registration and warping, Int. J. Comput. Vis. 60 (2004), no. 3, 225–240.
D. Isaacson, Distinguishability of conductivities by electric current computed tomography, IEEE Trans. Med. Imaging 5 (1986), no. 2, 91–95.
Bangti Jin, Taufiquar Khan, and Peter Maass, A reconstruction algorithm for electrical impedance tomography based on sparsity regularization, Internat. J. Numer. Methods Engrg. 89 (2012), no. 3, 337–353. MR 2876564, DOI 10.1002/nme.3247
L. V. Kantorovich, Mathematical methods of organizing and planning production, Management Sci. 6 (1959/60), 366–422. MR 129016, DOI 10.1287/mnsc.6.4.366
Ian Knowles, A variational algorithm for electrical impedance tomography, Inverse Problems 14 (1998), no. 6, 1513–1525. MR 1662464, DOI 10.1088/0266-5611/14/6/010
Robert V. Kohn and Alan McKenney, Numerical implementation of a variational method for electrical impedance tomography, Inverse Problems 6 (1990), no. 3, 389–414. MR 1057033, DOI 10.1088/0266-5611/6/3/009
Anders Logg, Automating the finite element method, Arch. Comput. Methods Eng. 14 (2007), no. 2, 93–138. MR 2339914, DOI 10.1007/s11831-007-9003-9
Robert J. McCann, Polar factorization of maps on Riemannian manifolds, Geom. Funct. Anal. 11 (2001), no. 3, 589–608. MR 1844080, DOI 10.1007/PL00001679
L. Métivier, R. Brossier, Q. Mérigot, and E. Oudet, A graph space optimal transport distance as a generalization of $L^p$ distances: application to a seismic imaging inverse problem, Inverse Problems 35 (2019), no. 8, 085001, 49. MR 3987717, DOI 10.1088/1361-6420/ab206f
L. Métivier, R. Brossier, Q. Mérigot, E. Oudet, and J. Virieux, An optimal transport approach for seismic tomography: application to 3D full waveform inversion, Inverse Problems 32 (2016), no. 11, 115008, 36. MR 3627047, DOI 10.1088/0266-5611/32/11/115008
G. Monge, Mémoire sur la théorie des déblais et des remblais, Mem. Math. Phys. Acad. Royale Sci. (1781), 666–704.
J. W. Neuberger, Sobolev gradients and differential equations, 2nd ed., Lecture Notes in Mathematics, vol. 1670, Springer-Verlag, Berlin, 2010. MR 2573187, DOI 10.1007/978-3-642-04041-2
G. Peyré and M. Cuturi, Computational optimal transport: With applications to data science, Foundations and Trends® in Machine Learning 11 (2019), 5-6, 355–607.
Rémi Peyre, Comparison between $\rm W_2$ distance and $\dot \textrm {H}^{-1}$ norm, and localization of Wasserstein distance, ESAIM Control Optim. Calc. Var. 24 (2018), no. 4, 1489–1501. MR 3922440, DOI 10.1051/cocv/2017050
R. E. Plessix, A review of the adjoint-state method for computing the gradient of a functional with geophysical applications, Geophys. J. Int. 167 (2006), no. 2, 495–503.
Julien Rabin, Julie Delon, and Yann Gousseau, Transportation distances on the circle, J. Math. Imaging Vision 41 (2011), no. 1-2, 147–167. MR 2824152, DOI 10.1007/s10851-011-0284-0
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 274683, DOI 10.1515/9781400873173
Luca Rondi and Fadil Santosa, Enhanced electrical impedance tomography via the Mumford-Shah functional, ESAIM Control Optim. Calc. Var. 6 (2001), 517–538. MR 1849414, DOI 10.1051/cocv:2001121
Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
J. Solomon, F. De Goes, G. Peyré, M. Cuturi et al, Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Trans. Graphics (ToG) 34 (2015), no. 4, 1–11.
G. Uhlmann, Electrical impedance tomography and Calderón’s problem, Inverse Problems 25 (2009), no. 12, 123011, 39. MR 3460047, DOI 10.1088/0266-5611/25/12/123011
Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9
Xu-Jia Wang, On the design of a reflector antenna. II, Calc. Var. Partial Differential Equations 20 (2004), no. 3, 329–341. MR 2062947, DOI 10.1007/s00526-003-0239-4
A. Wexler, B. Fry, and M. R. Neuman, Impedance-computed tomography algorithm and system, Appl. Optics 24 (1985), no. 23, 3985–3992.
Stephen J. Wright, Robert D. Nowak, and Mário A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process. 57 (2009), no. 7, 2479–2493. MR 2650165, DOI 10.1109/TSP.2009.2016892
Y. Yang, B. Engquist, J. Sun, and B. F. Hamfeldt, Application of optimal transport and the quadratic Wasserstein metric to full-waveform inversion, Geophysics 83 (2018), no. 1, R43–R62.
D. T. Zhou, J. Chen, H. Wu, D. H. Yang, and L. Y. Qiu, The Wasserstein-Fisher-Rao metric for waveform based earthquake location, arXiv preprint arXiv:1812.00304 (2018).