Lipschitz unimodal and isotonic regression on paths and trees

DOI10.1007/978-3-642-12200-2_34MaRDI QIDQ3557035zbMATH OpenOpenAlexFDO

Authors Jeff M. Phillips, Bardia Sadri, Pankaj K. Agarwal

Publication date 27 April 2010

Published in LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.5182

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: We describe algorithms for finding the regression of t, a sequence of values, to the closest sequence s by mean squared error, so that s is always increasing (isotonicity) and so the values of two consecutive points do not increase by too much (Lipschitz). The isotonicity constraint can be replaced with a unimodular constraint, where there is exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each scenario we describe near-linear time algorithms.

Recommendations

• Linear time isotonic and unimodal regression in the \(L_{1}\) and \(L_{\infty }\) norms
• Unimodal regression via prefix isotonic regression
• Isotonic regression via partitioning
• Strict \(L_{\infty }\) isotonic regression
• Weighted \(L_{\infty}\) isotonic regression

Cited in

(5)

• Isotonic regression under Lipschitz constraint
• Unimodal regression via prefix isotonic regression
• Weighted \(L_{\infty}\) isotonic regression
• Fluctuated fitting under the \(\ell _1\)-metric
• Linear time isotonic and unimodal regression in the \(L_{1}\) and \(L_{\infty }\) norms

This page was built for publication: Lipschitz unimodal and isotonic regression on paths and trees

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