A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines

We consider least-squares approximation of a function of one variable by a continuous, piecewise-linear approxim-and that has a small number of breakpoints. This problem was notably considered by Bellman who proposed an approximate algorithm based on dynamic programming. Many suboptimal approaches have been suggested, but so far, the only exact methods resort to mixed integer programming with superpolynomial complexity growth. In this paper, we present an exact and efficient algorithm based on dynamic programming with a hybrid value function. Empirical evidence suggest that the algorithm has a polynomial time complexity.

I. Introduction

A classic optimization problem, is that of approximating a function of one variable by a piecewise-linear approximand with a small number of breakpoints, that should be selected from a given set (see Fig. 1). While this problem has been studied extensively, we are not aware of any previous approach that efficiently finds an approximand that is optimal in 2-norm, continuous, and which may take arbitrary values at the breakpoints.