LP Formulation of - and -norm Regression

The l_infty -norm regression problem:

where $A in mathbf{R}^{m times n}$ , $y in mathbf{R}^m$ are given, can be written as the LP

$min_{t,x} : t ~:~ t ge a_i^Tx - y_i ge -t , ;; i=1,ldots,m,$

where a_i stands for the -th row of .

Similarly, the l_1 -norm regression problem:

can be written as the LP

$min_{t,x} : sum_{i=1}^n t_i ~:~ t_i ge a_i^Tx - y_i ge -t_i , ;; i=1,ldots,m.$

CVX does not require the user to transform the problem into LP format. The following syntax will work for any p in [1,+infty] :

CVX implementation
cvx_begin
   variable x(n,1)
   minimize( norm(A*x-y,p) )
cvx_end

A regression problem with random data $A in mathbf{R}^{1000 times 100}$ , $b in mathbf{R}^{1000}$ . The l_1 -norm tends to encourage sparsity of the residual vector: the top panel indeed shows a lot of the residual vector elements are zero. In contrast, the l_infty norm (bottom panel) encourages a lot of elements to have similar magnitude.