Approximating the distribution of the median and other robust estimators on uncertain data

Kevin A. Buchin, Jeff M. Phillips, Pingfan Tang

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

4 Downloads (Pure)

Samenvatting

Robust estimators, like the median of a point set, are important for data analysis in the presence of outliers. We study robust estimators for locationally uncertain points with discrete distributions. That is, each point in a data set has a discrete probability distribution describing its location. The probabilistic nature of uncertain data makes it challenging to compute such estimators, since the true value of the estimator is now described by a distribution rather than a single point. We show how to construct and estimate the distribution of the median of a point set. Building the approximate support of the distribution takes near-linear time, and assigning probability to that support takes quadratic time. We also develop a general approximation technique for distributions of robust estimators with respect to ranges with bounded VC dimension. This includes the geometric median for high dimensions and the Siegel estimator for linear regression.
Originele taal-2Engels
Titel34th International Symposium on Computational Geometry, SoCG 2018
RedacteurenCsaba D. Toth, Bettina Speckmann
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's14
ISBN van elektronische versie9783959770668
DOI's
StatusGepubliceerd - 1 jun 2018
Evenement34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hongarije
Duur: 11 jun 201814 jun 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume99
ISSN van geprinte versie1868-8969

Congres

Congres34th International Symposium on Computational Geometry, SoCG 2018
LandHongarije
StadBudapest
Periode11/06/1814/06/18

Vingerafdruk Duik in de onderzoeksthema's van 'Approximating the distribution of the median and other robust estimators on uncertain data'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K. A., Phillips, J. M., & Tang, P. (2018). Approximating the distribution of the median and other robust estimators on uncertain data. In C. D. Toth, & B. Speckmann (editors), 34th International Symposium on Computational Geometry, SoCG 2018 [16] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 99). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.16