Dimensionality Reduction for Tukey Regression

Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff

We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function $\Vert y{\Vert }_M={\sum }_{i}M(y_i)$ has $M(y_i)\approx |y_i{|}^p$…