Smoothing splines for discontinuous signals

Smoothing splines are standard methods of nonparametric regression for obtaining smooth functions from noisy observations. But as splines are twice differentiable by construction, they cannot capture potential discontinuities in the underlying signal. The smoothing spline model can be augmented such that discontinuities at a priori unknown locations are incorporated. The augmented model results in a minimization problem with respect to discontinuity locations. The minimizing solution is a cubic smoothing spline with discontinuities (CSSD) which may serve as function estimator for discontinuous signals, as a changepoint detector, and as a tool for exploratory data analysis. However, these applications are hardly accessible at the moment because there is no efficient algorithm for computing a CSSD. In this paper, we propose an efficient algorithm that computes a global minimizer of the underlying problem. Its worst case complexity is quadratic in the number of data points. If the number of detected discontinuities scales linearly with the signal length, we observe linear growth of the runtime. By the proposed algorithm, a CSSD can be computed in reasonable time on standard hardware. Furthermore, we implement a strategy for automatic selection of the hyperparameters. Numerical examples demonstrate the applicability of a CSSD for the tasks mentioned above.