Streaming Principal Component Analysis From Incomplete Data

Armin Eftekhari, Greg Ongie, Laura Balzano, Michael B. Wakin

Abstract

Linear subspace models are pervasive in computational sciences and particularly used for large datasets which are often incomplete due to privacy issues or sampling constraints. Therefore, a critical problem is developing an efficient algorithm for detecting low-dimensional linear structure from incomplete data efficiently, in terms of both computational complexity and storage. In this paper we propose a streaming subspace estimation algorithm called Subspace Navigation via Interpolation from Partial Entries (SNIPE) that efficiently processes blocks of incomplete data to estimate the underlying subspace model. In every iteration, SNIPE finds the subspace that best fits the new data block but remains close to the previous estimate. We show that SNIPE is a streaming solver for the underlying nonconvex matrix completion problem, that it converges globally to a stationary point of this program regardless of initialization, and that the convergence is locally linear with high probability. We also find that SNIPE shows state-of-the-art performance in our numerical simulations.

Introduction

Principal Component Analysis (PCA) is a cornerstone of data science, used to find low-dimensional structures in high-dimensional datasets. However, modern data often presents two major hurdles: its streaming nature, where data arrives sequentially and is too massive to store, and its incompleteness, where entries are missing due to sensor failures, privacy constraints, or deliberate undersampling.

While several "subspace tracking" algorithms exist, many lack rigorous theoretical convergence guarantees, especially when dealing with the nonconvex landscape of missing-data problems. The authors introduce SNIPE (Subspace Navigation via Interpolation from Partial Entries) to bridge this gap, providing an algorithm that is both practically high-performing and theoretically sound.

Comparison of complete (a) and incomplete (b) streaming data streams.

Methods

SNIPE processes incoming data in small blocks rather than vector-by-vector. It is built on the principle of least-change: at each step, it seeks a new subspace that best fits the current block of incomplete data while remaining as close as possible to the previous estimate.

Key technical features include:

  • Block Processing: By concatenating $b$ vectors into a block, SNIPE leverages low-rank structures more effectively than purely stochastic methods.
  • Interpolation: For missing entries, the algorithm uses the current subspace estimate to "fill in" gaps before performing a Rank-$r$ Singular Value Decomposition (SVD) to update the estimate.
  • Efficiency: It maintains an optimal computational complexity of $O(nr^2)$ flops per vector and a storage requirement of $O(nr)$, where $n$ is the ambient dimension and $r$ is the subspace rank.
Illustration of the block-wise data structure used in SNIPE for matrix completion.

Theoretical Contributions

The authors demonstrate that SNIPE is essentially a streaming solver for the nonconvex matrix completion problem. Significant theoretical contributions include:

  • Global Convergence: Proving that SNIPE converges to a stationary point regardless of initialization—a rare guarantee for nonconvex streaming algorithms.
  • Local Linearity: Once the estimate is sufficiently close to the true subspace, the error reduces at a linear rate (exponentially fast).
  • Coherence Sensitivity: The "spikiness" (coherence) of the data is identified as a critical bottleneck; signal concentration in few coordinates makes recovery harder under random subsampling.

Numerical Results

Evaluated on synthetic datasets, SNIPE consistently reached lower error rates faster than the modified Power Method and proved highly competitive with established algorithms like GROUSE and PETRELS. The experiments revealed a clear "phase transition": once the sampling probability $p$ passes a threshold related to rank and coherence, the estimation error drops precipitously toward zero. Empirical results suggest that a block size of $b \approx 2r$ provides the optimal balance between stability and convergence speed.

Conclusion and Future Work

SNIPE provides a robust framework for subspace estimation in the presence of missing data. While the current work proves convergence to a stationary point, future research will focus on identifying conditions for global optimality, extending proofs to account for additive measurement noise, and adapting the algorithm for dynamic subspaces that evolve over time.

Summary updated

Abstract

Linear subspace models are pervasive in computational sciences and particularly used for large datasets which are often incomplete due to privacy issues or sampling constraints. Therefore, a critical problem is developing an efficient algorithm for detecting low-dimensional linear structure from incomplete data efficiently, in terms of both computational complexity and storage. In this paper we propose a streaming subspace estimation algorithm called Subspace Navigation via Interpolation from Partial Entries (SNIPE) that efficiently processes blocks of incomplete data to estimate the underlying subspace model. In every iteration, SNIPE finds the subspace that best fits the new data block but remains close to the previous estimate. We show that SNIPE is a streaming solver for the underlying nonconvex matrix completion problem, that it converges globally to a stationary point of this program regardless of initialization, and that the convergence is locally linear with high probability. We also find that SNIPE shows state-of-the-art performance in our numerical simulations.
BibTeX
@misc{eftekhari2016streaming,
  author = {Armin Eftekhari and Greg Ongie and Laura Balzano and Michael B. Wakin},
  title = {{Streaming Principal Component Analysis From Incomplete Data}},
  year = {2016},
  eprint = {1612.00904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.00904},
}
Figure