License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.38
URN: urn:nbn:de:0030-drops-129045
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12904/
Go to the corresponding LIPIcs Volume Portal

Ding, Hu

A Sub-Linear Time Framework for Geometric Optimization with Outliers in High Dimensions

pdf-format:
LIPIcs-ESA-2020-38.pdf (0.8 MB)

Abstract

Many real-world problems can be formulated as geometric optimization problems in high dimensions, especially in the fields of machine learning and data mining. Moreover, we often need to take into account of outliers when optimizing the objective functions. However, the presence of outliers could make the problems to be much more challenging than their vanilla versions. In this paper, we study the fundamental minimum enclosing ball (MEB) with outliers problem first; partly inspired by the core-set method from Bădoiu and Clarkson, we propose a sub-linear time bi-criteria approximation algorithm based on two novel techniques, the Uniform-Adaptive Sampling method and Sandwich Lemma. To the best of our knowledge, our result is the first sub-linear time algorithm, which has the sample size (i.e., the number of sampled points) independent of both the number of input points n and dimensionality d, for MEB with outliers in high dimensions. Furthermore, we observe that these two techniques can be generalized to deal with a broader range of geometric optimization problems with outliers in high dimensions, including flat fitting, k-center clustering, and SVM with outliers, and therefore achieve the sub-linear time algorithms for these problems respectively.

BibTeX - Entry

@InProceedings{ding:LIPIcs:2020:12904,
  author =	{Hu Ding},
  title =	{{A Sub-Linear Time Framework for Geometric Optimization with Outliers in High Dimensions}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{38:1--38:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12904},
  URN =		{urn:nbn:de:0030-drops-129045},
  doi =		{10.4230/LIPIcs.ESA.2020.38},
  annote =	{Keywords: minimum enclosing ball, outliers, shape fitting, high dimensions, sub-linear time}
}

Keywords: minimum enclosing ball, outliers, shape fitting, high dimensions, sub-linear time
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI