Fast and Space-optimal Low-rank Factorization in the Streaming Model With Application in Differential Privacy

Streaming Matrix Factorization and differential privacy, interesting !

Fast and Space-optimal Low-rank Factorization in the Streaming Model With Application in Differential Privacy by Jalaj Upadhyay

In this paper, we consider the problem of computing a low-rank factorization of an m×n matrix in the general turnstile update model. We consider both the private and non-private setting. In the non-private setting, we give a space-optimal algorithm that computes a low-rank factorization. Our algorithm maintains three sketches of the matrix instead of five as in Boutsidis {\it et al.} (STOC 2016). Our algorithm takes O˜(1) time to update the sketch and computes the factorization in time linear in the sparsity and the dimensions of the matrix. In the private setting, we study low-rank factorization in the framework of differential privacy and under turnstile updates. We give two algorithms with respect to two levels of privacy. Both of our privacy levels are stronger than earlier studied privacy levels, namely that of Blocki {\it et al.} (FOCS 2012), Dwork {\it et al.} (STOC 2014), Hardt and Roth (STOC 2012, STOC 2013), and Hardt and Price (NIPS 2014).

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.