Towards An Efficient Approach for the Nonconvex $\ell_p$ Ball
  Projection: Algorithm and Analysis
  This paper primarily focuses on computing the Euclidean projection of a
vector onto the $\ell_{p}$ ball in which $p\in(0,1)$. Such a problem emerges as
the core building block in statistical machine learning and signal processing
tasks because of its ability to promote the sparsity of the desired solution.
However, efficient numerical algorithms for finding the projections are still
not available, particularly in large-scale optimization. To meet this
challenge, we first derive the first-order necessary optimality conditions of
this problem. Based on this characterization, we develop a novel numerical
approach for computing the stationary point by solving a sequence of
projections onto the reweighted $\ell_{1}$-balls. This method is practically
simple to implement and computationally efficient. Moreover, the proposed
algorithm is shown to converge uniquely under mild conditions and has a
worst-case $O(1/\sqrt{k})$ convergence rate. Numerical experiments demonstrate
the efficiency of our proposed algorithm.
