Grassmannian Optimization for Online Tensor Completion and Tracking With the t-SVD

Kyle Gilman, Davoud Ataee Tarzanagh, Laura Balzano

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.

Decomposition of a tensor into a sum of t-products between lateral slices and tubes.

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

Abstract

We propose a new fast streaming algorithm for the tensor completion problem of imputing missing entries of a low-tubal-rank tensor using the tensor singular value decomposition (t-SVD) algebraic framework. We show the t-SVD is a specialization of the well-studied block-term decomposition for third-order tensors, and we present an algorithm under this model that can track changing free submodules from incomplete streaming 2-D data. The proposed algorithm uses principles from incremental gradient descent on the Grassmann manifold of subspaces to solve the tensor completion problem with linear complexity and constant memory in the number of time samples. We provide a local expected linear convergence result for our algorithm. Our empirical results are competitive in accuracy but much faster in compute time than state-of-the-art tensor completion algorithms on real applications to recover temporal chemo-sensing and MRI data under limited sampling.
BibTeX
@article{gilman2022grassmannian,
  author = {Kyle Gilman and Davoud Ataee Tarzanagh and Laura Balzano},
  title = {{Grassmannian Optimization for Online Tensor Completion and Tracking With the t-SVD}},
  journal = {IEEE Trans. Signal Process.},
  year = {2022},
  doi = {10.1109/tsp.2022.3164837},
}
Figure