3
$\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$
5
5
$\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\\ 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.

$\endgroup$
13
  • $\begingroup$ I don't understand what you mean by that. In what way is this not a derivation? $\endgroup$ – Ben Grossmann Jun 14 '16 at 13:29
  • 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$ – Ben Grossmann Jun 14 '16 at 13:34
  • $\begingroup$ 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) $$ $\endgroup$ – Ben Grossmann Jun 14 '16 at 13:58
  • $\begingroup$ 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. $\endgroup$ – Ben Grossmann Jun 14 '16 at 14:02
  • 1
    $\begingroup$ @user1952009 I thought it's clear from the context ("orthogonal" projection) what I mean $\endgroup$ – Ben Grossmann Jun 14 '16 at 23:26
6
$\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$
4
  • $\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 '19 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 '19 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 '19 at 13:20
  • $\begingroup$ I think you're correct. I was jumping ahead here. $\endgroup$ – Royi Sep 13 '19 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$
3
  • $\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$ 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.