Estimating the extrema of noisy curves and optimization using spline surface approximation

Estimating maxima and minima of a noisy curve turns out to be very hard and to a large part is still an open question. In this blog post we will discover some strategies to encounter the problem. Another interpretation is given in the context of optimization. Consider an optimization problem where the (smooth) objective function is only evaluated at some, maybe random and noisy, points or due to computational issues can only be sparsely evaluated. Then this algorithm will give a fast estimate of the optimal values.

1. Estimation based on Splines

We assume that a smooth at least two times differentiable curve is observed at independent randomly-distributed points contaminated with additional noise. Our model is then given by

(1)

where are i.i.d. random variables with , and is independent of . Our goal is to determine all such that the derivative

(2)

1.1 Natural cubic splines

Consider the following minimization problem, among all functions with two continuous derivatives find such that

(3)

is minimized. where is a fixed smoothing parameter and . It can be shown [1], that (3) has an unique minimizer which is a particular natural cubic spline. More generally a natural cubic spline with knots is a piecewise polynomial of order 4, with additional constrains such that the the function is linear beyond the boundary knots, represented with Basis functions . When the knots are given by the natural cubic spines solves (3) in that case an optimal solution for 3 is given by .

Let

the solution to the minimization problem using is thus given by

(4)

A popular basis choice is derived from the truncated power series and given by

(5)

where

(6)

We will use this basis as illustration for our method from here on. An important inside is that for a fixed interval limited by the nodes , can be represented using a cubic function (see [2]). In particular

(7)

Accordingly,

(8)

For , the real possible extrema of are thus given by

(9)

this will then be an extrema of if and .

1.2 Estimation and Asymptotic

To estimate the extrema we replace the spline coefficients by , their estimated counterpart, as specified in (4) to derive and according to (8) and (9). First verify that for fixed ,

(10)

and

(11)

therefore

(12)

(13)

(14)

where , ,.

After using a Taylor (see here for example) expansion and some calculus we can derive

(15)

The first order Taylor expansion of the variance is given by

(16)

where

(17)

(18)

(19)

(20)

2. White noise representation

The white noise version, as descibed in [3], of (1) is

(21)

where the noise term can be interpreted as and is the error variance when the design point equals , and can be figuratively represented as a ‘derivative’ of standard Brownian motion, in the sense
that .

In the white noise case, the corresponding equivalent basis to is given by with the knot density then

(22)

Then the continuous analogue to (8) is given by

(23)

(24)

(25)

Accordingly is an extrema of if and only if

(26)

therefore an extrema is observed if is a fix point.

[1] P. Craven and G. Wahba, “Smoothing noisy data with spline functions,” Numerische mathematik, vol. 31, pp. 377-403, 1978.
[Bibtex]
@article{Wahba1979,
title={Smoothing noisy data with spline functions},
author={Peter Craven and Grace Wahba},
journal={Numerische Mathematik},
year={1978},
volume={31},
pages={377-403}
}
[2] C. H. Reinsch, “Smoothing by spline functions,” Numerische mathematik, vol. 10, pp. 177-183, 1967.
[Bibtex]
@article{Reinsch1967,
title={Smoothing by spline functions},
author={Christian H. Reinsch},
journal={Numerische Mathematik},
year={1967},
volume={10},
pages={177-183}
}
[3] P. Hall and J. D. Opsomer, “Theory for penalised spline regression,” Biometrika, vol. 92, iss. 1, p. 105–118, 2005.
[Bibtex]
@article{Hall92,
ISSN = {00063444},
URL = {http://www.jstor.org/stable/20441169},
abstract = {Penalised spline regression is a popular new approach to smoothing, but its theoretical properties are not yet well understood. In this paper, mean squared error expressions and consistency results are derived by using a white-noise model representation for the estimator. The effect of the penalty on the bias and variance of the estimator is discussed, both for general splines and for the case of polynomial splines. The penalised spline regression estimator is shown to achieve the optimal nonparametric convergence rate established by Stone (1982).},
author = {Peter Hall and J. D. Opsomer},
journal = {Biometrika},
number = {1},
pages = {105--118},
publisher = {[Oxford University Press, Biometrika Trust]},
title = {Theory for Penalised Spline Regression},
urldate = {2022-04-16},
volume = {92},
year = {2005}
}

This site uses Akismet to reduce spam. Learn how your comment data is processed.