Smoothing splines for discontinuous signals
arXiv:2211.12785 · doi:10.1080/10618600.2023.2262000
Abstract
Smoothing splines are twice differentiable by construction, so they cannot capture potential discontinuities in the underlying signal. In this work, we consider a special case of the weak rod model of Blake and Zisserman (1987) that allows for discontinuities penalizing their number by a linear term. The corresponding estimates are cubic smoothing splines with discontinuities (CSSD) which serve as representations of piecewise smooth signals and facilitate exploratory data analysis. However, computing the estimates requires solving a non-convex optimization problem. So far, efficient and exact solvers exist only for a discrete approximation based on equidistantly sampled data. In this work, we propose an efficient solver for the continuous minimization problem with non-equidistantly sampled data. Its worst case complexity is quadratic in the number of data points, and if the number of detected discontinuities scales linearly with the signal length, we observe linear growth in runtime. This efficient algorithm allows to use cross validation for automatic selection of the hyperparameters within a reasonable time frame on standard hardware. We provide a reference implementation and supplementary material. We demonstrate the applicability of the approach for the aforementioned tasks using both simulated and real data.
References in corpus (13)
- Optimal detection of changepoints with a linear computational cost
- Selective review of offline change point detection methods
- Wild binary segmentation for multiple change-point detection
- An Algorithm for Optimal Partitioning of Data on an Interval
- Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
- Nonparametric maximum likelihood approach to multiple change-point problems
- Consistencies and rates of convergence of jump-penalized least squares estimators
- Jump-sparse and sparse recovery using Potts functionals
- Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals
- Segmentation of the mean of heteroscedastic data via cross-validation
- Mumford-Shah and Potts Regularization for Manifold-Valued Data with Applications to DTI and Q-Ball Imaging
- The L1-Potts functional for robust jump-sparse reconstruction
- Smoothing for signals with discontinuities using higher order Mumford-Shah models