Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
What is the Orthogonal Projection onto the $ {\ell}_{\infty} $ Unit Ball?
Namely, given $ x \in {\mathbb{R}}^{n} $ what would be:
$$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) = \arg \min_{{ \left\| y \right\| }_{\infty} \leq 1} \left\{ {\left\| y - x \right\|}_{2}^{2} \right\} $$
I managed to get an answer using the Moreau Decomposition.
Yet I would be happy to see if someone can derive the answer directly.
Thank You.
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} $$
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.
N.B.: The problem can / should be solved using elementary geometry. You don't need KKT or other "heavy machinery".
Indeed, in $\mathbb R^n$ the $\ell_\infty$ unit-ball is a cartesian product of $n$ identical pieces, namely $\mathbb B_\infty = [-1,1]^n$. Thus the projection can be computed piece-wise (minimization of a separable function on a cartesian product), i.e $\text{proj}_{\mathbb B_\infty}(u) = (\text{proj}_{[−1,1]}(u_j))_{j=1,\ldots,n}$.
Exercise: Derive a formula for projection onto a compact 1-dimensional compact interval $[a,b]$. You're done
Just an addition which is helpful to program this projector efficiently for example with Numpy:
The awnser $$ ({\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right))_i = \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} $$
can also be formulated as
$$ ({\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right))_i = \operatorname{sign}(x_i)\min(1,|x_i|). $$
Therefore in vector formulation (which can be directly implemented in Numpy) we can write this simply as
$$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) = \operatorname{sign}(x)\min(1, |x|) = \operatorname{np.sign}(x)*\operatorname{np.minimum}(1,\operatorname{np.abs}(x)) $$
having imported Numpy as np and using its functions $\operatorname{np.sign},\ \operatorname{np.minimum},\ \operatorname{np.abs}$.
