Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

TL;DR

We derive sharp spectral-norm bounds for noisy low-rank approximation, improving prior results by up to $\sqrt{n}$. Applied to DP-PCA, our method resolves an open problem and matches empirical error via a novel contour bootstrapping technique.

Opening excerpt from the authors’ abstract. source