シンプレックスへの射影についての新しい論文が出ていた

計算としては、シンプレックスへの射影は
$ \{ x \in R^N : \sum_{i=1}^N x_i, x \ge 0\}$
への射影をどう計算するか、という問題で基礎的な問題ではあるが、ソートと同じような感じでいろいろなアルゴリズムが開発されている。

今日気がついたところでは、この内容について新しい論文が出ていた。

"Fast projection onto the simplex and the $\ell_1$ ball"
http://link.springer.com/article/10.1007/s10107-015-0946-6

数値実験用のソフトは C で組んであるとのこと。

前に別の論文にあったアルゴリズムをMatlabで実装してみたときは、setdiff や union などの集合を扱う計算に計算時間を取られていたが、そのあたりは C で組むと解消できているのかもしれない。

基礎的な問題であるけど、基礎的な問題であるからこそ、常に新しいアルゴリズムが研究されていて面白い。