Premium
Isotonic median regression for orders representable by rooted trees
Author(s) -
Chakravarti Nilotpal
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199208)39:5<599::aid-nav3220390502>3.0.co;2-#
Subject(s) - isotonic regression , mathematics , regression , statistics , isotonic , combinatorics , computer science , medicine , estimator
The isotonic median regression problem arising in statistics is as follows. We are given m observations falling into n sets, the i th set containing m i observations. The problem requires the determination of n real numbers, the i th being the value “fitted” to each observation in the i th set. These n numbers chosen must satisfy certain (total or partial) order requirements and minimize the distance between the vectors of observed and fitted values in the l 1 norm. We present a simple algorithm, of time complexity O ( mn ), for calculating isotonic median regression for orders representable by rooted trees. We believe that this algorithm is the best currently available for this problem. The algorithm is validated by a linear programming approach which provides additional insight.