论文标题
通过PCA在稀疏数据依赖性噪声中通过PCA进行快速稳健的子空间跟踪
Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
论文作者
论文摘要
这项工作研究了强大的子空间跟踪（ST）问题。稳健的st可以简单地理解为强壮PCA的（缓慢）时变的子空间扩展。它假设真实数据位于低维子空间中，该子空间是固定或随着时间而缓慢变化的。目的是在存在添加剂稀疏异常值的情况下跟踪随着时间的变化子空间，并快速执行此操作（延迟延迟）。我们引入了一种“快速”的迷你小批量鲁棒ST解决方案，该解决方案在轻度假设下被证明是正确的。在这里，“快速”表示两件事：（i）可以检测到子空间的变化，并且可以以几乎最佳的延迟跟踪子空间，并且（ii）执行此操作的时间复杂性与简单（非bud bust）PCA的时间复杂性相同。我们的主要结果假设分段恒定子空间（需要可识别性），但是我们还为每次有一点变化的情况提供了推论。 第二个贡献是在线性数据依赖性噪声中对PCA的新型非反应保证。这是有用的重要设置，用于线性依赖数据的噪声，该噪声稀疏，支持随着时间的流逝而变化足够多。我们提出的强大ST解决方案的子空间更新步骤的分析使用了此结果。
This work studies the robust subspace tracking (ST) problem. Robust ST can be simply understood as a (slow) time-varying subspace extension of robust PCA. It assumes that the true data lies in a low-dimensional subspace that is either fixed or changes slowly with time. The goal is to track the changing subspaces over time in the presence of additive sparse outliers and to do this quickly (with a short delay). We introduce a "fast" mini-batch robust ST solution that is provably correct under mild assumptions. Here "fast" means two things: (i) the subspace changes can be detected and the subspaces can be tracked with near-optimal delay, and (ii) the time complexity of doing this is the same as that of simple (non-robust) PCA. Our main result assumes piecewise constant subspaces (needed for identifiability), but we also provide a corollary for the case when there is a little change at each time. A second contribution is a novel non-asymptotic guarantee for PCA in linearly data-dependent noise. An important setting where this is useful is for linearly data dependent noise that is sparse with support that changes enough over time. The analysis of the subspace update step of our proposed robust ST solution uses this result.
