A Framework for Private Matrix Analysis
We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Wishart Mechanism for Differentially Private Principal Components Analysis
We propose a new input perturbation mechanism for publishing a covariance matrix to achieve $(\epsilon,0)$-differential privacy. Our mechanism uses a Wishart distribution to generate matrix noise. In particular, We apply…
Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
We study spectral graph clustering under edge differential privacy. We propose a matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix. While edge flipping al…
Graph ClusteringDifferentially Private Precision Matrix Estimation
In this paper, we study the problem of precision matrix estimation when the dataset contains sensitive information. In the differential privacy framework, we develop a differentially private ridge estimator by perturbing…
Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates
We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i) (ne…
Matrix CompletionDouble-Private Distributed Estimation Algorithm Using Differential Privacy and a Key-Like Proportionate Matrix with Its Performance Analysis
In this brief, we present an enhanced privacy-preserving distributed estimation algorithm, referred to as the ``Double-Private Algorithm," which combines the principles of both differential privacy (DP) and cryptography.…
Privacy Preserving