Beating randomized response on incoherent matrices

DOI10.1145/2213977.2214088MaRDI QIDQ5415548zbMATH OpenOpenAlexFDO

Authors Moritz Hardt, Aaron Roth

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0623

zbMATH Keywords

singular value decompositiondifferential privacy

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25)

Abstract: Computing accurate low rank approximations of large matrices is a fundamental data mining task. In many applications however the matrix contains sensitive information about individuals. In such case we would like to release a low rank approximation that satisfies a strong privacy guarantee such as differential privacy. Unfortunately, to date the best known algorithm for this task that satisfies differential privacy is based on naive input perturbation or randomized response: Each entry of the matrix is perturbed independently by a sufficiently large random noise variable, a low rank approximation is then computed on the resulting matrix. We give (the first) significant improvements in accuracy over randomized response under the natural and necessary assumption that the matrix has low coherence. Our algorithm is also very efficient and finds a constant rank approximation of an m x n matrix in time O(mn). Note that even generating the noise matrix required for randomized response already requires time O(mn).

Recommendations

• On differentially private low rank approximation
• Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Privacy-preserving linear and nonlinear approximation via linear programming

Cited in

(6)

• Beyond worst-case analysis in private singular vector computation
• Private low-rank approximation for covariance matrices, Dyson Brownian motion, and eigenvalue-gap bounds for Gaussian perturbations
• Old techniques in differentially private linear regression
• Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
• Privacy-preserving linear and nonlinear approximation via linear programming
• Differential privacy in probabilistic systems

This page was built for publication: Beating randomized response on incoherent matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415548)