Abstract
Optimal state estimation for linear discrete-time systems is considered. Motivated by the literature on differential privacy, the measurements are assumed to be corrupted by Laplace noise. The optimal least mean square error estimate of the state is approximated using a randomized method. The method relies on that the Laplace noise can be rewritten as Gaussian noise scaled by Rayleigh random variable. The probability of the event that the distance between the approximation and the best estimate is smaller than a constant is determined as function of the number of parallel Kalman filters that is used in the randomized method. This estimator is then compared with the optimal linear estimator, the maximum a posteriori (MAP) estimate of the state, and the particle filter.
Introduction
In modern control systems and signal processing, the Kalman filter is the standard for state estimation when noise is Gaussian. However, in applications involving differential privacy, noise is often intentionally added following a Laplace distribution to protect individual privacy. Standard linear estimators are no longer optimal in these non-Gaussian settings. While universal tools like Particle Filters exist, they can be computationally heavy and may not fully leverage the specific linear structure of the system. This paper introduces an efficient randomized approach to find the Minimum Mean Square Error (MMSE) estimate specifically for systems with Laplace-distributed measurement noise.
Methodology
The Rayleigh Decomposition
The core innovation of this research is a decomposition technique. The authors prove that a Laplace random variable can be represented as a Gaussian random variable whose variance is itself a random variable following a Rayleigh distribution. This "Rayleigh trick" allows the non-Gaussian problem to be reframed using the well-understood machinery of Gaussian estimation.
The Randomized Estimator
Using this insight, the authors propose a Randomized Estimator that operates through three main steps:
- Parallel Filtering: Multiple ($I$) parallel time-varying Kalman filters are executed.
- Sampling: For each filter, "Rayleigh scales" ($\tau$) are sampled, representing the hidden variance of the Laplace noise at each time step.
- Averaging: The final state estimate is the simple average of the estimates produced by these parallel filters.
This method provides a direct trade-off between computational cost and accuracy: as the number of parallel filters ($I$) increases, the approximation error decreases.
Numerical Evaluation
The proposed algorithms were evaluated using a synthetic discrete-time linear time-invariant (LTI) system with a 2D state vector, Gaussian process noise, and Laplace measurement noise. Performance was measured by the variance of the estimation error over time across 10,000 simulated scenarios.
As illustrated in Figure 1, the randomized estimator (using 1,000 samples) achieves a significantly lower Mean Square Error (MSE) than the optimal linear estimator, the MAP estimator, and a particle filter with 1,000 particles. Notably, the MAP estimator—which functions as a dynamic version of the LASSO regression—performs the worst in terms of error variance. This highlights that for privacy-corrupted data, the randomized MMSE approach is superior to standard likelihood-based methods.
Conclusion and Future Work
The randomized estimator offers a robust solution for state estimation in differentially private systems. While it requires more computational resources than a single linear filter, its structure is highly parallelizable. Future research directions include extending this framework to handle cases where both process and measurement noise follow Laplace distributions and developing more efficient sampling strategies for the Rayleigh scales to reduce computational overhead.
Summary updated