×

Linear time isotonic and unimodal regression in the \(L_{1}\) and \(L_{\infty }\) norms. (English) Zbl 1108.62062

Summary: We consider \(L_{1}\)-isotonic regression and \(L_{\infty }\) isotonic and unimodal regression. For \(L_{1}\)-isotonic regression, we present a linear time algorithm when the number of outputs are bounded. We extend the algorithm to construct an approximate isotonic regression in linear time when the output range is bounded. We present linear time algorithms for \(L_{\infty }\) isotonic and unimodal regression.

MSC:

62J05 Linear regression; mixed models
65C60 Computational problems in statistics (MSC2010)
62-04 Software, source code, etc. for problems pertaining to statistics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ayer, M. B.; Brunk, H. D.; Ewing, G. M.; Reid, W. T.; Silverman, E., An empirical distribution function for sampling with incomplete information, Ann. Math. Statist. (1955) · Zbl 0066.38502
[2] Barlow, R.; Ubhaya, V., Isotonic approximation, (Rustagi, J. S., Optimizing Methods in Statistics (1971), Academic Press: Academic Press New York) · Zbl 0274.62045
[3] Chakravarti, N., Isotonic median regression, a linear programming approach, Math. Oper. Res., 14, 2, 303-308 (1989) · Zbl 0677.90041
[4] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), Mcgraw-Hill: Mcgraw-Hill Cambridge, MA · Zbl 1047.68161
[5] Frisén, M., Unimodal regression, The Statistician, 35, 304-307 (1980)
[6] Geng, Z.; Shi, N.-Z., Isotonic regression for umbrella orderings, Appl. Statist., 39, 397-424 (1990) · Zbl 0715.62055
[7] M. Magdon-Ismail, J.H.-C. Chen, Y.S. Abu-Mostafa, The multilevel classification problem and a monotonicity hint, in: Intelligent Data Engineering and Learning (IDEAL 02), Third International Conference, August 2002; M. Magdon-Ismail, J.H.-C. Chen, Y.S. Abu-Mostafa, The multilevel classification problem and a monotonicity hint, in: Intelligent Data Engineering and Learning (IDEAL 02), Third International Conference, August 2002 · Zbl 1020.68788
[8] R.A. Mureika, T.R. Turner, P.C. Wollan, An algorithm for unimodal isotonic regression with application to locating a maximum, Technical Report 92-4, Department of Mathematics and Statistics, University of New Brunswick, 1992; R.A. Mureika, T.R. Turner, P.C. Wollan, An algorithm for unimodal isotonic regression with application to locating a maximum, Technical Report 92-4, Department of Mathematics and Statistics, University of New Brunswick, 1992
[9] Pan, G., Subset selection with additional order information, Biometrics, 52, 1363-1374 (1996) · Zbl 0867.62009
[10] Pardalos, P. M.; Xue, G.-L., Algorithms for a class of isotonic regression problems, Algorithmica, 23, 211-222 (1999) · Zbl 0921.68045
[11] Pardalos, P. M.; Xue, G.-L.; Yong, L., Efficient computation of an isotonic median regression, Appl. Math. Lett., 8, 2, 67-70 (1995) · Zbl 0820.62029
[12] Robertson, T.; Waltman, P., On estimating monotone parameters, Ann. Math. Statist., 1030-1039 (1968) · Zbl 0162.49801
[13] Robertson, T.; Wright, F. T.; Dykstra, R. L., Order Restricted Statistical Inference, Wiley Series in Probability and Statistics (1988), Wiley: Wiley New York · Zbl 0645.62028
[14] Sill, J.; Abu-Mostafa, Y. S., Monotonicity hints, (Mozer, M. C.; Jordan, M. I.; Petsche, T., Advances in Neural Information Processing Systems (NIPS), vol. 9 (1997), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 634-640
[15] Stout, Q. F., Optimal algorithms for unimodal regression, Comput. Sci. Statist., 32 (2000)
[16] Ubhaya, V., Isotone optimization I, J. Approx. Theory, 12, 146-159 (1974) · Zbl 0288.41019
[17] Ubhaya, V., Isotone optimization II, J. Approx. Theory, 12, 315-331 (1974) · Zbl 0292.41026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.