An Efficient Algorithm for Discrete $l_1$ Linear Approximation with Linear Constraints

Abstract

We describe an algorithm, based on the simplex method of linear programming, for solving the discrete $l_1$ approximation problem with any type of linear constraints. The numerical results reported here, combined with the fact that in the absence of constraints the present algorithm reduces to our earlier unconstrained $l_1$ algorithm, indicate that this algorithm is very efficient.