Sub-linear time hybrid approximations for Least Trimmed Squares estimator and related problems

Least Trimmed Squares (LTS) estimator is a statistical tool for estimating how well a set of points fits a hyperplane. As a robust alternative to the classical least squares estimator, LTS takes as input a set P of n points in ℝ^d and a fitting parameter m ≤ n, and computes a non-vertical hyperplane H so that the sum of the m smallest squared vertical distances from P to H is minimized. Previous research has indicated that although solving LTS (exactly or approximately) could be quite costly (i.e., it may take Ω(n^d-1) time to even approximate it when m=n is a positive constant c < 1), a hybrid version of approximation, which is a bi-criteria on residual approximation and quantile approximation, can be obtained in linear time in any fixed dimensional space. In this paper, we further show that an (ε_r, ε_q)-hybrid approximation of LTS can be computed in sub-linear time, where ε_r> 0 is the residual approximation ratio and 0 < ε_q<1 is the quantile approximation ratio. The running time is independent of the input size n, when m = ⊖(n). Comparing to existing result, our approach has quite a few advantages, e.g., is much simpler, has better robustness, takes only constant additional space, and can deal with big data (e.g., streaming data). Our result is based on new insights to the problem and several novel techniques, such as re-cursive slab partition, sequential orthogonal rotation, and symmetric sampling. Our technique can also be extended to achieve sub-linear time hybrid approximations for several related problems, such as data-oblivious computation for LTS in Secure Multi-party Computation (SMC) protocol, LTS on uncertain and range data, and the Orthogonal Least Trimmed Squares (OLTS) problem. It is likely that our technique will be applicable to other shape fitting problems