Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence

arXiv:2610.36691 · cs.DS · Submitted 2026-10-27 · Read on arXiv

cs.DS

Submitted: 2026-10-27

Updated: 2026-11-19

License: http://creativecommons.org/licenses/by/4.0/

The gist: In Principal Component Analysis (PCA), we are given as input a matrix A in R n times d and an integer k at most d, and the goal is to find the top k right-singular vectors of A.

Terminology

Abstract

In Principal Component Analysis (PCA), we are given as input a matrix A in R n times d and an integer k at most d, and the goal is to find the top k right-singular vectors of A. We consider the setting where each row of A is the private data of an individual, and we design an (ε,δ) -differentially private algorithm whose utility guarantee improves with the coherence of the input matrix. Prior works were either restricted to the case k=1 or ensured significantly weaker privacy protections. Our algorithm is based on a preconditioned variant of the power iteration method that is designed to significantly reduce the noise needed to ensure privacy.

Related papers