# Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2020.

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

- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Byzantine-Resilient Federated Learning at Edge](https://mlsanity.com/paper/2303.10434/) (2023)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [Linear Regression under Missing or Corrupted Coordinates](https://mlsanity.com/paper/2509.19242/) (2025)
- [A Combinatorial Approach to Robust PCA](https://mlsanity.com/paper/2311.16416/) (2023)

## Abstract (arXiv)

We study the problem of robustly estimating the mean of a d-dimensional distribution given N examples, where most coordinates of every example may be missing and varepsilon N examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than varepsilon N examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time widetilde O(Nd). Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.