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

Introduction

Principal component analysis (PCA) is a fundamental tool for dimensionality reduction, data visualization, and low-rank approximation [2]. Given a data matrix $A \in\mathbb{R}^{n \times d}$, PCA finds a low-dimensional subspace that captures as much of the variation in the data as possible. If $A = U\Sigma V^{\mathsf{T}}$ is the singular value decomposition of $A$, the optimal rank-$k$ subspace is spanned by the top $k$ right singular vectors $V_k = [v_1 \ \cdots\ v_k]$. It is also the rank $k$ subspace that maximizes the total squared lengths of the projections of the data.

When the rows of $A$ contain information about individuals, releasing a subspace computed from $A$ can reveal information about a particular row. This motivates differentially private algorithms for PCA. We consider row-level privacy, where each row represents the data of one individual. We assume that every row has $\ell_2$ norm at most 1, and two matrices are adjacent if one row is replaced. Normalizing the lengths of the rows is natural because we would like to measure the correlation with the entire dataset and no single data point should have an outsize contribution. The goal is to estimate $V_k$ while protecting the privacy of every individual row. In this model, Dwork et al. [ [9] give a private rank-$k$ PCA algorithm whose subspace error scales with $\widetilde{O}(\sqrt{d})$. Thus, the error can be large when the number of dimensions $d$ is large. This motivates utility guarantees that exploit additional structure of the input matrix. One such structural parameter is coherence, which is related to the largest absolute entries of the left singular vectors $U$. Intuitively, coherence captures the difficulty in privatizing the singular vectors because it measures the maximum correlation between the singular vectors and individual data rows. The more the singular vectors reveal about one row, the more perturbation we need to protect privacy. On the other hand, for many natural datasets, such as when the data is close to i.i.d. data generated from a generative model, the coherence can be shown to be small. Previous work has shown that coherence-dependent guarantees can substantially improve on worst-case bounds on low-coherence data [Hardt and Roth, 2012, 2013, Hardt and Price, 2014, Balcan et al., 2016, Nicolas et al., 2025, d’Orsi and Novikov, 2026, Nguyen et al., 2026].

However, most earlier coherence-dependent guarantees were obtained under privacy models different from the row-level $\ell_2$ model considered in our paper. For example, Hardt and Roth [ [12] consider entry-level adjacency, under which neighboring matrices differ in a single entry by at most 1. Subsequent rank-$k$ results use structured adjacency models that, when restricted to a one-row change, impose a $\ell_1$-norm restriction on the changed row [Nicolas et al., 2025, d’Orsi and Novikov, 2026]. These models do not cover all neighboring datasets in our setting, since a row $a$ satisfying $\|a\|_2\le1$ can have $\|a\|_1$ as large as $\sqrt{d}$. Nguyen et al. [ [17] recently gave the first coherence-adaptive guarantee under row-level $\ell_2$ privacy. However, their algorithm and analysis are specific to estimating a single leading singular vector, leaving the analogous rank-$k$ problem open.

In this work, we give a coherence-adaptive algorithm for estimating the top-$k$ right singular subspace under row-level $\ell_2$ differential privacy. Our result extends the coherence-adaptive utility guarantee of Nguyen et al. [ [17] from the leading singular vector to the top-$k$ singular subspace while retaining the same privacy model. Our algorithm is based on a preconditioned and clipped variant of block power iteration. It does not require the coherence or the ratio $\sigma_{k+1}^2/\sigma_k^2$ as input, and its utility improves when the input has low coherence. The prior work is also suboptimal when the ratio $\sigma_{k+1}^2/\sigma_k^2$ is very close to 1 whereas our algorithm remains near optimal for all regimes of the ratio.

Our contributions

Let $\Delta_k := \sigma_k^2 - \sigma_{k+1}^2$ and let $\left\lVert(I-\widehat{X}\widehat{X}^{\mathsf{T}})V_k \right\rVert_2$ denote the error of an output $\widehat{X} \in\mathbb{R}^{d \times k}$ with orthonormal columns. Let $a_i^{\mathsf{T}}$ denote the $i$th row of $A$, and recall that $\lVert a_i \rVert_2 \le1$. We write $U_k = U_{:,1:k}$, $\Sigma_k = \operatorname{diag}(\sigma_1,\ldots,\sigma_k)$, $\lVert U \rVert_\infty= \max_{i,j} |U_{ij}|$. For the $i$th standard basis vector $e_i$, we have $\lVert e_i^{\mathsf{T}} U_k \rVert_2 \le\sqrt{k} \lVert U \rVert_\infty$.

Our main result is the following:

Comparison with prior works

We additionally write $\lVert V\rVert_\infty:= \max_{i,j}|V_{ij}|$. We summarize our results in comparison with prior work in Table 1.