Orthogonal Projection onto the $ {L}_{\infty} $ Unit Ball

Solution 1:

By Moreau Decomposition:

$$ {\text{Prox}}_{f} \left( x \right) + {\text{Prox}}_{ {f}^{\ast} } \left( x \right) = x $$

For $ f \left( x \right) = \left\| \cdot \right\| $ the conjugate is given by the Projection onto the Dual Norm $ {f}^{\ast} \left( x \right) = {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) $.

Hence, for $ f \left( x \right) = { \left\| x \right\| }_{1} $ one would get

$$ {\text{Prox}}_{ {\left\| \cdot \right\| }_{1} } \left( x \right) = x - {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) $$

It is known that the $ \text{Prox} $ Operator for the $ {\ell}_{1} $ is given by Soft Threshold, thus:

$$ {\text{Prox}}_{ {\left\| \cdot \right\| }_{1} } { \left( x \right) }_{i} = \begin{cases} {x}_{i} - 1, & \text{if} & {x}_{i} \geq 1 \\ {x}_{i} - {x}_{i}, & \text{if} & \left | {x}_{i} \right | < 1 \\ {x}_{i} - \left( -1 \right), & \text{if} & {x}_{i} \leq -1 \end{cases} \Rightarrow {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) = \begin{cases} 1, & \text{if} & {x}_{i} \geq 1 \\ {x}_{i}, & \text{if} & \left | {x}_{i} \right | < 1 \\ -1, & \text{if} & {x}_{i} \leq -1 \end{cases} $$

Solution 2:

The "common sense" answer is that you simply want to get each $y_i$ as close as possible to $x_i$ without causing $y$ to leave the unit ball. That is, take $$ y_i = \begin{cases} -1 & x_i < -1\\ x_i & -1 \leq x_i \leq 1\\ 1 & x_i > 1 \end{cases} $$ In a sense, this is a greedy optimization at each coordinate. This works for this problem where it would fail for others because our choice for one coordinate does not affect the available choices for the other as it would in a ball other than the $\ell_\infty$ ball.

By KKT: the problem is $$ \text{maximize } f(y) = -\|x - y\|^2\\ \text{subject to } g_i(y) = y_i^2 - 1 \leq 0 \quad (i = 1,\dots, n) $$ For convenience, let $e_i$ be the $i$th standard basis vector (e.g. $e_2 = (0,1,0,\dots,0)$). We compute $$ \nabla f = -2(y_1-x_1,y_2-x_2, \dots,y_n - x_n)\\ \nabla g_i = 2y_i \mathbf e_i $$ A vector $y$ is stationary, then, if there are $\mu_i$ for which $$ 2\sum_i (x_i - y_i)\mathbf e_i = \sum_{i} \mu_i (2 y_i) \mathbf e_i $$ So $y$ only fails to be stationary if for some $i$, $y_i = 0$ but $x_i \neq 0$. So, if $x_i = 0$, the solution satisfies $y_i = 0$.

A vector $y$ is primally feasible exactly if it is in the $\ell_\infty$ ball.

A vector $y$ is dually feasible exactly if $\mu_i \geq 0$ for each $i$, which is to say that $y_i$ and $x_i - y_i$ are either both positive or both negative for each $i$. That is, we have either $0 \leq y_i \leq x_i$ or $x_i \leq y_i \leq 0$, which is to say simply that $y_i$ has the same sign as $x_i$ and $|y_i| \leq |x_i|$.

Finally, complementary slackness tells us that $\mu_ig_i(y) = \mu_i (y_i^2 - 1) = 0$ for all $i$. That is, for each $i$: we must either have $|y_i| = 1$, or $\mu_i = 0$. But, in order to have $\mu_i = 0$, we must have $y_i - x_i = 0 \implies y_i = x_i$.

Combining these last two conditions, we see that we must take $y_i = x_i$ whenever $|x_i| < 1$, and $|y_i| = 1$ (with sign to match that of $x_i$) otherwise.

So, we get precisely the desired result.