Optimal transportation for electrical impedance tomography
HTML articles powered by AMS MathViewer
- by Gang Bao and Yixuan Zhang;
- Math. Comp. 93 (2024), 2361-2389
- 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).
Bibliographic Information
- Gang Bao
- Affiliation: School of Mathematical Sciences, Zhejiang University, Hangzhou 310027, People’s Republic of China
- Email: baog@zju.edu.cn
- Yixuan Zhang
- Affiliation: School of Mathematical Sciences, Zhejiang University, Hangzhou 310027, People’s Republic of China
- ORCID: 0009-0004-0032-7916
- Email: 11935010@zju.edu.cn
- Received by editor(s): October 20, 2022
- Received by editor(s) in revised form: August 2, 2023, and September 19, 2023
- Published electronically: November 13, 2023
- Additional Notes: This work was supported in part by National Natural Science Foundation of China (11621101; U21A20425) and a Key Laboratory of Zhejiang Province.
- © Copyright 2023 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 2361-2389
- MSC (2020): Primary 49Q20, 35R30, 65M32
- DOI: https://doi.org/10.1090/mcom/3919
- MathSciNet review: 4759378