An O(n) algorithm for least squares quasi-convex approximation
type: Item
instance of: scholarly article
title: An O(n) algorithm for least squares quasi-convex approximation
zbMATH Open document ID: 0635.65009
DOI: 10.1016/0898-1221(87)90185-4
author: V. A. Ubhaya
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 62J02
zbMATH DE Number: 4034961
zbMATH Keywords: least squares distance function
zbMATH Keywords: curve fitting
zbMATH Keywords: statistical estimation
zbMATH Keywords: quasi-convex function
zbMATH Keywords: weight function
zbMATH Keywords: worst-case time complexity
zbMATH Keywords: best fit
zbMATH Keywords: parametric form
reviewed by: H. P. Dikshit
MaRDI profile type: Publication
full work available at URL: 0898-1221(87)90185-4
OpenAlex ID: W2072729993
cites work: Seven Kinds of Convexity
cites work: Q4773298
cites work: Q3341651
cites work: Note—A Note on Least Squares Fitting of Functions Constrained to be Either Nonnegative, Nondecreasing or Convex
cites work: Consistency in concave regression
cites work: Point Estimates of Ordinates of Concave Functions
cites work: Technical Note—On the Estimation of Convex Functions
cites work: An O(n) algorithm for discrete n-point convex approximation with applications to continuous case
cites work: Lipschitz condition in minimum norm problems on bounded functions
cites work: Q5658961
cites work: Least-Squares Fitting by Monotonic Functions Having Integer Values
cites work: Nonmetric multidimensional scaling. A numerical method
cites work: O(n) algorithms for discrete n-point approximation by quasi-convex functions
cites work: Quasi-convex optimization
cites work: Optimal Lipschitzian selection operator in quasi-convex optimization
cites work: Uniform approximation by quasi-convex and convex functions
cites work: Q3319751
cites work: A simple optimal control problem involving approximation by monotone functions
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Q3992847
cites work: Q5538132
published in: Computers & Mathematics with Applications
Recommended article: O(n) algorithms for discrete n-point approximation by quasi-convex functions
Recommended article: Algorithms for quasiconvex minimization
Recommended article: An efficient algorithm for convex quadratic semi-definite optimization
Recommended article: An Efficient Algorithm for the Classical Least Squares Approximation
Recommended article: A more efficient algorithm for convex nonparametric least squares
Recommended article: Approximation algorithms for quadratic programming
Recommended article: A quadratically convergent algorithm for structured low-rank approximation
Recommended article: A new complexity bound for the least-squares problem
Recommended article: Q4464624
description: scientific article; zbMATH DE number 4034961