In modern data science, we rarely deal with simple tables. We deal with multi-aspect data: a user interacts with an item at a specific time, or a sensor records multiple frequencies across various spatial locations. These are naturally represented as tensors (multi-dimensional arrays).
While traditional methods like CP or Tucker decomposition are powerful for finding hidden patterns in these arrays, they suffer from a "memory wall." As Takanori Maehara and Kohei Hayashi note in Expected Tensor Decomposition with Stochastic Gradient Descent, standard batch algorithms require the entire dataset to be stored in memory, which is impossible for high-velocity streams like social media or real-time sensor networks.
The solution is Incremental Tensor Analysis: a family of techniques that evolve a model slice-by-slice, updating the underlying low-rank structure without ever looking back at the full history of the data.
The Intuition: Evolving the Basis
The core idea behind incremental analysis is that the "latent structure" of data—the fundamental patterns that explain the observations—changes slowly. If you have a low-rank representation of yesterday's data, today's new data points likely live in a very similar subspace.
Instead of recomputing the decomposition from scratch, researchers like Weiming Hu propose updating the model by performing incremental Singular Value Decomposition (SVD) on the "unfolding" matrices of the tensor. In Incremental Tensor Subspace Learning and Its Applications to Foreground Segmentation and Tracking, this approach allows a system to adapt its "background model" in a video stream in real-time, accounting for lighting changes or moving shadows without needing to store every previous frame.
Stochastic Updates and Structural Augmentation
To achieve high speed, many algorithms move away from exact algebraic updates toward Stochastic Gradient Descent (SGD). By treating each new data point as a small signal to nudge the model, algorithms can maintain an up-to-date representation with minimal computation.
- Median K-Flats: Arthur Szlam and Gilad Lerman demonstrate in Median K-Flats for hybrid linear modeling with many outliers that using an $\ell_1$ "median" distance with SGD makes the model robust to outliers, which are common in streaming data.
- Core Augmentation: For Tucker decompositions, Eric Phipps and colleagues at Sandia National Laboratories developed techniques to incrementally augment the core tensor and factor matrices. This allows the model to grow in complexity only as much as the new data requires.
- Slice Sampling: Dongjin Choi and Lee Sael take a different path with CTD, which samples actual slices of the tensor. This makes the results more interpretable because the "factors" are real data observations rather than abstract mathematical constructs.
Handling Missing Data and High Velocity
In real-world streams, data is often "noisy" or "holy" (full of missing values). Qingquan Song explains in Tensor Completion Algorithms in Big Data Analytics that tracking the evolving subspace is often more efficient than standard SGD because it converges faster by exploiting the geometric structure of the data.
A sophisticated example of this is TOUCAN, developed by Kyle Gilman and Laura Balzano. In Grassmannian Optimization for Online Tensor Completion and Tracking in the t-SVD Algebra, they combine the algebraic efficiency of the t-SVD with optimization on Grassmann manifolds. This allows the algorithm to "fill in the blanks" of missing data in real-time with linear computational complexity.
Why It Works: The Power of Local Constraints
The effectiveness of these methods often comes from balancing global structure with local constraints. For instance, the STORTD algorithm by Yao Wang and Kaidong Wang for streaming traffic data imputation works because it doesn't just look at the tensor as a whole; it applies local spatial and temporal constraints.
By recognizing that a traffic sensor's reading is highly correlated with its neighbors and its own recent past, the model can update its factor matrices 1,000 times faster than batch methods. This shift from "global recomputation" to "local refinement" is what enables multi-way data analysis to keep pace with the modern world's data velocity.