SCIENCE@home

Optimal Reduced Isotonic Regression

J. Hardwick,Q. Stout

Published 2014 in arXiv.org

ABSTRACT

Isotonic regression is a shape-constrained nonparametric regression in which the regression is an increasing step function. For $n$ data points, the number of steps in the isotonic regression may be as large as $n$. As a result, standard isotonic regression has been criticized as overfitting the data or making the representation too complicated. So-called "reduced" isotonic regression constrains the outcome to be a specified number of steps $b$, $b \leq n$. However, because the previous algorithms for finding the reduced $L_2$ regression took $\Theta(n+bm^2)$ time, where $m$ is the number of steps of the unconstrained isotonic regression, researchers felt that the algorithms were too slow and instead used approximations. Other researchers had results that were approximations because they used a greedy top-down approach. Here we give an algorithm to find an exact solution in $\Theta(n+bm)$ time, and a simpler algorithm taking $\Theta(n+b m \log m)$ time. These algorithms also determine optimal $k$-means clustering of weighted 1-dimensional data.

PUBLICATION RECORD

  • Publication year

    2014

  • Venue

    arXiv.org

  • Publication date

    2014-12-08

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1412.2844
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY