2
$\begingroup$

Suppose that $V$ is a finite-dimensional real vector space equipped with some $\ell_p$ norm for $1 < p < \infty$. ($p$ is chosen this way so as to be strictly convex.)

Then suppose we have an affine subspace $S \subset V$, and we want to find the shortest vector $v \in S$ such that $||v||_p$ is minimized.

Now suppose we also have a second affine subspace $R \subset S \subset V$. We again want to find the shortest vector $v_2 \in R$ such that $||v_2||_p$ is minimized.

Does $v_2$ also minimize the distance $||v_2-v||_p$?

That is, does $v_2$ minimize not only the $\ell_p$ distance to the origin, but also the distance to $v$, the shortest vector in the larger subspace?

This seems to hold for $p=2$. Does it hold for all $\ell_p$ norms? For all strictly convex norms?

$\endgroup$
1
$\begingroup$

It does not hold for all $\ell_p$ norms. Somehow, I have got the feeling that it holds only for $\ell_2$, but I have no proof for that.

We can construct a counterexample for $\ell_p$ where $p$ is close to one. Since the shape of the unit ball for $p\to 1^+$ is very close to that in $\ell_1$ we may think in $\ell_1$ sense first and construct a counterexample that is robust to small variations in parameters. Let's take $V={\Bbb R}^3$ and $$ S\colon 3x+2y=3,\qquad R\colon\begin{cases}3x+2y=3,\\ 3z+2y=3.\end{cases} $$ Then minimizing $\|v\|_1$ for $v\in S$ we get $v=(1,0,0)$, and $\|v_2\|_1$ for $v_2\in R$ we get $v_2=(0,\frac32,0)$. However, $\|v_2-v\|_1=\frac52$ is not the shortest as $\|v_3-v\|_1=1$ for $v_3=(1,0,1)$.

We now argue that the optimal points $v$, $v_2$ and $v_3$ remain optimal for small variations of parameters (coefficients) in $S$ and $R$, then it is expected that the optimal points are going to be continuous in $p$ when $p\to 1^+$. Indeed, the numerical minimization for $p=1.1$ confirms that the optimal points are close to those above. I've tried Wolfram Alpha

Optimal $v$

Optimal $v_2$

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