Reducing the run-time complexity of support vector data descriptions

Support vector data description (SVDD) has become a very attractive kernel method due to its good results in many novelty detection problems. Similar to the support vector machine (SVM), the decision function of SVDD is also expressed in terms of the kernel expansion, which results in a run-time complexity linear in the number of support vectors. For applications where fast real-time response is needed, how to speed up the decision function is crucial. A fast SVDD (F-SVDD) algorithm is presented to deal with this issue. In F-SVDD, we first discover several important geometric properties in the feature space induced by the Gaussian kernel, and then solve the preimage problem for the agent of the SVDD sphere center based on the properties. The kernel expansion can thus be compressed into one with only one term, and the run-time complexity of the F-SVDD decision function is no longer linear in the support vectors, but is a constant. Results are very encouraging.