10
$\begingroup$

On an article I'm reading, I find that: if $v$ is a vector, the projection of of $v$ on the unit ball is: $$p(v)=\frac{v}{\max\{1,\|v\|\}}$$ I know that a projection of a point $v$ into a space is the nearest point to $v$ inside the space..why the expression above?

$\endgroup$
8
  • 4
    $\begingroup$ If $v$ is outside the closed unit ball, then $\|v|| > 1$, and hence $p(v) = \tfrac{1}{\|v\|}v$, which is on the unit sphere, and hence in the closed unit ball. If, instead, $v$ is inside the closed unit ball, then $\|v\| \leq 1$, and hence $p(v) = v$. So, $p$ maps vectors outside the closed unit ball to their normalisations, which lie on the unit sphere, and does nothing to vectors that are already in the closed unit ball. $\endgroup$ Jan 4, 2014 at 15:46
  • $\begingroup$ and it's the same of find $\arg_x \min {||x-v||} $ right? $\endgroup$
    – volperossa
    Jan 4, 2014 at 15:58
  • $\begingroup$ For $x$ restricted to the closed unit ball, yes, I think so. $\endgroup$ Jan 4, 2014 at 16:05
  • $\begingroup$ all clear! thank you :) $\endgroup$
    – volperossa
    Jan 4, 2014 at 16:06
  • $\begingroup$ Orthogonal Projection onto the $ {\ell}_{\infty} $ / l Infinity Ball - math.stackexchange.com/questions/1825747. $\endgroup$
    – Royi
    Jun 18, 2017 at 16:34

3 Answers 3

16
$\begingroup$

I presume the setting is a Hilbert space $\mathbb{H}$.

Then the projection onto the closed unit ball $\bar{B}$ is given by a solution to $\min_{ x \in \bar{B}} \|x-v\|$.

If $v=0$, it is clear that the solution is $x=0$, so we will assume $v \neq 0$ in the sequel.

We can write any $x \in \mathbb{H}$ as $x = \lambda v + w$, where $w \bot v$. In particular, we have $\|x\|^2 = \lambda^2 \|v\|^2 + \|w\|^2$, and so $\|x-v\|^2 = (1-\lambda)^2 \|v\|^2 + \|w\|^2$. Hence if $x = \lambda v + w \in \bar{B}$, we see that $\lambda v \in \bar{B}$, and $\|\lambda v-v\|^2 \le \|x-v\|^2$.

If we let $V = \operatorname{sp} \{v\}$, we see that $\min_{ x \in \bar{B}} \|x-v\| = \min_{ \lambda v \in \bar{B}} (1-\lambda)^2 \|v\|^2 $, which is a one dimensional problem.

Since $\lambda v \in \bar{B}$ iff $|\lambda| \le {1 \over \|v\|}$, we see that the problem is solved by $\lambda = \min(1,{1 \over \|v\|} )$, that is, $x= \min(1,{1 \over \|v\|} )v$.

It is straightforward to see that this is the same as $p(v) $ above.

$\endgroup$
2
  • $\begingroup$ can you give a hint for a projection onto a ball around some point $c$ with radius r? I thought maybe setting the function to be $min(||y-x-c||_2^2:||y-c||\leq r)$ $\endgroup$
    – convxy
    Jun 8, 2020 at 17:27
  • $\begingroup$ @ronkurman: Show that $v$ solves the above problem iff $c+rv$ solves your problem. Look at the problem geometrically. $\endgroup$
    – copper.hat
    Jun 8, 2020 at 17:32
10
$\begingroup$

You can do it using KKT Conditions.

Here is something I wrote once doing so (Solution to Home Work exercise I had):

enter image description here

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$
4
  • $\begingroup$ can you give a hint for a projection onto a ball around some point $c$ with radius r? I thought maybe setting the function to be $min(||y-x-c||_2^2:||y-c||\leq r)$ $\endgroup$
    – convxy
    Jun 8, 2020 at 17:24
  • $\begingroup$ If you look on the code it supports any radius $ r $. Shifting is no issue. Remove the shift form the input, project and them return it to the output. $\endgroup$
    – Royi
    Jun 8, 2020 at 19:36
  • $\begingroup$ How do you conclude that $x$ is normalized and $y$ must be divided by $\|y\|_2$? Basically how from the fact that $y$ is a scaled version of $x$, you go to $\frac{y}{\|y\|_2}$? $\endgroup$
    – DontWorry
    Nov 28, 2023 at 17:03
  • $\begingroup$ @DontWorry, They have the same direction and you need to to do the least distance. So it must be on the envelope of the ball. $\endgroup$
    – Royi
    Nov 28, 2023 at 20:55
2
$\begingroup$

An alternative solution that works in any inner product space: if $v$ is already in the unit ball, then clearly $p(v)=v$. We can thus assume that $\lVert v\rVert>1$. Given an arbitrary $a$ in the unit ball, it suffices to show that

$$\lVert v-a\rVert^2 \geq \left\lVert v-\frac v{\lVert v\rVert}\right\rVert^2.$$

Note that the RHS rewrites as $(\lVert v\rVert-1)^2$, and expanding the squares we find the equivalent inequality:

$$\lVert v \rVert^2 - 2\langle v,a \rangle + \lVert a \rVert^2 \geq \lVert v\rVert^2 - 2\lVert v\rVert +1, $$ which simplifies as $$ \lVert a \rVert^2 - 2\langle v,a \rangle + 2\lVert v \rVert -1 \geq 0.$$

To prove this last inequality, note that $$\begin{align} \lVert a \rVert^2 - 2\langle v,a \rangle + 2\lVert v \rVert -1 &\geq \lVert a \rVert^2 - 2\lVert v \rVert\lVert a \rVert + 2\lVert v \rVert -1 \tag{1} \\ &= \lVert a \rVert^2 + 2\lVert v \rVert(1-\lVert a \rVert) -1 \\&\geq \lVert a \rVert^2 + 2(1-\lVert a \rVert) -1 \tag{2} \\&= (\lVert a \rVert-1)^2 \geq 0.\end{align}$$

$(1)$: Cauchy-Schwarz inequality
$(2)$: multiply both sides of $\lVert v \rVert \geq 1$ by the nonnegative scalar $1-\lVert a \rVert$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .