A general theory for exact sparse representation recovery in convex optimization

Abstract In this paper, we investigate the recovery of the sparse representation of data in general infinite-dimensional optimization problems regularized by convex functionals. We show that it is possible to define a suitable non-degeneracy condition on the minimal-norm dual certificate, extending the well-established non-degeneracy source condition (NDSC) associated with total variation regularized problems in the space of measures, as introduced in Duval & Peyré (2014) Found. Comput. Math., 15, 1315–1355. In our general setting, we need to study how the dual certificate is acting, through the duality product, on the set of extreme points of the ball of the regularizer, seen as a metric space. This justifies the name metric non-degeneracy source condition (MNDSC). More precisely, we impose a second-order condition on the dual certificate, evaluated on curves with values in small neighbourhoods of a given collection of $n$ extreme points. By assuming the validity of the MNDSC, together with the linear independence of the measurements on these extreme points, we establish that, for a suitable choice of regularization parameters and noise levels, the minimizer of the minimization problem is unique and is uniquely represented as a linear combination of $n$ extreme points. The paper concludes by obtaining explicit formulations of the MNDSC for three problems of interest. First, we examine total variation regularized deconvolution problems, showing that the classical NDSC implies our MNDSC and recovering a result similar to Duval & Peyré (2014) Found. Comput. Math., 15, 1315–1355. Then, we consider one-dimensional functions of bounded variation (BV), regularized with their BV-seminorm and pairs of measures regularized with their mutual 1-Wasserstein distance. In each case, we provide explicit versions of the MNDSC and formulate specific sparse representation recovery results.