0
$\begingroup$

Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex defined for any $x\in \mathbb{R}^n$ by $$ P(x):=\operatorname{argmin}_{\tilde{x}\in \Delta_n}\,\|x-\tilde{x}\|^2. $$

This function is $1$-Lipschitz and therefore by Rademacher's theorem it is a.e. differentiable. Is it's weak derivative known explicitly in closed-form?

I have been looking in the proximity operator literature but nothing yet...

Related Discussion

Improve this question
$\endgroup$
5
  • $\begingroup$ See Theorem 5.2 in the book "Functional Analysis, Sobolev Spaces and Partial Differential Equations" by Haim Brezis. $\endgroup$
    – Liviu Nicolaescu
    Commented Feb 11, 2022 at 10:01
  • $\begingroup$ I feel like I'm missing something, but why does this result give the closed-form expression? $\endgroup$
    – ABIM
    Commented Feb 11, 2022 at 10:13
  • $\begingroup$ There is (to my knowledge) no closed-form solution, but there are efficient algorithms; see arxiv.org/abs/1101.6081 and the references therein. $\endgroup$
    – Christian Clason
    Commented Feb 11, 2022 at 10:18
  • $\begingroup$ Ah, I see that this reference (and the Condat paper, which is the second key reference) is already given in the answers to the linked math.stackexchange.com question. As far as I know, there's nothing to add to that. $\endgroup$
    – Christian Clason
    Commented Feb 11, 2022 at 10:22
  • 1
    $\begingroup$ In this case $P$ is piecewise affine so the differential is easy to compute. If $P(x)$ belongs to the relative interior of a $k$-dimensional face, say $x_{k+2}=\cdots =x_n=0$ and $x_1,\dotsc, x_k>0$, then the differential of $P(x)$ at $x$ is the orthogonal projection onto the $k$-plane given by the equations $$x_1+\cdots+x_{k+1}=x_{k+1}=\cdots =x_n=0.$$ $\endgroup$
    – Liviu Nicolaescu
    Commented Feb 11, 2022 at 11:50

0

Reset to default

You must log in to answer this question.