Hacker News Reader

Comment by skzv | Hacker News Reader

In many circumstances, particles filters are superior. Two major advantages off the top of my head are the ability to track multi-modal distributions (Kalman filters only track one peak) and apply non-Guassian likelihoods (Kalman filters assume Gaussian noise, while you can weight particles in a particle filter using any kind of distribution).

Particle filters do come at a cost of increased memory and processing usage. You need to propagate N particles at each epoch, each of which could have M dimensions of state (position, velocity, orientation, etc). So Kalman filters are likely preferred where memory and compute are at a premium.

View on HN

Kalman filter are an optimal solution to the linear problem (PF are not). If you do not have a linear problem, of course there may be better alternatives. PF and KF solves different problems.

What does 'linear' mean in this case exactly? Does it mean, that if the measurements are in space (i.e. location), then Kalman filter can only be applied when location is changing linearly, i.e. speed is constant?

Linear problems are ones in the form of sum(a_i * f_i(x)). So all Newton ballistics are linear because acceleration is a*x^2. Sometimes people who deal in probably refer to systems where the noise is Brownian as linear as well. So, both descriptions of linearity apply to a regular Kalman filter.

There are Extended Kalman Filter and Unscented Kalman Filters that are designated to relax both of these constraints, but they aren’t perfect.

When applied to a linear system with Gaussian noise, the particle filter will (approximately) recover the solution of the Kalman filter. So yes, they solve different problems, but the particle filter is more of a generalization of the Kalman filter.

Kalman filters are linear while Particle Filters are not necessarily. This can have a lot of implications depending on what you are doing.

Actually the biggest challenge of particle filters is to avoid sample degeneracy : when significant parts of the posterior density are no longer covered by particles.

The particle filter is insanely expensive, relative to the Kalman filter. I had a project that I had to give up on because the particle filter just made it too time-consuming to do.

Often alterations of the Kalman filter are a good compromise. E.g. the extended Kalman https://en.m.wikipedia.org/wiki/Extended_Kalman_filter

As you stated particle filters are computationally expensive. Also I found them more fidgety to configure for my application cases (in activity recognition).

Have you heard of the "Unscented Kalman Filter"? It goes by UKF. It uses a different approximation scheme than the EKF, which creates a linear approximation of the dynamics, in order to propagate the mean and variance. The UKF computation using "sigma points" resembles a specific part of the particle filter.

And why the name? Well the EKF stinks in many applications (it diverges). The UKF is more robust, especially when there is more significant uncertainty.

>Unscented Kalman Filter

Funny factoid: the paper that named the UKF did so because "it doesn't stink"

I explained that in my comment.

Ha yea, I missed that you used the word stink to describe the EKF. Sorry!

We upgraded from an EKF to a UKF for our drone. I feel like our code is a good reference for using an Unscented Kalman Filter to estimate a drone’s rotational state, later this year I expect to add an optical flow and ToF sensor and update the filter for better velocity and displacement estimation.

https://github.com/Flybrix/flybrix-firmware/blob/master/ukf....

Another extension is the ensemble Kalman filter (https://en.wikipedia.org/wiki/Ensemble_Kalman_filter), which can work well for certain kinds of nonlinear systems, and when it does it can be more robust than particle filters. (Particle filters can "collapse"; this limits their usefulness.)

The Extended Kalman Filter (EKF) relies on local linear linearizations to handle nonlinearity. This works for mildly nonlinear systems, but doesn’t do so well when the system is highly nonlinear (divergence happens).

The Unscented Kalman Filter (UKF) is a kind of particle-like filter but instead of propagating a large number of points, it only propagates carefully chosen “sigma points”. It’s much more economical and works relatively well with nonlinear systems.

To me, the gold standard in estimation is the Moving Horizon Estimator (MHE) [1] which solves an explicit optimization problem to arrive at the state estimate, which allows it to accommodate constraints in the system. It is however computationally much heavier than the Kalman family of filters.

I’ve implemented UKFs in the past and think they’re a good trade off between computational speed and accuracy in the presence of nonlinearities. They cannot handle constraints however, which is a major weakness that MHEs don’t succumb to. (Imagine you are estimating a quantity x in the interval [0, 1] - UKFs can return estimates like 1.32 or -0.3 whereas MHEs accommodate bound constraints like 0 <= x <= 1 as well as more complex constraints to prevent weird outputting impossible or weird state estimates)

[1] https://murray.cds.caltech.edu/images/murray.cds/0/0d/L4-2_M...

I mayve read the presentation wrong but it says 3s/iteration on the MHE. That’s insane. I’ve run close to real time UKF for nav and control applications so it’s an apples vs oranges comparison.

Right now, yes. There was a time where doppler filtering was too expensive in programmable COTS HW, or digital beamforming, or SVD... What's missing here is the gain vs optimisation effort. If there is an order of magnitude of gain here, we'll reduce the latency one way or the other. I see impossible-20-years-ago heavy-duty solvers in RT sensors more and more.

Also depending on your refresh rate 3s might still be worth it IF the filter gain is so much better.

For real time mechanical and electrical applications, the MHE is generally not competitive (at present) However, there many types of dynamic systems that are much slower like chemical plants (minute to hour level control) that can accommodate MHE’s execution time scales.

If you need to simultaneously handle nonlinearities and constraints, it may be a superior choice.

Also there are potential ways to make MHE run faster. For certain forms of the optimization problem (like a linear or quadratic program), it’s possible to convert it to a lookup table (search for “explicit MPC”) which can then be implemented in an embedded system for fast lookups.

That said, I agree with you in practice. An nonlinear optimization problem tends to be a numerical black box and can be hard to diagnose when things go wrong. The Kalman family of algorithms is much more straightforward (only involves function evaluations), faster and have failure modes that are much more easily understood. They just don’t do so well with constraints.

Reply on news.ycombinator.com