fastl1kick.m

It is fast sparse linear programming solver, with fast speeder.

function [err,v,s] = fastL1kick (f,A)

A = double(A);
[m,n] = size(A);
f = double(f);
lambda =0.1;
dt = 1e-8;   %Set dt < 1/norm(A'*A)
u = zeros(n,1);
v = zeros(n,1);
update = inf;
iter = 1;
err = zeros(400,1);s = zeros(400,1);temp=dt;
while (norm(A*u-f) > 0.1 && iter <10)
     u = (v - 1/lambda*sign(v)).*[abs(v)>=1/lambda];
    
    
    for i=1:n
        if v(i,1)<-1/lambda
           u(i,1)=0;
        end
    end
    
    
    s(iter,1) = min( abs(-1/lambda*sign(A'*(f-A*u))-v) ./ (A'*(f-A*u)) );
   %s(iter,1)= min(max(0,1.0/lambda*sign(temp*A'*(f-A*u))-v) ./ (temp*A'*(f-A*u)) );
   temp=max(s(iter,1),1);
    v = v + s(iter,1)*dt*A'*(f - A*u);
   
    subplot(211); plot(f,'r'); hold on; plot(A*u); 
    hold off; 
    title(['Iteration ',num2str(iter),'   |Au-f| = ',num2str(norm(A*u-f))]);
    subplot(212); plot(u);
    drawnow;
    err(iter,1)=sum((f-A*u).^2)/2;
    iter = iter+1;
    
    if norm(A*u-f,inf) <50 
    % break;
    end
end;

figure
plot(err,'r');