PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Tensor Factorizations for Incomplete Data

Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy, Morten Morup

arXiv:1005.2197v1math.NAphysics.data-an

TL;DR

Incomplete multi-way data challenge latent-structure modeling and missing-entry recovery. This paper fits CP models directly to known entries with weighted least squares, using first-order optimization in CP-WOPT. The method recovers factors under severe missingness and scales to large sparse tensors, while its CP restriction may limit missing-entry accuracy.

  • Problem

    Incomplete tensor data must be factorized to capture latent structure and potentially reconstruct missing entries across diverse applications.

  • Method

    CP-WOPT directly solves a weighted least squares CP formulation over known entries using first-order optimization and sparse data structures.

  • Results

    CP-WOPT recovers CP factors with 90% missing entries in 50 × 40 × 30 tensors and with 99.5% missing data in 1000 × 1000 × 1000 sparse tensors.

  • Takeaways & Limitations

    CP-WOPT captures EEG brain dynamics with missing channels and can recover missing network traffic data.

  • Takeaways & Limitations

    The restricted CP model may not recover missing entries as accurately as a more flexible Tucker model.

Abstract

from arXiv · show

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.

1. Introduction

The paper frames incomplete tensor data as a widespread obstacle to latent-structure analysis and missing-value reconstruction. It introduces CP-WOPT, which directly fits a CP model to known entries through weighted optimization and scales to severe missingness.

  • Motivation: Incomplete data arise from information loss, collection errors, costly experiments, electrode failures, packet losses, and image occlusions.The paper motivates tensor methods with examples from EEG, network traffic, and computer vision.
  • Motivation: Tensors capture multiple modes of variation that matrices cannot represent without flattening, including temporal, spectral, and spatial structure in EEG.The paper also identifies social-network, traffic, and bibliometric data as large, multimodal applications.
  • CP model: CANDECOMP/PARAFAC (CP) represents a three-way tensor using factor matrices A, B, and C with R components.The model is presented as a commonly used tensor decomposition and extends to N-way tensors.
  • CP-WOPT: CP-WOPT models only known entries by solving a weighted least squares problem with a binary weight tensor W.W equals 1 for known entries and 0 for missing entries, avoiding direct modeling of missing values.
  • CP-WOPT: CP-WOPT uses first-order optimization over all factor matrices simultaneously and specialized sparse structures to reduce storage and computation costs.The authors report successful factorization with noise and up to 99% missing data, including large sparse tensors.
  • Applications: The recovered factors can reconstruct missing entries, keeping their relative error close to the modeling error even with substantial missing data.The paper demonstrates this reconstruction objective alongside factor recovery.

2. Notation

This section establishes notation for tensors, matrices, vectors, entries, matricization, elementwise products, norms, and CP constructions. These definitions support the later weighted tensor-factorization formulation.

  • Notation: N-way tensors use script letters, matrices bold capitals, vectors bold lowercase letters, and scalar or entry values lowercase letters with subscripts.Tensor entries are indexed by one subscript for each mode.
  • Tensor operations: Mode-n matricization rearranges a tensor so its mode-n fibers become the columns of a matrix.Matricization is also called unfolding or flattening.
  • Tensor operations: The Hadamard product multiplies corresponding entries of two same-sized tensors elementwise.The notation X ∗ Y denotes this operation.
  • Norms: Tensor inner products sum products of corresponding entries, while the associated matrix and vector norms are the Frobenius and two-norms.A W-weighted tensor norm is also introduced for later incomplete-data objectives.
  • CP notation: The bracket notation J A(1), A(2), . . . , A(N) K constructs an N-way tensor from factor matrices whose sizes are I_n × R.For two matrices, the construction reduces to A B^T.

3. Related Work in Factorizations with Missing Data

Prior work extends missing-data factorization from matrices to tensors through imputation, alternating updates, and direct optimization. The paper positions CP-WOPT as a first-order alternative designed to scale beyond second-order approaches.

  • Matrix factorizations: Matrix missing-data factorization is commonly solved with EM, which imputes missing values using the current model and alternates factor updates.The related matrix-completion literature also studies recovery of missing entries from low-rank structure.
  • Matrix factorizations: Direct nonlinear matrix optimization uses a second-order damped Newton method, and prior comparisons identify nonlinear optimization as important for successful factorization.This approach differs from methods based on alternation, imputation, or hybrid combinations.
  • Uniqueness: Matrix decompositions have infinitely many equivalent solutions under invertible transformations, whereas CP can often recover a unique solution up to scaling and column permutation.The distinction concerns matrix rotational freedom versus CP’s more limited indeterminacies.
  • Tensor factorizations: Tensor missing-data methods also use EM-ALS, which fills missing tensor entries with the current CP model before alternating least-squares updates.This procedure extends the matrix EM strategy to tensor factorizations.
  • Direct tensor optimization: INDAFAC and CP-WOPT both solve the CP fitting problem for incomplete data, but INDAFAC uses second-order optimization while CP-WOPT uses first-order optimization for larger problem sizes.The comparison directly identifies scalability as CP-WOPT’s design goal.

4. CP-WOPT Algorithm

CP-WOPT formulates incomplete-data CP factorization as a weighted least-squares problem over known entries and solves it with gradient-based optimization. Sparse computations store and process only known values, reducing storage and computation requirements.

  • Weighted objective: The objective uses Y = W ∗ X and Z = W ∗JA(1), . . . , A(N)K to express the weighted residual computation.Y can be precomputed, while Z can be computed efficiently when W is sparse.
  • Weighted objective: CP-WOPT minimizes a weighted CP objective that models known tensor entries while ignoring missing ones.The factor matrices are optimized jointly, and any gradient-based optimization method can be used once function and gradient values are available.
  • Scope: In practice, the rank is generally unknown and not easily determined, and evaluating methods in that setting is identified as future work.The experiments assume the rank is known; prior results suggest direct optimization may have an advantage when rank is overestimated.
  • Sparse computation: For sparse missing-data tensors, CP-WOPT stores only known values and computes only corresponding model entries.The known values are indexed by I and stored in vectors such as y and z, avoiding storage for every tensor entry.
  • Sparse computation: Sparse function evaluation exploits expanded vectors and iterative accumulation to reduce storage costs while computing the same values as the dense formulation.The sparse vector z contains the nonzero entries of Z, and the scalar γ equals the squared norm of the known-value vector y.
  • Gradient computation: The sparse gradient calculation performs an mttkrp operation using known entries and products of mode-specific expanded vectors.Each gradient column is assembled from the observed data and factor-vector products excluding the differentiated mode.

5. Experiments

The experiments evaluate CP-WOPT on simulated and real three-way data, comparing it with EM-ALS and INDAFAC. Performance is assessed through factor recovery and missing-entry reconstruction under iterative optimization settings.

  • Evaluation scope: CP-WOPT is evaluated on both real and simulated three-way data and in two application settings.The study compares methods and demonstrates CP-WOPT performance on applications.
  • Compared methods: The comparison includes EM-ALS and INDAFAC, with INDAFAC described as a damped Gauss-Newton method.Earlier work reported that INDAFAC converged in fewer iterations than EM-ALS.
  • Experimental protocol: All algorithms use iterative stopping criteria based on relative function-value change, with a threshold of 10^-8.Additional method-specific gradient and iteration limits are also imposed for INDAFAC, CP-WOPT, and EM-ALS.
  • Experimental protocol: Multiple starting points are used for randomly generated problems, including initialization from n-mode singular vectors after replacing missing entries with zero.The authors report that this initialization performed better than random initialization in preliminary experiments with substantial missing data.
  • Evaluation metrics: Factor recovery is measured with factor match score, whose best possible value is 1.The score accounts for permutation ambiguity and ignores extra computed components when present.
  • Evaluation metrics: Missing-entry reconstruction is measured with tensor completion score, defined as the relative error in the missing entries.The best possible tensor completion score is 0.

5.3. Simulated data

The simulations evaluate CP-WOPT, INDAFAC, and EM-ALS on noisy tensors with random and structured missing data. Accuracy is generally comparable, while computational time and problem difficulty vary with sparsity, tensor size, and missingness.

  • Experimental setup: 60%, 70%, 80%, 90%, and 95% missing data were tested on tensors sized 50 × 40 × 30, 100 × 80 × 60, and 150 × 120 × 90.Each CP model used R = 5 components; thirty independent test problems were generated for each size and missing-data percentage.
  • Accuracy: CP-WOPT, INDAFAC, and EM-ALS were indistinguishable in accuracy across the simulated problems.Figure 4 summarizes FMS scores over 30 problems using cumulative results from multiple starts.
  • Accuracy: For all methods, additional starting points improve performance, with two or three starts generally sufficient for high FMS accuracy.For up to 90% missing data, median FMS values remain close to one and outliers decrease with multiple starts.
  • Problem difficulty: 95% missing data is more difficult for 50 × 40 × 30 tensors than for larger tensors, partly because smaller problems have lower ρ.For 95% missing data, ρ is approximately 5 for 50 × 40 × 30 and approximately 20 for 100 × 80 × 60; ρ is only a partial difficulty indicator.
  • Computational time: For 90% and 95% missing data, sparse CP-WOPT is fastest in most cases, exceeding a factor-of-10 speed advantage in some cases.For missingness up to 80%, dense CP-WOPT is faster than INDAFAC, while EM-ALS is fastest overall.
  • Computational time: CP-WOPT scales through sparse computations because it ignores missing values, whereas EM-ALS imputes them and operates on dense data.INDAFAC also ignores missing values, but its scalability is limited by the expense of solving its optimization problem.

5.4. Large-scale simulated data

CP-WOPT-Sparse is evaluated on large tensors with at least 99% missing data using sparse storage and computations over known entries. The experiments show high factor-match scores while substantially reducing storage requirements.

  • 1.25 million known values in a 500 × 500 × 500 tensor and 5 million in a 1000 × 1000 × 1000 tensor define the large-scale test cases.Both cases contain at least 99% missing data.
  • Sparse generation and storage avoid explicitly forming the full data, noise, and indicator tensors, operating instead on randomly selected known indices.The known-index set and indicator tensor are stored sparsely, and model values are calculated only at those indices.
  • 40MB stores the 1.25M known entries versus 1GB for the dense 500 × 500 × 500 tensor.The sparse estimate assumes 32 bytes per stored entry and the dense estimate assumes 8 bytes per entry.
  • All ten 500 × 500 × 500 problems achieved FMS greater than 0.99, with solve times ranging between 200 and 1000 seconds.
  • 160MB stores 5M entries in the 1000 × 1000 × 1000 case versus 8GB for dense storage; nine of ten problems achieved FMS greater than 0.99.Solve times ranged from 2000 to 10000 seconds, approximately 10 times slower than the smaller case.
  • Figure 6 reports means across ten runs for CP-WOPT-Sparse on the large-scale problems with at least 99% missing data.

5.5. EEG data

CP-WOPT is applied to incomplete multi-channel EEG tensors to recover latent brain dynamics despite randomly missing electrode channels. Factor similarities remain high even when a substantial fraction of channel data is removed.

  • The EEG tensor contains 64 channels and 28 measurements from 14 subjects, arranged across channels, time-frequency, and measurements modes.
  • A rank-3 CP model extracts factor matrices for channels, time-frequency, and measurements, visualized as head, matrix, and bar plots.The rows correspond to components r = 1, 2, 3, and colors encode low-to-high coefficients from blue to red.
  • Randomly missing channels model electrode malfunction, with missingness varying across measurements rather than removing the same channels everywhere.
  • With up to 30 missing channels per measurement, about 47% of the data, average FMS scores remain around 0.90.The extracted factor matrices still match the original factor matrices well, and the underlying brain dynamics remain visible.
  • The solution does not seriously degrade until 40 of 64 channels are removed.

5.6. Network traffic data

CP-WOPT is used for tensor completion of computer network traffic data by fitting a two-component CP model and reconstructing randomly withheld entries. Recovery remains close to the model’s baseline error under high missingness, while the CP restriction limits potential accuracy.

  • The GÉANT network traffic tensor has size 23 × 23 × 2756 and is modeled after preprocessing with X = log(T + 1).The selected period contains no missing time slices in the analyzed subset.
  • A 2-component CP model fits the traffic data with modeling error approximately 0.31, although unexplained residual variation remains.Adding components slightly lowers the error but produces models judged inappropriate for the data.
  • Randomly missing entries are reconstructed from the fitted factor matrices and evaluated using the tensor completion score across 30 instances.
  • The average TCS stays close to the approximately 0.31 modeling-error level even when the amount of missing data is high.With little missing data, the average TCS is around 0.31; Figure 9 reports the trend across missingness levels.
  • The CP model provides interpretable mode-specific factors, but its restricted form may be less accurate for completion than a more flexible Tucker model.The paper identifies this comparison as future research rather than an evaluated result.

6. Conclusions

The paper formulates incomplete-tensor CP factorization as weighted least squares and develops CP-WOPT, a scalable first-order method that models only known entries. Numerical studies and applications indicate accurate, scalable recovery under substantial missingness, including sparse large tensors, EEG data, and network traffic.

  • Contributions: CP-WOPT solves a weighted least squares objective over all factor matrices simultaneously using first-order optimization.The formulation ignores missing entries and models only known data entries.
  • Numerical findings: CP-WOPT recovers CP factors with 90% missing entries for 50 × 40 × 30 tensors and with 99.5% missing data for 1000 × 1000 × 1000 sparse tensors.The large tensor experiments used sparse tensors and demonstrated recovery from five million known entries in the paper context.
  • Numerical findings: CP-WOPT was faster than the best alternative in the reported studies and faster than EM-ALS at high percentages of missing data.The comparison included dense and sparse CP-WOPT implementations, INDAFAC, and EM-ALS.
  • Applications: In EEG analysis, CP-WOPT factors captured brain dynamics despite missing channels, while in network traffic analysis it recovered missing traffic data.The EEG data were centered using means of known entries; robust centering for incomplete data remains future work.
  • Practical scope: Omitting data can reduce storage and computation for large tensors and support rank determination or model assessment through cross-validation.The paper gives a 1000 × 1000 × 1000 tensor as an example that would normally require 8GB of storage.
  • Future work: Future work includes non-negativity constraints, sparsity penalties, and collective factorizations with shared factors.These extensions are intended to support more meaningful latent factors and joint factorization of multiple tensors.

Appendix A. Additional comparisons for randomly missing data

Additional comparisons on larger problems with randomly missing entries found comparable accuracy among CP-WOPT, INDAFAC, and EM-ALS, with further improvements from multiple starts.

  • Accuracy comparisons: CP-WOPT, INDAFAC, and EM-ALS were indistinguishable in FMS accuracy for 100 × 80 × 60 and 150 × 120 × 90 problems.The figures report cumulative results from multiple starts, including n-mode singular-vector and random initializations.
  • Initialization: Multiple starts produced comparable improvements for the larger randomly incomplete tensor problems.The first start used n-mode singular vectors, while the remaining starts were random.

Appendix B. Comparisons for structured missing data

The structured-missing-data experiments used controlled missing fibers and compared CP-WOPT, INDAFAC, and EM-ALS across tensor sizes and missingness levels. Accuracy declined with more structured missingness, and sparse CP-WOPT became faster beyond 80% missing data.

  • Experimental setup: The experiments used problems with up to 90% missing data and three starting points: n-mode singular vectors plus two random starts.This setup differed from the analogous experiments that used up to 95% missing data and more starts.
  • Missingness pattern: Structured missing fibers were created by zeroing randomly selected entries of an I × J binary mask and stacking it across the third mode.The mask was constrained to have no zero rows or columns, ensuring every slice retained at least one nonzero entry.
  • Accuracy results: Average FMS scores decreased as structured missingness increased and were generally lower than scores for comparable randomly missing data.The comparison indicates that the structure of the missing data affects factor-recovery accuracy.
  • Computational results: EM-ALS was fastest with 80% or less structured missing data, whereas sparse CP-WOPT was generally faster above 80% missing data.These timings were comparable to those observed for randomly missing data.
Loading 1005.2197v1…