A linear-time algorithm for linear \(L_ 1\) approximation of points (Q1115605)

We present a linear-time algorithm for approximating a set of n points by a linear function, or a line, that minimizes the \(L_ 1\) norm. The algorithmic complexity of this problem appears not to have been investigated, although an \(O(n^ 3)\) naive algorithm can be easily obtained based on some simple characteristics of an optimum \(L_ 1\) solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linear \(L_ 1\) approximation of many points in practice. The complexity of \(L_ 1\) linear approximation of a piecewise linear function is also touched upon.