8
$\begingroup$

What is the Orthogonal Projection onto the $ {L}_{1} $ Unit Ball?

Namely, given $ x \in {\mathbb{R}}^{n} $ what would be:

$$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{1} \leq 1 } \left( x \right) = \arg \min_{{ \left\| y \right\| }_{1} \leq 1} \left\{ {\left\| y - x \right\|}_{2}^{2} \right\} $$

Thank You.

$\endgroup$
  • 1
    $\begingroup$ Orthogonal Projection onto the $ {\ell}_{2} $ / l2 Ball - math.stackexchange.com/questions/627034. $\endgroup$ – Royi Jun 18 '17 at 16:41
  • $\begingroup$ Orthogonal Projection onto the $ {\ell}_{\infty} $ / l Infinity Ball - math.stackexchange.com/questions/1825747. $\endgroup$ – Royi Jun 18 '17 at 16:44
  • $\begingroup$ @JackD'Aurizio The space is finite dimension $\endgroup$ – Red shoes Jun 18 '17 at 17:34
  • 1
    $\begingroup$ @JackD'Aurizio, I know there is no simple closed form solution. But from the KKT Conditions I think one could get very close to a simple solution how to achieve it without heavy artillery like solvers. $\endgroup$ – Royi Jun 18 '17 at 18:31
  • 1
    $\begingroup$ Also see the function proj_l1.m in TFOCS for an $O(n\log n)$ implementation (with the big-O complexity limited by the sorting of $|x_i|$). While no closed-form solution is possible, iteration is not necessary. $\endgroup$ – Michael Grant Jun 19 '17 at 5:04
4
$\begingroup$

$$ \DeclareMathOperator{\sign}{sign} $$

The Lagrangian of the problem can be written as:

$$ \begin{align} L \left( x, \lambda \right) & = \frac{1}{2} {\left\| x - y \right\|}^{2} + \lambda \left( {\left\| x \right\|}_{1} - 1 \right) && \text{} \\ & = \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \lambda \left| {x}_{i} \right| \right) - \lambda && \text{Component wise form} \end{align} $$

The Dual Function is given by:

$$ \begin{align} g \left( \lambda \right) = \inf_{x} L \left( x, \lambda \right) \end{align} $$

The above can be solved component wise for the term $ \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \lambda \left| {x}_{i} \right| \right) $ which is solved by the soft Thresholding Operator:

$$ \begin{align} {x}_{i}^{\ast} = \sign \left( {y}_{i} \right) { \left( \left| {y}_{i} \right| - \lambda \right) }_{+} \end{align} $$

Where $ {\left( t \right)}_{+} = \max \left( t, 0 \right) $.

Now, all needed is to find the optimal $ \lambda \geq 0 $ which is given by the root of the objective function (Which is the constrain of the KKT Sytsem):

$$ \begin{align} h \left( \lambda \right) & = \sum_{i = 1}^{n} \left| {x}_{i}^{\ast} \left( \lambda \right) \right| - 1 \\ & = \sum_{i = 1}^{n} { \left( \left| {y}_{i} \right| - \lambda \right) }_{+} - 1 \end{align} $$

The above is a Piece Wise linear function of $ \lambda $ and its Derivative given by:

$$ \begin{align} \frac{\mathrm{d} }{\mathrm{d} \lambda} h \left( \lambda \right) & = \frac{\mathrm{d} }{\mathrm{d} \lambda} \sum_{i = 1}^{n} { \left( \left| {y}_{i} \right| - \lambda \right) }_{+} \\ & = \sum_{i = 1}^{n} -{ \mathbf{1} }_{\left\{ \left| {y}_{i} \right| - \lambda > 0 \right\}} \end{align} $$

Hence it can be solved using Newton Iteration.

In a similar manner the projection onto the Simplex (See @Ashkan answer) can be calculated.
The Lagrangian in that case is given by:

$$ \begin{align} L \left( x, \mu \right) & = \frac{1}{2} {\left\| x - y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x - 1 \right) && \text{} \\ \end{align} $$

The trick is to leave non negativity constrain implicit.
Hence the Dual Function is given by:

$$ \begin{align} g \left( \mu \right) & = \inf_{x \succeq 0} L \left( x, \mu \right) && \text{} \\ & = \inf_{x \succeq 0} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \mu {x}_{i} \right) - \mu && \text{Component wise form} \end{align} $$

Again, taking advantage of the Component Wise form the solution is given:

$$ \begin{align} {x}_{i}^{\ast} = { \left( {y}_{i} - \mu \right) }_{+} \end{align} $$

Where the solution includes the non negativity constrain by Projecting onto $ {\mathbb{R}}_{+} $

Again, the solution is given by finding the $ \mu $ which holds the constrain (Pay attention, since the above was equality constrain, $ \mu $ can have any value and it is not limited to non negativity as $ \lambda $ above).

The objective function (From the KKT) is given by:

$$ \begin{align} h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} - 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{+} - 1 \end{align} $$

The above is a Piece Wise linear function of $ \mu $ and its Derivative given by:

$$ \begin{align} \frac{\mathrm{d} }{\mathrm{d} \mu} h \left( \mu \right) & = \frac{\mathrm{d} }{\mathrm{d} \mu} \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{+} \\ & = \sum_{i = 1}^{n} -{ \mathbf{1} }_{\left\{ {y}_{i} - \mu > 0 \right\}} \end{align} $$

Hence it can be solved using Newton Iteration.

I wrote MATLAB code which implements them both at Mathematics StackExchange Question 2338491 - GitHub.
There is a test which compares the result to a reference calculated by CVX.

$\endgroup$
2
$\begingroup$

Hint: Because of the symmetric essences of the problem you may assume $x$ lies in first quadrant i.e, $x \ge 0$ and assume $x$ is out side of $\ell_1 $- Unit ball (other wise the answer is trivially $y=x$ ),Therefor under these assumption for sure we have $ 0 \leq y^{*} \leq x$ where $y^{*} $ is the unique optimal solution. To find $y^{*}$ you need to solve following Quadratic programming
\begin{aligned} & {\text{Min}} & & \sum_{i=1}^{n} (x_i -y_i)^2 \\ & \text{subject to} & & y \geq 0, \\ & & & \sum_{i=1}^{n} y_i =1 , \end{aligned}

Note that this is a smooth convex optimization problem with linear constraints, So it is easy to solve! To find a closed form solution set up $KKT$ systems.

Note that once you get solution from problem above, you can characterize all solutions for all cases depending on positions of $x$ in space. For example let $x = (-1, 2,0,0,3)$, you know the solution for above problem where $\bar{x}=(1,2,0,0,3),$ call it $\bar{y} =(y_1,y_2,..., y_n)$ then solution corresponding to $x$ is $y=(-y_1,y_2,...,y_n)$.

$\endgroup$
  • $\begingroup$ See @littleO's comment above. It's actually possible to solve this with an $O(n\log n)$ sort and $O(n)$ additional computations. $\endgroup$ – Michael Grant Jun 19 '17 at 5:06
  • $\begingroup$ @Ashkan, First +1 this lovely idea. I tried sketching the KKT. It doesn't look easy to get a closed form solution from them (Or any solution). Any idea? $\endgroup$ – Royi Jun 19 '17 at 17:58
  • $\begingroup$ OK, I gave it more thought and basically this is Projection onto the Unit Simplex / Probability Simplex which is as hard as projection to the L1 Unit Norm. Unless you have really nice way to solve the KKT of this. Thank You. $\endgroup$ – Royi Jun 19 '17 at 20:04
  • $\begingroup$ I will come back and respond your comment tonight (in my time zone). @Royi $\endgroup$ – Red shoes Jun 19 '17 at 20:06

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.