Efficient computation of an isotonic median regression (Q1893692): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:41, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient computation of an isotonic median regression |
scientific article |
Statements
Efficient computation of an isotonic median regression (English)
0 references
20 July 1995
0 references
We consider the following isotonic median regression problem (IMR): \[ \min \sum^ n_{i = 1} \sum^{m_ i}_{j = 1} | y_{ij} - x_ i |, \quad \text{s.t.} \quad x_ 1 \leq x_ 2 \leq \cdots \leq x_ n. \] The linear time median finding algorithm is not very practical and the linear programming approach to the IMR problem involves much overhead. More efficient implementation for the pooling adjacent violator (PAV) algorithm is desirable. We present two data structures for efficient implementation of the PAV algorithm. The first one uses balanced search trees and the second one uses merging.
0 references
running time
0 references
isotonic median regression
0 references
PAV algorithm
0 references
balanced search trees
0 references
merging
0 references