IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v53y2008i2p289-297.html
   My bibliography  Save this article

Unimodal regression via prefix isotonic regression

Author

Listed:
  • Stout, Quentin F.

Abstract

This paper gives algorithms for determining real-valued univariate unimodal regressions, that is, for determining the optimal regression which is increasing and then decreasing. Such regressions arise in a wide variety of applications. They are shape-constrained nonparametric regressions, closely related to isotonic regression. For unimodal regression on n weighted points our algorithm for the L2 metric requires only [Theta](n) time, while for the L1 metric it requires time. For unweighted points our algorithm for the L[infinity] metric requires only [Theta](n) time. All of these times are optimal. Previous algorithms were for the L2 metric and required [Omega](n2) time. All previous algorithms used multiple calls to isotonic regression, and our major contribution is to organize these into a prefix isotonic regression, determining the regression on all initial segments. The prefix approach reduces the total time required by utilizing the solution for one initial segment to solve the next.

Suggested Citation

  • Stout, Quentin F., 2008. "Unimodal regression via prefix isotonic regression," Computational Statistics & Data Analysis, Elsevier, vol. 53(2), pages 289-297, December.
    • Handle: RePEc:eee:csdana:v:53:y:2008:i:2:p:289-297
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167-9473(08)00396-4
    Download Restriction: Full text for ScienceDirect subscribers only.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Qian, Shixian, 1996. "An algorithm for tree-ordered isotonic median regression," Statistics & Probability Letters, Elsevier, vol. 27(3), pages 195-199, April.
    2. Ravindra K. Ahuja & James B. Orlin, 2001. "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints," Operations Research, INFORMS, vol. 49(5), pages 784-789, October.
    3. Zhi Geng & Ning‐Zhong Shi, 1990. "Isotonic Regression for Umbrella Orderings," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 39(3), pages 397-402, November.
    4. Turner, T. R. & Wollan, P. C., 1997. "Locating a maximum using isotonic regression," Computational Statistics & Data Analysis, Elsevier, vol. 25(3), pages 305-320, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Feng, Oliver Y. & Chen, Yining & Han, Qiyang & Carroll, Raymond J & Samworth, Richard J., 2022. "Nonparametric, tuning-free estimation of S-shaped functions," LSE Research Online Documents on Economics 111889, London School of Economics and Political Science, LSE Library.
    2. Cui, Zhenyu & Lee, Chihoon & Zhu, Lingjiong & Zhu, Yunfan, 2021. "Non-convex isotonic regression via the Myersonian approach," Statistics & Probability Letters, Elsevier, vol. 179(C).
    3. Oliver Y. Feng & Yining Chen & Qiyang Han & Raymond J. Carroll & Richard J. Samworth, 2022. "Nonparametric, tuning‐free estimation of S‐shaped functions," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(4), pages 1324-1352, September.
    4. Quentin F. Stout, 2012. "Strict L∞ Isotonic Regression," Journal of Optimization Theory and Applications, Springer, vol. 152(1), pages 121-135, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cui, Zhenyu & Lee, Chihoon & Zhu, Lingjiong & Zhu, Yunfan, 2021. "Non-convex isotonic regression via the Myersonian approach," Statistics & Probability Letters, Elsevier, vol. 179(C).
    2. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    3. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    4. Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.
    5. David Wu & Viet Hung Nguyen & Michel Minoux & Hai Tran, 2022. "Optimal deterministic and robust selection of electricity contracts," Journal of Global Optimization, Springer, vol. 82(4), pages 993-1013, April.
    6. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    7. Ravindra K. Ahuja & James B. Orlin, 2001. "Inverse Optimization," Operations Research, INFORMS, vol. 49(5), pages 771-783, October.
    8. Ravindra K. Ahuja & Dorit S. Hochbaum & James B. Orlin, 2003. "Solving the Convex Cost Integer Dual Network Flow Problem," Management Science, INFORMS, vol. 49(7), pages 950-964, July.
    9. T. Ibaraki & S. Imahori & M. Kubo & T. Masuda & T. Uno & M. Yagiura, 2005. "Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints," Transportation Science, INFORMS, vol. 39(2), pages 206-232, May.
    10. Wojciech Gamrot, 2013. "Maximum likelihood estimation for ordered expectations of correlated binary variables," Statistical Papers, Springer, vol. 54(3), pages 727-739, August.
    11. Turner, T. R. & Wollan, P. C., 1997. "Locating a maximum using isotonic regression," Computational Statistics & Data Analysis, Elsevier, vol. 25(3), pages 305-320, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:53:y:2008:i:2:p:289-297. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.