Isotonic Regression by Dynamic Programming

Rote, Günter

doi:10.4230/OASIcs.SOSA.2019.1

File

OASIcs.SOSA.2019.1.pdf

Filesize: 0.86 MB
18 pages

Document Identifiers

DOI: 10.4230/OASIcs.SOSA.2019.1
URN: urn:nbn:de:0030-drops-100274

Author Details

Günter Rote

Cite AsGet BibTex

Günter Rote. Isotonic Regression by Dynamic Programming. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.1

Abstract

For a given sequence of numbers, we want to find a monotonically increasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time O(n log n). While other algorithms with the same running time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures.

Keywords

Convex functions
dynamic programming
convex hull
isotonic regression

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

R. K. Ahuja and J. B. Orlin. A fast scaling algorithm for minimizing separable convex functions subject to chain constraints. Operations Research, 49:784-789, 2001. URL: http://dx.doi.org/10.1287/opre.49.5.784.10601.
R. E. Barlow, D. J. Bartholomew, J. M. Bremner, and H. D. Brunk. Statistical Inference under Order Restrictions. Wiley, 1972.
R. E. Barlow and H. D. Brunk. The Isotonic Regression Problem and its Dual. Journal of the American Statistical Association, 67(337):140-147, 1972. URL: http://dx.doi.org/10.1080/01621459.1972.10481216.
Heather Booth and Robert Endre Tarjan. Finding the minimum-cost maximum flow in a series-parallel network. J. Algorithms, 15:416-446, 1993. URL: http://dx.doi.org/10.1006/jagm.1993.1048.
M. R. Brown and R. E. Tarjan. A fast merging algorithm. J. Assoc. Comp. Mach., 26:211-226, 1979. URL: http://dx.doi.org/10.1145/322123.322127.
P. M. Pardalos, G. L. Xue, and Y. Li. Efficient computation of an isotonic median regression. Applied Math. Letters, 8(2):67-70, March 1995. URL: http://dx.doi.org/10.1016/0893-9659(95)00013-G.
Franco P. Preparata and Michael Ian Shamos. Computational Geometry. An Introduction. Springer, 1985.
Quentin F. Stout. Unimodal regression via prefix isotonic regression. Comp. Stat. and Data Anal., 53:289-297, 2008. URL: http://dx.doi.org/10.1016/j.csda.2008.08.005.