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

DOI10.1016/j.jda.2005.07.001zbMath1108.62062OpenAlexW2031841099MaRDI QIDQ866553

Malik Magdon-Ismail, Victor Boyarshinov

Publication date: 14 February 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.07.001

zbMATH Keywords

approximationmedianmonotonicoutput sensitive algorithmshape constrained

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to statistics (62-04) Linear regression; mixed models (62J05)

Related Items

Inradius and circumradius of various convex cones arising in applications, On estimation of isotonic piecewise constant signals, Adaptive risk bounds in unimodal regression, Optimal rates of statistical seriation, An \(O(n)\) algorithm for weighted least squares regression by integer quasi-convex and unimodal or umbrella functions, Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance

Cites Work

• Isotone optimization. II
• Algorithms for a class of isotonic regression problems
• Isotone optimization. I
• Efficient computation of an isotonic median regression
• Algorithm AS 257: Isotonic Regression for Umbrella Orderings
• An Empirical Distribution Function for Sampling with Incomplete Information
• Isotonic Median Regression: A Linear Programming Approach
• Subset Selection with Additional Order Information
• On Estimating Monotone Parameters
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item