Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors

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.

References in corpus (7)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Scalable Tensor Factorizations for Incomplete Data
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Rank regularization and Bayesian inference for tensor completion and extrapolation
• In-network Sparsity-regularized Rank Minimization: Algorithms and Applications
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion

Cited by in corpus (28)

• Image Reconstruction: From Sparsity to Data-adaptive Methods and Machine Learning
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Multi-Output Gaussian Processes for Crowdsourced Traffic Data Imputation
• Low-rank tensor completion: a Riemannian manifold preconditioning approach
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Network Volume Anomaly Detection and Identification in Large-scale Networks based on Online Time-structured Traffic Tensor Tracking
• Online Low-Rank Tensor Subspace Tracking from Incomplete Data by CP Decomposition using Recursive Least Squares
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD
• An Iterative Reweighted Method for Tucker Decomposition of Incomplete Multiway Tensors
• Stochastic Subsampling for Factorizing Huge Matrices
• An AO-ADMM approach to constraining PARAFAC2 on all modes
• Tensor Completion Algorithms in Big Data Analytics
• Online Categorical Subspace Learning for Sketching Big Data with Misses
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Matrix completion and extrapolation via kernel regression
• Robust Factorization of Real-world Tensor Streams with Patterns, Missing Values, and Outliers
• Variational Bayesian Inference for Robust Streaming Tensor Factorization and Completion
• Robust Factorization and Completion of Streaming Tensor Data via Variational Bayesian Inference
• Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations
• Bayesian Methods in Tensor Analysis
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Active Sampling for Accelerated MRI with Low-Rank Tensors
• Minimax Optimal Online Stochastic Learning for Sequences of Convex Functions under Sub-Gradient Observation Failures
• Multi-version Tensor Completion for Time-delayed Spatio-temporal Data
• Subspace-Aware Index Codes
• Estimating Traffic and Anomaly Maps via Network Tomography