Incremental Tensor Decomposition for High-Dimensional Streams

This direction is merged into another direction: online tensor decomposition. Its last version stays readable and citable here.

Version 1 of 135 papers42 conceptsfrozen 2026-10-04

In the era of big data, we often encounter information that is naturally multi-dimensional. A surveillance video is not just a flat image; it is a stack of frames over time. A social network is not just a list of users; it is a complex web of interactions across different platforms and time scales. Mathematically, we represent these structures as tensors—the multi-dimensional cousins of matrices.

The goal of tensor decomposition is to find the hidden "latent" patterns within these arrays. However, as Yining Wang and Animashree Anandkumar point out, tensors suffer from a "curse of dimensionality." Storing a 3rd-order tensor requires $O(d^3)$ space, meaning that as the number of dimensions or the length of the data stream grows, traditional "batch" methods quickly exhaust a system's memory.

Incremental tensor decomposition solves this by shifting from offline processing to a streaming paradigm. Instead of waiting for all data to arrive, these algorithms update their understanding of the world one "slice" or "mini-batch" at a time.

From Global Storage to Local Updates

The core intuition behind incremental decomposition is that we don't need to see the entire history of a dataset to understand its current structure. In a traditional batch setting, you must load the entire tensor into RAM to calculate the factor matrices (the building blocks of the decomposition).

In contrast, researchers like Piyush Rai and Changwei Hu have developed frameworks that process data in small batches. In their work, Scalable Probabilistic Tensor Factorization for Binary and Count Data, they use an online Expectation-Maximization (EM) algorithm. By recursively updating "sufficient statistics"—compact mathematical summaries of the data seen so far—the algorithm can discard old data slices while retaining their influence on the model. This reduces the memory footprint from cubic to linear relative to the number of dimensions.

Sketching the Essence of Data

When data arrives at high velocity, even processing mini-batches can be too slow. This is where sketching comes in. Instead of operating on the raw data, algorithms create a "sketch"—a compressed, fixed-size summary that preserves the essential structural information of the tensor.

Qianxin Yi and Yao Wang introduced t-FD, a deterministic sketching algorithm for streaming tensor Singular Value Decomposition (t-SVD). In Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions, they demonstrate that by updating a fixed-size sketch as each new data slice arrives, the memory footprint remains constant regardless of how long the stream lasts.

Similarly, the OCTen framework developed by Ravdeep Pasricha and Evangelos E. Papalexakis uses compressed summaries to track latent patterns in social networks. This approach allows long-term pattern tracking on hardware with fixed memory capacity, avoiding the linear growth in memory usage that plagues standard online methods.

Continuous Functions and Neural Representations

A recent evolution in this field moves away from discrete grids entirely. In Online Functional Tensor Decomposition via Continual Learning for Streaming Data Completion, Xi Zhang and Deyu Meng propose modeling streaming data as a continuous function using Implicit Neural Representations (INRs).

By parameterizing the tensor decomposition with a fixed-size neural network, the total number of learnable parameters stays constant. To prevent the network from "forgetting" old patterns as it learns from new data, they employ a "long-tail" memory replay. This allows the system to maintain high accuracy for real-time tasks like traffic flow imputation—where Yao Wang has shown that online approaches can run up to 1,000 times faster than traditional batch methods.

Why It Works: The Power of Stochasticity

The success of these methods often relies on stochastic optimization. By treating the decomposition as a series of small, random updates, these algorithms can actually avoid the "poor local minima" that trap batch algorithms.

As explored by Lara Kassab and Deanna Needell in their work on Sparseness-constrained Nonnegative Tensor Factorization, processing temporal tensors in mini-batches allows for the detection of both fleeting "bursty" events and long-term trends. The incremental nature of the update allows the model to be more sensitive to temporal changes, providing a "knob" to tune the scale of the patterns being recovered.

By combining tensor algebra with streaming algorithms, researchers have turned the "curse of dimensionality" into a manageable computational task, enabling real-time analysis of everything from brain structural covariance to global interest diffusion.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_incremental_tensor_decomposition_for_hig_536fa201,
  title = {Incremental Tensor Decomposition for High-Dimensional Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-tensor-decomposition-for-high-dimensional-streams/rdr_536fa2011b7e42d79aa0d3bfd633f007},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_incremental_tensor_decomposition_for_hig_536fa201_v1,
  title = {Incremental Tensor Decomposition for High-Dimensional Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-tensor-decomposition-for-high-dimensional-streams/rdr_536fa2011b7e42d79aa0d3bfd633f007/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}