Scalable Tensor Factorizations for Incomplete Data

Abstract

The problem of incomplete data - i.e., data with missing or unknown values - in multi-way arrays is ubiquitous in biomedical signal processing, network traffic analysis, bibliometrics, social network analysis, chemometrics, computer vision, communication networks, etc. We consider the problem of how to factorize data sets with missing values with the goal of capturing the underlying latent structure of the data and possibly reconstructing missing values (i.e., tensor completion). We focus on one of the most well-known tensor factorizations that captures multi-linear structure, CANDECOMP/PARAFAC (CP). In the presence of missing data, CP can be formulated as a weighted least squares problem that models only the known entries. We develop an algorithm called CP-WOPT (CP Weighted OPTimization) that uses a first-order optimization approach to solve the weighted least squares problem. Based on extensive numerical experiments, our algorithm is shown to successfully factorize tensors with noise and up to 99% missing data. A unique aspect of our approach is that it scales to sparse large-scale data, e.g., 1000 x 1000 x 1000 with five million known entries (0.5% dense). We further demonstrate the usefulness of CP-WOPT on two real-world applications: a novel EEG (electroencephalogram) application where missing data is frequently encountered due to disconnections of electrodes and the problem of modeling computer network traffic where data may be absent due to the expense of the data collection process.

References in corpus (1)

• The Power of Convex Relaxation: Near-Optimal Matrix Completion

Cited by in corpus (94)

• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination
• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Smooth PARAFAC Decomposition for Tensor Completion
• On Tensors, Sparsity, and Nonnegative Factorizations
• Bayesian Robust Tensor Factorization for Incomplete Multiway Data
• All-at-once Optimization for Coupled Matrix and Tensor Factorizations
• Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• Linked Component Analysis from Matrices to High Order Tensors: Applications to Biomedical Data
• Framelet Representation of Tensor Nuclear Norm for Third-Order Tensor Completion
• Aesthetic-based Clothing Recommendation
• Estimation of low-rank tensors via convex optimization
• Generalized Canonical Polyadic Tensor Decomposition
• Provable Tensor Factorization with Missing Data
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Rank regularization and Bayesian inference for tensor completion and extrapolation
• Bayesian Low Rank Tensor Ring Model for Image Completion
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Tensor Decompositions: A New Concept in Brain Data Analysis?
• Tensor Completion from Regular Sub-Nyquist Samples
• Numerical Optimization for Symmetric Tensor Decomposition
• Spatiotemporal Tensor Completion for Improved Urban Traffic Imputation
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Stable, Robust and Super Fast Reconstruction of Tensors Using Multi-Way Projections
• Bayesian Sparse Tucker Models for Dimension Reduction and Tensor Completion
• Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries
• Brain-Computer Interface with Corrupted EEG Data: A Tensor Completion Approach
• Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD
• A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem
• An Iterative Reweighted Method for Tucker Decomposition of Incomplete Multiway Tensors
• A condition number for the tensor rank decomposition
• A New Sampling Technique for Tensors
• Infinite Tucker Decomposition: Nonparametric Bayesian Models for Multiway Data Analysis
• Link Prediction via Generalized Coupled Tensor Factorisation
• Tensor Completion Algorithms in Big Data Analytics
• A multi-class approach for ranking graph nodes: models and experiments with incomplete data
• Higher-dimension Tensor Completion via Low-rank Tensor Ring Decomposition
• Exact Tensor Completion from Sparsely Corrupted Observations via Convex Optimization
• Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion
• High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format
• Discovering Hidden Structure in High Dimensional Human Behavioral Data via Tensor Factorization
• Robust Factorization of Real-world Tensor Streams with Patterns, Missing Values, and Outliers
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• The geometry of rank-one tensor completion
• A generalizable framework for low-rank tensor completion with numerical priors
• Alternating Least Squares Tensor Completion in The TT-Format
• A Unified Tensor-based Active Appearance Face Model
• Tracking Tensor Subspaces with Informative Random Sampling for Real-Time MR Imaging
• Uncovering migration systems through spatio-temporal tensor co-clustering
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Alternating minimization algorithms for graph regularized tensor completion
• Shared Memory Parallelization of MTTKRP for Dense Tensors
• MTC: Multiresolution Tensor Completion from Partial and Coarse Observations
• Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
• A Parallelizable Method for Missing Internet Traffic Tensor Data
• Bayesian Methods in Tensor Analysis
• Distributed Flexible Nonlinear Tensor Factorization
• Hierarchical Tensor Ring Completion
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
• Implicit Regularization in Tensor Factorization
• Frequency-Weighted Robust Tensor Principal Component Analysis
• Streaming Probabilistic Deep Tensor Factorization
• FasTer: Fast Tensor Completion with Nonconvex Regularization
• Robust Fusion of LiDAR and Wide-Angle Camera Data for Autonomous Mobile Robots
• Triple Decomposition and Tensor Recovery of Third Order Tensors
• Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion
• Bayesian Allocation Model: Inference by Sequential Monte Carlo for Nonnegative Tensor Factorizations and Topic Models using Polya Urns
• Variational Inference For Probabilistic Latent Tensor Factorization with KL Divergence
• Tuning Free Rank-Sparse Bayesian Matrix and Tensor Completion with Global-Local Priors
• Overcoming Missing and Incomplete Modalities with Generative Adversarial Networks for Building Footprint Segmentation
• PASTA: A Parallel Sparse Tensor Algorithm Benchmark Suite
• Tensor Completion via Tensor Networks with a Tucker Wrapper
• Individualized Context-Aware Tensor Factorization for Online Games Predictions
• A Tensor Rank Theory and Maximum Full Rank Subtensors
• Variational Bayesian inference for CP tensor completion with side information
• Multimodal Data Fusion based on the Global Workspace Theory
• Conditional Expectation Propagation
• Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery
• Nonparametric Sparse Tensor Factorization with Hierarchical Gamma Processes
• Sparse Logistic Tensor Decomposition for Binary Data
• High-order Tensor Completion for Data Recovery via Sparse Tensor-train Optimization
• Low Rank Symmetric Tensor Approximations
• Spatio-Temporal Graphical Counterfactuals: An Overview
• Location Order Recovery in Trails with Low Temporal Resolution
• Spatio-Temporal Tensor Sketching via Adaptive Sampling
• MLCTR: A Fast Scalable Coupled Tensor Completion Based on Multi-Layer Non-Linear Matrix Factorization
• An Efficient Tensor Completion Method via New Latent Nuclear Norm
• Multi-tensor Completion for Estimating Missing Values in Video Data
• High Order Singular Value Decomposition for Plant Biodiversity Estimation
• New penalized criteria for smooth non-negative tensor factorization with missing entries
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• Visually-aware Recommendation with Aesthetic Features
• Multi-version Tensor Completion for Time-delayed Spatio-temporal Data