Methods for approximating the projection onto a unit $\ell^p$ ball

51 Views Asked by At

Let $p\in\left[1,+\infty\right]$. I am curious if there are methods for computing (or approximating) the orthogonal projection onto the unit ball of the $\ell^p$ norm, i.e., given any $x$ in a Euclidean space $(\mathcal{X}, \|\cdot\|_2)$, compute $$ \underset{{\substack{y\in\mathcal{X}\\\|y\|_p\leq 1}}}{\textrm{Argmin}} \;\;\|x-y\|_2. \tag{$*$} $$ I know this is possible in closed-form for $p=1$, $p=2$, and $p=\infty$. However, my understanding is that closed-form solutions for general $p\in\left[1,+\infty\right]$ is an open question (please let me know if this has been solved!).

However, are there efficient methods of approximating a solution to ($*$)? As pointed out in the comments, some standard convex optimization tools could be used for this. If these tools are the most efficient (in some sense of the word), that would be great; however, are there also methods designed specifically for solving ($*$)?