liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An O(n2) algorithm for isotonic regression
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .ORCID iD: 0000-0003-1836-4200
Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
Linköping University, Faculty of Arts and Sciences. Linköping University, Department of Mathematics, Statistics.
2006 (English)In: Large-Scale Nonlinear Optimization / [ed] Pillo, Gianni; Roma, Massimo, New York: Springer Science+Business Media B.V., 2006, 25-33 p.Conference paper, Published paper (Other academic)
Abstract [en]

We consider the problem of minimizing the distance from a given n-dimensional vector to a set defined by constraints of the form xixj. 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.

Place, publisher, year, edition, pages
New York: Springer Science+Business Media B.V., 2006. 25-33 p.
Series
Nonconvex Optimization and Its Applications, ISSN 1571-568X ; 83
Keyword [en]
quadratic programming - large scale optimization - least distance problem - isotonic regression - pool-adjacent-violators algorithm
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-36280DOI: 10.1007/0-387-30065-1_3Local ID: 30828ISBN: 0-387-30063-5 (print)OAI: oai:DiVA.org:liu-36280DiVA: diva2:257128
Conference
40th WORKSHOP LARGE SCALE NONLINEAR OPTIMIZATION, Erice, Italy, June 22 - July 1, 2004,
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2015-06-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Burdakov, OlegSysoev, OlegGrimvall, AndersHussian, Mohamed

Search in DiVA

By author/editor
Burdakov, OlegSysoev, OlegGrimvall, AndersHussian, Mohamed
By organisation
The Institute of TechnologyOptimization Faculty of Arts and SciencesStatistics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 369 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf