This paper presents efficient algorithms for projecting a vector onto the $ \ell_1 $-ball, which is crucial for learning in high-dimensional spaces. The authors propose two projection methods: one that performs exact projection in $ O(n) $ expected time and another that projects in $ O(k \log n) $ time for vectors with $ k $ elements outside the $ \ell_1 $-ball. These methods are particularly useful for online learning in sparse feature spaces, such as text categorization. The algorithms are shown to outperform interior point methods and the exponentiated gradient algorithm, especially in terms of sparsity and convergence speed. The paper also describes efficient projection algorithms for the simplex and the $ \ell_1 $-ball. The first algorithm for the simplex runs in $ O(n \log n) $ time, while a second algorithm improves this to $ O(n) $ time using a median search approach. For sparse feature spaces, the authors introduce a more complex algorithm that uses red-black trees to achieve linear time complexity in the number of non-zero features and logarithmic time in the full dimension. This allows for efficient projection in high-dimensional settings where only a small number of features are non-zero. The paper includes experimental results demonstrating the effectiveness of the proposed algorithms on both synthetic and real datasets, including the Reuters RCV1 corpus and the MNIST handwritten digits dataset. The results show that $ \ell_1 $-projections outperform the exponentiated gradient algorithm in terms of convergence speed, empirical loss, and sparsity. In online learning scenarios, $ \ell_1 $-projections also outperform EG updates in terms of online regret and classification error rates. The algorithms are shown to be efficient and scalable, making them suitable for high-dimensional learning tasks.This paper presents efficient algorithms for projecting a vector onto the $ \ell_1 $-ball, which is crucial for learning in high-dimensional spaces. The authors propose two projection methods: one that performs exact projection in $ O(n) $ expected time and another that projects in $ O(k \log n) $ time for vectors with $ k $ elements outside the $ \ell_1 $-ball. These methods are particularly useful for online learning in sparse feature spaces, such as text categorization. The algorithms are shown to outperform interior point methods and the exponentiated gradient algorithm, especially in terms of sparsity and convergence speed. The paper also describes efficient projection algorithms for the simplex and the $ \ell_1 $-ball. The first algorithm for the simplex runs in $ O(n \log n) $ time, while a second algorithm improves this to $ O(n) $ time using a median search approach. For sparse feature spaces, the authors introduce a more complex algorithm that uses red-black trees to achieve linear time complexity in the number of non-zero features and logarithmic time in the full dimension. This allows for efficient projection in high-dimensional settings where only a small number of features are non-zero. The paper includes experimental results demonstrating the effectiveness of the proposed algorithms on both synthetic and real datasets, including the Reuters RCV1 corpus and the MNIST handwritten digits dataset. The results show that $ \ell_1 $-projections outperform the exponentiated gradient algorithm in terms of convergence speed, empirical loss, and sparsity. In online learning scenarios, $ \ell_1 $-projections also outperform EG updates in terms of online regret and classification error rates. The algorithms are shown to be efficient and scalable, making them suitable for high-dimensional learning tasks.