Noisy Power Method for Perturbed Subspace Iteration, Streaming PCA, and Differentially Private Spectral Analysis

If at each step ell of the Noisy Power Method (Figure 1) the perturbation G_ell in R^{d x p} satisfies 5||G_ell|| <= varepsilon*(sigma_k - sigma_{k+1}) and 5||U^T G_ell|| <= (sigma_k - sigma_{k+1})*cos theta_k(U, X_0) for varepsilon < 1/2, then the k-th principal angle tangent contracts at every step as tan theta_k(U, A X_ell + G_ell) <= max(varepsilon, max(varepsilon, (sigma_{k+1}/sigma_k)^{1/4})*tan theta_k(U, X_ell)) (Lemma 2.3) and reaches ||(I - X_L X_L^T)U|| = sin theta_k(U, X_L) <= tan theta_k(U, X_L) <= varepsilon in L = O((sigma_k / (sigma_k - sigma_{k+1}))*log(d*tau/varepsilon)) steps when initialized with a random p-dimensional orthonormal basis X_0 satisfying tan theta_k(U, X_0) <= tau*sqrt(d)/(sqrt(p) - sqrt(k - 1)) with probability 1 - tau^{-Omega(p+1-k)} - e^{-Omega(d)} (Theorem 2.4, Lemma 2.5, and Corollary 1.1).

For any (B, p)-round distribution D over R^d with covariance A = E_{z~D}[z z^T] (Definition 3.1), the O(pd)-space Streaming Power Method (SPM, Figure 2)—which divides n samples into L blocks of size T = floor(n/L) and updates Y_ell = A_ell X_{ell-1} = A X_{ell-1} + G_ell followed by QR factorization—outputs X_L satisfying tan theta(U, X_L) <= varepsilon with probability 9/10 using n <= O_tilde(B p sigma_k max{1/varepsilon^2, B p / (sqrt(p) - sqrt(k-1))^2} log^2(d) / ((sigma_k - sigma_{k+1})^3 d)) samples (Theorem 3.2), yielding n = O_tilde(((lambda_1^2 + sigma^2)^2 (lambda_k^2 + sigma^2) / (varepsilon^2 lambda_k^6)) d k) in the spiked covariance model for p = 2k (Corollary 3.3).

In the Private Power Method (PPM, Figure 3), injecting Gaussian noise G_ell ~ N(0, ||X_{ell-1}||_infty^2 sigma^2)^{d x p} with sigma = varepsilon^{-1}sqrt(4 p L log(1/delta)) satisfies entry-level (varepsilon, delta)-differential privacy (Claim 4.2); furthermore, because Gram-Schmidt orthonormalization commutes with any orthogonal transformation O sharing A's eigenbasis (GS(O V) = O * GS(V), Lemmas 4.11-4.12), the inner-product signs (sign(<u_i, x>))_{i=1}^d of any column x of X_ell are uniformly distributed in {-1, 1}^d (Lemma 4.13), bounding max_{ell in [L]} ||X_ell||_infty^2 <= O(mu(A) log(d) / d) in terms of matrix coherence mu(A) = max{d||U||_infty^2, d'||V||_infty^2} (Theorem 4.9) and achieving dimension-free subspace error ||(I - X_L X_L^T)U|| <= O((sigma * sqrt(mu(A) log(d) log(L)) / (sigma_k - sigma_{k+1})) * (sqrt(p) / (sqrt(p) - sqrt(k - 1)))) (Theorem 1.4).