Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
This work addresses computational bottlenecks in high-dimensional shape fitting for machine learning and data analysis, offering a more efficient solution with potential applications in kernel methods.
The paper tackles the probabilistic smallest enclosing ball (pSEB) problem in high dimensions by developing an algorithm that reduces its exponential dimension dependence to linear, using stochastic subgradient descent and sampling techniques, and applies it to extend support vector data description to probabilistic cases via kernel functions.
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.