Editing Simplex (section)

=== Projection onto the standard simplex ===
Especially in numerical applications of [[probability theory]], a [[Graphical projection|projection]] onto the standard simplex is of interest. Given&nbsp;{{tmath|p}}, possibly with coordinates that are negative or in excess of&nbsp;1, the closest point&nbsp;{{tmath|t}} on the simplex has coordinates 
: <math>t_i= \max\{p_i+\Delta\, ,0\},</math>
where&nbsp;<math>\Delta</math> is chosen such that&nbsp;<math display="inline">\sum_i\max\{p_i+\Delta\, ,0\}=1.</math>

<math>\Delta</math> can be easily calculated from sorting the coordinates of&nbsp;{{tmath|p}}.<ref>{{cite arXiv |eprint=1101.6081|title=Projection Onto A Simplex |author=Yunmei Chen |author2=Xiaojing Ye |year=2011 |class=math.OC }}</ref>
The sorting approach takes&nbsp;<math>O( n \log n)</math> complexity, which can be improved to&nbsp;{{math|O(''n'')}} complexity via [[Selection algorithm|median-finding]] algorithms.<ref>{{Cite journal | last1 = MacUlan | first1 = N. | last2 = De Paula | first2 = G. G. | doi = 10.1016/0167-6377(89)90064-3 | title = A linear-time median-finding algorithm for projecting a vector on the simplex of n | journal = Operations Research Letters | volume = 8 | issue = 4 | pages = 219 | year = 1989 }}</ref> Projecting onto the simplex is computationally similar to projecting onto the <math>\ell_1</math> ball. [[Integer programming|Also see Integer programming]].