Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles