# Fast Projection onto the Capped Simplex with Applications to Sparse Regression in Bioinformatics

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 19 references that are in the map.
- First posted on arXiv 16 Oct 2021.

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

- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)

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

- [Robust Phi-Divergence MDPs](https://mlsanity.com/paper/2205.14202/) (2022)
- [Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates](https://mlsanity.com/paper/2503.24075/) (2025)
- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)

## Abstract (arXiv)

We consider the problem of projecting a vector onto the so-called k-capped simplex, which is a hyper-cube cut by a hyperplane. For an n-dimensional input vector with bounded elements, we found that a simple algorithm based on Newton's method is able to solve the projection problem to high precision with a complexity roughly about O(n), which has a much lower computational cost compared with the existing sorting-based methods proposed in the literature. We provide a theory for partial explanation and justification of the method. We demonstrate that the proposed algorithm can produce a solution of the projection problem with high precision on large scale datasets, and the algorithm is able to significantly outperform the state-of-the-art methods in terms of runtime (about 6-8 times faster than a commercial software with respect to CPU time for input vector with 1 million variables or more). We further illustrate the effectiveness of the proposed algorithm on solving sparse regression in a bioinformatics problem. Empirical results on the GWAS dataset (with 1,500,000 single-nucleotide polymorphisms) show that, when using the proposed method to accelerate the Projected Quasi-Newton (PQN) method, the accelerated PQN algorithm is able to handle huge-scale regression problem and it is more efficient (about 3-6 times faster) than the current state-of-the-art methods.