Given two vectors $x, y$ in $\mathbb{R}^n$ and scalar $\alpha$, what is the value of $\alpha$ that minimizes $||\alpha x - y ||_1$? Give an algorithm to find the minimum.
I've tried couple of examples by hand but I am not getting anywhere. Either it's the value of $|\alpha x_i - y_i|$ that dominates the function or the median. Is there a systematic way to get the solution?
On
The key to solving this problem is to note that $\|ax-y\|_1$ is a piecewise linear, convex function of $a$. Any piecewise linear convex function that is bounded below is minimized at one of its "kinks" or vertices. If you can identify the locations of those kinks, a simple search will be sufficient.
(It's possible for a piecewise linear convex function to achieve its minimum between two kinks; for example, $f(a)=\max\{|a|-1,0\}$. But note that the two surrounding vertices are also minimizers. So the search approach is always valid.)
So where are those kinks? In this case, it is exactly the set of points where $ax_i-y_i$ changes sign: $$a \in \{ y_i / x_i ~|~ i=1,2,\dots, n,~x_i\neq 0\}.$$ Therefore, the solution is $$a = y_q / x_q, \quad q = \mathop{\textrm{argmin}}_{i:x_i\neq 0} \sum_j |x_jy_i/x_i - y_j| .$$ You can exhaustively search all $n$ points if you want, for $O(n^2)$ complexity. or you can sort them and start your search from the median value of $a$. That would still be $O(n^2)$ worst case.
This reduces to a Euclidean geometry problem, by restriction to the subspace spanned by $x$ and $y$.
There are two cases, where the line does/doesn't intersect $C$, which should be similar to the types you described from examples. Nonintersecting case is the problem of finding lines of support parallel to the given one.