Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
arXiv:2006.08030 · doi:10.1109/JSAIT.2020.3040365
Abstract
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.
arXiv commentTo appear in IEEE Journal of Special Areas in Information Theory
References in corpus (15)
- User-friendly tail bounds for sums of random matrices
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
- Sparse PCA: Optimal rates and adaptive estimation
- Finite sample approximation results for principal component analysis: a matrix perturbation approach
- An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
- Fast Algorithms for Robust PCA via Gradient Descent
- Minimax sparse principal subspace estimation in high dimensions
- Non-convex Robust PCA
- Normal approximation and concentration of spectral projectors of sample covariance
- Robust PCA with Partial Subspace Knowledge
- Provable Dynamic Robust PCA or Robust Subspace Tracking
- Provable Subspace Tracking from Missing Data and Matrix Completion
- Nearly Optimal Robust Subspace Tracking
- Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise