L1-Norm Minimization as a Linear Program

In this post, I try to answer the following Quora question: Given two vectors $x,y \in R^n$, how do you find a scalar $c$ s.t. you minimize $||c*x - y||_1$

In the following, a Linear Programming (LP) formulation is described—assuming $c$ to be non-negative, otherwise one can make use of two-non-negative-variable difference trick.

$\begin{eqnarray} \min_{c,t} &\mathbf{1}^T \mathbf{t} \\\text{s.t.}& \forall i \in \{1,\ldots,n\},\\&c \cdot x_i - y_i\leq t_i\\& y_i-c \cdot x_i\leq t_i\nonumber\end{eqnarray}$

In fact, one of the established modelling and solving systems, CVX, automatically transforms both of these problems [$\ell_1, \ell_\inf$] into LPs. Here is a MATLAB script that compares the above with CVX’s solution:

% get the vectors
n = 10;
x = rand(n,1);
y = rand(n,1);

% formulate the LP problem in MATLAB
[opt_sol, fval] = linprog([0,ones(1,n)],[x,-eye(n,n); -x, -eye(n,n)], [y;-y]);
c_mat_lp = opt_sol(1);
% for comparison with CVX 
% using CVX builtin expression
cvx_begin quiet
    variable c(1)
    minimize(norm(c.*x-y,1))
cvx_end
% LP formulation in CVX
cvx_begin quiet
    variable clp
     variable t(n)
     minimize sum(t)
     subject to 
        clp .* x - y <= t
        y - clp.* x  <= t 
cvx_end

disp (['LP MATLAB solver: obj-val ' num2str(fval) ' c-val ' num2str(c_mat_lp)])
disp (['CVX L1-norm solver: obj-val ' num2str(norm(c.*x-y,1)) ' c-val ' num2str(c)])
disp (['CVX LP formulation: obj-val ' num2str(norm(clp.*x-y,1)) ' c-val ' num2str(clp)])