Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

DOI10.1145/2582112.2582131MaRDI QIDQ4635533zbMATH OpenOpenAlexFDO

Authors Hu Ding, Jinhui Xu

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2582112.2582131

zbMATH Keywords

large-scale dataleast trimmed squares estimatorrobust linear regressionsecure multi-party computationsub-linear timeuncertain data

Mathematics Subject Classification ID

Robustness and adaptive procedures (parametric inference) (62F35) Linear regression; mixed models (62J05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• An exact polynomial time algorithm for computing the least trimmed squares estimate
• New algorithms for computing the least trimmed squares regression estimator
• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• A practical approximation algorithm for the LTS estimator
• Sublinear time algorithms for approximate semidefinite programming
• Efficient algorithm for a class of least squares estimation problems
• A practical approximation algorithm for the LMS line estimator
• Time- and Space-Efficient Algorithms for Least Median of Squares Regression
• A new complexity bound for the least-squares problem

Cited in

(4)

• An exact polynomial time algorithm for computing the least trimmed squares estimate
• A practical approximation algorithm for the LTS estimator
• A unified framework for clustering constrained data without locality property
• On the least trimmed squares estimator

This page was built for publication: Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635533)