Sparsity of solutions for variational inverse problems with finite-dimensional data

• DOI: 10.1007/s00526-019-1658-1
• Publication Date: 2019-12-02T16:23:51Z
• Authors: Kristian Bredies; Marcello Carioni
• Keywords: Optimization and Control (math.OC); FOS: Mathematics; 0101 mathematics; 16. Peace & justice; Mathematics - Optimization and Control; 01 natural sciences

AbstractIn this paper we characterize sparse solutions for variational problems of the form$$\min _{u\in X} \phi (u) + F(\mathcal {A}u)$$minu∈Xϕ(u)+F(Au), whereXis a locally convex space,$$\mathcal {A}$$Ais a linear continuous operator that maps into a finite dimensional Hilbert space and$$\phi $$ϕis a seminorm. More precisely, we prove that there exists a minimizer that is “sparse” in the sense that it is represented as a linear combination of the extremal points of the unit ball associated with the regularizer$$\phi $$ϕ(possibly translated by an element in the null space of$$\phi $$ϕ). We apply this result to relevant regularizers such as the total variation seminorm and the Radon norm of a scalar linear differential operator. In the first example, we provide a theoretical justification of the so-called staircase effect and in the second one, we recover the result in Unser et al. (SIAM Rev 59(4):769–793, 2017) under weaker hypotheses.