An O(n) O ( n ) algorithm for weighted least squares regression by integer quasi-convex and unimodal or umbrella functions
The problem of fitting n n data points by an integer quasi-convex (also quasi-concave, umbrella or unimodal) function using the weighted least squares distance function is considered. An algorithm of linear time (O(n) O ( n ) ) worst-case complexity and thus optimal is constructed for computing a best fit. This problem arises in the context of curve fitting or statistical estimation.
least squares regression integer quasi-convex regression integer unimodal regression integer umbrella regression umbrella ordering isotonic regression linear time algorithms greatest convex minorant (gcm) least concave majorant (lcm)