Linear L 1 Approximation for a Discrete Point Set and L 1 Solutions of Overdetermined Linear Equations
Nabih N. Abdelmalek · Journal of the ACM · 1971
An algorithm for calculating the best linear Li approximation for a discrete point ~t with arbitrary approximating set of functions has been derived.The algorithm handles also the solution of overdetermined linear equations which minimizes the error in the L1 norm.This algorithm is based on a theorem by Hoel, that the polynomials of best pth power approximation converge to the polynomial of best L~ approximation as p --. 1.The coefficients of the /~ approximation are calculated starting with p = 2 and reducing p uniformly from 2 to 1.In any step, the results of the previous step are taken as the initial values for minimizing iteratively the resulting nonlinear equation of the present step.Two numerical examples are given.I.