Minimum sum of distances estimator: Robustness and stability

Abstract

We consider the problem of estimating a state x from noisy and corrupted linear measurements y = Ax + z + e, where z is a dense vector of small-magnitude noise and e is a relatively sparse vector whose entries can be arbitrarily large. We study the behavior of the ℓ1 estimator x̌ = arg minx ||y - Ax||1, and analyze its breakdown point with respect to the number of corrupted measurements ||e||o. We show that the breakdown point is independent of the noise. We introduce a novel algorithm for computing the breakdown point for any given A, and provide a simple bound on the estimation error when the number of corrupted measurements is less than the breakdown point. As a motivational example we apply our algorithm to design a robust state estimator for an autonomous vehicle, and show how it can significantly improve performance over the Kalman filter. © 2009 AACC.