Simpler Minimum Enclosing Ball: Fast approximate MEB algorithm for extensive kernel methods
Yongqing Wang, Yongkang Zou, Suiwu Zheng, Xinlan Guo · 2008
We develop a simple and fast (1 + ∈)-approximate algorithm for computing the Minimum Enclosing Ball (MEB) of a points set in high dimensional Euclidean space without requirement of any numerical solver. We prove theoretically that the proposed Simpler Minimum Enclosing Ball (SMEB) algorithm converges to the optimum within any precision in O(1/∈) iterations. Compared to the MEB algorithms adopted in the Core Vector Machines (CVM) and Simpler Core Vector Machines (SCVM) recently arisen, it has the competitive performances in both training time and accuracy. Besides, the proposed algorithm does not need any extra requirement of kernels, it can be linked with extensive kernel methods, consequently. We also present the potential application areas for the algorithm theoretically, such as Unbalanced SVM and Ranking SVM. Experiments demonstrate the validity of the algorithm we proposed.