search

nwojke / deep_sort

Simple Online Realtime Tracking with a Deep Association Metric
GNU General Public License v3.0
5.27k stars 1.47k forks source link

Kalman filter covariance update formula #222

Open bamfpga opened 4 years ago

bamfpga commented 4 years ago

Hi, Very nice implementation. I've been analysing the code for the Kalman filter linear algebra equations, I understood all of them, except for the last one, the covariance update, which does not seem to match any of the forms presented at https://en.wikipedia.org/wiki/Kalman_filter, neither classic or Joseph form. How was this equation derived?

Another question? Is solving a linear sistem using Cholesky decomposition cheaper than performing a tradition matrix inversion using for example Gauss-Jordan method. Thanks in advance!

studentbrad commented 3 years ago

Cholesky decomposition is faster than inverting a matrix using Gauss-Jordan elimination in most cases. There are several ways to decompose a matrix as well as compute the inverse. Generally, computing the inverse is slow.

From what I can see, the covariance update assumes the identity matrix is negligible in the Joseph form. Screenshot from 2020-11-05 15-09-32 This factors the equation down to: P = KHPH^TK^T + KRK^T = K(HPH^T + R)K^T = KSK^T

studentbrad commented 3 years ago

This actually has a name. It took awhile to find in literature, but is commonly referred to as Symmetric form.

bamfpga commented 3 years ago

Thanks for the response!

BhautikDonga commented 3 years ago

I have found this one helpful for resolving this query.

studentbrad commented 3 years ago

I have found this one helpful for resolving this query.

Good find. This is a better explanation of what is going on. I'll add that this proof is only valid once we assume the covariance matrix P is symmetric. Otherwise (KHP^T)^T is not equal to KHP. Hence the name Symmetric Form.