Principal Component Analysis in the local differential privacy model

In this paper, we study the Principal Component Analysis (PCA) problem under the (distributed) non-interactive local differential privacy model. For the low dimensional case (i.e., p << n), we show the optimal rate of Theta(kp/n epsilon(2)) (omitting the eigenvalue terms) for the private minimax risk of the k-dimensional PCA using the squared subspace distance as the measurement, where n is the sample size and E is the privacy parameter. For the high dimensional (i.e., p >> n) row sparse case, we first give a lower bound of Omega(ks log p/n epsilon(2))) on the private minimax risk, where s is the underlying sparsity parameter. Then we provide an efficient algorithm to achieve the upper bound of O(s(2) log p/n epsilon(2)). Experiments on both synthetic and real world datasets confirm our theoretical guarantees. (C) 2019 Elsevier B.V. All rights reserved.