Linear L1 Approximation for a Discrete Point Set and L1 Solutions of Overdetermined Linear Equations

Download
  1. Get@NRC: Linear L1 Approximation for a Discrete Point Set and L1 Solutions of Overdetermined Linear Equations (Opens in a new window)
DOIResolve DOI: http://doi.org/10.1145/321623.321628
AuthorSearch for:
TypeArticle
Journal titleJournal of the Association for Computing Machinery
ISSN0004-5411
Volume18
Issue1
Pages4147; # of pages: 7
SubjectL1 norm; l1 approximation; pth power approximation; overdetermined system of linear equations; minimization; normal equations; nonlinear equations; Tchebycheff set; characteristics of the solution; Polya algorithm
AbstractAn 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 → 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.
Publication date
LanguageEnglish
AffiliationNational Research Council Canada
Peer reviewedYes
NRC number16549
NPARC number21273608
Export citationExport as RIS
Report a correctionReport a correction
Record identifierd488e558-c99c-46cb-a52b-f7cdcb1b88d9
Record created2015-01-16
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)