A Framework for Private Matrix Analysis
This work addresses privacy-preserving data analysis for streaming data, offering incremental improvements by extending existing methods to new variants and settings.
The authors tackled the problem of private matrix analysis in the sliding window model, developing efficient differentially private algorithms for tasks like spectral approximation and principal component analysis with o(W) space, and introduced new algorithms for sparse and non-negative variants where none existed before.
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.