A new LAD curve-fitting algorithm: Slightly overdetermined equation systems in \(L_ 1\) (Q789142)

Given n points \((x_ i,y_ i)\in R^{k+1}\), the least absolute deviation (LAD) curve-fitting problem is to minimize \(f(c)=\sum^{n}_{i=1}| y_ i-\sum^{k}_{j=1}x_{ij}c_ j|\) over \(c\in R^ k\), where \(x_{ij}\) is the j-th component of the vector \(x_ i\) and \(c_ j\) is the j-th component of the vector c. The authors propose a new procedure for solving this well-known problem when \(k\leq n\). The LAD curve-fitting problem is first converted into an equivalent minimization problem with linear equality constraints and then an algorithm is designed to solve the latter problem which becomes easier to solve as k grows towards n. The procedure is demonstrated by a simple example, and computational experience is recorded.