 A O(n) algorithm for the discrete best L4 monotonic approximation problemI.C. Demetriou Econometrics and Statistics, 2021, vol. 17, issue C, 130-144 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. Keywords: Algorithm; Approximation; Data smoothing; First differences; Isotonic regression; L4 norm; Monotonic (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ecosta:v:17:y:2021:i:c:p:130-144 DOI: 10.1016/j.ecosta.2020.04.002 Access Statistics for this article Econometrics and Statistics is currently edited by E.J. Kontoghiorghes, H. Van Dijk and A.M. Colubi More articles in Econometrics and Statistics from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.