# Efficient Projection Algorithms onto the Weighted l1 Ball

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2020.

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

- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [A Binary Characterization Method for Shape Convexity and Applications](https://mlsanity.com/paper/2203.11395/) (2022)
- [Robust Egocentric Referring Video Object Segmentation via Dual-Modal Causal Intervention](https://mlsanity.com/paper/2512.24323/) (2025)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted ℓ1 ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted ℓ1 ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compress sensing, feature selection. We illustrate this effectiveness by adapting an efficient compress sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size 107.