Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
- 30 March 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 63 (10) , 2663-2677
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 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 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 nonseparable 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 batch nuclear-norm regularized estimator. Under the same unifying framework, a novel online (adaptive) algorithm is developed to obtain multi-way decompositions of 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.Keywords
All Related Versions
Funding Information
- MURI (AFOSR FA9550-10-1-0567)
This publication has 33 references indexed in Scilit:
- Modeling and Optimization for Big Data Analytics: (Statistical) learning tools for our era of data delugeIEEE Signal Processing Magazine, 2014
- Online dictionary learning from big data using accelerated stochastic approximation algorithms2014
- Dynamic Anomalography: Tracking Network Anomalies Via Sparsity and Low RankIEEE Journal of Selected Topics in Signal Processing, 2012
- Tensor Versus Matrix Completion: A Comparison With Application to Spectral DataIEEE Signal Processing Letters, 2011
- Matrix Completion With NoiseProceedings of the IEEE, 2010
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Adaptive Algorithms to Track the PARAFAC Decomposition of a Third-Order TensorIEEE Transactions on Signal Processing, 2009
- Rank, Trace-Norm and Max-Norm2005
- Local Minima and Convergence in Low-Rank Semidefinite ProgrammingMathematical Programming, 2004