Tight Differentially Private PCA via Matrix Coherence

We revisit the task of computing the span of the top $r$ singular vectors $u_1, \ldots, u_r$ of a matrix under differential privacy. We show that a simple and efficient algorithm—based on singular value decomposition and standard perturbation mechanisms—returns a private rank-$r$ approximation whose error depends only on the rank-$r$ coherence of $u_1, \ldots, u_r$ and the spectral gap ór $\sigma_r - \sigma_{r+1}$. This resolves a question posed by Hardt and Roth [HR13]. Our estimator outperforms the state of the art—significantly so in some regimes. In particular, we show that in the dense setting, it achieves the same guarantees for single-spike PCA in the Wishart model as those attained by optimal non-private algorithms, whereas prior private algorithms failed to do so.