Two fast algorithms for projecting a point onto the canonical simplex

Аннотация

Two fast orthogonal projection algorithms of a point onto the canonical simplex are analyzed. These algorithms are called the vector and scalar algorithms, respectively. The ideas underlying these algorithms are well known. Improved descriptions of both algorithms are given, their finite convergence is proved, and exact estimates of the number of arithmetic operations needed for their implementation are derived, and numerical results of the comparison of their computational complexity are presented. It is shown that on some examples the complexity of the scalar algorithm is maximal but the complexity of the vector algorithm is minimal and conversely. The orthogonal projection of a point onto the solid simplex is also considered.