A polynomial algorithm on computing LAD splines. (English) Zbl 0748.65012

Li, Wei; Li, Xiamping; Asano, Chooichiro

Mem. Fac. Sci., Kyushu Univ., Ser. A 45, No. 2, 309-322 (1991).

Summary: The authors prove that least absolute deviations (LAD) splines can be calculated by solving a specific convex quadratic programming problem. A polynomial time algorithm, which requires no more than \(O(n^ 3L)\) arithmetic operations, is designed to solve this programming problem. The algorithm is taken into practice successfully on an IBM personal computer with Turbo Pascal. By comparing with least squares deviations splines, the paper shows that the method of smoothing statistical data with LAD splines is more robust and effective.

MSC:

65D07	Numerical computation using splines
65K05	Numerical mathematical programming methods
65D10	Numerical smoothing, curve fitting
65C99	Probabilistic methods, stochastic differential equations
90C20	Quadratic programming
90C25	Convex programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C60	Abstract computational complexity for mathematical programming problems
90C90	Applications of mathematical programming

Keywords:

statistical data smoothing; least absolute deviations splines; convex quadratic programming; polynomial time algorithm; least squares deviations splines; LAD splines

Software:

Turbo Pascal