An O(n) algorithm for least squares quasi-convex approximation (Q1097626)

Denoting a function f on \(S=\{1,2,...,n\}\), \(n>1\), by \((f_ 1,f_ 2,...,f_ n)\), we say that f is quasi-convex if \(f_ j\leq \max \{f_ p,f_ q\}\), holds for all j with \(p\leq j\leq q\) for all \(1\leq p\leq q\leq n\) [cf. \textit{J. Ponstein}, SIAM Rev. 9, 115-119 (1967; Zbl 0164.065)]. The author studies here the problem of finding a quasi-convex function g corresponding to a given f so as to minimize \(\sum^{n}_{i=1}w_ i(f_ i-g_ i)^ 2\) where w is the weight function with \((w_ 1,w_ 2,...,w_ n)>0\). An algorithm of O(n) worst-case time complexity for computing a best fit is developed. Such problems arise in the analysis of the functional relationship between dependent and independent variables where the existence of any definite parametric form of relationship is not known.