Show how to formulate the problem of linear regression with respect to the absolute value loss function as a linear program.
$$ \min_{w} \sum_{t=1}^{m} |\langle w, x_{i}\rangle-y_{i}| $$
There was a hint given that suggested to first show that
$$ |c| = \min_{a \geq 0} a \ \ \text{such that} \: c \leq a \: \text{and} \: c \geq -a $$
I think I was able to show that, but I am a little bit stuck with formulating the linear program. So I introduced $a$ which was given in the hint to formulate
Minimize $a$ subject to $$ a_{i} \geq \langle w, x_{i}\rangle-y_{i} $$ and $$ a_{i} \geq - \langle w, x_{i}\rangle+y_{i} $$
but does that make sense? Shouldn't $w$ appear in the minimization part somehow? And how could I incorporate the summation, can I simply sum over $i$ on both sides or is there some way to write this as a matrix multiplication?
$$\min_{w, a} \sum_{i=1}^m a_i$$
subject to $$a_i \ge \langle w, x_i\rangle - y_i$$
$$a_i \ge -\langle w, x_i\rangle + y_i$$
Note that during the optimization $a$ and $w$ will influence each other, we do not need $w$ to appear in the objective function explicitly.