L1-Norm Minimization Problem

Hi there,

i am currently facing the following problem: i want to minimize the L1-norm (sum of distances between my datapoints and a streight line). Therefore i wrote the following lines which just worked fine for my random data:

cvx_setup;

%Definition of random Data
a = .9;
x = sort(4*(rand(25,1)-.5));
b = a*x + .1*randn(size(x));

%Minimization
cvx_begin;
    variable aL1;
    minimize( sum(abs(aL1*x-b)) );
cvx_end;

%Visualization
figure;
plot(x,b,'.','color','b');
hold on;
xgrid = -2:0.1:2;
plot(xgrid, xgrid*aL1);
title('L1 Norm')

However when i offset my data by a constant "b" the optimization does not fit.

cvx_setup;

%Definition of random Data
a = .9;
x = sort(4*(rand(25,1)-.5));
b = a*x + .1*randn(size(x));
b = b+10;

%Minimization
cvx_begin;
    variable aL1;
    minimize( sum(abs(aL1*x-b)) );
cvx_end;

%Visualization
figure;
plot(x,b,'.','color','b');
hold on;
xgrid = -2:0.1:2;
plot(xgrid, xgrid*aL1);
title('L1 Norm')

Can anybody describe me how to tune my code to fit the optimal streight regarding an constant axis offset? Setting the first datapoint to zero is not working at all, because the optimization is currently only regarding a slope and no axis offset. Thus the first point would be part of the axis...

Thanks!

[William Rose]

@Jan Marvin Schäfer

I see you are using an external package called cvx for convex minimization problems. I'm not faamiliar with cvx. I woudl probably use fmincon() or fminunc() which are native Matlab.

Does cvx let you specify two variables to adjust? If so, add b to the line specifying aL1.

variable aL1, b;

following whatever the syntax is for cvx.

Answer 1

[Matt J]

Your fit fails because you need an additional unknown variable to model the non-zero y-intercept of the line. I am also not too familiar with CVX, but you could use minL1lin instead,

https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations

if for no other reason than to corroborate your results.

a = .9;
x = sort(4*(rand(25,1)-.5));
b = a*x + .1*randn(size(x));
b = b+10;

coeffs=minL1lin(x(:).^[1,0],b),

Optimal solution found.

coeffs = 2×1

0.9335 10.0579

plot(x,b,'.','color','b');
hold on;
xgrid = -2:0.1:2;
plot(xgrid, xgrid*coeffs(1)+coeffs(2));
title('L1 Norm')

[Jan Marvin Schäfer]

Hi there!

Thanks for your help, this code works for me :)