An O(n2) algorithm for isotonic regression

Burdakov, Oleg, 1953- (författare): Linköpings universitet,Tekniska högskolan,Optimeringslära

Sysoev, Oleg, 1981- (författare): Linköpings universitet,Filosofiska fakulteten,Statistik

Grimvall, Anders, 1945- (författare): Linköpings universitet,Filosofiska fakulteten,Statistik

Hussian, Mohamed, 1969- (författare): Linköpings universitet,Filosofiska fakulteten,Statistik

(creator_code:org_t)

New York : Springer Science+Business Media B.V. 2006
2006
Engelska.
Ingår i: Large-Scale Nonlinear Optimization. - New York : Springer Science+Business Media B.V.. - 0387300635 ; , s. 25-33

Relaterad länk:: https://urn.kb.se/re...; visa fler...; https://doi.org/10.1...; visa färre...

Abstract Ämnesord

Stäng

We consider the problem of minimizing the distance from a given n-dimensional vector to a set defined by constraints of the form xi ≤ xj. Such constraints induce a partial order of the components xi, which can be illustrated by an acyclic directed graph. This problem is also known as the isotonic regression (IR) problem. IR has important applications in statistics, operations research and signal processing, with most of them characterized by a very large value of n. For such large-scale problems, it is of great practical importance to develop algorithms whose complexity does not rise with n too rapidly. The existing optimization-based algorithms and statistical IR algorithms have either too high computational complexity or too low accuracy of the approximation to the optimal solution they generate. We introduce a new IR algorithm, which can be viewed as a generalization of the Pool-Adjacent-Violator (PAV) algorithm from completely to partially ordered data. Our algorithm combines both low computational complexity O(n2) and high accuracy. This allows us to obtain sufficiently accurate solutions to IR problems with thousands of observations.

Av författaren/redakt...: Burdakov, Oleg, ...; Sysoev, Oleg, 19 ...; Grimvall, Anders ...; Hussian, Mohamed ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.