Anomaly detection with score functions based on the reconstruction error of the kernel PCA

International audienceWe propose a novel non-parametric statistical test that allows the detection of anomalies given a set of (possibly high dimensional) sample points drawn from a nominal probability distribution. Our test statistic is the distance of a query point mapped in a feature space to its projection on the eigen-structure of the kernel matrix computed on the sample points. Indeed, the eigenfunction expansion of a Gram matrix is dependent on the input data density f0. The resulting statistical test is shown to be uniformly most powerful for a given false alarm level alpha when the alternative density is uniform over the support of the null distribution. The algorithm can be computed in O(n^3 + n^2) and testing a query point only involves matrix vector products. Our method is tested on both artificial and benchmarked real data sets and demonstrates good performances w.r.t. competing methods