Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate…
Bias-VarianceTrade-off in Kalman Filter-Based Disturbance Observers
The performance of disturbance observers is strongly influenced by the level of prior knowledge about the disturbance model. The simultaneous input and state estimation (SISE) algorithm is widely recognized for providing…
State EstimationOnline Identification and Tracking of Subspaces from Highly Incomplete Information
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulat…
Matrix CompletionLucidFusion: Generating 3D Gaussians with Arbitrary Unposed Images
Recent large reconstruction models have made notable progress in generating high-quality 3D objects from single images. However, these methods often struggle with controllability, as they lack information from multiple v…
3D GenerationImage to 3DHighly Efficient Rotation-Invariant Spectral Embedding for Scalable Incomplete Multi-View Clustering
Incomplete multi-view clustering presents significant challenges due to missing views. Although many existing graph-based methods aim to recover missing instances or complete similarity matrices with promising results, t…
ClusteringIncomplete multi-view clustering