IDEAS home Printed from https://ideas.repec.org/a/eee/ecosta/v17y2021icp130-144.html
   My bibliography  Save this article

A O(n) algorithm for the discrete best L4 monotonic approximation problem

Author

Listed:
  • Demetriou, I.C.

Abstract

An approximation to discrete noisy data is constructed that obtains monotonicity. Precisely, we address the problem of making the least sum of 4th powers change to the data that provides nonnegative first differences. An algorithm is proposed for this highly structured strictly convex programming calculation that includes the method of van Eeden. The algorithm generates the solution in n−1 steps by identifying the subset of the constraints that are satisfied as equations, where n is the number of data. By using suitable arrays, the algorithm reduces the amount of work in a way that takes advantage of the fact that the solution consists of sets of equal components, calculates the equal components for each set by solving a cubic equation and, effectively updates the arrays to the next one. It is proved that the work of each step of the algorithm amounts to O(1) computer operations and at most one cubic root extraction. Some numerical experiments with synthetic and real data show that the algorithm is extremely fast.

Suggested Citation

  • Demetriou, I.C., 2021. "A O(n) algorithm for the discrete best L4 monotonic approximation problem," Econometrics and Statistics, Elsevier, vol. 17(C), pages 130-144.
    • Handle: RePEc:eee:ecosta:v:17:y:2021:i:c:p:130-144
    DOI: 10.1016/j.ecosta.2020.04.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2452306220300393
    Download Restriction: Full text for ScienceDirect subscribers only. Contains open access articles
    File URL: https://libkey.io/10.1016/j.ecosta.2020.04.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Ioannis C. Demetriou, 2019. "A Decomposition Theorem for the Least Squares Piecewise Monotonic Data Approximation Problem," Springer Optimization and Its Applications, in: Ioannis C. Demetriou & Panos M. Pardalos (ed.), Approximation and Optimization, pages 119-134, Springer.
    2. J. Kruskal, 1964. "Nonmetric multidimensional scaling: A numerical method," Psychometrika, Springer;The Psychometric Society, vol. 29(2), pages 115-129, June.
    Full references (including those not matched with items on IDEAS)

    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. Beniaich, Adnane & Guimarães, Danielle Vieira & Avanzi, Junior Cesar & Silva, Bruno Montoani & Acuña-Guzman, Salvador Francisco & dos Santos, Wharley Pereira & Silva, Marx Leandro Naves, 2023. "Spontaneous vegetation as an alternative to cover crops in olive orchards reduces water erosion and improves soil physical properties under tropical conditions," Agricultural Water Management, Elsevier, vol. 279(C).
    2. Giuseppe Arbia & Giovanni Lafratta, 2002. "Anisotropic spatial sampling designs for urban pollution," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 51(2), pages 223-234, May.
    3. Samuel Shye, 2010. "The Motivation to Volunteer: A Systemic Quality of Life Theory," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 98(2), pages 183-200, September.
    4. Muñoz-Mas, Rafael & Vezza, Paolo & Alcaraz-Hernández, Juan Diego & Martínez-Capel, Francisco, 2016. "Risk of invasion predicted with support vector machines: A case study on northern pike (Esox Lucius, L.) and bleak (Alburnus alburnus, L.)," Ecological Modelling, Elsevier, vol. 342(C), pages 123-134.
    5. la Grange, Anthony & le Roux, Niël & Gardner-Lubbe, Sugnet, 2009. "BiplotGUI: Interactive Biplots in R," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 30(i12).
    6. Simensen, Trond & Halvorsen, Rune & Erikstad, Lars, 2018. "Methods for landscape characterisation and mapping: A systematic review," Land Use Policy, Elsevier, vol. 75(C), pages 557-569.
    7. Silvia Vilčeková & Ilija Zoran Apostoloski & Ľudmila Mečiarová & Eva Krídlová Burdová & Jozef Kiseľák, 2017. "Investigation of Indoor Air Quality in Houses of Macedonia," IJERPH, MDPI, vol. 14(1), pages 1-12, January.
    8. Funk, Patrick & Davis, Alex & Vaishnav, Parth & Dewitt, Barry & Fuchs, Erica, 2020. "Individual inconsistency and aggregate rationality: Overcoming inconsistencies in expert judgment at the technical frontier," Technological Forecasting and Social Change, Elsevier, vol. 155(C).
    9. Moris Triventi, 2014. "Higher education regimes: an empirical classification of higher education systems and its relationship with student accessibility," Quality & Quantity: International Journal of Methodology, Springer, vol. 48(3), pages 1685-1703, May.
    10. Jessica Dafflon & Pedro F. Da Costa & František Váša & Ricardo Pio Monti & Danilo Bzdok & Peter J. Hellyer & Federico Turkheimer & Jonathan Smallwood & Emily Jones & Robert Leech, 2022. "A guided multiverse study of neuroimaging analyses," Nature Communications, Nature, vol. 13(1), pages 1-13, December.
    11. Karim Abou-Moustafa & Frank P. Ferrie, 2018. "Local generalized quadratic distance metrics: application to the k-nearest neighbors classifier," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 12(2), pages 341-363, June.
    12. Camacho, Maximo & Perez-Quiros, Gabriel & Saiz, Lorena, 2006. "Are European business cycles close enough to be just one?," Journal of Economic Dynamics and Control, Elsevier, vol. 30(9-10), pages 1687-1706.
    13. Mingxu Zhao & Nalaka Geekiyanage & Jianchu Xu & Myo Myo Khin & Dian Ridwan Nurdiana & Ekananda Paudel & Rhett Daniel Harrison, 2015. "Structure of the Epiphyte Community in a Tropical Montane Forest in SW China," PLOS ONE, Public Library of Science, vol. 10(4), pages 1-19, April.
    14. Willem Heiser, 1991. "A generalized majorization method for least souares multidimensional scaling of pseudodistances that may be negative," Psychometrika, Springer;The Psychometric Society, vol. 56(1), pages 7-27, March.
    15. Luís Francisco Aguiar & Pedro C. Magalhães & Maria Joana Soares, 2010. "Synchronism in Electoral Cycles: How United are the United States?," NIPE Working Papers 17/2010, NIPE - Universidade do Minho.
    16. Janghyeok Yoon & Kwangsoo Kim, 2012. "Detecting signals of new technological opportunities using semantic patent analysis and outlier detection," Scientometrics, Springer;Akadémiai Kiadó, vol. 90(2), pages 445-461, February.
    17. Kennen, Jonathan G. & Kauffman, Leon J. & Ayers, Mark A. & Wolock, David M. & Colarullo, Susan J., 2008. "Use of an integrated flow model to estimate ecologically relevant hydrologic characteristics at stream biomonitoring sites," Ecological Modelling, Elsevier, vol. 211(1), pages 57-76.
    18. Sagarra, Marti & Mar-Molinero, Cecilio & Agasisti, Tommaso, 2017. "Exploring the efficiency of Mexican universities: Integrating Data Envelopment Analysis and Multidimensional Scaling," Omega, Elsevier, vol. 67(C), pages 123-133.
    19. José Luis Ortega Priego, 2003. "A Vector Space Model as a methodological approach to the Triple Helix dimensionality: A comparative study of Biology and Biomedicine Centres of two European National Research Councils from a Webometri," Scientometrics, Springer;Akadémiai Kiadó, vol. 58(2), pages 429-443, October.
    20. Jacques de Wet & Daniela Wetzelhütter & Johann Bacher, 2021. "Standardising the reproduction of Schwartz’s two-dimensional value space using multi-dimensional scaling and goodness-of-fit test procedures," Quality & Quantity: International Journal of Methodology, Springer, vol. 55(4), pages 1155-1179, August.

    More about this item

    Keywords

    Algorithm; Approximation; Data smoothing; First differences; Isotonic regression; L4 norm; Monotonic;
    All these keywords.

    JEL classification:

    • L4 - Industrial Organization - - Antitrust Issues and Policies

    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:ecosta:v:17:y:2021:i:c:p:130-144. 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: https://www.journals.elsevier.com/econometrics-and-statistics .

    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.