0
$\begingroup$

In the AI for Robotics course from Udacity, Sebastian Thrun mentions that "the complexity of the particle filter grows exponentially with the number of dimensions". Why is this the case? We have to keep track of $n$ particles each of which has $d$ dimensions so wouldn't the memory complexity be $O(n*d)$?

$\endgroup$

2 Answers 2

1
$\begingroup$

You need enough particles so that you can sample across each of those dimensions.

If I have a particle filter with just X position, and my particles are spread in the range [0, 1], I might need, e.g, 3 particles: {0, 0.5, 1.0}.

If I have a particle filter with (X, Y) position and both dimensions have the same [0, 1] range, then I need one particle for every combination of X and Y: {(0, 0), (0, 0.5), (0, 1), (0.5, 0), (0.5, 0.5), (0.5, 1), (1, 0), (1, 0.5), (1, 1)}.

$\endgroup$
1
$\begingroup$

It's the number of particles that will grow exponentially. An array of particles, with $n$ particles in each dimension, with $d$ dimensions, will have $n^d$ particles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.