DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2019.47

Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling

Authors: Amer Krivošija and Alexander Munteanu

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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.

Cite as

Amer Krivošija and Alexander Munteanu. Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{krivosija_et_al:LIPIcs.SoCG.2019.47,
  author =	{Krivo\v{s}ija, Amer and Munteanu, Alexander},
  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 =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.47},
  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}
}

Search Results

Documents authored by Munteanu, Alexander

Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling

Abstract

Cite as

Thanks for your feedback!

Could not send message