PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor Completion Algorithms in Big Data Analytics

Qingquan Song, Hancheng Ge, James Caverlee, Xia Hu

arXiv:1711.10105v2stat.MLcs.AIcs.LG

TL;DR

Tensor completion seeks to fill missing entries in partially observed tensors, while existing work lacks a comprehensive account spanning domains and big-data conditions. This survey synthesizes general, auxiliary-information, scalable, and dynamic algorithms, along with applications and experimental frameworks. It concludes by identifying challenges and future research directions, including scalability and rank-estimation constraints.

  • Problem

    Tensor completion fills missing entries in partially observed tensors, but advances across domains and big-data settings lack a comprehensive survey.

  • Method

    The survey organizes tensor completion advances into general methods and approaches addressing variety, volume, and velocity, and reviews applications and experimental frameworks.

  • Results

    The survey presents advances in tensor completion theory and practice across general, auxiliary-information, scalable, and dynamic methods, applications, and experiments.

  • Takeaways & Limitations

    Tensor completion offers methods for real-world problems involving auxiliary information, large-scale data, and dynamic patterns, while the survey highlights future research directions.

  • Takeaways & Limitations

    Estimating tensor rank is often difficult, limiting the applicability of completion algorithms that fix the CP rank.

Abstract

from arXiv · show

Tensor completion is a problem of filling the missing or unobserved entries of partially observed tensors. Due to the multidimensional character of tensors in describing complex datasets, tensor completion algorithms and their applications have received wide attention and achievement in areas like data mining, computer vision, signal processing, and neuroscience. In this survey, we provide a modern overview of recent advances in tensor completion algorithms from the perspective of big data analytics characterized by diverse variety, large volume, and high velocity. We characterize these advances from four perspectives: general tensor completion algorithms, tensor completion with auxiliary information (variety), scalable tensor completion algorithms (volume), and dynamic tensor completion algorithms (velocity). Further, we identify several tensor completion applications on real-world data-driven problems and present some common experimental frameworks popularized in the literature. Our goal is to summarize these popular methods and introduce them to researchers and practitioners for promoting future research and applications. We conclude with a discussion of key challenges and promising research directions in this community for future exploration.

1 INTRODUCTION

Tensor completion fills missing entries in partially observed multidimensional data, but high-order structure makes direct matrix-based solutions computationally difficult. This survey organizes recent advances around big data’s variety, volume, and velocity, while covering applications, experiments, and open challenges.

  • Motivation: Tensor completion imputes missing or unobserved entries in partially observed tensors arising from incomplete multidimensional datasets.The survey distinguishes this task from tensor decomposition, whose goal is to obtain interpretable representations for subsequent tasks.
  • Challenges: High-order characteristics increase the space and computational complexity of tensor completion beyond traditional matrix completion approaches.Matrix-level methods typically slice or unfold tensors, but this can prevent their practical use on high-order data.
  • Motivation: Existing surveys largely address matrix completion or tensor decomposition, leaving advances in tensor completion across domains insufficiently consolidated.The survey responds to this gap from a big data analytics perspective.
  • Survey Organization: The survey organizes methods around big data’s variety, volume, and velocity through auxiliary information, scalable algorithms, and dynamic completion methods.It focuses on the first three of big data’s five commonly described V challenges, excluding veracity and value for model-based organization.
  • Scope: The survey also covers real-world applications, experimental simulations, evaluation metrics, and open challenges with promising future directions.These elements extend the survey beyond algorithm taxonomy to practical data-driven evaluation and research outlook.

2 TENSOR COMPLETION PROBLEM

This section defines tensor completion as low-rank recovery of missing entries under observation constraints, then develops rank-based and observation-based problem variants.

  • Preliminaries: Tensor matricization unfolds a tensor into a matrix using a predefined mode ordering; forward and backward arrangements are valid when used consistently.
  • Tensor Completion Problem: Low-rank tensor completion seeks a minimum-rank completed tensor that satisfies equality constraints on observed entries.
  • Rank Variants: Common rank variants use CP rank or tensor n-rank, with tensor n-rank enabling generalizations of matrix trace-norm methods through matricizations.
  • Rank Variants: CP-rank minimization is impractical because computing CP rank is NP-hard, motivating fixed-rank, upper-bound, norm-based, or dynamic rank-search formulations.
  • Observation Constraints: The basic observation constraint assumes noise-free, uniformly random sampling, while variants incorporate noise or alternative Gaussian measurement operators.

3 GENERAL TENSOR COMPLETION ALGORITHMS

The survey introduces general tensor completion algorithms as foundational methods, organizing them into decomposition-based, trace-norm-based, and other variants before discussing advanced approaches.

  • General tensor completion algorithms are categorized into decomposition-based, trace-norm-based, and other variants as a foundation for later advanced methods.

3.1 Decomposition Based Approaches

Decomposition-based completion methods use CP or Tucker representations and handle missing values through EM-like imputation or missing-skipping optimization.

  • 3.1 Decomposition Based Approaches: CP and Tucker decomposition are the two principal decomposition methods reviewed for completion with missing values.
  • CP-Based Methods: The EM-like approach alternates parameter estimation with missing-value imputation, commonly within alternating projection optimization.
  • CP-Based Methods: The missing-skipping approach masks or omits unobserved entries during optimization and is used in gradient-based and probabilistic methods.
  • CP-Based Methods: CP-WOPT uses first-order gradient optimization and is shown to provide effectiveness and higher scalability across different missing ratios.
  • CP-Based Methods: Missing-skipping CP models are usually more robust than EM-like models at large missing ratios but can be difficult to optimize with projection-based algorithms.
  • Tucker-Based Methods: Tucker-based methods are usually more effective than CP-based methods under the same rank assumptions and ideal hyperparameter selections.
  • Hierarchical Tensor Methods: Hierarchical tensor representations generalize the Tucker model for high-order tensors and are commonly optimized with projected-gradient or Riemannian iterations.

3.2 Trace Norm Based Approaches

Trace-norm approaches relax tensor-rank minimization through unfolding-based or factorized formulations, with SNN enabling rank-free completion but potentially costly large-matrix SVDs. Subsequent variants target improved sample requirements, lower computation, or greater structural flexibility.

  • SNN extends matrix trace-norm relaxation by summing trace norms across tensor unfoldings, enabling completion without predefining tensor rank.The unfolding matrices remain coupled by multilinear correlations, but the convex formulation is tractable in practice.
  • ADMM solves the trace-norm completion formulation by introducing auxiliary matrices constrained to equal tensor unfoldings, then iteratively updating auxiliary variables, multipliers, and the tensor.The described algorithm initializes auxiliary matrices and multipliers to zero and updates them until a stopping criterion is satisfied.
  • Singular value thresholding applies shrinkage to singular values, while tensor updates may use EM-like, exact, or inexact approaches.For SVTδ(A), each singular value is reduced by δ and truncated at zero.
  • New trace-norm structures seek better convex relaxations because SNN is neither the tightest tensor-rank relaxation nor optimal in sample-size requirements.Examples include applying a single regularizer to a more balanced unfolding and developing tensor-nuclear-norm or incoherent trace-norm structures.
  • Factorized trace-norm methods place constraints on CP or Tucker factors, reducing computation and allowing additional structure compared with unfolding-based minimization.These approaches address the cost of SVDs on potentially large matrices and can partly alleviate rank pre-definition issues.

3.3 Other Variants

Other tensor-completion variants address nonnegative data, corrupted observations, fixed-rank optimization, and alternative sampling or relaxation strategies. The survey also organizes representative algorithms for comparison.

  • Nonnegative Tensor Completion: Nonnegative tensor completion imposes nonnegative constraints on latent factor matrices, using methods such as block coordinate descent or ADMM with iterative nonnegative thresholding.These constraints are motivated by applications including image completion and medical data analysis.
  • Algorithm Comparison: Table 2 compares general tensor-completion algorithms using categories including CPD, Tucker decomposition, SNN, and MAP.The caption defines CPD as CP decomposition, TD as Tucker Decomposition, SNN as Sum of nuclear norms, and MAP as Maximum a posteriori estimation.
  • Robust Tensor Completion: Robust tensor completion separates a tensor into a low-rank component and a sparse component to model outliers, gross corruptions, and differing noise patterns.Trace-norm and l1-norm terms can jointly relax low-rank and sparse recovery objectives.
  • Riemannian Optimization: Riemannian optimization treats completion as a fixed-rank problem by embedding the rank constraint in a smooth tensor manifold.Its iterative procedure alternates projected gradient steps with retraction back to the low-rank manifold.
  • Other Methods: The survey also identifies alternative Tucker-rank relaxations, adaptive sampling methods, and matrix-based approaches as additional completion strategies.These methods are listed as representative approaches beyond the variants discussed in detail.

3.4 Statistical Assumption and Theoretical Analysis

The survey analyzes when tensor completion can uniquely and exactly recover missing entries under sampling and incoherence assumptions. It compares theoretical observation bounds across convex, non-convex, CP-based, and adaptive approaches.

  • Sampling and incoherence assumptions: Tensor completion theory asks when a unique and exact reconstruction is feasible, using statistical assumptions about observations and tensor incoherence.Uniform random sampling, alternative measurement operators, and incoherence conditions determine recovery guarantees.
  • Sampling and incoherence assumptions: Gaussian measurements use tensors with independent standard normal entries, while Fourier measurements provide structured sampling and fast multiplication routines.Fourier measurement is contrasted with subgaussian measurement as a structured alternative for recovery analysis.
  • Sampling and incoherence assumptions: Uniform sampling can fail for coherent tensors because informative mass may concentrate in a small number of entries.Adaptive sampling is introduced for sparse, clustered populations where non-adaptive methods may require substantially more observations.
  • Observation bounds: For Tucker rank (r,...,r), SNN-based recovery may require more observations than non-convex formulations, whose sufficient bound is (2r)^N + 2rIN + 1 measurements almost surely.The SNN bound is described as necessary but far from the tensor's degrees-of-freedom scale.
  • Observation bounds: CrI^(N−1) observations suffice with high probability for an Nth-order Tucker-rank tensor under the stated incoherence conditions.The bound is presented for tensors of size I in each mode and constant C.
  • Observation bounds: A balanced single trace-norm regularizer is proposed as a tighter convexification than summing trace norms across all mode unfoldings.The motivation is to improve sampling efficiency relative to the SNN model.
  • Observation bounds: For CP rank-r tensors under square-deal sampling, Cr^[N/2] entries are sufficient for recovery.The square-deal setting uses dense random projections rather than individual observed entries.

4 TENSOR COMPLETION WITH AUXILIARY INFORMATION

Auxiliary information is incorporated into tensor completion through similarity-based regularization, coupled factorization, and hybrid or other constraint-based models. These approaches use side information to improve completion, particularly when observations are sparse.

  • 4.1 Similarity Based Approaches: Similarity-based methods impose within-mode or cross-mode regularization using auxiliary similarity matrices.AirCP incorporates spatio-temporal information through similarity matrices when imputing missing online memes.
  • 4.1 Similarity Based Approaches: Combining auxiliary-information regularization with decomposition methods was shown to improve completion accuracy, especially with sparse observations.
  • 4.2 Coupled Matrices/Tensors Factorization: Coupled matrix and tensor factorization jointly imputes a target tensor and factorizes an auxiliary matrix while sharing latent factors in the coupled mode.Both the target tensor and auxiliary matrix are assumed to have low-rank structure.
  • 4.2 Coupled Matrices/Tensors Factorization: CMTF maintained low recovery accuracy until the error rate exceeded 90%, whereas CP recovery error sharply increased beyond an 80% missing ratio.
  • 4.3 Other Approaches: Hybrid models combine similarity matrices with coupled cross-mode features, while other methods use smooth constraints or coupled trace norms.

5 SCALABLE TENSOR COMPLETION

Scalable tensor completion addresses high computational and memory costs in large, sparse tensors. Key strategies avoid intermediate data explosion, distribute computation, exploit sparsity, and reduce oversized tensor-matrix operations.

  • 5.1 Challenges: Large-scale tensor completion is challenging because datasets may contain billions of elements per mode and incur high computational and space costs.
  • 5.1.1 Intermediate Data Explosion Problem: Intermediate data explosion occurs when operations such as Khatri-Rao products create matrices too large for available memory.For I = 1 million, J = 1 million, and R = 10, A ⊙B has size 1 trillion × 10.
  • 5.1.2 Decentralization of the Tensor Data Problem: Distributed ALS, PSGD, CDTF, and SALS parallelize tensor updates, but communication and memory costs can remain scalability bottlenecks.PSGD exchanges all latent parameters after each iteration, while row-distributed ALS requires each machine to load fixed matrices.
  • 5.1.1 Intermediate Data Explosion Problem: Adaptive, piecemeal tensor-matrix multiplication reduces memory demands by selecting operation orders and processing one slice or fiber at a time.
  • 5.1.1 Intermediate Data Explosion Problem: GigaTensor avoids intermediate data explosion by reordering computation, exploiting tensor sparsity, and sequentially applying operations instead of materializing the Khatri-Rao product.

6 DYNAMIC TENSOR COMPLETION

Dynamic tensor completion extends completion to streaming and multi-aspect settings where data evolves over time or across multiple modes. Online methods update factors incrementally, while newer methods address all-mode changes and auxiliary information.

  • 6.1 Streaming Tensor Completion: Streaming tensor completion processes incomplete temporal slices as they arrive rather than collecting the entire tensor in advance.
  • 6.1 Streaming Tensor Completion: A forgetting factor decays the influence of past data to support subspace tracking in non-stationary environments.
  • 6.1 Streaming Tensor Completion: Online CP completion updates the new temporal factor from each arriving slice, then adjusts non-incremental factors with stochastic gradient descent.These methods assume a rarely and smoothly changing streaming tensor subspace.
  • 6.2 Multi-Aspect Streaming Tensor Completion: Multi-aspect streaming allows a tensor to grow along any mode, creating challenges in coordinating multidimensional dynamics and imputing new missing entries.
  • 6.2 Multi-Aspect Streaming Tensor Completion: MAST handles all-mode-change dynamics through partition, substitution, and re-decomposition while imputing missing entries.Substituting the old tensor with its decomposition can improve optimization speed when the old tensor is a large fraction of the new tensor.
  • 6.2 Multi-Aspect Streaming Tensor Completion: SIITA uses a Tucker-based online inductive framework to support multi-aspect streaming completion while incorporating auxiliary information.The method is reported to achieve superior performance in both batch and streaming settings.

7 APPLICATIONS

Tensor completion applications span social computing and urban analytics, where multidimensional temporal, relational, and contextual data motivate tensor formulations. Recommender systems particularly exploit tensor methods for ternary interactions and auxiliary information.

  • Tensor completion applications include link prediction, recommendation, information diffusion, and network traffic analysis in social and urban computing.
  • Social Computing: Dynamic interactions and multiple node-interaction types add dimensions that make tensor completion natural for link prediction.
  • Social Computing: Tensor-based recommendation methods model ternary user-item-tag relations that matrix algorithms cannot easily represent.
  • Social Computing: Temporal and contextual dimensions can improve recommendation beyond static matrix-based systems.
  • Social Computing: Auxiliary models such as TAPER use homogeneous and heterogeneous similarities for personalized expert recommendation, achieving high-quality precision and recall.
  • Urban Computing: CP Weighted OPTimization addresses network-traffic tensor completion with both recovery accuracy and scalability.

7.2 Healthcare, Bioinformatics and Medical Applications

Tensor completion is applied across healthcare, bioinformatics, medical imaging, and computer vision because these datasets are multidimensional and often incomplete. Applications include image reconstruction, video processing, hyperspectral analysis, and biological data completion.

  • Healthcare and Medical Applications: Incomplete MRI and CT data motivate tensor completion for medical image reconstruction and diagnosis-related analytics.
  • Healthcare and Medical Applications: Healthcare and bioinformatics applications include medical questionnaires, RNA sequencing, and computational phenotyping.
  • Computer Vision: Computer-vision completion problems include image inpainting, video decoding, compressed sensing, and spectral data analysis.
  • Computer Vision: Images naturally form tensors, making tensor-based algorithms suitable for coordinating color and other dimensions in image inpainting.
  • Computer Vision: Hyperspectral datasets represent contiguous spectral bands and can treat scene as an additional tensor mode.
  • Computer Vision: OLSTEC reconstructs incomplete video streams and shows rapid adaptivity to changed backgrounds.

7.5 Compressed Sensing

Compressed sensing recovers high-dimensional sparse signals from limited measurements, while tensor extensions address high-order multilinear data. Kronecker structure and low-rank assumptions support practical tensor recovery methods.

  • Compressed sensing recovers sparse signals from few nonadaptive linear random measurements using efficient convex and thresholding algorithms.
  • Tensor completion applications in this area include video and other multilinear datasets.
  • Kronecker-based compressed sensing extends compressed sensing to high-order tensors for practical implementation.
  • Generalized tensor compressed sensing methods exploit Kronecker structure with approaches such as ℓ1-minimization.

8 EXPERIMENTAL SETUP

The survey describes experimental practices for constructing synthetic tensors and evaluating completion methods. Frameworks cover CP, Tucker, and auxiliary-information settings, with metrics selected according to application type.

  • Synthetic benchmarks vary assumptions about rank, noise, sampling, and auxiliary information because ideal real-world tensors with known properties are difficult to obtain.
  • Common constructions include rank-R CP tensors, Tucker tensors with rank (R1,R2,R3), and CP tensors with auxiliary similarity information.
  • Synthetic Data Construction: CP synthetic tensors sample and normalize factor-matrix columns, with Gaussian noise controlled by a noise parameter such as SNR or SIR.
  • Synthetic Data Construction: Tucker tensors are generated by sampling a core tensor and factor matrices from N(0, 1), usually followed by factor-matrix orthogonalization.
  • Synthetic Data Construction: Auxiliary-information benchmarks can use linearly constructed factor matrices whose neighboring rows are similar, producing tri-diagonal similarity matrices.
  • Evaluation Metrics: Evaluation metrics depend on application, including RMSE for recommendation, AUC for binary classification, and nDCG for information retrieval.
  • Evaluation Metrics: Relative error, percentage of fitness, tensor completion score, and mean absolute or squared errors are commonly used completion metrics.
  • Evaluation Metrics: Classification-oriented applications may evaluate precision, recall, F-measure, and AUC globally or by averaging scores across slices.

9 CONCLUSION AND FUTURE OUTLOOK

The survey identifies persistent challenges in tensor completion as data volume, heterogeneity, dynamics, veracity, and value increase. It highlights scalability constraints and several directions for future research.

  • Volume: Large-scale and high-order tensors increase demands on tensor completion algorithms in both time and space.The survey identifies intermediate data explosion and data decentralization as two underlying scalability challenges.
  • Volume: Despite proposed scalability approaches, space and time complexities continue to limit practical applications.
  • Other Aspects: Future work may integrate heterogeneous data across large-scale and dynamic settings.
  • Other Aspects: Tensor completion research can also examine big data from veracity and value perspectives beyond variety, velocity, and volume.
Loading 1711.10105v2…