𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient computation of an isotonic median regression

✍ Scribed by P.M. Pardalos; G.-L. Xue; L. Yong

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
240 KB
Volume
8
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

The isotonic median regression problem arises from statistics. An algorithm, the PAV algorithm, has been proposed for solving this problem since 1980. In this paper, we propose two kinds of data structures for efficiently implementing the PAV algorithm. The running time of the algorithm is also improved.

πŸ“œ SIMILAR VOLUMES

An approximation algorithm for least med
An approximation algorithm for least median of squares regression
✍ Clark F. Olson πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 486 KB

Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates a regression solution with median residual no more than twice the optimal median re

Computing the update of the repeated med
Computing the update of the repeated median regression line in linear time
✍ Thorsten Bernholt; Roland Fried πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 210 KB

The repeated median line estimator is a highly robust method for fitting a regression line to a set of n data points in the plane. In this paper, we consider the problem of updating the estimate after a point is removed from or added to the data set. This problem occurs, e.g., in statistical online