2025/01/15 by Chancelier, Jean-Philippe, de Lara, Michel, Deza, Antoine +1
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2501.08651
Sparse optimization seeks an optimal solution with few nonzero entries. To achieve this, it is common to add to the criterion a penalty term proportional to the ℓ1-norm, which is recognized as the archetype of sparsity-inducing norms. In this approach, the number of nonzero entries is not controlled a priori. By contrast, in this paper, we focus on finding an optimal solution with at most~k nonzero coordinates (or for short, k-sparse vectors), where k is a given sparsity level (or ``sparsity budget''). For this purpose, we study the class of generalized k-support norms that arise from a given source norm. When added as a penalty term, we provide conditions under which such generalized k-support norms promote k-sparse solutions. The result follows from an analysis of the exposed faces of closed convex sets generated by k-sparse vectors, and of how primal support identification can be deduced from dual information. Finally, we study some of the geometric properties of the unit balls for the k-support norms and their dual norms when the source norm belongs to the family of ℓp-norms.