What Is the Relationship Between a Kalman Filter and Polynomial Regression?

Question

What is the relationship, if any, between Kalman filtering and (repeated, if necessary) least squares polynomial regression?

Answer 1

1. There is a Difference in terms of optimality criteria

Kalman filter is a Linear estimator. It is a linear optimal estimator - i.e. infers model parameters of interest from indirect, inaccurate and uncertain observations.

But optimal in what sense? If all noise is Gaussian, the Kalman filter minimizes the mean square error of the estimated parameters. This means, that when underlying noise is NOT Gaussian the promise no longer holds. In case of nonlinear dynamics, it is well-known that the problem of state estimation becomes difficult. In this context, no filtering scheme clearly outperforms all other strategies. In such case, Non-linear estimators may be better if they can better model the system with additional information. [See Ref 1-2]

Polynomial regression is a form of linear regression in which the relationship between the independent variable x and the dependent variable y is modeled as an nth order polynomial.

$$ Y = a_0 + a_1x + a_2x^2 + \epsilon $$

Note that, while polynomial regression fits a nonlinear model to the data, these models are all linear from the point of view of estimation, since the regression function is linear in terms of the unknown parameters $a_0, a_1, a_2$. If we treat $x, x^2$ as different variables, polynomial regression can also be treated as multiple linear regression.

Polynomial regression models are usually fit using the method of least squares. In the least squares method also, we minimize the mean squared error. The least-squares method minimizes the variance of the unbiased estimators of the coefficients, under the conditions of the Gauss–Markov theorem. This theorem, states that ordinary least squares (OLS) or linear least squares is the Best Linear Unbaised Estimator (BLUE) under following conditions:

a. when errors have expectation zero i.e. $E(e_i) = 0 $
b. have equal variances i.e. $ Variance(e_i) = \sigma^2 < \infty $
c. and errors are uncorrelated i.e. $ cov(e_i,e_j) = 0 $

NOTE: that here, errors don't have to be Gaussian nor need to be IID. It only needs to be uncorrelated.

2. Kalman Filter is an evolution of estimators from least square

In 1970, H. W. Sorenson published an IEEE Spectrum article titled "Least-squares estimation: from Gauss to Kalman." [See Ref 3.] This is a seminal paper that provides great insight about how Gauss' original idea of least squares to today's modern estimators like Kalman.

Gauss' work not only introduced the least square framework but it was actually one of the earliest work that used a probabilistic view. While least squares evolved in the form of various regression methods, there was another critical work that brought filter theory to be used as an estimator.

The theory of filtering to be used for stationary time series estimation was constructed by Norbert Wiener during 1940s (during WW-II) and published in 1949 which is now known as Wiener filter. The work was done much earlier, but was classified until well after World War II). The discrete-time equivalent of Wiener's work was derived independently by Kolmogorov and published in 1941. Hence the theory is often called the Wiener-Kolmogorov filtering theory.

Traditionally filters are designed for the desired frequency response. However, in case of Wiener filter, it reduces the amount of noise present in a signal by comparison with an estimation of the desired noiseless signal. Weiner filter is actually an estimator. In an important paper, however, Levinson (1947) [See Ref 6] showed that in discrete time, the entire theory could be reduced to least squares and so was mathematically very simple. See Ref 4

Thus, we can see that Weiner's work gave a new approach for estimation problem; an evolution from using least squares to another well-established filter theory. However, the critical limitation is that Wiener filter assumes the inputs are stationary. We can say that Kalman filter is a next step in the evolution which drops the stationary criteria. In Kalman filter, state space model can dynamically be adapted to deal with non-stationary nature of signal or system.

The Kalman filters are based on linear dynamic systems in discrete time domain. Hence it is capable of dealing with potentially time varying signal as opposed to Wiener. As the Sorenson's paper draws parallel between Gauss' least squares and Kalman filter as

...therefore, one sees that the basic assumption of Gauss and Kalman are identical except that later allows the state to change from one time to next. The difference introduces a non-trivial modification to Gauss' problem but one that can be treated within the least squares framework.

3. They are same as far as causality direction of prediction is concerned; besides implementation efficiency

Sometimes it is perceived that Kalman filter is used for prediction of future events based on past data where as regression or least squares does smoothing within end to end points. This is not really true. Readers should note that both the estimators (and almost all estimators you can think of) can do either job. You can apply Kalman filter to apply Kalman smoothing.

Similarly, regression based models can also be used for prediction. Given the training vector, $X_t$ and you applied $Y_t$ and discovered the model parameters $α_0 ... a_K$ now for another sample $X_k$ we can extrapolate $Y_K$ based on the model.

Hence, both methods can be used in the form of smoothing or fitting (non-causal) as well as for future predictions (causal case). However, the critical difference is the implementation which is significant. In case of polynomial regression - with entire process needs to get repeated and hence, while it may be possible to implement causal estimation but it might be computationally expensive. [While, I am sure there must be some research by now to make things iterative].

On the other hand, Kalman filter is inherently recursive. Hence, using it for prediction for future only using on past data will be very efficient.

Here is another good presentation that compares several methods: Ref 5

References

1. Best Introduction to Kalman Filter - Dan Simon Kalman Filtering Embedded Systems Programming JUNE 2001 page 72

2. Presentation: Lindsay Kleeman Understanding and Applying Kalman Filtering

3. H. W. Sorenson Least-squares estimation: from Gauss to Kalman IEEE Spectrum, July 1970. pp 63-68.

4. Lecture Note MIT Course ware - Inference from Data and Models (12.864) - Wiener and Kalman Filters

5. Presentation Simo Särkkä From Linear Regression to Kalman Filter and Beyond Helsinki University of Technology

6. Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." J. Math. Phys., v. 25, pp. 261–278.

Answer 2

The difference is quite huge, since they are two completely different models which can be used to tackle the same problem. Let's do a quick recap.

Polynomial regression is a way of function approximation. We have a data set of the form $\lbrace x_i, z_i \rbrace$ and wish to determine the functional relationship, which is often expressed by estimating the probability density $p(z|x)$. Under the assumption that this $p$ is a Gaussian, we get the least squares solution as a maximum likelihood estimator.

Kalman filtering is a special way of inference in a linear dynamical system. LDSs are a special case of state space models, in which we assume that the data we observe is generated by a the application of a linear transform to the subsequent steps of a Markov chain over Gaussian random variables. Thus what we actually do is to model $p(x_{1:T})$, which is the probability of a time series. The process of Kalman Filtering is then to predict the next value of a time series, e.g. maximize $p(x_{t+1}|x_{1:t})$. But the same model can be used to do inference on smoothing, interpolation and many more things.

Thus: polynomial regression does function approximation, Kalman filtering does time series prediction. Two totally different things, but time series prediction is a special case of function approximation. Also, both models base quite different assumptions on the data they observe.

Answer 3

Not an expert on kalman filters, however I believe traditional Kalman filtering presumes a linear relationship between the observable data, and data you wish to infer, in contrast to more intricate ones like the Extended Kalman filters that can assume non-linear relationships.

With that in mind, I believe that for a traditional Kalman filter, on-line linear regression, would be similar to Kalman in performance. However, a polynomial regression can also be used that would assume a non-linear relationship that a traditional Kalman might not be able to capture.

Answer 4

Kalman filtering gives multiple predictions for the next state, where an extrapolation of a regression would not.

The Kalman filters are also focused on including noise factors (based on Gaussian distributions).

Answer 5

A lot has been said already, allow me to add some comments:

Kalman filters are an application of Bayesian probability theory, which means that "a priori information" or "prior uncertainty" can (and must) be specified. As I understand, this is not the case with traditional least-squares fitting. While observations (data) can be weighted with probabilities in LSQ fitting, prior knowledge of a solution cannot be readily taken into account.

In summary, solutions found by a KF will depend on

a) a model to provide 'predictions'

b) measurements which are 'observations'

c) uncertainty on predictions and observations

d) a priori knowledge of the solution.

"prior knowledge" is specified as a variance on the initial guess, but is not relevant or utilized to the same extent in every application.

As mentioned before, a common use of the KF is to reduce noise in real-time observations. Comparing observations with model predictions can help to estimate the 'true measurement' devoid of noise. This common application is why the KF is called a filter.

The initial guess in this example would be the assumed solution at time zero from which the KF starts, with associated "prior uncertainty". Often you will have some unknown parameters in the predictive model, but which can be constrained by the measurements i.e. are "observable". The KF will improve its estimates of both those parameters and the "true measurements" as it moves through the time series of data. In that case the initial state is often specified to simply result in consistent filtering performance: defined as the actual estimation errors being within the uncertainty bounds that the KF provides with its solution. In this example, the prior uncertainty on the initial state may be specified to be large, giving the KF opportunity to correct any errors it contains. Small values may also be specified, to nudge the filter towards future estimates that make sense (are consistent with observations).

This area of KF design may involve trial and error, or engineering judgement, to come up with values of the initial state and its uncertainty that result in good performance. For this reason, this and other aspects of KF filter design which involve specifying uncertainties to result in good performance (be it numerical, estimation, prediction...) is often referred to as "filter tuning".

But in other applications, a more rigorous and useful approach to prior uncertainties can be adopted. The previous example was about real-time estimation (to filter noise out of uncertain measurements). The initial state and its variance (prior uncertainty) are almost a necessary evil to initialize the filter at an early time, after which the initial state becomes increasingly unimportant as future observations are used to improve estimates. Consider now a Kalman filter applied to measurements and model predictions at a specific time t_s. We have uncertain observations, an uncertain model, but we also have some prior knowledge about the solution we are looking for. Let's say we know its Gaussian PDF: mean and variance. In this case the solution could depend very strongly on the prior uncertainty, meaning item d) above, where the hope is that the added information improves the KF solution (smaller error and less uncertainty).

This feature, which is fundamental to Bayesian theory, allows the KF to solve stochastic problems while taking into account every kind of uncertainty/information that is typically available. Because the KF has been developed and applied for decades, its basic features are not always described in detail. In my experience, many papers and books focus on optimality and linearization (extended KF, unscented KF, and so on). But I've found great descriptions of the links between Bayesian theory and KF, by reading introductory papers and texts on "particle filters". Those are another and more recent implementation of Bayesian estimation, look them up if you're interested!

Answer 6

I suggest this reference regarding the comparison between least-squares and Kalman filters :

Fundamentals of Kalman Filtering: A Practical Approach by P. Zarchan & H. Mussof

Especially Chapter 3 (Recursive Least-Squares Filtering) and Chapter 4 (Polynomial Kalman Filters).

In Chapter 4, the authors show that the discrete (time) n-th order polynomial Kalman filter with zero process noise and infinite initial state covariance matrix is completely equivalent to the n-th order recursive least-squares filter (in terms of gains and variance prediction).