Provable Subspace Tracking from Missing Data and Matrix Completion

Abstract

We study the problem of subspace tracking in the presence of missing data (ST-miss). In recent work, we studied a related problem called robust ST. In this work, we show that a simple modification of our robust ST solution also provably solves ST-miss and robust ST-miss. To our knowledge, our result is the first `complete' guarantee for ST-miss. This means that we can prove that under assumptions on only the algorithm inputs, the output subspace estimates are close to the true data subspaces at all times. Our guarantees hold under mild and easily interpretable assumptions, and allow the underlying subspace to change with time in a piecewise constant fashion. In contrast, all existing guarantees for ST are partial results and assume a fixed unknown subspace. Extensive numerical experiments are shown to back up our theoretical claims. Finally, our solution can be interpreted as a provably correct mini-batch and memory-efficient solution to low-rank Matrix Completion (MC).

arXiv commentWriting changes; includes a detailed discussion of noise analysis; contains discussion for Matrix Completion; Accepted to IEEE Transactions on Signal Processing

References in corpus (17)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• A Simpler Approach to Matrix Completion
• Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support
• Guaranteed Matrix Completion via Non-convex Factorization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fast Algorithms for Robust PCA via Gradient Descent
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Non-convex Robust PCA
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Universal Matrix Completion
• Fast matrix completion without the condition number
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Provable Dynamic Robust PCA or Robust Subspace Tracking
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Nearly Optimal Robust Subspace Tracking
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems

Cited by in corpus (4)

• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Provable Low Rank Phase Retrieval