2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I gave to you, a one-line self-complete answer under the comments section here math.stackexchange.com/a/1477742/168758 ... $\endgroup$ – dohmatob Jun 14 '16 at 20:16
  • $\begingroup$ @dohmatob, Could you add it here as well? I will +1 it. Thank You. $\endgroup$ – Royi Jun 14 '16 at 21:13
  • $\begingroup$ @user1952009, Yes, this is the Euclidean Norm. If you have another solution, I'd love to see. $\endgroup$ – Royi Jun 14 '16 at 21:44
  • $\begingroup$ what do you mean another solution ? Omnomnomnom answered, and the others answered to $\min_{\|y\|_\infty} \|x-y\|_\infty$ $\endgroup$ – reuns Jun 14 '16 at 21:45
  • $\begingroup$ @user1952009, I meant maybe you have a different way to show it. I think everyone answered the same problem which is defined above. $\endgroup$ – Royi Jun 14 '16 at 21:59
3
$\begingroup$

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\\ y_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.

$\endgroup$
  • $\begingroup$ Can you derive it specifically? $\endgroup$ – Royi Jun 14 '16 at 13:24
  • $\begingroup$ I don't understand what you mean by that. In what way is this not a derivation? $\endgroup$ – Omnomnomnom Jun 14 '16 at 13:29
  • $\begingroup$ I meant derivation by solving the Optimization Problem above. Thank You. $\endgroup$ – Royi Jun 14 '16 at 13:32
  • 1
    $\begingroup$ 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? $\endgroup$ – Omnomnomnom Jun 14 '16 at 13:34
  • 1
    $\begingroup$ @user1952009 I thought it's clear from the context ("orthogonal" projection) what I mean $\endgroup$ – Omnomnomnom Jun 14 '16 at 23:26
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ${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. $\endgroup$ – Zalon Sep 13 at 3:30
  • $\begingroup$ @Zalon, I didn't get your comment. If the conjugate function is wrong then I wouldn't get the correct answer. $\endgroup$ – Royi Sep 13 at 7:43
  • $\begingroup$ 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. $\endgroup$ – Zalon Sep 13 at 13:20
  • $\begingroup$ I think you're correct. I was jumping ahead here. $\endgroup$ – Royi Sep 13 at 16:55
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ so you understood his question as $\displaystyle \min_{\|y\|_\infty \le 1} \|y-x\|_\infty$ ? $\endgroup$ – reuns Jun 14 '16 at 21:42
  • $\begingroup$ 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...) $\endgroup$ – dohmatob Jun 14 '16 at 23:54
  • $\begingroup$ @dohmatob, What about the l1 $ {\ell}_{1} $ Unit Ball? Is there a simple derivation? $\endgroup$ – Royi Jun 18 '17 at 16:35
  • $\begingroup$ 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) $\endgroup$ – dohmatob Jun 18 '17 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.