Beating Randomized Response on Incoherent Matrices

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).

References in corpus (1)

• Lower bounds in differential privacy

Cited by in corpus (21)

• Extremal Mechanisms for Local Differential Privacy
• The Noisy Power Method: A Meta Algorithm with Applications
• MVG Mechanism: Differential Privacy under Matrix-Valued Query
• Federated Principal Component Analysis
• Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• An Anti-Folk Theorem for Large Repeated Games with Imperfect Monitoring
• Wishart Mechanism for Differentially Private Principal Components Analysis
• Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized Response
• Near-Optimal Algorithms for Differentially-Private Principal Components
• Differential privacy and robust statistics in high dimensions
• Smooth Sensitivity Based Approach for Differentially Private Principal Component Analysis
• Beyond Worst-Case Analysis in Private Singular Vector Computation
• Analytic Theory to Differential Privacy
• A Framework for Private Matrix Analysis
• On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm
• On Differentially Private Online Collaborative Recommendation Systems
• The Price of Differential Privacy for Low-Rank Factorization
• Private Graph Data Release: A Survey
• Privately Learning Subspaces
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy