# Dimensionality Reduction for Tukey Regression

arXiv: https://arxiv.org/abs/1905.05376 · HTML: https://mlsanity.com/paper/1905.05376/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2019.

## Built on by (most cited first, 12 of 12)

- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions](https://mlsanity.com/paper/2410.05462/) (2024)
- [Adaptive Sketches for Robust Regression with Importance Sampling](https://mlsanity.com/paper/2207.07822/) (2022)
- [CVD-SfM: A Cross-View Deep Front-end Structure-from-Motion System for Sparse Localization in Multi-Altitude Scenes](https://mlsanity.com/paper/2508.01936/) (2025)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)

## Abstract (arXiv)

We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function |y|M = sumi M(yi) has M(yi) ≈ |yi|p for residual errors yi smaller than a prescribed threshold τ, but M(yi) becomes constant for errors |yi| > τ. Our results depend on a new structural result, proven constructively, showing that for any d-dimensional subspace L subset ℝn, there is a fixed bounded-size subset of coordinates containing, for every y ∈ L, all the large coordinates, with respect to the Tukey loss function, of y. Our methods reduce a given Tukey regression problem to a smaller weighted version, whose solution is a provably good approximate solution to the original problem. Our reductions are fast, simple and easy to implement, and we give empirical results demonstrating their practicality, using existing heuristic solvers for the small versions. We also give exponential-time algorithms giving provably good solutions, and hardness results suggesting that a significant speedup in the worst case is unlikely.