Situations where complexity is too big to exceed linearity and gaussianity

Question

I'm studing about Kalman Filter and Particle Filter in multiple target tracking in computer vision (tracking pedestrians). Reading sientific papers I'm colliding with a lot of sentences like:

The assumptions of linearity and Gaussianity of the Kalman Filter cannote manage complex scenario.

Now.. I'd like to find some real example of scenario where those assumptions are exceeded. Because I don't really understand where I should use Kalman Filter or not. Can anyone give me some example?

Real videos (like youtube or similar) are very good example.

Answer 1

Well, let's look at the two issues: 1) linearity and 2) Gaussianity.

Linearity

If you're imaging moving 3D objects (people) with a single camera, then you're working with a 2D projection of those 3D objects. That dimensionality reduction can cause non-linearities to appear.

Take a 2D to 1D example: an object moving in a circle in 2D. The object is moving with constant velocity and constant acceleration. All nice and linear. Project that object onto a 1D surface (a line) and the velocity and acceleration are now (co)sinusoidal.

One of the underlying assumptions in Kalman filtering (well, the sort usually presented) is that the system you're modeling is linear. When dimensionality reduction (3D $\rightarrow$ 2D) is involved, this may not be true.

Gaussianity

When a system is linear, any noises tend to be additive. When Gaussian noise is added to Gaussian noise (or, for enough samples, noise of just about any distribution is added to noise of just about any distribution), the result is also Gaussian.

If the system is non-linear, then the operations involved cause Gaussian noise to be transformed into potentially non-Gaussian noise.

For example, if you divide one Gaussian variable with another, the distribution of the result is Cauchy.

What's so bad about that? The mean (average) of a Cauchy random variable does not exist. The variance of a Cauchy random variable does not exist.

The Kalman filter is all about tracking means and variances of variables in the system. If the system is non-linear, it's possible that the relevant quantities' means and variances do not exist, so application of a Kalman filter is meaningless.

Answer 2

In addition to Peter's answer, if you have a nonlinear system that is well-behaved in a sense of being only mildly nonlinear or at least exhibiting no discontinuities, special variants of the Kalman filter can still be applied.

Extended Kalman Filter

This filter linearizes the system at the current state of the system using a first order Taylor Series Approximation. However, this fails for strongly nonlinear systems.

The issue with the extended Kalman Filter is that the posterior distributions (if nonlinearities are in the system) are no longer Gaussian and cannot be accurately described by just means and variances. The EKF now linearizes the perfectly known nonlinear system and introduces further errors.

Unscented Kalman Filter

A different approach is used by the Unscented Kalman Filter (UKF) and it's central element, the unscented transformation. Here, a discrete distribution is constructed that exhibits the same mean and variance of the current Kalman Filter state. This distribution is very easy to transform with the exact nonlinear system. The mean and variance of the resulting discrete distribution are then calculated and are again assumed to stem from a Gaussian distribution by the rest of the Kalman filter (hence, there is still inaccuracies).

However, if you have a strongly nonlinear system with discontinuities (think about a navigation algorithm that has a map with obstacles, the transition between allowed and blocked areas are discontinuous), all of these algorithms will most likely fail.

Particle Filter

Here you can use particle filters. Each particle represents a point in your state space and is usually associated with a weight that represents how much believe that particle has (though there's a lot of different variants of the PF). In the prediction step, the particle is "moved" according to your system model and as long as you can sample from the distributions, they can be arbitrarily complex. So, instead of tracking a mean and variance, you actually move the particle by a possible realization or your system model. That is the reason why you need so many particles, to get a good coverage of the complete distribution. In the update step, the weight of the particle is updated by comparing it's state with the measurements and other information (think the floor-map again in the robot example) that can again, be highly nonlinear. In the end, unlikely particles are usually erased and replaced by particles in more likely areas. The particles are then representing your posterior distribution. Areas with many particles are more likely to contain the actual state and areas without particles are highly unlikely.

Have a look at this video of an indoor/outdoor navigation system:

Youtube Video

It shows a comparison of a Kalman Filter and a Particle Filter. As long as the user is outside and has a GPS navigation, both systems perform similarly well. However, when the user goes inside the building and the GPS positioning is lost, the Kalman Filter looses all absolute reference and needs to rely solely on the IMU. The IMU has measurement errors that eventually add up and the Kalman estimate slowly drifts away, eventually even moving outside the screen. It cannot use the floorplan as information since this results in a highly non-gaussian distribution that cannot be usefully expressed merely in terms of means and variances. The particle filter on the other hand has no problem with this scenario and keeps tracking the position very well.

Of course, particle filters have downsides. Sampling from complicated distributions can be an expensive operation. It is usually not trivial to decide on the number of particles or when to annihilate a particle due to low likelihood. So quite a bit of tweaking is usually required. Tracking all those particles requires a lot of memory and a lot of particles are required especially for high-dimensional problem. And finally, their performance will not be better for linear systems involving Gaussian distributions as for this case the Kalman Filter is optimal.