Tensor Completion Algorithms in Big Data Analytics

1 INTRODUCTION

• Tensor completion fills missing or unobserved tensor entries, a task arising from incomplete data and multidimensional applications such as image completion and video compression.Missingness can result from mal-operations, limited permissions, or data missing at random.Source: §1 · p. 1
• Matrix completion methods may lose tensor mode redundancy and multiway structure, while high-order tensors also raise space and computational complexity.Tensor-based approaches may use carefully designed matricization to preserve multiway properties.Source: §1 · pp. 1–2
• Tensor completion is distinct from tensor decomposition: its goal is imputing entries, and decomposition methods may perform poorly without careful treatment of missing data.The introduction gives vanilla alternating least squares for CANDECOMP/PARAFAC decomposition as an example.Source: §1 · p. 2
• The survey addresses a gap in comprehensive coverage by reviewing general and advanced tensor completion methods, applications, experiments, and open challenges from a big-data perspective.It focuses on variety, volume, and velocity among big data’s challenges.Source: §1 · pp. 2–3
• The survey organizes its coverage around general completion methods and methods addressing variety through auxiliary information, volume through scalability, and velocity through dynamic completion.It also introduces multilinear algebra and problem formulations before summarizing methods, then covers applications, experimental simulations and metrics, and future directions.Source: §1 · pp. 2–3

2.1 Preliminaries

• Preliminaries define an Nth-order tensor as an N-way array and mode-n matricization as unfolding it into a matrix; forward or backward mode orderings are acceptable if calculations stay consistent.The section introduces tensor operations and notation following.Source: §2.1 · p. 3, §2 · p. 3, Figure 2 · p. 4

2.2 Tensor Completion Problem

• Low-rank tensor completion seeks a minimum-rank tensor X matching observed entries T_Ω, with rank_* chosen to reflect the assumed tensor rank.The formulation is presented as a generalization of matrix completion and a starting point for variants.Source: §2.2 · p. 5

2.2.1 Rank Variants.

• CP-rank minimization is impractical because computing CP rank is NP-hard; fixing rank is difficult to estimate, motivating upper bounds or dynamic rank search.Fixed-rank formulations can replace rank minimization with computable norms or minimize prediction error against observations.Source: §2.2.1 · pp. 5–6
• Tensor n-rank (Tucker rank) extends matrix completion techniques via matricizations, but favors one-mode-versus-rest structure [152]; TT and tubal ranks are alternatives [66] [152].The section notes that there is no absolute conclusion that one tensor rank is always better than another.Source: §2.2.1 · p. 6

2.2.2 Constraint Variants.

• The equality constraint X_Ω=T_Ω represents noise-free observations and uniform Bernoulli sampling; variants accommodate Gaussian noise [12] or Gaussian measurement operators.Other equivalent constraint forms use linear projection operators to represent sampling over an index set.Source: §2.2.2 · pp. 6–7

• The section groups general tensor completion approaches into decomposition-based, trace-norm-based, and other variants.Source: §3 · p. 7
• These methods are included for their foundational role or because their original focus was not big data analytics.Source: §3 · p. 7
• The surveyed methods are not necessarily more straightforward or less scalable than advanced tensor completion methods.Source: §3 · p. 7

3.1 Decomposition Based Approaches

• Tensor decompositions provide latent structure for heterogeneous, multi-aspect data, and missing-value decomposition was an early precursor to low-rank tensor completion [103, 148, 2, 18, 83, 192, 199].The overview focuses on CP and Tucker while noting hierarchical tensor representations and PARAFAC2 as other possible approaches.Source: §3.1 · p. 7

3.1.1 CANDECOMP/PARAFAC (CP) Based Methods.

• CP completion uses EM-like imputation or missing-skipping (MS) optimization; MS methods are usually more robust at high missing ratios, while projection-based optimization can be difficult [2].EM-like methods iteratively replace missing entries with a CP low-rank estimate, but their convergence may slow and local-minimum risk rise as missingness increases. INDAFAC uses a Levenberg–Marquardt Gauss–Newton method and is computationally efficient at high missing ratios; CP-WOPT [2] uses first-order gradients and offers effectiveness and scalability across missing ratios.Source: §3.1.1 · pp. 8–9

3.1.2 Tucker-Based Methods.

• Tucker completion adapts both EM-like and MS missing-data strategies, including HOOI-based imputation, observed-value SGD, and probabilistic pTucker.Examples include HOSVD to track a low-rank subspace followed by SGD on observed values [90], and pTucker, which omits missing entries from the likelihood.Source: §3.1.2 · p. 9
• Under matching rank assumptions and ideal hyperparameters, Tucker methods are usually more effective, whereas CP is often unique and more computationally flexible for distributed large-scale data.Tucker's general core captures interactions beyond strictly trilinear ones; CP's uniqueness, aside from permutation and scaling, can support interpretation with domain constraints.Source: §3.1.3 · p. 9

3.1.3 Tucker-Based Methods vs CP-Based Methods.

• Hierarchical tensor representations generalize Tucker for high-order tensors and use projected-gradient methods, including Riemannian gradient iteration with hierarchical singular-value thresholding.Each Riemannian gradient iteration takes a gradient step in ambient space, then maps back to the low-rank tensor manifold; a related Riemannian optimization approach constructs a manifold from hierarchical representations [93].Source: §3.1.3 · p. 10

3.2 Trace Norm Based Approaches

• The SNN model sums nuclear norms of tensor unfoldings as a convex relaxation of tensor n-rank, allowing completion without predefining tensor rank.The unfolding matrices remain coupled through their multilinear correlations.Source: §3.2 · p. 10
• Liu et al. introduced the first trace-norm tensor completion algorithm, while later work commonly uses ADMM or related splitting methods.For the noiseless case, methods either decrease the regularization weight or remove the error term; Liu et al. report the latter is more efficient.Source: §3.2 · pp. 10–11
• Mu et al. proposed applying a single trace norm to a more balanced unfolding instead of summing unfolding norms, with analysis of sampling bounds.Other structures target tensor tubal-rank or incoherence, with sampling-size findings addressed in the statistical analysis [217].Source: §3.2 · pp. 11–12
• Factorized approaches apply trace-norm constraints to decomposition factors rather than large unfoldings to reduce computation, accommodate structure, and partly avoid predefined ranks [107, 127, 213].Examples include Hankelized factors for exponential-signal completion and trace-norm constraints on CP or Tucker factors.Source: §3.2 · p. 12
• Mardani et al. extended a Frobenius-norm reformulation of matrix trace norm to tensors for online completion.The matrix reformulation uses a low-rank factorization X = UV⊤.Source: §3.2 · p. 12

3.3.1 Non-negative Constrained Approaches.

• For nonnegative tensor completion, methods constrain latent factor matrices (e.g., BCD or ADMM), while integer-valued tensors can use gKL divergence.The cited applications include image completion and medical data analysis.Source: §3.3.1 · p. 12

3.3.2 Robust Tensor Completion.

• For outliers and gross non-Gaussian corruptions, robust completion separates T into low-rank X and sparse E, often jointly minimizing trace and l1 norms.Trace norm relaxes rank minimization, while l1 serves as a convex surrogate for the l0 norm.Source: §3.3.2 · pp. 12–13
• Li et al. use block coordinate descent; Goldfarb and Qin use convex ADMM; others use sparse-factor ADMM [84], variational Bayes, or online stochastic optimization.The cited applications include separating corrupted noise and image restoration, as well as background subtraction.Source: §3.3.2 · p. 13

3.3.3 Riemannian Optimization.

• Riemannian completion treats fixed-rank tensors as a smooth manifold, using projected-gradient and retraction steps; Tucker and hierarchical Tucker spaces provide manifold choices.Tucker factorized orthogonal matrices parameterize the manifold and tangent space [93]; hierarchical Tucker supports high-dimensional applications.Source: §3.3.3 · pp. 13–14
• For three-order tensors, Kasai et al. [93] use a block-diagonal Hessian approximation and tangent-space metric in preconditioned conjugate gradients, at cost O(|Ω|r1r2r3).HOSVD and hierarchical singular value thresholding are cited as retraction maps that return updates to the low-rank manifold.Source: §3.3.3 · p. 14
• Other completion approaches include alternative convex relaxations for Tucker ranks, adaptive sampling [16], and matrix-based methods.The survey lists representative algorithms in Table 2 for summary and comparison.Source: §3.3.3 · p. 14

3.4 Statistical Assumption and Theoretical Analysis.

• A low-rank tensor is not always recoverable: a tensor with one nonzero entry can be missed with 10% probability even when 90% of entries are randomly sampled.The section therefore asks when unique and exact completion can be expected with high probability.Source: §3.4 · p. 14

3.4.1 Sampling Assumption.

• Uniform random sampling is standard, while Gaussian, Fourier, and adaptive measurements are alternatives; Fourier sampling offers structured measurements and fast multiplication routines [16].Gaussian measurements are defined as linear maps formed from tensors with i.i.d. standard normal entries.Source: §3.4.1 · pp. 14–15

3.4.2 Incoherence Assumption.

• Incoherence requires information to be distributed comparably across entries; coherence concentrates tensor mass in a few entries, risking missing informative values under uniform random sampling.The tensor condition bounds mode-wise subspace coherence by μ, and mutual incoherence is also introduced.Source: §3.4.2 · p. 15

3.4.3 Number of Observed Entries.

• For Tucker rank (r, …, r), Gaussian-measured SNN requires more than CrI^(N−1) observations with high probability [194, 138], while nonconvex completion is sufficient with (2r)^N + 2rIN + 1 almost surely.The SNN bound is also shown to be necessary; the nonconvex bound is contrasted with the tensor's degrees of freedom.Source: §3.4.3 · p. 16
• The square-deal approach gives sufficient observation bounds for CP-rank recovery and high-probability recovery of Tucker-rank tensors [138].The section summarizes these bounds alongside their sampling strategies and incoherence assumptions in Table 3.Source: §3.4.3 · pp. 16–17, Table 3 · p. 17
• For CP rank-r tensors, proper incoherent nuclear-norm minimization can recover from O((r^2 I^(3/2) + r^(N−1)I)(log(I))^2) uniformly sampled entries [217].The section also describes a balanced reshaping trace-norm convexification as an alternative to combining all mode-n trace norms.Source: §3.4.3 · p. 16
• Adaptive sensing exploits highly informative entries as an alternative to random sampling, potentially substantially reducing required observations; the cited approaches do not generalize to random samples and need little or no incoherence assumptions [108, 16].Source: §3.4.3 · pp. 16–17

4.1 Similarity Based Approaches

• Similarity-based methods regularize CP or Tucker factorization with within-mode or cross-mode similarity matrices, improving completion accuracy especially for sparse observations.AirCP uses spatial and temporal relationships to construct mode similarities; domain knowledge guides their definitions, and probabilistic approaches treat them as inverse kernel matrices for factor priors.Source: §4.1 · pp. 17–18

4.2 Coupled Matrices/Tensors Factorization

• CMTF jointly factorizes an incomplete tensor and auxiliary matrices with shared latent factors, and is reported to retain recovery performance at higher missing rates than CP.CP has comparable recovery accuracy below an 80% missing ratio but its recovery error rises sharply beyond that; CMTF retains low recovery error until the error rate exceeds 90%. A Riemannian variant adds coupled-matrix regularizers and optimizes them with Riemannian Conjugate Gradient descent.Source: §4.2 · p. 19

4.3.1 Hybrid Models.

• TAPER combines AirCP-style similarity matrices with cross-mode features represented as coupled matrices, and evaluates combinations of heterogeneous contextual information.Source: §4.3.1 · pp. 19–20

4.3.2 Coupled Trace Norm.

• Wimalawarne et al. [203] define three coupled trace norms using concatenations of coupled matrices with latent factors or target-tensor matricizations.For the first mode of a third-order tensor, the coupled overlapped trace norm uses the concatenation of the target tensor's mode-1 unfolding and its corresponding coupled matrix.Source: §4.3.2 · p. 20
• Other side-information constraints include componentwise linear and smoothness constraints with automatic rank search, and factorization An = BnCn optimized by nonlinear least squares.The latter approach is reported to be faster and more accurate than traditional CP methods when few entries are observed or missing entries are structured.Source: §4.3.3 · p. 20

5.1 Scalable CP and Tucker-Based Methods

• CP- and Tucker-based methods face intermediate-data explosion and data decentralization challenges; missingness and sparsity also affect completion costs, and sparse-decomposition optimizers may transfer across tasks.The survey distinguishes completion, which imputes missing entries, from decomposition, while noting that sparse tensors create shared scalability challenges.Source: §5.1 · p. 21

5.1.1 Intermediate Data Explosion Problem.

• GigaTensor reorders sparse ALS computations to avoid materializing Khatri-Rao products, reducing intermediate-data size from O(JKR+m) to O(max(J+m,K+m)).HaTen2 extends the approach by unifying sparse Tucker and PARAFAC decomposition in a framework that can be adapted to completion with an indication tensor.Source: §5.1.1 · p. 23

5.1.2 Decentralization of the Tensor Data Problem.

• FLEXIFACT distributes disjoint tensor blocks across machines to distribute memory demands, while CDTF and SALS use column-wise or subset updates in MapReduce to address communication costs.FLEXIFACT aggregates updated parameters at a master between strata, whereas CDTF and SALS were developed to overcome the high communication cost of approaches like FLEXIFACT.Source: §5.1.2 · p. 24

5.2 Other Approaches

• Other scalable approaches approximate tensor trace norms or use tensor-train relaxation and randomized alternating least squares for higher-order completion.The tensor-train approach derives a completion error bound and aims for time and space efficiency.Source: §5.2 · p. 25

6 DYNAMIC TENSOR COMPLETION

• Dynamic analysis includes online CP methods and Tucker methods, while dynamic tensor completion has received less attention.Related work also includes histogram-based multi-aspect streaming analysis.Source: §6 · p. 26, §6.1 · p. 26

6.1 Streaming Tensor Completion

• Streaming completion receives each incomplete temporal slice only at its timestamp, unlike batch completion, which assumes all slices are collected in advance.Earlier work used PARAFAC for missing-future-data imputation, while topic modeling for traffic forecasting is described as closer to prediction than completion.Source: §6.1 · p. 26, Figure 7 · p. 27
• Online SGD factorizes and imputes each arriving slice by solving its temporal factor, then updating other factors; it assumes the streaming subspace changes rarely and smoothly.OLSTEC uses recursive least squares for faster convergence on dramatically changing subspaces, at higher time complexity: O(|Ωt|R^2 + (I1 + I2)R^3) versus O(|Ωt|R^2).Source: §6.1 · p. 27

6.2 Multi-Aspect Streaming Tensor Completion

• Multi-aspect streaming allows growth along any tensor mode, and MAST handles all-mode changes through partition, substitution, and re-decomposition.Substituting the old tensor with its CP decomposition can speed optimization when the old tensor is large relative to the new tensor; a forgetting factor alleviates substitution error, and a temporal special case further reduces completion error.Source: §6.2 · pp. 27–28
• SIITA [141] provides a Tucker-based multi-aspect streaming completion framework that incorporates auxiliary information and is reported to perform well in batch and streaming settings.The section characterizes dynamic tensor completion as an early-stage area with substantial opportunities and challenges.Source: §6.2 · p. 28

7 APPLICATIONS

• Applications are examined through the concrete problem, its tensor-completion formulation, and the methods applied across several domains.The survey includes social sciences, computer vision and signal processing, healthcare and bioinformatics, among others.Source: §7 · p. 28

7.1 Social Computing

• Social computing applies computational methods to study individual activities and societal relationships, with multiple problems suited to tensor completion.Other related applications include social-aware image-tag refinement and truth discovery.Source: §7.1 · p. 28, §7.1.5 · p. 31

7.1.1 Link Prediction.

• Dynamic links and multiple interaction types add dimensions to graph data, motivating tensor completion for predicting missing edges or future connections.Temporal interactions and distinct node-interaction types extend traditional matrix-based link prediction.Source: §7.1.1 · p. 28
• For link prediction, temporal bipartite graphs support CP-based forecasting [45], while interaction types form a third mode used with node similarities or coupled factorization.The coupled-factorization framework was applied to UCLAF and Digg datasets, with different loss functions and factorization models compared in practice; see also [49].Source: §7.1.1 · pp. 28–29

7.1.2 Recommender Systems.

• For personalized tag recommendation, Rendle et al. proposed ranking-based, pairwise-interaction, and factorization-machine methods, while temporal and contextual tensors support richer recommendation.The first method outperformed HOSVD and PageRank in quality and runtime; the pairwise approach improved prediction accuracy and speed, and factorization machines address sparsity where SVMs fail.Source: §7.1.2 · p. 29
• Auxiliary information supports location-based activity recommendation, while Taper models user-expert-topic relations and similarities to achieve high-quality recommendations by precision and recall.The four side-information sources in include location features, GPS user-location visits, and user and activity similarities; these regularizers alleviate sparsity.Source: §7.1.2 · pp. 29–30

7.1.3 Urban Computing.

• Urban mobility applications use robust tensor recovery for traffic data with unknown outlier locations, coupled Tucker factorization for sparse travel-time estimation, and sliding-window completion for short-term traffic prediction.The travel-time tensor combines road segments, drivers, and time slots with denser historical data and geographic and temporal similarity matrices; the sliding-window method models week × day × point data.Source: §7.1.3 · p. 30

7.1.4 Information Diffusion.

• Online meme diffusion is modeled as a meme × location × time tensor, with latent auxiliary relationships among all three modes used to recover distributions across three missing-data scenarios.Real-world Twitter hashtag experiments tested random missingness, entire memes missing at locations, and entire locations missing.Source: §7.1.4 · p. 30

7.2 Healthcare, Bioinformatics and Medical Applications

• For incomplete medical data, tensor completion has been applied to MRI and streaming cardiac MRI, medical questionnaires, RNA sequencing, electronic health records, and EEG [13] [2].Methods include Bayesian probability PARAFAC with prior information, combined trace-norm and decomposition approaches, and scalable CP factorization; Rubik combines knowledge-guided constraints to complete and denoise EHRs for clinical analysis.Source: §7.2 · p. 31

7.3 Chemometrics

• On the amino acid fluorescence and flow injection chemical datasets, studies considered several missing patterns, and auxiliary mode similarities improved completion accuracy, especially with sparse observations.The missing patterns included randomly missing values, spectra or vectors, and systematically missing spectra or vectors; flow injection data were tested with element-wise and slice-wise missingness.Source: §7.3 · p. 31

7.4 Computer Vision

• Tensor completion in computer vision addresses image inpainting, video decoding, compressed sensing, and spectral data analysis.RGB images are third-order tensors, whose multiple dimensions and multilinear correlations tensor-based methods can leverage for applications including surveillance, interaction, retrieval, and biometric identification.Source: §7.4 · p. 32, §7.4.1 · p. 32

7.4.1 Image Completion.

• For facial image completion on the Olivetti face benchmark, Signoreto et al. distinguish pure “hard completion” from semi-supervised soft completion with partial labels; their spectral-regularized framework handles both pure completion and multitask cases.Source: §7.4.1 · p. 32

7.4.2 Video Completion.

• Video completion covers inpainting and compression, with methods for color-video tensors and online tracking of incomplete streams.Kasai uses recursive least squares for online CP decomposition and evaluates sequential airport-hall surveillance frames; OLSTEC reconstructs streams by reordering cropped incomplete frames and rapidly adapts to changed backgrounds.Source: §7.4.2 · pp. 32–33

7.5 Compressed Sensing

• Compressed sensing, initiated by in 2006, recovers sparse signals from few nonadaptive random linear measurements using methods such as ℓ1-minimization and iterative hard thresholding.The survey treats image and video compression as special cases because images and videos are multidimensional signals.Source: §7.5 · p. 33
• The Kronecker-based model supports high-order tensor compressed sensing, and generalized algorithms exploit Kronecker structure through approaches such as ℓ1-minimization.Source: §7.5 · p. 33
• Sidiropoulos et al. use CP identifiability to recover low-rank tensors from Kronecker measurements by fitting a compressed-domain model, then decompressing each mode.Source: §7.5 · p. 33
• Rauhut reconstructs low-rank tensors using hierarchical tensor formats and an H-SVD-based approach, but reliance on large-matrix SVDs limits scaling to large mode sizes [38].Source: §7.5 · p. 33
• Friedland et al. [56] enable simultaneous all-mode acquisition and compression while preserving tensor structure, whereas Li et al. use structured sparsity for nonstationary signals and reduced sampling and recovery costs.Caiafa and Cichocki [23] propose a fast, non-iterative method based on low multilinear rank that assumes no specific sparsity patterns and suits large-scale problems.Source: §7.5 · p. 33

7.6 Other Applications

• Applications include hierarchical Tucker interpolation of seismic frequency slices and climate-record completion with spatial-temporal auxiliary information, which improved efficiency and estimation error in cokriging and forecasting.Source: §7.6.1 · p. 33

7.6.1 Climate Data Analysis.

• Numerical-analysis applications include recovering compressed tensors associated with singular functions and completing solution tensors for parameterized linear systems from discretized stochastic elliptic PDEs.Source: §7.6.2 · p. 34

8.1 Synthetic Data Construction

• Synthetic examples cover rank-R CP tensors, rank-(R1,R2,R3) Tucker tensors, and rank-R CP tensors with auxiliary similarity, using third-order tensors for convenience.These constructions address the difficulty of obtaining real-world tensors with known rank and sampling assumptions.Source: §8.1 · p. 34

8.1.1 Rank-

• A common rank-R CP construction samples factor entries from N(0,1), normalizes columns, and adds Gaussian noise; Acar et al. [2] note it yields a unique decomposition with probability one.Missing entries may be sampled uniformly using a Bernoulli distribution or structured as missing fibers or slices, with choices guided by incoherence assumptions and the completion method.Source: §8.1.1 · p. 34

8.1.2 Rank (R1,R2,R3) Tucker Tensor.

• For Tucker rank (R1,R2,R3), the core and factor matrices are sampled from N(0,1), factor matrices are usually orthogonalized, and missingness is generated as for CP tensors.Source: §8.1.2 · p. 34

8.1.3 Rank-

• Narita et al. construct rank-R CP tensors with tri-diagonal similarity matrices by generating factor matrices column by column, making neighboring rows similar.The paper notes auxiliary information may enable exact recovery even when slices are missing.Source: §8.1.3 · pp. 34–35

8.2 Evaluation Metrics

• Metrics depend on the application: RMSE is used in recommender systems, AUC in binary classification, and nDCG in information retrieval, and other suitable metrics may be selected.Source: §8.2 · p. 35

8.2.1 Relative Standard Error / Percentage of Fitness / Tensor Completion Score.

• Relative error is the most commonly used metric; percentage of fitness measures reconstruction fit, and Acar et al.’s [2] Tensor Completion Score is a refined relative error.Source: §8.2 · p. 35, §8.2.1 · p. 35

8.2.2 MSE / RMSE / MAE.

• Mean-square error, root-mean-square deviation, and mean absolute error are frequently used, especially for recommendation problems.Source: §8.2.2 · p. 35
• Classification-oriented tensor completion studies use precision, precision@k, recall, F-measure, and AUC; AUC may use all missing entries or average scores across slices.Source: §8.2.3 · p. 35

Volume: Tensor Completion with Large-Scale and High-order Data

• Large-scale and high-order completion still faces computational limits, uncertain generalization, hard-to-verify assumptions, and the challenge of combining tensor methods with data-hungry deep learning.The authors identify intermediate-data explosion and data decentralization as underlying scalability challenges; hierarchical Tucker methods have been applied to high-order problems, while sampling methods may require difficult-to-guarantee assumptions such as incoherence [16].Source: §9 · p. 36

Velocity: Tensor Completion in Dynamic Data Analytics

• Dynamic completion needs methods that coordinate changing tensor sizes and modes, account for how dynamic patterns affect models and imputation, and establish theoretical guarantees.Fixed-rank assumptions may fail for dynamically changed tensors, and static strategies may reduce completion effectiveness; the authors note a lack of analysis such as convergence results, sufficient conditions, or statistical assumptions.Source: §9 · p. 36

Variety: Tensor Completion with Heterogeneous Data Sources

• Heterogeneous sources, domain knowledge, and expertise offer future directions for improving completion, including integration with deep learning and applications to large-scale or dynamic settings.Prior work incorporating human knowledge has reported favorable performance in healthcare.Source: §9 · pp. 36–37

Other Aspects

• Future work should also examine veracity by addressing uncertainty in datasets, algorithms, and results, and value by assessing practical usefulness for real-world applications.The authors frame veracity and value as additional big-data perspectives beyond the “3V” challenges.Source: §9 · p. 37