Efficient computation of an isotonic median regression

DOI10.1016/0893-9659(95)00013-GMaRDI QIDQ1893692zbMATH OpenFDO

Authors Yanyan Li

Publication date 20 July 1995

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(95)00013-G

zbMATH Keywords

balanced search treesisotonic median regressionmergingPAV algorithmrunning time

Mathematics Subject Classification ID

Parametric inference under constraints (62F30) Linear inference, regression (62J99) Probabilistic methods, stochastic differential equations (65C99)

Review text

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.

Recommendations

• An algorithm for isotonic median regression
• Isotonic Median Regression: A Linear Programming Approach
• An efficient estimator for regression median
• A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems
• An algorithm for computing multivariate isotonic regression
• Bounded isotonic median regression
• An O(n^2) algorithm for isotonic regression
• scientific article; zbMATH DE number 1215258
• On the computation and some applications of multivariate isotonic regression

Cites work

• Algorithms in order restricted statistical inference and the Cauchy mean value property
• An algorithm for isotonic median regression
• scientific article; zbMATH DE number 89994 (Why is no real title available?)
• scientific article; zbMATH DE number 193111 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Isotonic Median Regression: A Linear Programming Approach
• Multiple isotonic median regression
• On Estimating Monotone Parameters

Cited in

(12)

• Isotonic regression under Lipschitz constraint
• Least squares isotonic regression in two dimensions
• Unimodal regression via prefix isotonic regression
• Isotonic regression via partitioning
• Isotonic Median Regression: A Linear Programming Approach
• scientific article; zbMATH DE number 89994 (Why is no real title available?)
• A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems
• Data preordering in generalized PAV algorithm for monotonic regression
• An algorithm for isotonic median regression
• Pooling adjacent violators under interval constraints
• Bounded isotonic median regression
• Linear time isotonic and unimodal regression in the \(L_{1}\) and \(L_{\infty }\) norms

This page was built for publication: Efficient computation of an isotonic median regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1893692)