Proximal Operators of Sorted Nonconvex Penalties

--This work studies the problem of sparse signal recovery with automatic grouping of variables. T o this end, we investigate sorted nonsmooth penalties as a regularization approach for generalized linear models. These penalties are designed to promote clustering of variables due to their sorted nature, while the nonconvexity reduces the shrinkage of coefficients. Our goal is to provide efficient ways to compute their proximal operator, enabling the use of popular proximal algorithms to solve composite optimization problems with this choice of sorted penalties. We distinguish between two classes of problems: the weakly convex case where computing the proximal operator remains a convex problem, and the nonconvex case where computing the proximal operator becomes a challenging nonconvex combinatorial problem. We demonstrate the practical interest of using such penalties on several experiments. R is a data-fidelity term and the penalty Ψ is a regularization term that should embed some properties of the solution. Among them, sparsity and structure are particularly useful for a model as they improve its in-terpretability and decrease its complexity. Sparsity is most usually enforced through a penalty term favoring variable selection, i.e. solutions that use only a subset of features.