Fast and Robust Least Squares Estimation in Corrupted Linear Models
Subsampling methods have been recently proposed to speed up least squares estimation in large scale settings. However, these algorithms are typically not robust to outliers or corruptions in the observed covariates. The concept of influence that was developed for regression diagnostics can be used to detect such corrupted observations as shown in this paper. This property of influence -for which we also develop a randomized approximation -motivates our proposed subsampling algorithm for large scale corrupted linear regression which limits the influence of data points since highly influential points contribute most to the residual error. Under a general model of corrupted observations, we show theoretically and empirically on a variety of simulated and real datasets that our algorithm improves over the current state-of-the-art approximation schemes for ordinary least squares.
This paper looks at alternatives to LS for solving linear regressionproblems.  Classical statistics will consider a score function as away of weighting observations.  But, these would only capture anadditive error which is different than Gaussian.  This paper instead,also considers the influence of a point.  Statisticians for years havethrown out influential outliers--but as	far as I can find, this	is thefirst automatic	procedure that	uses influence as a way	ofdown-weighting a	regression.The probabilistic model	presented here is not the driving force	of thepaper. 	In other words,	it is pretty easy to identify which points arecontaminated and which are clean.  (This is very easy for large psince the two distributions won't overlap.)  So	if the estimatorpresented was tied to this model, I would be unexcited about theresults.  But, the estimator is	fairly natural.	 So the	model is onlybeing used as an example.1) Put a line where the accuracy of the MLE for your probabilisticmodel would be.  You shouldn't end up being close to this line sinceyou aren't assuming your model.  But it still is a more usefulcomparison point than the LS line.  If you don't want to bother	withdoing the de-convolution problem, you can assume that the ML hasaccess to the random variables U.  Then	it will	be a lower bound onhow well it will perform.  As p	--> infinity, this lower bound willbecome tight.2) Make the connection to some of the literature on the use of scoringfunctions (Since this goes back to the early 1970's I'm not going tosuggest any literature).  For example, the aRWS can be thought of asdown weighting points by a 1/epsilon^2.  If one were to down weight by1/epsilon, that would correspond to doing a L-1 regression.  So itwould be similar to assuming a double exponential distribution for theerrors.  Your weighting function is even more draconian.  So whatdistribution does it correspond to if you think of it as a score?(I'm guessing it looks like a Cauchy distribution--but onlyapproximately.)  (Note: you are sampling, whereas I'm more used tothinking of weights.  So it might be that your 1/epsilon^2 sampling isrelated to a 1/epsilon weight.  If so, then it is approximating a L-1regression.  This would be very nice to point out if it were true.)3) Are you claiming to be the first people to suggest weighting by1/influence?  This might be true--but it is a strong claim.4) I think what you are doing is using a different regression functionfor "large observations" than you use for "small observations."  Oneway to test this and provide a better comparison for LS would be todefine tilde-l as you do and then interact this variable with all yourX's in your regression.  This will allow the LS methods to have accessto tilde-l.  Hence LS should be able to end up with a better estimatorsince it now can have different slopes for the pure X observationsthan it has for the X+W observations.5) There is extensive literature on both errors in variables androbust regressions.  At least a few of these 1000+ papers should havesomething useful to say.  Put in at least some effort into findingsomething that connects.  That will help the implied claim that yourmethods are in fact new.6) PLease look at this 1980's NBER paper: http://www.nber.org/chapters/c11698.pdf In particular, equations (15) and (16).  This is very close to the estimator you are using.  It would be nice if you were to chase down some of the modern references and see if there are any connections to your work.