Convergence of the Huber Regression M-Estimate in the Presence of Dense Outliers

Abstract—We consider the problem of estimating a determin-istic unknown vector which depends linearly on noisy measure-ments, additionally contaminated with (possibly unbounded) addi-tive outliers. The measurement matrix of the model (i.e., the ma-trix involved in the linear transformation of the sought vector) is assumed known, and comprised of standardGaussian i.i.d. entries. The outlier variables are assumed independent of themeasurement matrix, deterministic or random with possibly unknown distribu-tion. Under these assumptions we provide a simple proof that the minimizer of the Huber penalty function of the residuals converges to the true parameter vector with a-rate, even when outliers are dense, in the sense that there is a constant linear fraction of contaminated measurements which can be arbitrarily close to one. The constants influencing the rate of convergence are shown to ex-plicitly depend on the outlier contamination level. Index Terms—Breakdown point (BP), dense outliers, Huber es-timator, performance analysis. I