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
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.
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)])