1
$\begingroup$

Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find

$$ \widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|. $$

I am also interested in the special case where we further constrain $w_i\ge0$ for all $i=1,\ldots,n$.

This is a convex program so it can be approximated numerically, but I am interested in an analytic / closed-form solution as a function of the $x_j$, i.e. $\widehat{w}=\widehat{w}(x_1,\ldots,x_p)$.

This problem seems distressingly simple but it has thwarted my attempts at a closed-form solution. Any ideas?

Edit: As a result of Ilya's nice example, the following special case is still of interest to me: Take $j=1$ and assume $w\ge 0$ (i.e. all components of $w$ are nonnegative) -

$$ \widehat{w}(x) \in \arg\min_{\Vert w\Vert=1, w\ge 0}|\langle w,x\rangle|. $$

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I doubt there is an analytic solution. Assume that $\|x_j\|=1$ for all $j$, so the $x_j$ are the points on the sphere. If there is a large ball on this sphere which is free of the points, and if the rest ot the sphere is covered more or less densely, then the answer is the center of this ball, regardless of the specific ppositions of the points. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 30, 2016 at 15:57
  • $\begingroup$ I love good counterexamples like this! The idea of thinking about the special case $\Vert x_j\Vert=1$ did not occur to me. Any thoughts on the case $w_i\ge 0$ and $j=1$? $\endgroup$
    – JohnA
    Commented Sep 30, 2016 at 17:02
  • $\begingroup$ Well, if $x$ has coordinates of both signs (or a zero coordinate), then you may choose $w$ orthogonal to $x$. Othewise we may assume that $x>0$. Then $w$ is clearly a vector in the direction of the axis corresponding to smallest coordinate of $x$. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 30, 2016 at 17:12

0

Reset to default

You must log in to answer this question.