Abstract
We describe algorithms for finding the regression of t, a sequence of values, to the closest sequence s by mean squared error, so that s is always increasing (isotonicity) and so the values of two consecutive points do not increase by too much (Lipschitz). The isotonicity constraint can be replaced with a unimodular constraint, for exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each we describe near-linear time algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Arge, L., Yi, K.: I/O-efficient batched union-find and its applications to terrain analysis. In: Proc. 22 ACM Symp. on Comp. Geometry (2006)
Agarwal, P.K., Phillips, J.M., Sadri, B.: Lipschitz unimodal and isotonic regression on paths and trees. Technical report, arXiv:0912.5182 (2009)
Angelov, S., Harb, B., Kannan, S., Wang, L.-S.: Weighted isotonic regression under the l 1 norm. In: Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (2006)
Attali, D., Glisse, M., Hornus, S., Lazarus, F., Morozov, D.: Persistence-sensitive simplification of functions on surfaces in linear time. INRIA (2008) (manuscript)
Ayer, M., Brunk, H.D., Ewing, G.M., Reid, W.T., Silverman, E.: An empirical distribution function for sampling with incomplete information. Annals of Mathematical Statistics 26, 641–647 (1955)
Bajaj, C., Pascucci, V., Schikore, D.: Visualization of scalar topology for structural enhancement. In: IEEE Visualization, pp. 51–58 (1998)
Barlow, R.E., Bartholomew, D.J., Bremmer, J.M., Brunk, H.D.: Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression. John Wiley and Sons, Chichester (1972)
Bremer, P., Edelsbrunner, H., Hamann, B., Pascucci, V.: A multi-resolution data structure for two-dimensional morse functions. In: Proceedings 14th IEEE Visualization Conference, pp. 139–146 (2003)
Brown, M.R., Tarjan, R.E.: A fast merging algorithm. J. Alg. 15, 416–446 (1979)
Brunk, H.D.: Maximum likelihood estimates of monotone parameters. Annals of Mathematical Statistics 26, 607–616 (1955)
Danner, A., Mølhave, T., Yi, K., Agarwal, P.K., Arge, L., Mitasova, H.: Terrastream: from elevation data to watershed hierarchies. In: 15th ACM International Symposium on Advances in Geographic Information Systems (2007)
Edelsbrunner, H., Harer, J.: Persistent Homology: A Survey. Contemporary Mathematics, vol. 453. American Mathematical Society, Providence (2008)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proc. 41 Symp. on Foundatons of Computer Science (2000)
Edelsbrunner, H., Morozov, D., Pascucci, V.: Persistence-sensitive simplification functions on 2-manifolds. In: Proc. 22 ACM Symp. on Comp. Geometry (2006)
Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in x + y and matrices with sorted columns. J. Comput. Syst. Sci. 24, 192–208 (1982)
Grotzinger, S.J., Witzgall, C.: Projection onto order simplexes. Applications of Mathematics and Optimization 12, 247–270 (1984)
Guskov, I., Wood, Z.J.: Topological noise removal. In: Graphics Interface (2001)
Jewel, W.S.: Isotonic optimization in tariff construction. ASTIN 8, 175–203 (1975)
Maxwell, W.L., Muckstadt, J.A.: Establishing consistent and realistic reorder intervals in production-distribution systems. Operations Res. 33, 1316–1341 (1985)
Ni, X., Garland, M., Hart, J.C.: Fair Morse functions for extracting the topological structure of a surface mesh. ACM Transact. Graphics 23, 613–622 (2004)
Pardalos, P.M., Xue, G.: Algorithms for a class of isotonic regression problems. Algorithmica 23, 211–222 (1999)
Preparata, F.P., Shamos, M.I.: Computational geometry: an introduction. Springer, New York (1985)
Soille, P., Vogt, J., Cololmbo, R.: Carbing and adaptive drainage enforcement of grid digital elevation models. Water Resources Research 39(12), 1366–1375 (2003)
Spouge, J., Wan, H., Wilbur, W.J.: Least squares isotonic regression in two dimensions. Journal of Optimization Theory and Applications 117, 585–605 (2003)
Stout, Q.F.: Optimal algorithms for unimodal regression. Computing Science and Statistics 32, 348–355 (2000)
Stout, Q.F.: Unimodal regression via prefix isotonic regression. Computational Statistics and Data Analysis 53, 289–297 (2008)
Thompson Jr., W.A.: The problem of negative estimates of variance components. Annals of Mathematical Statistics 33, 273–289 (1962)
Zomorodian, A.: Computational topology. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC Press (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agarwal, P.K., Phillips, J.M., Sadri, B. (2010). Lipschitz Unimodal and Isotonic Regression on Paths and Trees. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)