We know that 1-norm is defined as $\|v \|_1 = |v_{1}| + \dots + |v_{n}|$ for the vector $v = \left(v_1, \dots, v_n\right)^T$. Suppose we have
program (a)
$$ \min\limits_{x} \|Ax-b\|_1 $$
and program (b)
$$ \min\limits_{u,x} e^{T}u $$ $$ \text{subject to} -u\le Ax-b \le u, $$
where $ e = (1, \dots, 1)^{T} $.
How to prove program (a) and program (b) are equivalent?
Proof: Write (b) in the following equivalent form,
$$ \min\limits_{x}(\min\limits_u e^T u), $$ $$ \text{subject to} -u\le Ax-b \le u. $$
where the minimization of $u$ is over a fixed $x$. For any $y$, $-u\le y\le u \Longleftrightarrow |y|\le u \implies e^T|y|\le e^T u$. For a given $x$, $u=|Ax-b|$ satisfies the constraint, and by the previous sentence, minimizes the inner minimization problem, i.e. $\min\limits_u e^T u$ under $-u\le Ax-b \le u$. Therefore, problem (b) is equivalent to $$ \min\limits_{x} e^{T}|Ax-b| $$
which is (a).
