Differentially Private Robust Low-Rank Approximation

In this paper, we study the following robust low-rank matrix approximation problem: given a matrix A is an element of R-nxd ,find a rank-k matrix M, while satisfying differential privacy, such that parallel to A - M parallel to(p )<= alpha. OPTk(A) + tau, where parallel to B parallel to(p) is the = entry-wise l(p)-norm of B and OPTk(A) := min(rank(X)<= k) parallel to A - X parallel to(p). It is well known that low-rank approximation w.r.t. entrywise l(p)-norm, for p is an element of [1, 2), yields robustness to gross outliers in the data. We propose an algorithm that guarantees alpha = (O) over tilde (k(2)), tau = (O) over tilde (k(2)(n + kd/epsilon), runs in (O) over tilde((n+d)poly k) time and uses O(k (n+d) log k) 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 Pi such that parallel to A - A Pi parallel to(p) <= alpha . OPTk(A) + tau.