Least Squares Isotonic Regression in Two Dimensions

J. Spouge, H. Wan and W.J. Wilbur
Additional contact information
J. Spouge: National Institutes of Health
H. Wan: National Center for Genome Resources
W.J. Wilbur: National Institutes of Health

Journal of Optimization Theory and Applications, 2003, vol. 117, issue 3, No 9, 585-605

Abstract: Abstract Given a finite partially-ordered set with a positive weighting function defined on its points, it is well known that any real-valued function defined on the set has a unique best order-preserving approximation in the weighted least squares sense. Many algorithms have been given for the solution of this isotonic regression problem. Most such algorithms either are not polynomial or they are of unknown time complexity. Recently, it has become clear that the general isotonic regression problem can be solved as a network flow problem in time O(n4) with a space requirement of O(n2), where n is the number of points in the set. Building on the insights at the basis of this improvement, we show here that, in the case of a general two-dimensional partial ordering, the problem can be solved in O(n3) time and, when the two-dimensional set is restricted to a grid, the time can be further improved to O(n2).

Keywords: Quasiorders; partial orders; weighted least-square fits; network flows; grids; dynamic programming (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1023901806339 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:117:y:2003:i:3:d:10.1023_a:1023901806339

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1023901806339

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().