This answer contains an amazing explanation of how the epigraph form can be used to cast the $l_\infty$ norm minimisation problem as a linear program: How can the infinity norm minimization problem be rewritten as a linear program?
However, I am unsure how the epigraph form can be applied to the $l_1$ norm minimisation problem. My understanding of the epigraph form is that we can say $\text { minimise (over } x \text { ) } f_0(x)$ is equivalent to $\text{minimise (over } x, t \text { ) } t \text { subject to } f_0(x)-t \leq 0 \text {. }$
If I do this to the $l_1$ norm minimisation problem, then I get that the epigraph form is: $$\min_{(x,t)} t \quad s.t. \sum_i |a_i^Tx - b_i| \leq t\,.$$ I don't understand how/why $t_i$s are introduced into the final LP form (pictured below)?
I would very much appreciate a derivation like in the link provided earlier.
Not an answer, but too long for a comment.
To see why the problems are equivalent:
Let $P_1$ be $\min_{x,(t_1,t_2,...)} \{ \sum_i t_i \mid |a_i^Tx -b_i| \le t_i \}$ and $P_2$ be $\min_{x,t} \{ t \mid \sum_i|a_i^Tx -b_i| \le t \}$.
Suppose $(x,(t_1,t_2,...))$ is feasible for $P_1$, then $(x,\sum_i t_i)$ is feasible for $P_2$ and $t = \sum_i t_i$. Hence the value of $P_2$ must be $\le$ the value of $P_1$.
Similarly, if $(x,t)$ is feasible for $P_2$, then $(x, (|a_1^Tx -b_1|, |a_2^Tx-b_2|,...))$ is feasible for $P_1$ and $\sum_i |a_i^Tx -b_i| \le t$. Hence the value of $P_1$ must be $\le $ the value of $P_2$.