Dual form of $L_1$ norm approximation as a linear programming problem

Question

According to my text:

Given an overdetermined system, the residual vector is:

$$\textbf{r} = \textbf{Ca} - \textbf{f}$$

The $L_1$ norm approximation seeks to minimize the residual r:

$$\text{minimize Z} = \sum_{n=1}^{n}|r_i|$$

My question is how is the dual form derived? And where does $C^Tw$ = 0 come from?

Answer 1

The primal problem is

min Z=$\sum_{i=1}^n u_i+\sum_{i=1}^n v_i$

$\textbf{Ca-u+v}=\textbf{f}$

There is no term with $a_j$ in the objective function. Thus the RHS of the corresponding dual constraint is equal to zero. And $a_j$ is not restricted. It follows that the corresponding dual constraint is an equality. $\textbf w$ is the vector for the dual variables. Regarding all this information the constraint of the dual form is

$C^Tw=0$