Abstract 

In this paper, we study the following robust low-rank matrix approximation problem: given a matrix find a rank-k matrix M , while satisfying differential privacy, such that where is the It is well known that low-rank approximation w.r.t. entrywise -norm, for yields robustness to gross outliers in the data. We propose an algorithm that guarantees time and uses space. We study extensions to the streaming setting where entries of the matrix arrive in an arbitrary order and output is produced at the very end or continually. We also study the related problem of differentially private robust principal component analysis (PCA), wherein we return a rank-k projection matrix  such that