Multiway data analysis allows us to capture complex, multidimensional interactions in fields ranging from genomics to deep learning. However, representing data as high-dimensional tensors introduces a severe computational bottleneck: the curse of dimensionality. Storing an explicit $d$-th order tensor scales exponentially ($O(n^d)$) with the number of dimensions. Even when the underlying data is sparse or low-rank, standard optimization algorithms often require flattening tensors into massive matrices (matricization) or computing dense intermediate Kronecker, Khatri-Rao, or outer products.
As Zhe et al. note in Scalable Nonparametric Multiway Data Analysis, holding entire multiway datasets in memory or relying on expensive distributed clusters is highly impractical for standard hardware. To bypass this limitation, a powerful paradigm has emerged: implicit tensor computation. By mathematically restructuring operations, algorithms can execute tensor decompositions, regressions, and contractions directly on raw data matrices or factorized components without ever materializing the high-dimensional tensor or its massive intermediate representations.
Defeating the Intermediate Data Explosion
The most common bottleneck in tensor factorization occurs during alternating optimization steps, such as Alternating Least Squares (ALS). To update a single factor matrix, standard algorithms compute a Khatri-Rao product ($\mathbf{A} \odot \mathbf{B}$) of the remaining factors. If the factors are large, this product creates a massive, dense intermediate matrix that can easily exhaust system memory—a phenomenon known as "intermediate data explosion."
Traditional Explicit Approach (Memory Explosion):
[Factor A] ⊙ [Factor B] ──> [Massive Intermediate Matrix] ──> Multiply with Tensor
Implicit Approach (DFacTo / PARCUBE):
[Sparse Input Data] ──> Sequence of Small Matrix-Vector Products ──> Direct Update
We can avoid this explosion by changing the order of operations. In DFacTo: Distributed Factorization of Tensors, Choi et al. show that the core computational bottleneck can be mathematically reframed as a sequence of simple sparse matrix-vector products. Instead of explicitly constructing the large matrix resulting from the Khatri-Rao product, the operations are decoupled.
Similarly, Papalexakis et al. demonstrate in Large Scale Tensor Decompositions: Algorithmic Developments and Applications that decoupling large-scale matrix products allows for exact tensor decompositions by operating directly on the sparse input tensor and smaller factor matrices. Because the large intermediate structures are never materialized, memory consumption drops from exponential to linear relative to the tensor dimensions.
Reshape-Free and Symbolic Operations
Tensors are traditionally manipulated by physically rearranging their memory layout—unfolding them into matrices to leverage optimized Basic Linear Algebra Subprograms (BLAS) and then folding them back into tensors. This constant reshaping introduces massive data-movement overhead.
Implicit tensor computation avoids physical reshaping through two primary techniques:
- Factorized Multiplication Shortcuts: In Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization, Yao et al. utilize mathematical shortcuts to perform matrix multiplications directly on factorized components. This bypasses the physical folding and unfolding of data entirely, eliminating computational overhead and memory movement.
- On-the-Fly Index Transformation: Rather than generating an explicit intermediate matrix for tensor unrolling, index transformations can be computed dynamically. For instance, in High Performance and Portable Convolution Operators for Multicore Processors, San Juan et al. embed image-to-column (
im2col) tensor transformations directly into the data-packing phase of a matrix multiplication library, hiding the transformation overhead and eliminating the intermediate memory footprint.
By executing operations directly in the tensor format using tensor-matrix products, Ahmadi-Asl et al. show in Corrections to "Randomized Algorithms for Computation of Tucker Decomposition and Higher Order SVD (HOSVD)" that memory complexity can be successfully reduced from exponential growth to a linear sum of dimensions and ranks.
Implicit Higher-Order Moment Estimation
A classic application where tensors become prohibitively expensive is the statistical Method of Moments, which requires computing higher-order moments like skewness (3rd-order) or kurtosis (4th-order). For a dataset with $d$ features, a 3rd-order moment tensor requires $O(d^3)$ storage.
In Estimating Higher-Order Moments Using Symmetric Tensor Decomposition, Sherman et al. demonstrate that the core operation of multiplying a symmetric tensor by a vector multiple times can be mathematically reformulated into a series of matrix-vector products using the original raw observations matrix.
$$\mathcal{T} \times_1 v \times_2 v \times_3 v \implies \frac{1}{N} \sum_{i=1}^N (x_i^T v)^3$$
Instead of explicitly constructing the high-dimensional moment tensor $\mathcal{T}$, optimization gradients and function values are evaluated directly from the raw data matrix. As a result, the computational cost scales linearly with the number of features rather than exponentially with the moment order.
Kileel et al. leverage this exact mechanism in Moment Estimation for Nonparametric Mixture Models Through Implicit Tensor Decomposition, extracting necessary information directly from data and Gram matrices to make higher-order statistical analysis feasible on standard hardware.
Sparsity-Aware and Observed-Only Optimization
When tensors represent sparse or partially observed data (such as user-item ratings or multi-view similarities), explicit algorithms often suffer because they treat missing entries as zeros, filling up memory with unneeded data.
Implicit tensor frameworks maintain efficiency by restricting all loss functions and algebraic updates exclusively to observed entries. In Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries, Park et al. implement a row-wise update rule that isolates calculations to observed data. This prevents the intermediate data explosion typically caused by materializing large dense matrices during factorization.
This principle applies equally to multi-view clustering. Selee shows in Extracting clusters from large datasets with multiple similarity measures. that performing tensor decomposition directly on sparse object-feature matrices avoids the memory overhead of generating dense similarity matrices. By bypassing the explicit computation of the outer product of feature vectors, the system ensures that computational complexity scales strictly with the number of non-zero entries in the raw data, rather than the square of the number of objects.
Key Foundational Work
Extracting clusters from large datasets with multiple similarity measures. (2007) — contributed 4 concept elements to this direction.
Sparse Higher-Order Principal Components Analysis (2012) — contributed 1 concept elements to this direction.
Wedderburn Rank Reduction and Krylov Subspace Method for Tensor Approximation. Part 1: Tucker Case (2012) — contributed 1 concept elements to this direction.