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
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references