On the discrete linear L1 approximation and L1 solutions of overdetermined linear equations

AbstractUsow's algorithm for solving the discrete linear L1 approximation problem is generalized so that it can also solve an Overdetermined system of linear equations in the L1 norm. It is then shown that this algorithm is completely equivalent to a dual simplex algorithm applied to a linear programming problem in nonnegative bounded variables. However, one iteration in the former is equivalent to one or more iterations in the latter.A dual simplex algorithm is described which seems to be the most efficient and capable method for solving these two problems. Its efficiency is due to the absence of artificial variables and to its simplicity. Its capability is due to the fact that the Haar condition associated with Usow's method is completely relaxed. Numerical results are given