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.

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