Introduction
Modern high-dimensional data, such as hyperspectral video and medical imaging, are naturally represented as multi-way tensors. Processing these signals in real-time presents two primary challenges: the computational and memory burden of batch processing, and the need to adapt to dynamic, time-varying underlying structures. While the Tensor Singular Value Decomposition (t-SVD) is a powerful framework for capturing spatial-shifting and scaling correlations, existing t-SVD methods are predominantly batch-oriented. This paper introduces TOUCAN (Tensor rank-One Update on the Complex grassmanniAN), a fast streaming algorithm designed for completing and tracking low-tubal-rank tensors with missing entries.
The TOUCAN Framework
TOUCAN leverages the t-SVD framework to achieve linear computational complexity and constant memory usage. The core of the approach lies in several key innovations:
The t-SVD and Block-Term Decomposition
A significant theoretical contribution of this work is the bridge between t-SVD and the Block-Term Decomposition (BTD). The authors prove that the t-SVD can be viewed as a specialized form of BTD, linking the t-SVD framework to classical multilinear algebra.
As illustrated in the figure above, the tensor $\vec{x}$ is represented as a sum of t-products: $\vec{x} = \sum_{i=1}^r \vec{u}_i * \vec{w}_i$. This decomposition allows for efficient updates as new data slices arrive.
Grassmannian Optimization in the Fourier Domain
By operating in the Fourier domain, complex t-product operations decompose into independent matrix operations. TOUCAN treats the problem of subspace tracking as finding a point on a Grassmann manifold—the space of all $r$-dimensional subspaces. The algorithm employs incremental gradient descent along geodesics to update the subspace estimate for each incoming data slice. To handle missing entries, an inner Conjugate Gradient Descent (CGD) loop estimates optimal weights before the subspace update.
Experimental Evaluation
The performance of TOUCAN was validated across synthetic and real-world datasets:
- Chemo-sensing: In gas measurement experiments, TOUCAN demonstrated a significant speedup, performing approximately 28x faster than the TNN-ADMM batch method and 23x faster than TCTF, while maintaining comparable accuracy.
- Dynamic MRI: On in vivo myocardial perfusion data, TOUCAN achieved competitive reconstruction errors with substantially lower wall-clock time compared to other online CP-based methods like OLSTEC and TeCPSGD.
- Convergence: The authors provide theoretical guarantees of local expected linear convergence, ensuring the algorithm's reliability when initialized near the true subspace.
Conclusion
TOUCAN offers a robust solution for online tensor completion, particularly for signals characterized by temporal shifts and scaling. By combining the t-SVD framework with Grassmannian optimization, it achieves the efficiency required for high-rate streaming applications. Future work may explore automated rank selection and the use of learned orthogonal transforms to further enhance performance across diverse data orientations.
Summary updated