Beating Randomized Response on Incoherent Matrices

Details Beating Randomized Response on Incoherent Matrices Beating Randomized Response on Incoherent Matrices

2011-11-02

arxiv.org/abs/1111.0623v1

Computer Science

Data Structures and Algorithms

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Beating Randomized Response on Incoherent Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Beating Randomized Response on Incoherent Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beating Randomized Response on Incoherent Matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-329929