2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 29 '16 at 0:19
1
$\begingroup$

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.

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