Introduction
Modern sensing technologies, ranging from hyperspectral cameras to dynamic MRI machines, generate vast quantities of multi-way data. In practice, this data is often incomplete due to sensor failure or sampling constraints and typically arrives as a continuous stream. Traditional "batch" algorithms, which require storing the entire dataset in memory, are ill-suited for high-rate streaming applications. Furthermore, most existing tensor completion methods struggle to track non-stationary data that changes over time.
The TOUCAN Framework
The researchers propose TOUCAN (Tensor rank-One Update on the Complex grassmanniAN), a high-speed streaming algorithm designed for completing and tracking missing data in three-way tensors. TOUCAN leverages the algebraic power of the tensor Singular Value Decomposition (t-SVD) and optimization on Grassmann manifolds to achieve linear computational complexity and constant memory usage.
The core innovations of TOUCAN include:
- BTD Equivalence: A new theoretical link showing that the t-SVD is a specialized form of Block-Term Decomposition (BTD), allowing the tensor problem to be treated as a collection of matrix problems in the Fourier domain.
- Fourier Domain Separability: By transforming data into the frequency domain using the Fast Fourier Transform (FFT), the algorithm can update different frequency components in parallel.
- Grassmannian Optimization: Instead of standard gradient descent, TOUCAN performs incremental gradient descent on the Grassmann manifold (the space of all subspaces). This maintains mathematical consistency (orthonormality) without expensive SVD computations at every step.
- Conjugate Gradient Descent (CGD): An internal CGD loop efficiently estimates weights for each new data slice as it arrives.
Experimental Evaluation
TOUCAN was evaluated across three distinct data types:
- Synthetic Data: Low-tubal-rank tensors tested for scaling and convergence.
- Chemo-sensing: A dataset of 71 sensors recording gas concentrations, testing the ability to track dynamic, non-stationary signals.
- Dynamic MRI: Myocardial perfusion data involving high-dimensional motion and time-varying dynamics.
Key Results
- Speed and Efficiency: In synthetic tests, TOUCAN was orders of magnitude faster than state-of-the-art batch algorithms like TNN-ADMM and TCTF. For large tensors, it completed tasks in seconds that took other methods minutes or hours.
- Memory Footprint: TOUCAN required as little as 0.3% of the memory used by batch methods, as it only stores the current subspace estimate rather than the entire tensor.
- Accuracy and Tracking: On gas sensor data, TOUCAN achieved NRMSE comparable to top online CP-decomposition methods but with significantly lower overhead. Its incremental nature allows it to adapt to abrupt system dynamics on the fly.
- Theoretical Grounding: The authors provide a mathematical proof for local expected linear convergence, providing theoretical backing for the algorithm's empirical success.
Discussion and Future Work
The discovery that t-SVD is a specific case of BTD bridges the gap between t-SVD algebra and classical multilinear algebra. By optimizing on the Grassmann manifold, TOUCAN naturally adheres to low-rank structures without heavy regularization parameters that often plague other streaming methods.
However, limitations remain. TOUCAN currently relies on a fixed Discrete Fourier Transform (DFT) basis; future work may involve learning an optimal orthogonal basis for specific data types. Additionally, automated methods for estimating the "tubal-rank" ($r$) and determining the optimal tensor orientation are open research challenges.
Summary updated