scipy: BUG: signal: numerically incorrect `savgol_coeffs` (and `savgol_filter`)
Basic Problem
When I ran a grid search for optimizing the Savitzky-Golay filter parameters, I found that for high polyorders, the coefficients from scipy.signal.savgol_coeffs are numerically incorrect (see Reproducing Example). It is very simple to check because the sum of the coefficients should be 1.0 (± numerical tolerance).
This also affects scipy.signal.savgol_filter because it calls scipy.signal.savgol_coeffs.
When does it occur?
I tested many window_length-polyorder-combinations and got the following plot where the circled area shows failed computations (the left dark-blue corner was not evaluated because the smoothing was not possible given too small windows for the polynomial):
For higher polyorders this happens for smaller window_lengths already. window_lengths > 100 are maybe not common, but also not completely unrealistic. For good smoothness - especially with the Savitzky-Golay filter that has the discontinuity of the filter coefficients at the edges that severely limits its noise suppression (sudden drop to 0 which is not C0- or higher -continuous) - higher polynomial degrees with long window_lengths are the better choice (actually, the plot also indicates that because the best solution is roughly window_length=95 for polyorder=9 which is only slightly better than window_length=55 for polyorder=5, but the first has way less residual noise because its filter edge discontinuity is less pronounced).
I also found the following StackExchange Question where this problem was already pointed out together with the fact that the Matlab implementation is still capable of computing the coefficients correctly.
What is the cause?
The problem is that np.linalg.lstsq is used to solve the unmodified Vandermonde-system of the polynomial fit in this block of scipy.signal.savgol_coeffs:
# Form the design matrix A. The columns of A are powers of the integers
# from -pos to window_length - pos - 1. The powers (i.e., rows) range
# from 0 to polyorder. (That is, A is a vandermonde matrix, but not
# necessarily square.)
x = np.arange(-pos, window_length - pos, dtype=float)
if use == "conv":
# Reverse so that result can be used in a convolution.
x = x[::-1]
order = np.arange(polyorder + 1).reshape(-1, 1)
A = x ** order
# y determines which order derivative is returned.
y = np.zeros(polyorder + 1)
# The coefficient assigned to y[deriv] scales the result to take into
# account the order of the derivative and the sample spacing.
y[deriv] = float_factorial(deriv) / (delta ** deriv)
# Find the least-squares solution of A*c = y
coeffs, _, _, _ = lstsq(A, y)
np.linalg.lstsq can basically cut out the singular values of an SVD of the Vandermonde-system. Since the matrix A becomes more and more ill-conditioned as polyorder and window_length increase, some singular values will drop below the zero-treshold which will trigger their removal. This is typical for polynomials since A can become imbalanced quite easily by the dominance of the high power terms.
So, A @ coeffs = y is not solved in a Least Squares sense anymore, but in a regularized Least Squares sense where coeffs with lower Euclidean norms are favoured. Such coeffs however do not sum up to 1.0 and the smoothing gets obscured.
How could this be solved?
I’m currently testing out multiple solutions like matrix balancing (probably called on LAPACK level for np.linalg.lstsq already) and normalization (mean subtraction and column scaling).
As a quick fix,
coeffs, _, _, _ = lstsq(A, y)
could be changed to
coeffs, _, rank, _ = lstsq(A, y)
if rank <= polyorder: # the actual check is rank < (polyorder + 1) to be more concise
warn("The linear system is badly conditioned, the coefficients might be incorrect.")
Of course, this does not really solve the problem, but warning the user reduces the risk of misuse.
Beyond Savitzky-Golay with ordinary polynomials (monomials), there could also be other basis functions as described in this post .
Reproducing Code Example
### Imports ###
import numpy as np
from scipy.signal import savgol_coeffs
### Working Example ###
# this works
assert np.isclose(
savgol_coeffs(
window_length=35,
polyorder=9,
).sum(),
1.0,
)
### Failure Case ###
# this fails because `window_length` is too big
assert np.isclose(
savgol_coeffs(
window_length=175,
polyorder=9,
).sum(),
1.0,
)
Error message
-
SciPy/NumPy/Python version and system information
The problem is still part of SciPy's current version 1.13.1 independent of NumPy and other system factors.
About this issue
- Original URL
- State: open
- Created 2 years ago
- Comments: 25 (8 by maintainers)
Just a note in passing: there are both kinds of mpmath usages in scipy tests, both calling mpmath routines in a test itself, and using mpmath to generate reference values.
For the former, here’s one example: https://github.com/scipy/scipy/blob/4b8ae1a7a8df1d7d2f061d8c77dcc70f1510ee71/scipy/signal/tests/test_filter_design.py#L1108
For the latter, here’s one somewhat related example: https://github.com/scipy/scipy/blob/4b8ae1a7a8df1d7d2f061d8c77dcc70f1510ee71/scipy/interpolate/_interpnd_info.py I’d imagine that depending on how large is the mpmath code, it may end up either as a separate file (make sure the file is not installed then, and reference the file in a comment from the test), or as a code comment in a test itself.