# Tight Differentially Private PCA via Matrix Coherence

arXiv: https://arxiv.org/abs/2510.26679 · HTML: https://mlsanity.com/paper/2510.26679/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2025.

## Built on by (most cited first, 3 of 3)

- [Adaptive Power Iteration Method for Differentially Private PCA](https://mlsanity.com/paper/2602.11454/) (2026)
- [Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds](https://mlsanity.com/paper/2605.15943/) (2026)
- [Gap-free Differentially Private PCA for Gaussian Data](https://mlsanity.com/paper/2609.31614/) (2026)

## Abstract (arXiv)

We revisit the task of computing the span of the top r singular vectors u1, ldots, ur 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 u1, ldots, ur and the spectral gap σr - σr+1. This resolves a question posed by Hardt and Roth~citehardt2013beyond. 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. In addition, we prove that (rank-r) coherence does not increase under Gaussian perturbations. This implies that any estimator based on the Gaussian mechanism -- including ours -- preserves the coherence of the input. We conjecture that similar behavior holds for other structured models, including planted problems in graphs. We also explore applications of coherence to graph problems. In particular, we present a differentially private algorithm for Max-Cut and other constraint satisfaction problems under low coherence assumptions.