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.SoCG.2019.47
URN: urn:nbn:de:0030-drops-104515
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10451/
Go to the corresponding LIPIcs Volume Portal

Krivosija, Amer ; Munteanu, Alexander

Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling

pdf-format:
LIPIcs-SoCG-2019-47.pdf (0.5 MB)

Abstract

We study a variant of the median problem for a collection of point sets in high dimensions. This generalizes the geometric median as well as the (probabilistic) smallest enclosing ball (pSEB) problems. Our main objective and motivation is to improve the previously best algorithm for the pSEB problem by reducing its exponential dependence on the dimension to linear. This is achieved via a novel combination of sampling techniques for clustering problems in metric spaces with the framework of stochastic subgradient descent. As a result, the algorithm becomes applicable to shape fitting problems in Hilbert spaces of unbounded dimension via kernel functions. We present an exemplary application by extending the support vector data description (SVDD) shape fitting method to the probabilistic case. This is done by simulating the pSEB algorithm implicitly in the feature space induced by the kernel function.

BibTeX - Entry

@InProceedings{krivosija_et_al:LIPIcs:2019:10451,
  author =	{Amer Krivosija and Alexander Munteanu},
  title =	{{Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10451},
  URN =		{urn:nbn:de:0030-drops-104515},
  doi =		{10.4230/LIPIcs.SoCG.2019.47},
  annote =	{Keywords: geometric median, convex optimization, smallest enclosing ball, probabilistic data, support vector data description, kernel methods}
}

Keywords: geometric median, convex optimization, smallest enclosing ball, probabilistic data, support vector data description, kernel methods
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

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