Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Towards the methodology for solving the minimum enclosing ball and related problems
Methodology is provided towards the solution of the minimum enclosing ball problem. This problem concerns the determination of the unique spherical surface of smallest radius enclosing a given bounded set in the d-dimens…
Towards the mathematical foundation of the minimum enclosing ball and related problems
Theoretical background is provided towards the mathematical foundation of the minimum enclosing ball problem. This problem concerns the determination of the unique spherical surface of smallest radius enclosing a given b…
Few-Shot Continual Learning via Flat-to-Wide Approaches
Existing approaches on continual learning call for a lot of samples in their training processes. Such approaches are impractical for many real-world problems having limited samples because of the overfitting problem. Thi…
Continual LearningData AugmentationLearning Confidence Ellipsoids and Applications to Robust Subspace Recovery
We study the problem of finding confidence ellipsoids for an arbitrary distribution in high dimensions. Given samples from a distribution $D$ and a confidence parameter $α$, the goal is to find the smallest volume ellips…
On a minimum enclosing ball of a collection of linear subspaces
This paper concerns the minimax center of a collection of linear subspaces. When the subspaces are $k$-dimensional subspaces of $\mathbb{R}^n$, this can be cast as finding the center of a minimum enclosing ball on a Gras…