Online Segmented Recursive Least Squares (OSRLS)

Shortly after R. Bellman developed the dynamic programming approach to sequential optimization, he provided an example of its use that is often referred to as segmented least squares (SLS), which finds the optimal segmentation of a series of data into piece-wise-linear segments in a non-recursive, hindsight manner in polynomial time. We extend SLS to its piece-wise-linear Markov signal modeling counterpart, and use this approach to develop a purely sequential prediction algorithm that performs nearly as well as the best piece-wise-linear Markov signal model determined in hindsight. We call this the online segmented recursive least squares (OSRLS) algorithm and demonstrate its performance for prediction of piecewise-stationary Gauss Markov signals. The OSRLS algorithm sequentially detects the regions over which the signal is piecewise-stationary through a recursive implementation of the SLS algorithm over past observations. The performance of OSRLS is compared with a traditional recursive least squares (RLS) and the batch (hindsight) segmented least squares solution on a synthetically generated piece-wise-stationary auto regressive model.