A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization

Abstract

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., arXiv:1907.11589, 2019) 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 in iteratively adding suitably chosen atoms to the current sparse iterate, and subsequently optimize 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 at reconstructing heavily undersampled dynamic data, together with the presence of noise.

arXiv comment40 pages, 8 figures, 1 table

References in corpus (12)

• Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures
• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• Splines are Universal Solutions of Linear Inverse Problems with Generalized-TV regularization
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• A Variational Reconstruction Method for Undersampled Dynamic X-ray Tomography based on Physical Motion Models
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Dynamic Cell Imaging in PET with Optimal Transport Regularization
• A sparse control approach to optimal sensor placement in PDE-constrained parameter estimation problems
• On the extremal points of the ball of the Benamou-Brenier energy
• An optimal transport approach for solving dynamic inverse problems in spaces of measures
• Derivation of Linearised Polycrystals from a 2D system of edge dislocations
• Inverse point source location with the Helmholtz equation on a bounded domain

Cited by in corpus (10)

• On the extremal points of the ball of the Benamou-Brenier energy
• Towards a mathematical theory of trajectory inference
• Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
• A superposition principle for the inhomogeneous continuity equation with Hellinger-Kantorovich-regular coefficients
• Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms
• Dimension reduction, exact recovery, and error estimates for sparse reconstruction in phase space
• Conditional gradients for total variation regularization with PDE constraints: a graph cuts approach
• Proximal methods for point source localisation
• Sparsity for dynamic inverse problems on Wasserstein curves with bounded variation
• On extreme points and representer theorems for the Lipschitz unit ball on finite metric spaces