[size=+1]
The Savitzky-Golay Algorithm[/size]
In 1964,
Abraham Savitzky and Marcel J E Golay published a paper that began by reviewing a variety of different methods for smoothing and differentiation of time series. They then confined their attention to one particular method (which is now known as the Savitzky-Golay algorithm, even though they didn't invent it), and described their clever technique for implementing that method (which is also known as the Savitzky-Golay algorithm).
To keep those two things straight, I'll refer to the method they implemented as Savitzky-Golay smoothing/differentiation, and I'll refer to their technique for implementing that method as the Savitzky-Golay implementation technique, or as Savitzky-Golay convolution.
[size=+1]
Savitzky-Golay Smoothing/Differentiation[/size]
Savitzky-Golay smoothing is one member of the infinite family of smoothing methods that replaces each point of a time series by a smoothed point computed as follows:
- Select a window (neighborhood) surrounding the point.
- For some parameterized function (such as a polynomial of degree n), determine the parameters for which the function best fits the points within the window.
- Using those parameters, calculate the value of the function at the point. That is the smoothed value.
Different methods use different windows, different kinds of parameterized functions, and different notions of best fit.
For each method of that family, the value of the kth derivative at each point can be estimated by computing the value of the kth derivative of the best-fit function at each point.
With Savitzky-Golay smoothing/differentiation:
- The window is symmetrical about the point to be smoothed, with an odd number of points in the window.
- The parameterized function is a polynomial of some degree n.
- The best-fitting polynomial is defined as the one that minimizes the equally weighted sum of squared errors at each point within the window.
Savitzky-Golay smoothing/differentiation is popular because those are often good choices. Polynomials and their derivatives have obvious physical interpretations for position, velocity, and acceleration. Minimization of least squares is a familiar and convenient technique with pleasant mathematical and computational properties.
For many applications, the most questionable choice is the decision to give equal weight to the squared error at each point. Most methods give less weight to the error at points farther away from the center of the window.
Some of the engineers here would understand this better than I, but I am told that giving equal weight to the squared error at each point yields a fairly flat frequency response within a range determined by the width of the window.
On the other hand, this feature of Savitzky-Golay smoothing may give too much influence to outliers or noise at the extremes of a window. It also creates lag when wide windows are used to smooth a time series for position that may have resulted from sudden changes in acceleration.
That could be of concern when analyzing video of building collapses. To find out whether it's a problem, we'd have to understand the purposes of the analysis.
[size=+1]
Savitzky-Golay Convolution[/size]
Although weighting the square error at each point
equally may be questionable, it allowed Savitzky and Golay to implement the method more efficiently.
Savitzky and Golay noticed that finding the coefficients of the polynomial of degree n that minimizes the sum of squared errors over a window of width w is equivalent to computing n+1 convolutions, each of length w, using convolution coefficients that depend only on n and w.
These convolution coefficients can be computed ahead of time. For an example of how these convolution coefficients are derived, see
Wikipedia's current article on numerical smoothing and differentiation.
All desired derivatives at the point can be computed directly from the smoothing polynomial's coefficients. That takes O

time for each derivative.
As an alternative, the desired derivatives can be computed via convolutions, with convolution coefficients calculated ahead of time as for the smoothing polynomial. That takes O(w) time for each derivative, so this alternative technique is competitive when windows are small.
The Savitzky-Golay paper contains tables showing the values of these convolution coefficients for windows with up to 25 points, smoothing polynomials of degree up to 6, and derivatives up to the fifth derivative.
Savitzky and Golay also pointed out that these convolutions can be performed using integer arithmetic, followed by just one division for each convolution.
In 1964, that was hugely important. On most machines of that time, floating point arithmetic was several orders of magnitude slower than integer arithmetic.
On modern computers, floating point arithmetic is just about as fast as integer arithmetic, so that advantage of Savitzky-Golay convolution has disappeared.
For small windows, the precomputed convolution coefficients should still make Savitzky-Golay convolution run faster than minimizing the sum of squared errors, especially if you're calculating only the smoothed time series and a couple of derivatives.
As the window size increases, Savitzky-Golay convolution takes longer. Using separate convolutions for each derivative also takes longer, but that implementation technique is optional even if the smoothing polynomial is calculated via Savitzky-Golay convolution.
Minimizing the sum of squared errors might well be faster for large windows, because the sums needed for minimization can be computed in constant time (independent of the window size) as rolling
averages sums. In addition, for sufficiently large windows, differentiating and evaluating polynomials will be faster than using Savitzky-Golay convolutions to compute those derivatives.
[size=+1]
Simple Implementation of Savitzky-Golay Smoothing/Differentiation[/size]
In 1964, the world's fastest computer was about ten thousand times as slow as the laptop I'm using today.
I implemented Savitzky-Golay smoothing/differentiation by minimizing the sum of squared errors and computing all non-trivial derivatives of the best-fit polynomial.
My implementation might run slower than Savitzky-Golay convolution, but it produces exactly the same results (up to roundoff error). My code was able to take advantage of existing libraries for computing best-fit polynomials, and it shouldn't be hard to change my code to support more sophisticated methods that give less weight to errors farther away from the central point.