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.