Scalable Tensor Factorizations for Incomplete Data

By Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy, Morten Mørup. arXiv.org, 2010

654 citations recorded by the source corpus.

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 × 1000 × 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.

Subfields: Computational Mathematics, Radiology, Nuclear Medicine and Imaging, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e23dd37582dfc31c25a5df644e3d08986c650182

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Radiology, Nuclear Medicine and Imaging

In Signal Processing

Citations in the corpus

Limestone: High-throughput candidate phenotype generation via tensor factorization (2014, methodology): “FMS is [40,78,79] commonly used to compare two tensor factorization results, quantifying the closeness via a single number between ½ 0 ; 1 (cid:11) .”
Rubik: Knowledge Guided Tensor Factorization and Completion for Health Data Analytics (2015, methodology): “[1] proposed to apply tensor factorization in missing data to achieve low rank tensor completion.”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[1] Evrim Acar, Daniel M Dunlavy, Tamara G Kolda, and Morten Mørup.”
Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination (2014, methodology): “We have performed experiments on this dataset by using FBCP, CPWOPT, FaLRTC and HardC. methods, and the initial rank was set to 100.”
Distributed large-scale tensor decomposition (2014, background): “Note that the data explosion problem can also be handled by exploiting sparseness of both data and latent factors as in [11, 12, 13].”
Recommender systems based on user reviews: the state of the art (2015, methodology): “Then, a decomposition method, called CP Weighted OPTimization (CP-WOPT) (Acar et al. 2011), is applied to decompose the high-order tensor into a sum of rankone tensors: A (with size I × R) for users, B (with size J × R) for items, and C (with size (K + 1) × R)) for aspects (note that the first entry”
Tensors for Data Mining and Data Fusion (2016, methodology): “…et al. 2009; Zheng et al. 2010; Acar et al. 2011, 2012; Narita et al. 2012; Yokota et al. 2012; Wang et al. 2014; Ermis¸ et al. 2015] One of the most popular models is the so-called Coupled Matrix-Tensor Factorization (CMTF) [Acar et al. 2011], where one or more matrices are coupled with a tensor.”
Multimodal Data Fusion: An Overview of Methods, Challenges, and Prospects (2015, background): “It turns out that the same applies also in the case of missing values, see [16], [99], [160]–[162] and references therein.”
Low-rank tensor completion by Riemannian optimization (2014, methodology): “In [3], gradient optimization techniques have been proposed for fitting the factors of CP decomposition.”