An Efficient Algorithm for Generating Univariate Cubic L 1 Splines

An active set based algorithm for calculating the coefficients of univariate cubic L ₁ splines is developed. It decomposes the original problem in a geometric-programming setting into independent optimization problems of smaller sizes. This algorithm requires only simple algebraic operations to obtain an exact optimal solution in a finite number of iterations. In stability and computational efficiency, the algorithm outperforms a currently widely used discretization-based primal affine algorithm.