Dimensionality-reduced Secure Outlier Detection on Union of Subspaces

摘要

In the problem of outlier detection (OD) on a union of subspaces (UoS), inliers are assumed to lie around a union of low-dimensional subspaces, and the goal is to detect the outliers that are not close to any of these subspaces. Among various algorithms, sparse self-representation-based ones have attracted much attention because of their theoretical performance guarantee. However, these algorithms need direct access to all raw data, and thus have poor data security and privacy protection capability. To solve this problem, in this paper we propose a new algorithm called dimensionality-reduced secure outlier detection (DrSOD), which uses random projection as a preprocessing step to avoid direct access to the raw data. We theoretically prove that DrSOD can correctly detect outliers with overwhelming probability under connectivity assumptions. In addition, the random projection step improves the computational efficiency of the algorithm. Experiments on synthetic and real-world datasets also demonstrate the effectiveness and efficiency of DrSOD.