Robust Linear Regression via $\ell_0$ Regularization
Open Access
- 9 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 66 (3) , 698-713
Abstract
Linear regression in the presence of outliers is an important problem and is challenging as the support of outliers is not known beforehand. Many robust estimators solve this problem via explicitly or implicitly assuming that outliers are sparse and result in large observation errors. We propose an Algorithm for Robust Outlier Support Identification (AROSI) utilizing a novel objective function with $\mathcal{l}_0$-‘norm’ regularization which models the sparsity of outliers. The optimization procedure naturally utilizes the large observation error assumption of outliers and directly operates on the $\mathcal{l}_0$-‘norm’ and is guaranteed to converge. When only sparse outliers are present (no dense inlier noise), we show that, under certain model and algorithm parameter settings, AROSI can recover the solution exactly. In the case where both dense inlier noise and sparse outliers are present, we prove that the estimation error is bounded. Extensive empirical comparisons with state-of-the-art methods demonstrate the advantage of the proposed method.Keywords
Funding Information
- NSF (IIS-1522125)
This publication has 45 references indexed in Scilit:
- Dense Error Correction Via $\ell^1$-MinimizationIEEE Transactions on Information Theory, 2010
- The Dantzig selector: Statistical estimation when p is much larger than nThe Annals of Statistics, 2007
- Portfolio optimization with linear and fixed transaction costsAnnals of Operations Research, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Unmasking Multivariate Outliers and Leverage PointsJournal of the American Statistical Association, 1990
- Least Median of Squares RegressionJournal of the American Statistical Association, 1984
- Random sample consensusCommunications of the ACM, 1981
- The Fitting of Power Series, Meaning Polynomials, Illustrated on Band-Spectroscopic DataTechnometrics, 1974
- The 1972 Wald Lecture Robust Statistics: A ReviewThe Annals of Mathematical Statistics, 1972