Linear L 1 Approximation for a Discrete Point Set and L 1 Solutions of Overdetermined Linear Equations
- 1 January 1971
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 18 (1) , 41-47
- https://doi.org/10.1145/321623.321628
Abstract
An algorithm for calculating the best linear L1 approximation for a discrete point set 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 the best pth power approximation coverge to the polynomial of the best L1 approximation as p \u2192 1. The coefficients of the Lp 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 inital values for minimizing iteratively the resulting non-linear equation of the present step. Two numerical examples are given.Peer reviewed: YesNRC publication: YeKeywords
This publication has 7 references indexed in Scilit:
- Solutions of overdetermined linear equations which minimize error in an abstract normNumerische Mathematik, 1969
- On the Construction and Comparison of Difference SchemesSIAM Journal on Numerical Analysis, 1968
- On $L_1 $ Approximation II: Computation for Discrete Functions and Discretization EffectsSIAM Journal on Numerical Analysis, 1967
- Algorithms for bestL 1 andL ∞ linear approximations on a discrete setNumerische Mathematik, 1966
- A Rapidly Convergent Descent Method for MinimizationThe Computer Journal, 1963
- On the “Best” and “Least Q th” Approximation of an Overdetermined System of Linear EquationsJournal of the ACM, 1957
- Certain Problems in the Theory of Closest ApproximationAmerican Journal of Mathematics, 1935