  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.
