×

A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization. (English) Zbl 07698612

Summary: We develop a dynamic generalized conditional gradient method (DGCG) for dynamic inverse problems with optimal transport regularization. We consider the framework introduced in Bredies and Fanzon (ESAIM: M2AN 54:2351-2382, 2020), where the objective functional is comprised of a fidelity term, penalizing the pointwise in time discrepancy between the observation and the unknown in time-varying Hilbert spaces, and a regularizer keeping track of the dynamics, given by the Benamou-Brenier energy constrained via the homogeneous continuity equation. Employing the characterization of the extremal points of the Benamou-Brenier energy (Bredies et al. in Bull Lond Math Soc 53(5):1436-1452, 2021), we define the atoms of the problem as measures concentrated on absolutely continuous curves in the domain. We propose a dynamic generalization of a conditional gradient method that consists of iteratively adding suitably chosen atoms to the current sparse iterate, and subsequently optimizing the coefficients in the resulting linear combination. We prove that the method converges with a sublinear rate to a minimizer of the objective functional. Additionally, we propose heuristic strategies and acceleration steps that allow to implement the algorithm efficiently. Finally, we provide numerical examples that demonstrate the effectiveness of our algorithm and model in reconstructing heavily undersampled dynamic data, together with the presence of noise.

MSC:

65K10 Numerical optimization and variational techniques
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
90C49 Extreme-point and pivoting methods
28A33 Spaces of measures, convergence of measures
35F05 Linear first-order PDEs

Software:

CVXOPT

References:

[1] Alberti, GS; Ammari, H.; Romero, F.; Wintz, T., Dynamic spike superresolution and applications to ultrafast ultrasound imaging, SIAM Journal on Imaging Sciences, 12, 3, 1501-1527 (2019) · Zbl 1439.65236
[2] Aliprantis, CD; Border, K., Infinite Dimensional Analysis (2006), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1156.46001
[3] Ambrosio, L.; Fusco, N.; Pallara, D., Functions of Bounded Variation and Free Discontinuity Problems (2000), Oxford: Oxford University Press, Oxford · Zbl 0957.49001
[4] Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Birkhäuser, Basel (2005) · Zbl 1090.35002
[5] Andersen, M.S., Dahl, J., Vandenberghe, L.: CVXOPT: A Python package for convex optimization, version 1.1.5. Available at: https://cvxopt.org/
[6] Andersen, MS; Dahl, J.; Liu, Z.; Vandenberghe, L.; Sra, S.; Nowozin, S.; Wright, SJ, Interior-point methods for large-scale cone programming, Optimization for Machine Learning, 55-83 (2012), Cambridge, Massachusetts: MIT Press, Cambridge, Massachusetts
[7] Bach, F., Duality between subgradient and conditional gradient methods, SIAM Journal on Optimization, 25, 1, 115-129 (2015) · Zbl 1358.90155
[8] Benamou, J-D; Brenier, Y., A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numerische Mathematik, 84, 3, 375-393 (2000) · Zbl 0968.76069
[9] Bonnet, S.; Koenig, A.; Roux, S.; Hugonnard, P.; Guillemaud, R.; Grangeat, P., Dynamic X-ray computed tomography, Proceedings of the IEEE, 91, 10, 1574-1587 (2003)
[10] Boyd, N.; Schiebinger, G.; Recht, B., The alternating descent conditional gradient method for sparse inverse problems, SIAM Journal on Optimization, 27, 2, 616-639 (2017) · Zbl 1365.90195
[11] Boyer, C.; Chambolle, A.; Castro, YD; Duval, V.; de Gournay, F.; Weiss, P., On representer theorems and convex regularization, SIAM Journal on Optimization, 29, 2, 1260-1281 (2019) · Zbl 1423.49036
[12] Bredies, K., Carioni, M., Fanzon, S.: A superposition principle for the inhomogeneous continuity equation with Hellinger-Kantorovich-regular coefficients. arXiv e-prints (2020) arXiv:2007.06964 · Zbl 1518.35226
[13] Bredies, K., Carioni, M., Fanzon, S., Walter, D.: Linear convergence of accelerated generalized conditional gradient methods. arXiv e-prints (2021) arXiv:2110.06756
[14] Bredies, K.; Carioni, M., Sparsity of solutions for variational inverse problems with finite-dimensional data, Calculus of Variations and Partial Differential Equations, 59, 1, 14 (2020) · Zbl 1430.49036
[15] Bredies, K.; Fanzon, S., An optimal transport approach for solving dynamic inverse problems in spaces of measures, ESAIM: Mathematical Modelling and Numerical Analysis, 54, 6, 2351-2382 (2020) · Zbl 07357930
[16] Bredies, K.; Lorenz, D., Mathematical Image Processing (2018), Basel: Birkhäuser, Basel · Zbl 1418.94001
[17] Bredies, K.; Lorenz, DA, Iterated hard shrinkage for minimization problems with sparsity constraints, SIAM Journal on Scientific Computing, 30, 2, 657-683 (2008) · Zbl 1170.46067
[18] Bredies, K.; Pikkarainen, HK, Inverse problems in spaces of measures, ESAIM: Control, Optimisation and Calculus of Variations, 19, 1, 190-218 (2013) · Zbl 1266.65083
[19] Bredies, K.; Lorenz, DA; Maass, P., A generalized conditional gradient method and its connection to an iterative shrinkage method, Computational Optimization and Applications, 42, 2, 173-193 (2009) · Zbl 1179.90326
[20] Bredies, K., Carioni, M., Fanzon, S., Romero, F.: On the extremal points of the ball of the Benamou-Brenier energy. Bulletin of the London Mathematical Society 53(5), 1436-1452 (2021) · Zbl 1505.49036
[21] Burger, M., Dirks, H., Frerking, L., Hauptmann, A., Helin, T., Siltanen, S.: A variational reconstruction method for undersampled dynamic X-ray tomography based on physical motion models. Inverse Problems 33(12), 124008 (2017) · Zbl 1381.92041
[22] Candès, EJ; Romberg, JK; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[23] Candès, EJ; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Communications on Pure and Applied Mathematics, 67, 6, 906-956 (2014) · Zbl 1350.94011
[24] Chizat, L., Peyré, G., Schmitzer, B., Vialard, F.-X.: An interpolating distance between optimal transport and Fisher-Rao metrics. Foundations of Computational Mathematics 18(1), 1-44 (2018) · Zbl 1385.49031
[25] Clarkson, KL, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, ACM Transactions on Algorithms, 6, 4, 63 (2010) · Zbl 1300.90026
[26] Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Modeling & Simulation, 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[27] Dacorogna, B., Direct Methods in the Calculus of Variations, Applied Mathematical Sciences (2008), New York: Springer, New York · Zbl 1140.49001
[28] Daubechies, I.; Defrise, M.; De Mol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57, 11, 1413-1457 (2004) · Zbl 1077.65055
[29] de Castro, Y.; Gamboa, F., Exact reconstruction using Beurling minimal extrapolation, Journal of Mathematical Analysis and Applications, 395, 1, 336-354 (2012) · Zbl 1302.94019
[30] Denoyelle, Q., Duval, V., Peyré, G., Soubies, E.: The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy. Inverse Problems 36(1), 014001 (2019) · Zbl 1434.65082
[31] Diestel, J.; Uhl, JJ, Vector Measures (1977), Providence: American Mathematical Society, Providence · Zbl 0369.46039
[32] Ding, Q., Burger, M., Zhang, X.: Dynamic SPECT reconstruction with temporal edge correlation. Inverse Problems 34(1), 014005 (2017) · Zbl 1437.92070
[33] Dunn, JC, Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals, SIAM Journal on Control and Optimization, 17, 2, 187-211 (1979) · Zbl 0403.49028
[34] Duval, V., An epigraphical approach to the representer theorem, Journal of Convex Analysis, 28, 3, 819-836 (2021) · Zbl 1483.52007
[35] Epstein, CL, Introduction to the Mathematics of Medical Imaging (2007), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia
[36] Evans, LC; Gariepy, RF, Measure Theory and Fine Properties of Functions (2015), Boca Raton, Florida: CRC Press, Boca Raton, Florida · Zbl 1310.28001
[37] Fanzon, S.; Palombaro, M.; Ponsiglione, M., Derivation of linearised polycrystals from a two-dimensional system of edge dislocations, SIAM Journal on Mathematical Analysis, 51, 5, 3956-3981 (2019) · Zbl 1425.74071
[38] Fanzon, S., Ponsiglione, M., Scala, R.: Uniform distribution of dislocations in Peierls-Nabarro models for semi-coherent interfaces. Calculus of Variations and Partial Differential Equations 59(4), 141 (2020) · Zbl 1440.74263
[39] Flinth, A.; Weiss, P., Exact solutions of infinite dimensional total-variation regularized problems, Information and Inference: A Journal of the IMA, 8, 3, 407-443 (2018) · Zbl 1470.49065
[40] Flinth, A.; de Gournay, F.; Weiss, P., On the linear convergence rates of exchange and continuous methods for total variation minimization, Mathematical Programming, 190, 1, 221-257 (2021) · Zbl 1475.49032
[41] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3, 1-2, 95-110 (1956)
[42] Holler, M.; Kunisch, K., On infimal convolution of TV-type functionals and applications to video and image reconstruction, SIAM Journal on Imaging Sciences, 7, 4, 2258-2300 (2014) · Zbl 1308.94019
[43] Jaggi, M.: Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In: Dasgupta, S., McAllester, D. (eds.) Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, pp. 427-435 (2013)
[44] Kantorovitch, L., On the translocation of masses, Comptes Rendus (Doklady) de l’Académie des Sciences de l’URSS, 37, 199-201 (1942) · Zbl 0061.09705
[45] Kondratyev, S.; Monsaingeon, L.; Vorotnikov, D., A new optimal transport distance on the space of finite Radon measures, Advances in Differential Equations, 21, 11-12, 1117-1164 (2016) · Zbl 1375.49062
[46] Lauteri, G., Luckhaus, S.: An energy estimate for dislocation configurations and the emergence of Cosserat-type structures in metal plasticity. arXiv e-prints (2016) arXiv:1608.06155
[47] Liero, M.; Mielke, A.; Savaré, G., Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures, Inventiones mathematicae, 211, 969-1117 (2018) · Zbl 1412.49089
[48] Lingala, SG; Hu, Y.; DiBella, E.; Jacob, M., Accelerated dynamic MRI exploiting sparsity and low-rank structure: \(k-t\) SLR, IEEE Transactions on Medical Imaging, 30, 5, 1042-1054 (2011)
[49] Neitzel, I.; Pieper, K.; Vexler, B.; Walter, D., A sparse control approach to optimal sensor placement in PDE-constrained parameter estimation problems, Numerische Mathematik, 143, 4, 943-984 (2019) · Zbl 1423.35452
[50] Otazo, R.; Candès, E.; Sodickson, DK, Low-rank plus sparse matrix decomposition for accelerated dynamic MRI with separation of background and dynamic components, Magnetic Resonance in Medicine, 73, 3, 1125-1136 (2015)
[51] Pieper, K.; Walter, D., Linear convergence of accelerated conditional gradient algorithms in spaces of measures, ESAIM: Control, Optimisation and Calculus of Variations, 27, 38 (2021) · Zbl 1483.65089
[52] Pieper, K.; Tang, BQ; Trautmann, P.; Walter, D., Inverse point source location with the Helmholtz equation on a bounded domain, Computational Optimization and Applications, 77, 1, 213-249 (2020) · Zbl 1447.35387
[53] Read, WT; Shockley, W., Dislocation models of crystal grain boundaries, Physical Review, 78, 3, 275-289 (1950) · Zbl 0037.13303
[54] Santambrogio, F., Optimal Transport for Applied Mathematicians (2015), Basel: Birkhäuser, Basel · Zbl 1401.49002
[55] Saumier, L-P; Khouider, B.; Agueh, M., Optimal transport for particle image velocimetry: real data and postprocessing algorithms, SIAM Journal on Applied Mathematics, 75, 6, 2495-2514 (2015) · Zbl 1330.76111
[56] Schloegl, M.; Holler, M.; Schwarzl, A.; Bredies, K.; Stollberger, R., Infimal convolution of total generalized variation functionals for dynamic MRI, Magnetic Resonance in Medicine, 78, 1, 142-155 (2017)
[57] Schmitt, U.; Louis, AK, Efficient algorithms for the regularization of dynamic inverse problems: I, Theory. Inverse Problems, 18, 3, 645 (2002) · Zbl 1003.65049
[58] Schmitt, U.; Louis, AK; Wolters, C.; Vauhkonen, M., Efficient algorithms for the regularization of dynamic inverse problems: II, Applications. Inverse Problems, 18, 3, 659-676 (2002) · Zbl 1003.65050
[59] Schmitzer, B.; Wirth, B., Dynamic models of Wasserstein-1-type unbalanced transport, ESAIM: Control, Optimisation and Calculus of Variations, 25, 23 (2019) · Zbl 1510.90206
[60] Schmitzer, B.; Schafers, KP; Wirth, B., Dynamic cell imaging in PET with optimal transport regularization, IEEE Transactions on Medical Imaging, 39, 5, 1626-1635 (2020)
[61] Schuster, T., Hahn, B., Burger, M.: Dynamic inverse problems: modelling, regularization, numerics. Inverse Problems 34(4), 040301 (2018) · Zbl 1395.00048
[62] Tibshirani, R.: Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B (Methodological), 267-288 (1996) · Zbl 0850.62538
[63] Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109, 3, 475-494 (2001) · Zbl 1006.65062
[64] Unser, M., A unifying representer theorem for inverse problems and machine learning, Foundations of Computational Mathematics, 21, 4, 941-960 (2021) · Zbl 1479.46088
[65] Unser, M., Fageot, J.: Native Banach spaces for splines and variational inverse problems. arXiv e-prints (2019) arXiv:1904.10818
[66] Unser, M.; Fageot, J.; Ward, JP, Splines are universal solutions of linear inverse problems with generalized TV regularization, SIAM Review, 59, 4, 769-793 (2017) · Zbl 1382.41011
[67] Weickert, J.; Schnörr, C., Variational optic flow computation with a spatio-temporal smoothness constraint, Journal of Mathematical Imaging and Vision, 14, 3, 245-255 (2001) · Zbl 0988.68821
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.