7
$\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$
  • 2
    $\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$ – Branimir Ćaćić Jan 4 '14 at 15:46
  • $\begingroup$ and it's the same of find $\arg_x \min {||x-v||} $ right? $\endgroup$ – volperossa Jan 4 '14 at 15:58
  • $\begingroup$ For $x$ restricted to the closed unit ball, yes, I think so. $\endgroup$ – Branimir Ćaćić Jan 4 '14 at 16:05
  • $\begingroup$ all clear! thank you :) $\endgroup$ – volperossa Jan 4 '14 at 16:06
  • $\begingroup$ Orthogonal Projection onto the $ {\ell}_{\infty} $ / l Infinity Ball - math.stackexchange.com/questions/1825747. $\endgroup$ – Royi Jun 18 '17 at 16:34
10
$\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$
7
$\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$

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.