# minimize $l_1$ distance between vectors

Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal. In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$.

How should I approach such problem? The $l_1$ norm has weird derivative. Is there some analytical solution, or should I use something like ternary search?

• Could you clarify what you're looking for? If you're looking for an algorithm, that's on-topic. If "write down the equation 'derivative equals zero' and solve it" is the answer, then this is an off-topic maths question; likewise, if you're asking for advice about how to solve that equation. – David Richerby Apr 29 '16 at 0:19

Define $r_i=a_i/b_i$. Sort the vectors in increasing order of $r_i$. Let's assume (wlog) the $r_i$'s are in increasing order, i.e., $r_1 \le r_2 \le r_3 \le \cdots$. Let $R=\{r_1,r_2,\dots,r_n\}$.
Notice that your objective function is differentiable at all $x$ such that $x \notin R$. In fact, it is linear on each open interval $(r_i,r_{i+1})$. It follows that it attains a maximum at one of the values $r_i$.
So, it suffices to try each of $r_1,r_2,\dots,r_n$ as possible values for $k$, and see which minimizes the objective function. This leads to a simple $O(n^2)$ time algorithm. With some optimization and clever tricks you can get this down to $O(n \lg n)$ time, by avoiding re-computing the objective function from scratch each time and re-using work.