A linear-time algorithm for linear \(L_ 1\) approximation of points (Q1115605)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear-time algorithm for linear \(L_ 1\) approximation of points |
scientific article |
Statements
A linear-time algorithm for linear \(L_ 1\) approximation of points (English)
0 references
1989
0 references
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.
0 references
computational geometry
0 references
modified pruning technique
0 references
linear \(L_ 1\) approximation
0 references
