betaFeedback

WorksMathematics

Smoothing splines with some discontinuities

Abstract

We generalize cubic smoothing splines to signals with a finite number of discontinuities at unknown positions. Rather than changing the roughness penalty, we deform the domain over which it is computed: every interval between consecutive observations can be stretched by a non-negative warp, subject to a total budget, and the optimizer spends the budget only where a jump makes stretching cheaper than bending. The estimator inherits the state-space form of smoothing splines, so it can be fitted by maximum likelihood with the Kalman filter, and it also admits a fast alternating algorithm that solves a banded linear system and takes a projected-gradient step on the warps. The budget is selected by an extended Bayesian information criterion whose constant is calibrated by simulation. In a Monte Carlo comparison the new estimators reconstruct a piecewise-smooth signal more accurately than the cubic smoothing spline with discontinuities of Storath and Weinmann, at the cost of more false alarms. Two energy applications illustrate the method: the temperature response of electricity demand in Northern Italy, and retail fuel prices, whose discontinuities, changes in excise duties, are dated by public record. The three supplements follow the references.

main.pdf

Introduction

Data recorded over an ordered index often behave smoothly for long stretches punctuated by a handful of sharp, isolated changes: a policy shock in a price series, a phase transition in a physical process, a saturation threshold in a demand curve. Cubic smoothing splines [4] (Wecker and Ansley 1983), and their equivalent state-space signal-extraction formulation (Harvey and Koopman, 2000), recover the smooth part of such signals well, but they are twice continuously differentiable by construction: the roughness penalty that makes them smooth also prevents them from reproducing a discontinuity, which is either washed out over several observations or, if the penalty is relaxed everywhere, accommodated at the price of overfitting the noise elsewhere. What is needed is an estimator that is smooth almost everywhere and sharp exactly where the data demand it, without the analyst having to specify in advance where.

This paper proposes such an estimator. The idea is to leave the classical roughness penalty unchanged and to deform the domain over which it is computed. Every pair of consecutive observations is allowed a non-negative domain warp γi≥0\gamma_i \ge0, an amount of fictitious domain length inserted between them, subject to a total budget MM, and the roughness of the spline is penalized on the warped domain. Where the signal is smooth, warping buys nothing, the optimal γi\gamma_i is zero and the fit coincides with an ordinary smoothing spline. Where the signal jumps, the same vertical change can be spread over a longer warped interval at a much lower curvature cost, so the optimizer concentrates the budget on the few intervals where a jump is present. Strictly speaking, the fitted function remains continuous: it approximates a discontinuity much as a steep sigmoid approximates a step function. Because the mechanism is a reparameterization of the domain, the estimator inherits the state-space representation of smoothing splines, which we use for maximum likelihood estimation via the Kalman filter, and it also admits a fast alternating algorithm that avoids numerical likelihood maximization altogether.

The idea of penalizing discontinuities directly, rather than smoothing through them, goes back to the weak rod and weak plate models of Blake and Zisserman (1987) and to the Mumford–Shah functional (Mumford and Shah, 1989), which penalize the roughness of a piecewise-smooth function together with the number of its discontinuities and lead to a combinatorial search over candidate discontinuity sets. The estimator closest to ours, and our benchmark throughout, is the cubic smoothing spline with discontinuities (CSSD) of Storath and Weinmann (2024), which specializes the weak-rod functional to cubic splines and non-equidistant data and solves it exactly by dynamic programming. Wavelet shrinkage (Donoho and Johnstone, 1994) denoises jumpy signals by thresholding multiresolution coefficients, but it targets equidistant designs and does not produce a piecewise-smooth curve. The fused lasso (Tibshirani et al., 2005) and trend filtering (Kim et al., 2009; Tibshirani, 2014) penalize the ℓ1\ell_1 norm of successive differences of the fitted values or of their derivatives, a convex problem with automatic knot placement, but the knots are a by-product of a coefficient-level penalty rather than of an explicit, interpretable deformation. Free-knot splines (Koo, 1997) and two-stage procedures, which first locate breaks with a changepoint detector such as PELT (Killick et al., 2012) and then smooth between them, decouple detection from estimation. Our formulation keeps the roughness penalty unchanged and reparameterizes the metric in which it is computed, so that detection and estimation are solved jointly, through a single continuous, non-negative vector γ\gamma.

Section 2 introduces the domain-warping formulation, its state-space form, the alternating algorithm and the tuning of the method. Section 3 compares the estimators with CSSD and with a classical smoothing spline by Monte Carlo simulation, and Section 4 applies them to two energy-related data sets, chosen to cover the two kinds of data the method is meant for. The first application investigates the temperature response of electricity demand, a cross-sectional relation estimated on hourly observations ordered by temperature rather than by time, irregularly spaced and with many ties, whose discontinuities are thresholds of the physical system and are not known in advance. The second uses weekly time series of retail fuel prices, serially dependent and close to a stochastic trend, in which changes in the excise duty shift the level of the prices at dates that are a matter of public record, so that the estimated discontinuities can be checked against a ground truth that real data rarely offer. Section 5 concludes. Three supplements accompany the paper: the Computational Supplement collects derivations and implementation details, the Calibration Supplement the tuning of the method, and the Application Supplement additional results for the two applications.

Methodology

The main idea

Let (xi,yi)(x_i,y_i), i=1,…,ni=1,\ldots,n, be the observations, with x1<x2<⋯<xnx_1 < x_2 < \cdots< x_n, and let δi=xi+1−xi\delta_i = x_{i+1}-x_i be the length of the ii-th interval of the physical domain (i.e., the physical interval between consecutive knots). We introduce a vector of non-negative domain warps γ=(γ1,…,γn−1)T\boldsymbol{\gamma} = (\gamma_1,\ldots,\gamma_{n-1})^{\mathsf{T}} and define the length of the ii-th interval in a latent domain as τi=δi+γi\tau_i = \delta_i + \gamma_i.

If γi=0\gamma_i = 0 the physical and latent intervals coincide; if γi>0\gamma_i > 0 the interval [xi,xi+1)[x_i,x_{i+1}) is stretched. On each interval the function is a cubic polynomial fi(s)f_i(s) in the latent coordinate s∈[0,τi]s \in[0,\tau_i], which is linked to the physical coordinate by the linear dilation si(x)=(x−xi)(1+γi/δi)s_i(x) = (x-x_i)(1+\gamma_i/\delta_i), so that the function observed in the physical domain is f(x)=fi(si(x))f(x) = f_i(s_i(x)) for xi≤x<xi+1x_i \le x < x_{i+1}, $i=1,\ldots,n-1. A function that is smooth in the latent domain can thus be steep in the physical one: the dilation compresses a smooth latent transition into a short physical interval, where it appears as a jump if γi\gamma_i is large.

The estimator minimizes

J(f,γ)=∑i=1n(yi−f(xi))2+λ∑i=1n−1∫0τi(d2fi(s)ds2)2 dss.t.γi≥0,∑i=1n−1γi≤M,(1)J(f,\gamma)=\sum_{i=1}^{n}(y_i-f(x_i))^2+\lambda\sum_{i=1}^{n-1}\int_0^{\tau_i}\left(\frac{d^2f_i(s)}{ds^2}\right)^2\,ds \qquad\text{s.t.}\qquad\gamma_i\ge0,\quad\sum_{i=1}^{n-1}\gamma_i\le M, \tag*{(1)}

which balances the distance from the observations against the roughness of the function measured in the latent domain; λ\lambda is the smoothing constant and MM the warping budget.

The mechanism becomes transparent when one looks at the roughness penalty of a single interval, which we call its energy by analogy with the bending energy of an elastic beam. For a cubic segment covering a height difference Δi=fi+1−fi\Delta_i=f_{i+1}-f_i, the energy is dominated, for short intervals, by a proportional term such that

∫0τi(fi′′(s))2 ds∝(Δyi)2τi3=(Δyi)2(δi+γi)3\int_0^{\tau_i}(f_i''(s))^2\,ds \propto\frac{(\Delta y_i)^2}{\tau_i^3}=\frac{(\Delta y_i)^2}{(\delta_i+\gamma_i)^3}

(see § 2.1.2 and the exact statement is in § 6 of the Computational Supplement).

The key intuition behind the proposed approach is that a discontinuity is difficult for a classical cubic smoothing spline because the spline is forced to explain a large change in the response over a very short interval of the physical domain. On the one hand, in regions of discontinuity, if ∣Δyi∣\lvert\Delta y_i \rvert is large while δi\delta_i is small, the standard energy term would explode (→∞\to\infty); a large change over a short physical interval is therefore very expensive for an ordinary smoothing spline, which is forced to over-smooth it. Instead, our algorithm allocates a large positive γi\gamma_i that dilates the denominator (δi+γi)3(\delta_i+\gamma_i)^3 and lets the curve complete the same transition as a smooth, low-energy curve in the latent domain (the penalty cost is then drastically reduced), so that a discontinuity in the physical domain is represented as a smooth transition in a locally stretched domain (Figure 1). On the other hand, in regions of continuity where the signal evolves gradually, extra domain length brings little reduction of energy and the optimal γi\gamma_i stays at or near zero, the latent interval equals the physical interval (τi≈δi\tau_i \approx\delta_i), so that the fit behaves as a standard cubic smoothing spline. The budget constraint ∑i=1n−1γi≤M\sum_{i=1}^{n-1}\gamma_i \le M is what makes the solution sparse: it prevents the whole domain from being stretched uniformly and forces the warping onto the few intervals where it is most valuable, so that large values of γ^i\hat{\gamma}_i are data-driven indicators of jumps or sharp regime changes.

The design points are taken to be distinct. A tie would make δi\delta_i vanish, and with it the latent length of an interval that carries no warp, so that neither the roughness penalty of that interval nor the transition of the state-space form of § 2.1.1 would be defined; more fundamentally, a warp on an interval of zero length would be a discontinuity between responses recorded at the same value of the covariate, which no data can identify. Tied observations, common when the covariate is recorded at a coarse resolution, are therefore collapsed into their mean at each distinct value, weighted by the number of replicates. The reduction leaves the fitted curve unchanged, but the within-group scatter that it discards still informs the observation variance, and the information criterion of § 2.1.3 counts the candidate locations on the distinct values and the observations on the raw data (§ 11 of the Computational Supplement).

Domain warping: same observed values on the physical and latent warped domains

Figure 1. Domain warping. The same observations on the physical domain (a) and on the latent warped domain (b), at the same horizontal scale. Away from the jump the intervals are unchanged and the grey connectors are vertical; at the jump, positive warps stretch the interval (τi=δi+γi\tau_i = \delta_i + \gamma_i, in yellow, with a lighter stretching of the neighboring intervals in blue), so that the same vertical change is completed over a longer latent interval at a lower curvature cost. The latent domain is longer than the physical one by the total warping ∑iγi\sum_i \gamma_i.

A signal extraction formulation

Smoothing splines can also be obtained by signal extraction (Wahba, 1978; Wecker and Ansley, 1983): the cubic smoothing spline is f^t=E[f(xt)∣Y1=y1,…,Yn=yn]\hat{f}_t = \mathrm{E}[f(x_t) \mid Y_1 = y_1, \ldots, Y_n = y_n] when the data are generated by Yt=f(xt)+εtY_t = f(x_t) + \varepsilon_t, εt∼NID⁡(0,λσ2)\varepsilon_t \sim\operatorname{NID}(0,\lambda\sigma^2), d2f/dx2=σw(x)d^2f/dx^2 = \sigma w(x), with w(x)w(x) a continuous-time standard white noise and diffuse initial conditions for f(x1)f(x_1) and its derivative. This model has the state-space form (see, e.g., Harvey and Koopman, 2000)

Yt=f(xt)+εt,εt∼NID⁡(0,λσ2)Y_t = f(x_t) + \varepsilon_t,\quad\varepsilon_t \sim\operatorname{NID}(0,\lambda\sigma^2)
\begin{bmatrix} f(x_{t+1}) \\ f'(x_{t+1}) \end{bmatrix} = \begin{bmatrix} 1 & \delta_t \\ 0 & 1 \end{bmatrix} \begin{bmatrix} f(x_t) \\ f'(x_t) \end{bmatrix} + \begin{bmatrix} \eta_t \\ \zeta_t \end{bmatrix}, \quad \begin{bmatrix} \eta_t \\ \zeta_t \end{bmatrix} \sim\operatorname{NID}\left( \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \sigma^2 \begin{bmatrix} \delta_t^3/3 & \delta_t^2/2 \\ \delta_t^2/2 & \delta_t \end{bmatrix} \right) \tag*{(2)}\end{bmatrix}

with (f(x1),f′(x1))T∼N(0,κI2)(f(x_1),f'(x_1))^\mathsf{T} \sim\mathrm{N}(0,\kappa I_2), κ→∞\kappa\to\infty. The Kalman filter delivers the likelihood of (σ,λ)(\sigma,\lambda), and the state smoother the smoothing spline itself.

Adapting this representation to the latent domain only requires replacing the physical increments δt\delta_t with their warped counterparts τt=δt+γt\tau_t = \delta_t + \gamma_t. The likelihood is then maximized with respect to (σ,λ,γ1,…,γn−1)(\sigma,\lambda,\gamma_1,\ldots,\gamma_{n-1}) subject to γt≥0\gamma_t \ge0 and ∑tγt≤M\sum_t \gamma_t \le M, a problem for which the algorithm of Svanberg (2002), implemented in the NLopt library (Johnson, 2007), is effective. The analytical scores are available in closed form from one pass of the Kalman filter and smoother, so that a gradient of dimension n+1n+1 never has to be approximated by finite differences; for γt\gamma_t they contain an additional term, because γt\gamma_t enters the transition matrix as well as the disturbance covariance (§ 10 of the Computational Supplement). Since the likelihood is not convex, good starting values for γ\gamma are important, and values close to zero are generally a good choice. We call this estimator SSJ–MLE (smoothing splines with jumps, maximum likelihood); when λ\lambda is fixed at a supplied value and the likelihood is maximized with respect to the remaining parameters, we call it SSJ–KFS.

An alternating domain-warping algorithm

As an alternative to the numerical maximization of a non-convex likelihood, we minimize (1) for given λ\lambda and MM by block coordinate descent, alternating a spline step, in which γ\gamma is fixed and ff solves a convex quadratic problem, with a warping step, in which ff is fixed and γ\gamma takes a projected-gradient step. We call the resulting estimator SSJ–ATW (alternating domain warping). Each iteration costs O(nlog⁡n)O(n \log n) operations.

Spline step (ff-step). In this step, γ\gamma is fixed. Let z=(f1,f1′,f2,f2′,…,fn,fn′)Tz = (f_1,f'_1,f_2,f'_2,\ldots,f_n,f'_n)^\mathsf{T} collect the values and first derivatives of the function at the observations. By a well-known argument based on Hermite polynomials (see Section 2 of Dougherty et al., 1989), the energy of interval ii (i.e., the contribution of the interval ii to the total roughness energy) is the quadratic form

ki:=∫0τi(d2fi(s)ds2)2ds=viTKivi,vi=(fi,fi′,fi+1,fi+1′)T,(3)k_i := \int_0^{\tau_i} \left(\frac{d^2 f_i(s)}{ds^2}\right)^2 ds = v_i^\mathsf{T}K_i v_i,\qquad v_i = (f_i,f'_i,f_{i+1},f'_{i+1})^\mathsf{T}, \tag*{(3)}

with the local stiffness matrix

Ki=1τi3[126τi−126τi6τi4τi2−6τi2τi2−12−6τi12−6τi6τi2τi2−6τi4τi2]K_i = \frac{1}{\tau_i^3} \begin{bmatrix} 12 & 6\tau_i & -12 & 6\tau_i \\ 6\tau_i & 4\tau_i^2 & -6\tau_i & 2\tau_i^2 \\ -12 & -6\tau_i & 12 & -6\tau_i \\ 6\tau_i & 2\tau_i^2 & -6\tau_i & 4\tau_i^2 \end{bmatrix}

References

  1. [1]Chen, J. and Chen, Z. (2008), ‘Extended Bayesian information criteria for model selection with large model spaces’, Biometrika 95(3), 759–771.DOI
  2. [2]Maranzano, P. and Pelagatti, M. (2025), ‘A Hodrick–Prescott filter with automatically selected breaks’, Economic Modelling 150, 107132.DOI
  3. [3]Otto, P., Fassò, A. and Maranzano, P. (2024), ‘A review of regularised estimation methods and cross-validation in spatiotemporal statistics’, Statistics Surveys 18, 299–340. URL: https://doi.org/10.1214/24-SS150
  4. [4]Wahba, G. (1978), ‘Improper priors, spline smoothing and the problem of guarding against model errors in regression’, Journal of the Royal Statistical Society: Series B (Methodological) 40(3), 364–372.DOI

Paper details

vlnc:W_k8cmmebg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents