Provable Subspace Tracking From Missing Data and Matrix Completion

Praneeth Narayanamurthy, Vahid Daneshpajooh, Namrata VaswaniIEEE TSP 2019 · DOI

TL;DR

This paper introduces a novel algorithm, NORST-miss, that provably tracks low-dimensional subspaces in data with missing entries, even when the subspace changes over time. This work offers the first complete theoretical guarantees for this challenging problem and also provides a provably correct and efficient solution for low-rank matrix completion.

What Problem Does This Paper Address?

Many real-world datasets, such as video surveillance or recommendation systems, suffer from missing data. Understanding the underlying low-dimensional structure (subspace) of this data is crucial for tasks like anomaly detection or data reconstruction. However, tracking this subspace becomes significantly harder when data is missing. Existing methods either struggle with time-varying subspaces or offer only partial theoretical guarantees, meaning they don't fully explain under what conditions they will work. This paper tackles the problem of "Subspace Tracking with Missing Data" (ST-miss) and provides a provable solution that handles both missing entries and dynamic subspaces, a significant step towards robust and reliable data analysis.

Methods

The core contribution is a modification of a previously proposed algorithm called NORST (Nearly Optimal Robust Subspace Tracking). The new algorithm, NORST-miss, adapts NORST to handle missing data. It uses a mini-batch approach, processing data in chunks. Key techniques include:

  • Projected Least Squares (LS): This step estimates the missing entries of the data vector by projecting it onto the orthogonal complement of the current subspace estimate.
  • Subspace Update: This phase uses the "filled-in" data to refine the subspace estimate, often employing Singular Value Decomposition (SVD) on a batch of data.
  • Change Detection: The algorithm includes a mechanism to detect when the underlying subspace has changed, allowing it to adapt quickly.

The theoretical guarantees are "complete," meaning they prove that under mild assumptions on the input data, the algorithm's output will be close to the true subspace. The algorithm is also designed to be memory-efficient.

Datasets

The paper uses synthetic datasets generated according to specific models (e.g., Bernoulli model for missing entries, piecewise constant subspace changes) to validate theoretical claims. Real-world video data from the "Meeting Room" dataset is also used for experiments, demonstrating the algorithm's performance on practical scenarios like background recovery.

Key Insights and Ideas

  • Bridging ST-miss and Matrix Completion: The paper elegantly shows that a provable solution for ST-miss can also be interpreted as a provably correct mini-batch solution for low-rank matrix completion, unifying two related problems.
  • Complete Guarantees for Dynamic Subspaces: Unlike prior work that often assumed fixed subspaces or provided only partial guarantees, this paper offers a complete theoretical framework for tracking time-varying (piecewise constant) subspaces with missing data.
  • Near-Optimal Performance: The algorithm achieves near-optimal delay for subspace change detection and tracking, meaning it adapts to changes very quickly.
  • Practical Efficiency: Despite strong theoretical guarantees, NORST-miss is shown to be computationally efficient and memory-frugal, making it suitable for real-world applications.

Key Results

  • Provable Accuracy: The algorithm is proven to track subspaces to any desired accuracy ($\epsilon$) with high probability, under mild assumptions on data incoherence and missing entry distribution.
  • Fast Adaptation: NORST-miss can detect and track subspace changes with a near-optimal delay, significantly outperforming previous methods in dynamic scenarios.
  • Efficient Matrix Completion: The algorithm provides a provably correct and memory-efficient solution for low-rank matrix completion, especially competitive in regimes where subspaces change frequently.
  • Experimental Validation: Numerical experiments show that NORST-miss performs comparably to or better than state-of-the-art methods like PETRELS, especially in scenarios with time-varying subspaces, while being significantly faster.

Limitations and Future Work

  • Assumptions: While the assumptions are mild, the algorithm still relies on data incoherence and bounded fractions of missing entries. The paper notes that the requirement on observed entries can be higher than some existing matrix completion methods, though it offers advantages in terms of probabilistic models.
  • Streaming vs. Mini-batch: The current approach is mini-batch, not fully streaming. Developing a provably correct streaming solution without assuming i.i.d. Bernoulli missing entries is an open question.
  • Reducing Observed Entries: Further work could focus on reducing the number of required observed entries.
  • Control Applications: The authors pose an interesting future direction: can the tracked estimates be used for active sampling or "control" in applications where the observation set can be designed?
  • Robust ST-miss: While the paper extends to robust ST-miss, there's room to relax outlier magnitude lower bounds and explore more general probabilistic models for missing and outlier entries.

Summary updated

BibTeX
@article{narayanamurthy2019provable,
  author = {Praneeth Narayanamurthy and Vahid Daneshpajooh and Namrata Vaswani},
  title = {{Provable Subspace Tracking From Missing Data and Matrix Completion}},
  journal = {IEEE TSP},
  year = {2019},
  doi = {10.1109/tsp.2019.2924595},
}
Figure