# Towards An Efficient Approach for the Nonconvex ℓp Ball Projection: Algorithm and Analysis

arXiv: https://arxiv.org/abs/2101.01350 · HTML: https://mlsanity.com/paper/2101.01350/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 10 of 10)

- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs](https://mlsanity.com/paper/1409.8147/) (2014)
- [A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization](https://mlsanity.com/paper/2010.12169/) (2020)
- [On Strong NP-Completeness of Rational Problems](https://mlsanity.com/paper/1802.09465/) (2018)
- [Efficient Dictionary Learning with Sparseness-Enforcing Projections](https://mlsanity.com/paper/1604.04767/) (2016)
- [Inexact Primal-Dual Gradient Projection Methods for Nonlinear Optimization on Convex Set](https://mlsanity.com/paper/1911.07758/) (2019)
- [Matrix-Free Solvers for Exact Penalty Subproblems](https://mlsanity.com/paper/1402.1917/) (2014)
- [On Fej'er monotone sequences and nonexpansive mappings](https://mlsanity.com/paper/1507.05585/) (2015)

## Built on by (most cited first, 4 of 4)

- [HoP: Homeomorphic Polar Learning for Hard Constrained Optimization](https://mlsanity.com/paper/2502.00304/) (2025)
- [An Iteratively Reweighted Method for Sparse Optimization on Nonconvex ℓp Ball](https://mlsanity.com/paper/2104.02912/) (2021)
- [Constrained Optimization Involving Nonconvex ℓp Norms: Optimality Conditions, Algorithm and Convergence](https://mlsanity.com/paper/2110.14127/) (2021)
- [Anderson acceleration for iteratively reweighted ℓ1 algorithm](https://mlsanity.com/paper/2403.07271/) (2024)

## Abstract (arXiv)

This paper primarily focuses on computing the Euclidean projection of a vector onto the ℓp ball in which p∈(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 ℓ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/√k) convergence rate. Numerical experiments demonstrate the efficiency of our proposed algorithm.