Abstract

Linear Robust Regression (LRR) seeks to fifind the parameters of a linear mapping from noisy data corrupted from outliers, such that the number of inliers (i.e. pairs of points where the fifitting error of the model is less than a given bound) is maximized. While this problem is known to be NP hard, several tractable relaxations have been recently proposed along with theoretical conditions guaranteeing exact recovery of the parameters of the model. However, these relaxations may perform poorly in cases where the fifitting error for the outliers is large. In addition, these approaches cannot exploit available a-priori information, such as cooccurrences. To circumvent these diffificulties, in this paper we present an alternative approach to robust regression. Our main result shows that this approach is equivalent to a “self-scaled” `1 regularized robust regression problem, where the cost function is automatically scaled, with scalings that depend on the a-priori information. Thus, the proposed approach achieves substantially better performance than traditional regularized approaches in cases where the outliers are far from the linear manifold spanned by the inliers, while at the same time exhibits the same theoretical recovery properties. These results are illustrated with several application examples using both synthetic and real data