论文标题
私人矩阵分析的框架
A Framework for Private Matrix Analysis
论文作者
论文摘要
我们在滑动窗口模型中研究了私人矩阵分析，其中只有最后的$ w $更新对矩阵可用于分析。我们为频谱近似，主成分分析和线性回归提供了第一个高效的$ O（w）$ space私有算法。我们还启动并显示了有效的私有算法，用于主要组件分析的两个重要变体：稀疏主成分分析和非负主成分分析。在我们的工作之前，即使在静态数据设置中，也没有以稀疏和非负差异性主体组件分析而闻名的结果。这些算法是通过确定由流矩阵形成的阳性半足质矩阵的足够条件来获得的。我们还显示了计算低级别近似所需的空间的下限，即使该算法给出了乘法近似和累加误差。这是通过减少到一定的沟通复杂性问题来进行的。
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.
