arXiv preprint ·
Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In Principal Component Analysis (PCA), we are given as input a matrix $A\in\mathbb{R}^{n\times d}$ and an integer $k\leq 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space
Uniformity Testing for the Monomer-Dimer Model
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.