Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors

Morteza Mardani, Gonzalo Mateos, Georgios B. Giannakis

Abstract

Modern data analysis frequently encounters massive, streaming datasets characterized by significant missing entries. Traditional batch matrix completion methods, while effective, are often computationally prohibitive for real-time applications and exceed memory limits. This paper presents a suite of scalable online algorithms for subspace tracking and imputation in matrices and tensors. By reformulating nuclear-norm regularization into a separable form, the authors develop second-order Recursive Least Squares (RLS) and first-order Stochastic Gradient Descent (SGD) methods. These algorithms offer theoretical convergence guarantees and demonstrate superior performance in real-world applications, including network traffic monitoring and cardiac MRI reconstruction.

Introduction

In the era of "Big Data," information is often simultaneously massive, streaming, and incomplete. Examples range from network monitoring systems where only a fraction of links are measured at any moment, to recommendation engines where new user ratings arrive continuously. The standard approach to handling missing data is matrix completion, which assumes an underlying low-rank structure. However, traditional batch algorithms require storing the entire dataset in memory and rely on computationally expensive Singular Value Decompositions (SVD), making them unsuitable for streaming or high-velocity data.

Existing online trackers often lack the theoretical guarantees or robust regularization needed to handle high levels of noise and missingness. This work bridges the gap between robust batch methods and efficient online tracking by introducing a framework that handles streaming data with the same reliability as batch processing.

Methodology

The core innovation of this work lies in the handling of nuclear-norm regularization—the gold standard for enforcing low-rank structure—in a streaming context. The authors introduce several key techniques to make this possible:

  1. Separable Reformulation: Since the nuclear norm is typically non-separable, the authors utilize a mathematical reformulation to recast it as the sum of Frobenius norms of two smaller factor matrices ($X = LQ'$). This allows the optimization problem to be updated piece-by-piece as new data arrives.
  2. Alternating Recursive Least Squares (RLS): A second-order algorithm is developed to update the subspace estimate with each new data vector. While computationally more intensive ($O(P\rho^3)$), it provides high accuracy.
  3. Accelerated Stochastic Gradient Descent (SGD): For massive scales, a first-order SGD approach using Nesterov acceleration is proposed. This version is significantly faster ($O(|\omega_t|\rho^2)$) and optimized for big data landscapes.
  4. Tensor Extension: The framework is extended to multi-way arrays (tensors) using the PARAFAC decomposition. This represents one of the first online algorithms capable of decomposing and imputing tensors with missing entries in real-time.
Visualization of the streaming data imputation process where partial observations are used to track and complete the underlying low-rank structure over time.

Experimental Evaluation

The algorithms were validated using both synthetic and high-impact real-world datasets:

  • Synthetic Data: Low-rank matrices and tensors were tested with varying levels of Gaussian noise and up to 75% missing entries.
  • Internet-2 Traffic: Real-world origin-to-destination flow traffic from a US backbone network was used to track network anomalies.
  • FOURDIX Cardiac MRI: A dataset of cardiac magnetic resonance imagery was used to reconstruct full images from a small subset of pixels, simulating faster, lower-radiation scans.

Key Results and Insights

  • The Power of "Forgetting": By employing an exponentially-weighted criterion, the algorithms can "forget" old data, allowing them to track non-stationary subspaces. This is critical for adapting to shifts in underlying data structures, such as changing network traffic patterns.
  • Batch Performance at Online Speed: The authors provide proof that these online estimates asymptotically converge to the same global optimum as the batch nuclear-norm estimator, offering theoretical reliability without the computational bottleneck.
  • Superior Accuracy and Stability: In network traffic tests, the proposed RLS algorithm consistently outperformed state-of-the-art trackers like GROUSE and PETRELS, particularly in scenarios with extreme sparsity. In MRI reconstruction, the tensor algorithm successfully imputed images with 75% missing pixels, achieving a relative estimation error as low as 0.046.
  • Tensor Efficiency: Utilizing a tensor model proved far more efficient than "unfolding" tensors into matrices, as it preserves multi-way relationships and reduces the number of tracked variables.

Conclusion and Future Work

This suite of algorithms provides a robust solution for real-time imputation in big data environments. While the current convergence proofs rely on independent and identically distributed (i.i.d.) data assumptions, future work aims to incorporate spatiotemporal correlations using kernels to better model real-world time series. Additionally, the authors suggest exploring formal optimality guarantees for rapidly shifting dynamic environments and relaxing technical requirements for global optimality to further enhance robustness.

Summary updated

Abstract

Extracting latent low-dimensional structure from high-dimensional data is of paramount importance in timely inference tasks encountered with `Big Data' analytics. However, increasingly noisy, heterogeneous, and incomplete datasets as well as the need for {\em real-time} processing of streaming data pose major challenges to this end. In this context, the present paper permeates benefits from rank minimization to scalable imputation of missing data, via tracking low-dimensional subspaces and unraveling latent (possibly multi-way) structure from \emph{incomplete streaming} data. For low-rank matrix data, a subspace estimator is proposed based on an exponentially-weighted least-squares criterion regularized with the nuclear norm. After recasting the non-separable nuclear norm into a form amenable to online optimization, real-time algorithms with complementary strengths are developed and their convergence is established under simplifying technical assumptions. In a stationary setting, the asymptotic estimates obtained offer the well-documented performance guarantees of the {\em batch} nuclear-norm regularized estimator. Under the same unifying framework, a novel online (adaptive) algorithm is developed to obtain multi-way decompositions of \emph{low-rank tensors} with missing entries, and perform imputation as a byproduct. Simulated tests with both synthetic as well as real Internet and cardiac magnetic resonance imagery (MRI) data confirm the efficacy of the proposed algorithms, and their superior performance relative to state-of-the-art alternatives.
BibTeX
@article{mardani2014subspace,
  author = {Morteza Mardani and Gonzalo Mateos and Georgios B. Giannakis},
  title = {{Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors}},
  journal = {IEEE Trans. Signal Process.},
  year = {2014},
  doi = {10.1109/tsp.2015.2417491},
}
Figure