World Scientific
  • Search
    Quick Search in Journals
    Access type:
    Quick Search anywhere
    Access type:
    Advanced Search
  • My Cart
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Browse the 2024 Asian Studies Catalogue!
No Access

An Active-Set-Based Recursive Approach for Solving Convex Isotonic Regression with Generalized Order Restrictions

    https://doi.org/10.1142/S0217595923500252Cited by:0 (Source: Crossref)
    Previous
    Next

    Abstract

    This paper studies the convex isotonic regression with generalized order restrictions induced by a directed tree. The proposed model covers various intriguing optimization problems with shape or order restrictions, including the generalized nearly isotonic optimization and the total variation on a tree. Inspired by the success of the pool-adjacent-violator algorithm and its active-set interpretation, we propose an active-set-based recursive approach for solving the underlying model. Unlike the brute-force approach that traverses an exponential number of possible active-set combinations, our algorithm has a polynomial time computational complexity under mild assumptions.

    References

    • Ayer, M, HD Brunk, GM Ewing, WT Reid and E Silverman (1955). An empirical distribution function for sampling with incomplete information. Annals of Mathematical Statistics, 26, 641–647. Crossref, Google Scholar
    • Barbero, A and S Sra (2018). Modular proximal optimization for multidimensional total-variation regularization. Journal of Machine Learning Research, 19, 1–82. Google Scholar
    • Bertsimas, D and JN Tsitsiklis (1997). Introduction to Linear Optimization. Belmont, MA: Athena Scientific. Google Scholar
    • Best, MJ and N Chakravarti (1990). Active set algorithms for isotonic regression: A unifying framework. Mathematical Programming, 47, 425–439. Crossref, Google Scholar
    • Best, MJ, N Chakravarti and VA Ubhaya (2000). Minimizing separable convex functions subject to simple chain constraints. SIAM Journal on Optimization, 10, 658–672. Crossref, Google Scholar
    • Brunk, HD (1955). Maximum likelihood estimates of monotone parameters. Annals of Mathematical Statistics, 26, 607–616. Crossref, Google Scholar
    • Chakravarti, N (1989). Isotonic median regression: A linear programming approach. Mathematics of Operation Research, 14, 303–308. Crossref, Google Scholar
    • Chakravarti, N (1992). Isotonic median regression for orders representable by rooted trees. Naval Research Logistics, 39, 599–611. Crossref, Google Scholar
    • Chang, X, YL Yu, Y Yang and EP Xing (2016). Semantic pooling for complex event analysis in untrimmed videos. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39, 1617–1732. Crossref, Google Scholar
    • Condat, L (2013). A direct algorithm for 1D total variation denoising. IEEE Signal Processing Letters, 20, 1054–1057. Crossref, Web of Science, Google Scholar
    • Deo, N (1974). Graph Theory with Applications to Engineering and Computer Science. Englewood Cliffs, NJ: Prentice Hall. Google Scholar
    • Frisen, M (1986). Unimodal regression. The Statistician, 35, 479–485. Crossref, Google Scholar
    • Höefling, H (2010). A path algorithm for the fused lasso signal approximator. Journal of Computational and Graphical Statistics, 19, 984–1006. Crossref, Web of Science, Google Scholar
    • Kolmogorov, V, T Pock and M Rolinek (2016). Total varaition on a tree. SIAM Journal on Imaging Sciences, 9, 605–636. Crossref, Google Scholar
    • Lu, C and DS Hochbaum (2022). A unified approach for a 1D generalized total variation problem. Mathematical Programming, 194, 415–442. Crossref, Web of Science, Google Scholar
    • Matyasovszky, I (2013). Estimating red noise spectra of climatological time series. Quarterly Journal of the Hungarian Meteorological Service, 117, 187–200. Google Scholar
    • Restrepo, A and AC Bovik (1993). Locally monotonic regression. IEEE Transactions on Signal Processing, 41, 2796–2810. Crossref, Google Scholar
    • Rockafellar, RT (1970). Convex Analysis. Princeton, NJ: Princeton University Press. Crossref, Google Scholar
    • Ryu, YU, R Chandrasekaran and V Jacob (2004). Prognosis using an isotonic prediction technique. Management Science, 50, 777–785. Crossref, Web of Science, Google Scholar
    • Silvapulle, MJ and PK Sen (2005). Constrained Statistical Inference: Inequality, Order and Shape Restrictions. John Wiley & Sons. Google Scholar
    • Stout, QF (2008). Unimodal regression via prefix isotonic regression. Computational Statistics & Data Analysis, 53, 289–297. Crossref, Web of Science, Google Scholar
    • Tibshirani, R, H Höefling and R Tibshirani (2011). Nearly-isotonic regression. Technometrics, 53, 54–61. Crossref, Web of Science, Google Scholar
    • West, DB (2001). Introduction to Graph Theory. Upper Saddle River, NJ: Prentice Hall. Google Scholar
    • Wu, C, J Thai, S Yadlowsky, A Pozdnoukhov and A Bayen (2015). Cellpath: Fusion of cellular and traffic sensor data for route flow estimation via convex optimization. Transportation Research Part C: Emerging Technologies, 59, 111–128. Crossref, Web of Science, Google Scholar
    • Yu, Z, X Chen and X Li (2023). A dynamic programming approach for generalized nearly isotonic regression. Mathematical Programming Computation, 15, 195–225. Crossref, Google Scholar
    • Yu, YL and EP Xing (2016). Exact algorithms for isotonic regression and related. Journal of Physics: Conference Series, 699. Google Scholar