Minimum sum of distances estimator: Robustness and stability
Yoav Sharon, John N. Wright, Yi Ma · 2009
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 ℓ1estimator x̂ = arg minx||y - Ax||1, and analyze its breakdown point with respect to the number of corrupted measurements ||e||0. 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.