In data science, multi-way arrays—or tensors—are the natural choice for representing complex, high-dimensional relationships. Whether tracking video frames over time, monitoring traffic across a city sensor network, or capturing user interactions on a website, tensors preserve the multi-dimensional structure that standard matrix flattening destroys.
However, as data streams in indefinitely, traditional batch tensor decomposition methods (such as CP or Tucker decomposition) fail. They require the entire dataset to be resident in memory and recompute the latent factors from scratch whenever new data arrives. This creates a computational bottleneck where the time complexity grows linearly or super-linearly with the history length ($O(N)$).
To unlock real-time analytics, researchers have developed online tensor decomposition. The core intuition behind this direction is to process incoming data streams slice-by-slice or element-by-element, ensuring that both computational complexity and memory footprints remain constant ($O(1)$) relative to the history length.
Decoupling Subspaces from Coefficients
The primary reason online tensor decomposition works without revisiting historical data is the structural decoupling of the tensor into two distinct components: a persistent, slowly evolving subspace (basis) and rapidly changing, transient representation coefficients.
When a new slice of data arrives, we do not need to re-evaluate the entire history. Instead, we project the new data onto the existing subspace to calculate the current coefficients, and then apply a minor, incremental adjustment to the basis itself.
Streaming Data Slice ----> [ Project onto Existing Basis ] ----> Current Coefficients
|
v
[ Incremental Basis Update ] ----> Updated Persistent Basis
Li 0006 et al. demonstrate this mechanism in Online Robust Low-Rank Tensor Learning by utilizing a bi-factor decomposition. By updating the basis incrementally, their model avoids performing expensive Singular Value Decompositions (SVD) on the entire accumulated dataset, accelerating processing speeds by orders of magnitude.
Similarly, Hu et al. show in Incremental Tensor Subspace Learning and Its Applications to Foreground Segmentation and Tracking that running an incremental SVD directly on the unfolding matrices of incoming data allows the sample mean and eigenbasis to adapt continuously. This allows real-time tracking applications to discard raw historical frames immediately after ingestion. To handle environments where older data becomes irrelevant, the authors can restrict these updates to a sliding window, as explored by Xu et al. in Anomaly Detection in Road Networks Using Sliding-Window Tensor Factorization, keeping the background model fresh and computationally lightweight.
Recursive and Stochastic Optimization
When data arrives as a continuous stream of discrete events or irregular slices, exact algebraic updates become intractable. Online tensor decomposition solves this by framing the decomposition as an online optimization problem, utilizing stochastic gradient descent (SGD) or the online Alternating Direction Method of Multipliers (ADMM).
The mathematical trick here is to isolate the objective function so that historical data is compressed into a fixed-size summary matrix (often acting as a historical gradient cache or information matrix). Consequently, the optimization step for a new slice depends strictly on the incoming data size and the historical summary, never the raw history.
- Isolating History: In Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors - Algorithm and Application, Jang et al. separate the objective function into historical and current components. This allows their algorithm to handle irregular tensors—where both the number of subjects and the length of their records grow simultaneously—with a time complexity proportional only to the size of the incoming chunk.
- Stochastic Updates: Maehara et al. leverage incremental stochastic updates in Expected Tensor Decomposition with Stochastic Gradient Descent to dynamically evolve multi-way models. For continuous-time event sequences, Xu et al. combine point processes with an online stochastic ADMM strategy in Online Continuous-Time Tensor Factorization Based on Pairwise Interactive Point Processes, updating latent factors sequentially as events unfold.
- Real-Time Video Processing: Andrews Sobral applies this in Online Stochastic Tensor Decomposition for Background Subtraction in Multispectral Video Sequences, demonstrating that stochastic optimization can maintain a low-rank background model in near real-time, running over twenty times faster than batch alternatives.
Bounding Parameter Growth via Advanced Representations
Even if an algorithm processes data slice-by-slice, a fundamental problem remains: if the temporal or spatial dimension of a tensor grows indefinitely, the corresponding factor matrices in a standard CP or Tucker decomposition must also grow. This violates the strict constant-memory requirement of true streaming systems.
To circumvent this limitation, recent architectures alter how the tensor is parameterized, utilizing geometric constraints or functional representations to fix the number of learnable parameters.
Manifold Optimization
Instead of allowing factor matrices to grow, we can track the underlying low-rank structure as a point moving along a fixed-dimensional geometric surface. Gilman et al. introduce this in Grassmannian Optimization for Online Tensor Completion and Tracking With the t-SVD via the TOUCAN algorithm. By performing incremental gradient descent directly on the Grassmann manifold, they achieve linear computational complexity and constant memory usage relative to the number of time samples.
Implicit Neural Representations (INRs)
Another solution is to treat the tensor not as a discrete grid of cells, but as a continuous function mapping coordinates (like space and time) to values.
Standard Streaming Tensor: [Time 1: Matrix] -> [Time 2: Matrix] -> [Time 3: Matrix] (Grows Infinitely)
Functional Tensor (INR): (Coordinate: x, y, t) ----> [ Fixed-Size Neural Network ] ----> Value
As proposed by Zhang et al. in Online Functional Tensor Decomposition via Continual Learning for Streaming Data Completion, parameterizing the tensor decomposition with a fixed-size neural network ensures that the total number of learnable weights remains entirely constant. As the data stream extends, the network updates its internal weights via continual learning rather than expanding its architecture, completely bypassing the parameter explosion of traditional online tensor methods.
Key Foundational Work
Mining large time-evolving data using matrix and tensor tools (2007) — contributed 3 concept elements to this direction.