Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms

Abstract

A precise characterization of the extremal points of sublevel sets of nonsmooth penalties provides both detailed information about minimizers, and optimality conditions in general classes of minimization problems involving them. Moreover, it enables the application of accelerated generalized conditional gradient methods for their efficient solution. In this manuscript, this program is adapted to the minimization of a smooth convex fidelity term which is augmented with an unbalanced transport regularization term given in the form of a generalized Kantorovich-Rubinstein norm for Radon measures. More precisely, we show that the extremal points associated to the latter are given by all Dirac delta functionals supported in the spatial domain as well as certain dipoles, i.e., pairs of Diracs with the same mass but with different signs. Subsequently, this characterization is used to derive precise first-order optimality conditions as well as an efficient solution algorithm for which linear convergence is proved under natural assumptions. This behaviour is also reflected in numerical examples for a model problem.

References in corpus (7)

• Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
• Imaging with Kantorovich-Rubinstein discrepancy
• Splines are Universal Solutions of Linear Inverse Problems with Generalized-TV regularization
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
• On the extremal points of the ball of the Benamou-Brenier energy
• Asymptotic linear convergence of fully-corrective generalized conditional gradient methods

Cited by in corpus (4)

• Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
• Conditional gradients for total variation regularization with PDE constraints: a graph cuts approach
• On extremal points for some vectorial total variation seminorms
• On extreme points and representer theorems for the Lipschitz unit ball on finite metric spaces