Differentially Private Robust Low-Rank Approximation

Authors:
Raman Arora Johns Hopkins University
Vladimir Braverman Johns Hopkins University
Jalaj Upadhyay Johns Hopkins University

Introduction:

In this paper, the authors study the following robust low-rank matrix approximation problem: given a matrix $A in R^{n imes d}$, find a rank-$k$ matrix $B$, while satisfying differential privacy, such that $ orm{ A - B }_p leq alpha mathsf{OPT}_k(A) + au,$ where $ orm{ M }_p$ is the entry-wise $ell_p$-norm and $mathsf{OPT}_k(A):=min_{mathsf{rank}(X) leq k} orm{ A - X}_p$.

Abstract:

In this paper, we study the following robust low-rank matrix approximation problem: given a matrix $A \in \R^{n \times d}$, find a rank-$k$ matrix $B$, while satisfying differential privacy, such that $ \norm{ A - B }_p \leq \alpha \mathsf{OPT}_k(A) + \tau,$ where $\norm{ M }_p$ is the entry-wise $\ell_p$-norm and $\mathsf{OPT}_k(A):=\min_{\mathsf{rank}(X) \leq k} \norm{ A - X}_p$. It is well known that low-rank approximation w.r.t. entrywise $\ell_p$-norm, for $p \in [1,2)$, yields robustness to gross outliers in the data. We propose an algorithm that guarantees $\alpha=\widetilde{O}(k^2), \tau=\widetilde{O}(k^2(n+kd)/\varepsilon)$, runs in $\widetilde O((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 $\norm{ A - A \Pi }_p \leq \alpha \mathsf{OPT}_k(A) + \tau.$

You may want to know: