Efficient Computation of the Non-convex Quasi-norm Ball Projection with Iterative Reweighted Approach

Abstract

In this study, we focus on computing the projection onto the ${\ell }_p$ quasi-norm ball, which is challenging due to the non-convex and non-Lipschitz nature inherent in the ${\ell }_p$ quasi-norm with $0<p<1$. We propose a novel localized approximation method that yields a Lipschitz continuous concave surrogate function for the ${\ell }_p$ quasi-norm with improved approximation quality. Building on this approximation, we enhance the state-of-the-art iterative reweighted algorithm proposed by Yang et al. (J Mach Learn Res 23:1-31, 2022) by constructing tighter subproblems. This improved algorithm solves the ${\ell }_p$ quasinorm ball projection problem through a series of tractable projections onto the weighted ${\ell }_1$ norm balls. Convergence analyses and numerical studies demonstrate the global convergence and superior computational efficiency of the proposed method.