The Minimum Sum of Squares Change to Univariate Data that gives Convexity

Let n measurements of a real valued function of one variablebe given. If the function is convex but the data have lost convexitydue to the errors of the measuring process, then the least sumof squares change to the data that provides nonnegative seconddivided differences may be required. An algorithm is proposedfor this highly structured quadratic programming calculation.First a procedure that requires only O(n) computer operationsgenerates a starting point for the main calculation, and thena version of the iterative method of Goldfarb & Idnani (1983)is applied. It is proved that the algorithm converges, the analysisbeing a special case of the theory of Goldfarb & Idnani.The algorithm is efficient because the matrices that occur arebanded due to representing the required fit as a linear combinationof B-splines. Some numerical results illustrate the method.They suggest that the algorithm can be used when n is very large,because the O(n) starting procedure identifies most of the convexityconstraints that are active at the solution.