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

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}$$

• ${f}^{\ast} \left( x \right) = {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right)$ is not correct. Proximal mapping of the function is right-hand side. Sep 13, 2019 at 3:30
• @Zalon, I didn't get your comment. If the conjugate function is wrong then I wouldn't get the correct answer.
– Royi
Sep 13, 2019 at 7:43
• I think $\text{Prox}_{f^*}(x)={\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right)$ instead of ${f}^{\ast} \left( x \right) = {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right)$. Ooooooh, I get you. You write down the "Projection" directly. Sep 13, 2019 at 13:20
• I think you're correct. I was jumping ahead here.
– Royi
Sep 13, 2019 at 16:55

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.

• I don't understand what you mean by that. In what way is this not a derivation? Jun 14, 2016 at 13:29
• Well, I have followed a line of reasoning that has allowed me to deduce the solution to the optimization problem. Hence, I would say that I have solved the optimization problem. You seem, however, to disagree. So what exactly is it that you're looking for? Are you looking for a solution via a specific method? Are you looking for a more rigorous proof that this is indeed the solution? Jun 14, 2016 at 13:34
• I could give a proof that this answer is indeed correct, but I don't think that qualifies as a "derivation" by your standards. KKT should be easy enough; our optimization 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)$$ Jun 14, 2016 at 13:58
• I guess as a mathematician, I would say that the point of a derivation is to get a good guess (for which intuition suffices here), and then something is usually shown to be true by a proof that either that the intuition of the derivation holds rigorously or that it just happens to yield the right answer. Jun 14, 2016 at 14:02
• @user1952009 I thought it's clear from the context ("orthogonal" projection) what I mean Jun 14, 2016 at 23:26

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

• so you understood his question as $\displaystyle \min_{\|y\|_\infty \le 1} \|y-x\|_\infty$ ? Jun 14, 2016 at 21:42
• No, not at all. How did you come up with that ? If you don't understand something about my solution, I'd be happy to explain (even though it should be crystal clear as it stands...) Jun 14, 2016 at 23:54
• For the $\ell_1$ ball see stanford.edu/~jduchi/projects/DuchiShSiCh08.pdf for an $\mathcal O(n \log n)$ algorithm. BTW, can be improved to $\mathcal O(n)$ (see Laurent Condat, e.g) Jun 18, 2017 at 21:11
• Do you have suggestion how to prove it in $\mathbb{C}^n$ field? Sep 23, 2021 at 8:21
• To prove what ? Sep 23, 2021 at 9:17

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}$$.

• If you're worried about computational efficiency, then x = x.clip(a, b) projects onto the interval [a, b]. If x is an n-dimensional vector, then it projects onto the box [a,b]^n ;) Apr 20, 2022 at 16:18