Balancing between estimation accuracy and computation

For sequential probabilistic estimation tools such as sequential Monte Carlo method, there is an intrinsic trade-off between accuracy and the amount of computation one can afford. In our problem, this balance depends on the number of targets in the system and the number of events that happen, which can be roughly partitioned into three categories:

1)

There are only a few targets and events. In this case, approximation errors early in the procedure can grow very fast as computation is carried out. On the other hand, because the combinatorial choices are limited, this case can be treated with high fidelity, with the only assumption being good split rule and sensor statistics.

2)

There are a few targets but a large number of events. Propagating the probability mass through many events will likely accumulate significant errors when there are only a few targets, unless an extremely reliable split rule and sensor statistics are available. If this is the case, the method for the first category will perform well. Otherwise, a probabilistic approach may give results that are far off from the true distribution; the nondeterministic approach discussed in Section V would be a better alternative.

3)

There are many targets in the system, in which case there is more freedom in making simplifications without dramatically altering the outcome.

To provide an idea of what we mean by ``a few'' and ``many,'' our non-optimized Java implementation for the first category can handle tens of targets and events, beyond which the JavaVM will run out of memory. In comparison, the heuristics employed for the third category can handle thousands of targets and events. In the next two subsections, we give detailed analysis of the first and third categories.