Efficient Projections onto the L1-Ball for Learning in High Dimensions

We describe efficient algorithms for projecting a vector onto the L1-ball. We present two methods for projection. The first performs exact projection in O(n) time, where n is the dimension of the spac