⚡ electrical engineering

Approximating Analytically-Intractable Likelihood Densities with Deterministic Arithmetic for Optimal Particle Filtering

This paper introduces a new particle filtering method that leverages deterministic arithmetic on a specialized UxHw computing platform to approximate analytically-intractable likelihood densities, achieving significant improvements in speed, accuracy, and false-zero rates compared to traditional Monte Carlo alternatives for non-Gaussian non-linear systems.

Original authors: Orestis Kaparounakis, Yunqi Zhang, Phillip Stanley-Marbell

Published 2026-03-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Orestis Kaparounakis, Yunqi Zhang, Phillip Stanley-Marbell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Guessing the Future in a Foggy World

Imagine you are driving a self-driving car. You need to know exactly where you are and where you are going. But the world is messy: your GPS is sometimes wrong, your speedometer is jittery, and the road might be slippery.

To solve this, engineers use a tool called a Particle Filter. Think of this as a "crowd of guessers."

You release 1,000 tiny digital ghosts (particles) into the simulation.
Each ghost guesses a different possible location for your car.
As you get new data (like seeing a stop sign), you ask: "How likely is it that this ghost is right?"
If a ghost's guess matches the stop sign perfectly, you give it a high score (weight). If it's way off, you give it a low score.
Finally, you keep the high-scoring ghosts and discard the bad ones to update your best guess of where the car is.

The Problem: The "Impossible Math" Bottleneck

The tricky part is calculating that score (the "likelihood").

Simple Math: If the world were perfectly predictable (like a straight line), you could calculate the score instantly with a simple formula.
The Real World: In reality, the math is often a tangled knot. The sensors are noisy, the physics are weird, and the equations are so complex that no one can write a simple formula for them. This is called an "analytically-intractable" problem.

The Old Solution (Monte Carlo):
To solve this tangled knot, the old method uses a technique called Monte Carlo simulation.

The Analogy: Imagine you need to guess the average height of people in a room, but you can't measure them all. So, you close your eyes, pick a random person, measure them, write it down, and repeat this 1,000 times. Then you average the results.
The Flaw: To get a good answer, you have to repeat this "random guessing" thousands of times. It's slow, it uses a lot of battery power, and because it relies on luck, sometimes you get a bad answer just by chance (like picking only tall people by accident). In a self-driving car, waiting for 1,000 random guesses is too slow.

The New Solution: The "Deterministic Arithmetic" Machine

This paper introduces a new way to do the math using a special hardware chip called UxHw (Uncertainty-extended Hardware).

The Analogy: Instead of closing your eyes and guessing 1,000 times, imagine you have a super-smart calculator that doesn't deal with single numbers. It deals with entire clouds of possibilities at once.
When you ask this calculator, "What happens if I add this noise to this speed?", it doesn't guess. It performs a precise, step-by-step arithmetic operation on the entire shape of the uncertainty cloud.
It takes the "cloud" of where the car might be, smears it through the physics of the road, smears it through the sensor noise, and instantly tells you the exact shape of the new "cloud" of possibilities.
Then, it looks at your actual sensor reading and says, "Based on this entire cloud, here is the exact probability that this reading is correct."

Why This is a Game-Changer

The researchers tested this new method against the old "random guessing" method on a complex system (the Gordon–Salmond–Smith model). Here is what they found:

Speed (The 37x Boost):
The new method was up to 37 times faster than the old method for the same level of accuracy.
- Analogy: It's like switching from a horse-drawn carriage that stops to ask a random passerby for directions, to a high-speed train that knows the exact map and never stops.
Reliability (No More "Zero" Mistakes):
The old method sometimes fails completely. If the "random guess" misses the target area, it says the likelihood is zero. This is dangerous because it tells the car, "This is impossible!" when it's actually just unlikely.
- The Result: The old method said "Impossible" (zero likelihood) 82% of the time in tricky situations. The new method only did it 1.5% of the time. It rarely gives up.
Better Accuracy:
Because the new method doesn't rely on luck, it gives a more accurate picture of where the car is. The "error" in the car's position was reduced by up to 19% compared to the old method.

The Takeaway

This paper presents a new "engine" for self-driving robots and drones.

Before: They had to guess wildly thousands of times to figure out where they were, which was slow and sometimes led to crashes or getting lost.
Now: They use a special computer chip that does precise math on "clouds of uncertainty." It's faster, more reliable, and doesn't waste energy on random guessing.

This means we can finally put powerful, complex AI into small, battery-powered robots (like warehouse bots or drones) that need to make split-second decisions without getting stuck in slow math calculations.

1. Problem Statement

Particle filtering (PF) is a standard technique for state estimation in non-linear, non-Gaussian systems (e.g., autonomous robotics, target tracking). However, its performance relies heavily on the accurate computation of the likelihood density $p(z_k | x_k)$ , which represents the probability of an observation given a state.

The Core Challenge: In many real-world scenarios, the observation model is analytically intractable (non-linear, non-Gaussian, or discontinuous), making the likelihood calculation impossible to solve in closed form.
Current Limitations:
- Monte Carlo (MC) Methods: The standard approach approximates the likelihood by sampling noise and averaging results. This is computationally expensive, introduces stochastic variance, and often fails in real-time, resource-constrained embedded systems.
- Particle Degeneracy: In systems with narrow observation uncertainty (e.g., uniform noise with small support), MC methods frequently fail to sample the "support" of the observation distribution. This leads to a "likelihood collapse" where the filter assigns a zero likelihood to valid observations, causing the filter to diverge or reset.
- Latency: The computational cost of MC simulations often exceeds the power and latency budgets of embedded platforms like drones or self-driving cars.

2. Methodology

The authors propose a novel particle filtering method that replaces stochastic sampling with deterministic arithmetic on probability distributions. This approach leverages a specialized hardware architecture called UxHw (Uncertainty-extended Hardware).

A. The UxHw Approach

Instead of sampling individual noise instances, the method treats probability density functions (PDFs) as first-class data types that can be manipulated via arithmetic operations (addition, multiplication, etc.) directly on the hardware.

Deterministic Propagation: The transition noise ( $\mu_\upsilon$ ) and observation noise ( $\mu_\nu$ ) are represented as parametric distributions.
Composition: The system composes the transition model $f$ $f$ and observation model $h$ $h$ by propagating these distributions through the functions.
- Step 1: Compute the predictive state distribution $X_k = f(x_{k-1}, \upsilon_k)$ .
- Step 2: Compute the predictive observation distribution $Z_k = h(X_k, \nu_k)$ .
- Step 3: Evaluate the density of the resulting $Z_k$ distribution at the actual measurement $z_k$ to obtain the likelihood.
Tunable Approximation: The method uses a configuration parameter $\eta$ (related to the resolution of the distribution representation) to trade off between computational speed and distribution fidelity.

B. Integration with Optimal Auxiliary Particle Filter

The method is implemented within a Predictive-Lookahead Auxiliary Particle Filter (APF).

Unlike standard bootstrap filters that sample first and then weight, the APF uses a "proxy likelihood" to select parent particles before sampling the transition noise.
The proposed method computes this proxy likelihood deterministically using UxHw, avoiding the need for the expensive Monte Carlo integration typically required for optimal proposals in non-Gaussian systems.

3. Key Contributions

Tunably-Approximative Likelihood Computation: A new method to compute likelihoods for arbitrary, analytically-intractable densities using Turing-complete transformations on random variables within standard programming syntax, mapped to UxHw hardware.
Deterministic Time Guarantees: By eliminating random sampling, the method provides predictable runtime and memory usage, making it suitable for hard real-time systems.
Experimental Validation: Comprehensive benchmarking on the Gordon–Salmond–Smith system (a classic non-linear, non-Gaussian benchmark) across 540 system configurations (varying Gaussian, Laplacian, and Uniform noise) and a total of 294,840 evaluation points.

4. Results

The study compares the UxHw approach against Monte Carlo (MC) simulation and baseline pointwise evaluation.

Speedup:
- UxHw achieves up to 37.7x speedup compared to an equal-accuracy Monte Carlo alternative (specifically, MC with 701 iterations vs. UxHw $\eta=8$ ).
- Even with higher fidelity settings (UxHw $\eta=64$ ), a 7.9x speedup is maintained against MC with 11,046 iterations.
Accuracy (RMSE):
- The UxHw approach reduces the Root Mean Square Error (RMSE) by an average of 3.3% compared to equal-speed MC.
- In specific configurations (e.g., 600 particles with UxHw $\eta=8$ ), the RMSE improvement reaches 18.9%.
Robustness (Likelihood Collapse):
- In systems with narrow uniform measurement uncertainty, standard MC methods falsely assign zero likelihood 81.89% of the time (leading to filter failure).
- The UxHw method reduces this "false-zero" rate to 1.52%.
- This robustness translates to a 2 percentage point reduction in the rate of filter weight distribution collapses (necessitating filter resets).
Sample Efficiency:
- UxHw filters achieve a higher Effective Sample Size (ESS), indicating better utilization of particles and less degeneracy compared to MC alternatives.

5. Significance and Impact

Enabling Real-Time Non-Gaussian Filtering: This work bridges the gap between powerful, complex likelihood models and the strict resource constraints of embedded systems. It allows autonomous robots and drones to use sophisticated, non-linear sensor models in real-time without relying on heavy Monte Carlo simulations.
Hardware-Software Co-Design: The paper demonstrates the practical utility of specialized hardware (UxHw) that performs arithmetic on probability distributions natively, moving beyond the limitations of general-purpose CPUs/GPUs for probabilistic inference.
Reliability: By removing stochastic variance from the likelihood calculation, the method significantly improves the reliability of state estimation in safety-critical applications where filter divergence is unacceptable.

In summary, the paper presents a paradigm shift from stochastic approximation to deterministic distribution arithmetic, offering a solution that is simultaneously faster, more accurate, and more robust for particle filtering in complex, non-linear environments.