Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square

This paper proposes ALS-IRLS, a novel outlier-robust algorithm that integrates an innovation-level adaptive thresholding mechanism with an IRLS-based Huber cost function to significantly improve the accuracy of noise covariance estimation and state filtering in the presence of measurement outliers compared to conventional methods.

The Gist

Imagine you are trying to teach a robot to walk through a foggy, noisy room. To do this, the robot uses a "Kalman Filter," which is like a smart guesser. It predicts where the robot will be next, checks its sensors to see where it actually is, and then blends those two pieces of information to make the best guess possible.

However, for this guesser to work perfectly, it needs to know two things:

1. How much the robot wobbles on its own (Process Noise).
2. How much the sensors lie or glitch (Measurement Noise).

In the real world, we rarely know these numbers exactly. So, we have to estimate them by watching the robot move. This is where the Autocovariance Least Squares (ALS) method comes in. It's like a detective looking at a history of sensor data to figure out the noise levels.

The Problem: The "Bad Apple" Effect

The old detective (standard ALS) is very sensitive to "bad apples." Imagine you are trying to calculate the average height of a group of people. If one person is a giant (an outlier caused by a sensor glitch or a sudden jump), the old detective gets confused. It thinks, "Wow, everyone must be huge!" and calculates a massive, wrong average.

In our robot example, a single sensor glitch makes the old detective think the sensors are incredibly unreliable. It then tells the robot to ignore its own movement predictions and trust the sensors blindly, causing the robot to stumble and fall.

The Solution: The "Smart Filter" (ALS-IRLS)

This paper introduces a new, super-smart detective called ALS-IRLS. It uses a "two-tier" strategy to handle the bad apples, like a bouncer at a club and a security guard inside.

Tier 1: The Bouncer (Innovation-Level Thresholding)

Before the detective even starts crunching numbers, it puts on a pair of "smart glasses."

• The Metaphor: Imagine the robot is walking, and every step it takes is a "prediction." The sensor tells it where it is. The difference between the prediction and the sensor is the "innovation" (the surprise).
• The Action: If the robot predicts it's on the floor, but the sensor suddenly says it's on the ceiling, the "Bouncer" says, "That's impossible! That's a glitch!" and throws that specific data point out of the room immediately.
• The Result: The detective never even sees the giant bad apples. It only looks at the normal, healthy data.

Tier 2: The Security Guard (Iteratively Reweighted Least Squares)

Sometimes, a bad apple sneaks past the bouncer, or a piece of data is just "suspicious" but not obviously broken.

• The Metaphor: Imagine the detective is now trying to solve a puzzle. Most pieces fit perfectly. But one piece looks a little warped.
• The Action: Instead of forcing that warped piece to fit (which would ruin the whole picture), the Security Guard says, "We'll use that piece, but we'll hold it very lightly so it doesn't pull the whole puzzle out of shape."
• The Magic: The detective does this iteratively. It solves the puzzle, sees which pieces are still pulling things out of shape, and then makes them even lighter. It repeats this until the picture is perfect. This is the "Iteratively Reweighted Least Squares" (IRLS) part.

Why This Matters

The paper tested this new method against the old one and some other "robust" methods. Here is what happened:

1. Accuracy: The old method was off by a huge margin (like estimating a 5-foot person as 50 feet tall). The new method was almost perfect, reducing the error by 100 times.
2. The "Oracle" Goal: In science, there is an "Oracle" (a magical being that knows the true noise levels perfectly). The new method got the robot's performance to within 9% of this magical Oracle.
3. Better than the Competition: Other methods tried to fix the problem by changing how the robot thinks (using complex math to handle glitches). But this paper showed that if you just fix the data first (by removing the glitches), the robot can use simple, standard thinking and still perform amazingly well.

The Bottom Line

Think of the old method as trying to bake a cake while someone keeps throwing rocks into the batter. You end up with a rock-filled mess.

The new ALS-IRLS method is like having a chef who:

1. Inspects the ingredients and throws out the rocks before they hit the bowl.
2. Stirs gently, making sure any tiny pebbles that slipped through don't ruin the texture.

The result? A perfect cake (a robot that walks smoothly) even in a very messy, noisy kitchen. This proves that cleaning your data is often more powerful than trying to build a smarter algorithm to cope with dirty data.

Technical Summary

Here is a detailed technical summary of the paper "Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square" by Jiahong Li and Fang Deng.

1. Problem Statement

The paper addresses the critical challenge of estimating process noise covariance ($Q$) and measurement noise covariance ($R$) in Kalman Filters (KF) for Linear Time-Invariant (LTI) systems when the system is subject to measurement outliers.

• Context: Standard Kalman Filters assume Gaussian noise. However, in practice, sensors often suffer from faults or external interference, leading to "heavy-tailed" noise distributions (outliers).
• Limitation of Existing Methods:
  • Autocovariance Least Squares (ALS): A popular, computationally efficient method for estimating $Q$ and $R$ without specific noise models. However, it relies on the Least Mean Squares (LMS) criterion ($\ell_2$-norm), making it highly sensitive to outliers. A single contaminated data point can severely bias the autocovariance estimates, leading to filter divergence.
  • Outlier-Robust KFs (ORKF): Existing robust filters (e.g., Student-t KF, Maximum Correntropy KF) often assume fixed, misspecified noise covariances or rely on complex parametric/non-parametric distributions that are computationally expensive and difficult to tune in real-time.
• Goal: Develop a method that accurately recovers noise covariances ($Q, R$) from data contaminated by outliers, thereby enabling the Kalman Filter to operate near its optimal performance (Oracle bound) even in noisy environments.

2. Methodology: ALS-IRLS

The authors propose ALS-IRLS, a novel algorithm that integrates the Iteratively Reweighted Least Squares (IRLS) framework into the standard ALS method. The approach employs a two-tier robustification strategy:

Tier 1: Innovation-Level Adaptive Thresholding

Before calculating the autocovariance matrix, the algorithm filters the raw innovation sequence ($e_k = z_k - H\hat{x}_{k|k-1}$).

• Mechanism: It uses a robust scale estimate based on the Median Absolute Deviation (MAD) to determine a dynamic threshold ($\gamma_{thr} = 3.5 \hat{\sigma}_e$).
• Action: Any innovation exceeding this threshold is flagged as an outlier and removed from the dataset used to compute the empirical autocovariance vector ($\hat{b}$).
• Benefit: This "hard" removal eliminates heavily contaminated data points that would otherwise dominate the least-squares solution.

Tier 2: IRLS with Huber Cost Function

After forming the regression problem $A\theta = b$ (where $\theta$ contains the vectorized $Q$ and $R$), the algorithm applies IRLS to handle residual outliers.

• Formulation: The standard LMS criterion is replaced with a Huber cost function ($\rho(\cdot)$), which behaves quadratically for small residuals and linearly for large residuals.
• Iterative Process:
  1. Initialize weights $W$ as identity.
  2. Solve the weighted least squares problem: $\theta^{(t+1)} = (A^T W^{(t)} A)^{-1} A^T W^{(t)} b$.
  3. Update weights based on the residuals: $w_i = 1$ if $|r_i| \le \delta$, and $w_i = \delta/|r_i|$ if $|r_i| > \delta$ (where $\delta$ is the Huber threshold).
  4. Repeat until convergence.
• Constraint Handling: The algorithm enforces Positive Semi-Definite (PSD) constraints on the estimated $Q$ and $R$ matrices after each outer iteration by projecting eigenvalues to zero if negative.

3. Key Contributions

1. Reformulation of ALS: The authors establish a theoretical link between outlier-robust regression and ALS, transforming the noise covariance estimation problem into a robust regression problem solvable via IRLS.
2. Two-Tier Robustification: The unique combination of MAD-based hard thresholding (at the innovation level) and Huber-based soft reweighting (at the autocovariance regression level) provides a high breakdown point (up to 50%) while maintaining computational efficiency.
3. Convergence and Complexity: The paper provides a proof of convergence for the ALS-IRLS sequence to a unique global minimizer under standard conditions. It also analyzes computational complexity, showing it scales similarly to standard ALS but with a multiplier for IRLS iterations.
4. Superior Performance: The method demonstrates that accurate covariance estimation is more critical for downstream performance than using complex robust filter structures with incorrect noise models.

4. Simulation Results

The authors evaluated ALS-IRLS on a third-order LTI system with $\epsilon$-contamination (15% outlier rate, magnitude 8$\times$ standard deviation).

• Covariance Estimation Accuracy:

  • Standard ALS: Failed completely, overestimating $Q$ by ~10.7$\times$ and $R$ by ~36.7$\times$ due to outlier bias.
  • ALS-IRLS: Achieved near-perfect recovery. The Root Mean Square Error (RMSE) for both $Q$ and $R$ was reduced by more than two orders of magnitude compared to standard ALS.
  • Robustness: Performance remained stable even as the outlier rate increased from 0% to 30%.

• Downstream State Estimation:

  • The Kalman Filter using ALS-IRLS estimates achieved a state estimation RMSE of 1.97, which is within 9% of the Oracle lower bound (1.80, using true covariances).
  • Comparison: It significantly outperformed existing robust filters (Student-t KF and MCKF), which suffered from misspecified fixed covariances. The proposed method reduced state estimation error by a factor of 2.3$\times$ to 3.5$\times$ compared to these benchmarks.

5. Significance

• Paradigm Shift: The paper argues that for systems with unknown noise statistics, accurate online covariance recovery is more effective than relying solely on robust filter update steps. A standard KF with correct covariances outperforms a robust KF with incorrect covariances.
• Practicality: The algorithm retains the computational simplicity of the original ALS method, making it suitable for real-time applications where complex Bayesian or non-parametric methods are too heavy.
• Reliability: By decoupling outlier rejection at the measurement level from the regression level, the method ensures that the Kalman Filter remains stable and optimal even in the presence of severe sensor faults or environmental anomalies.

In conclusion, ALS-IRLS provides a rigorous, efficient, and highly robust solution for noise covariance estimation, effectively bridging the gap between theoretical optimality and practical robustness in Kalman filtering.