Fast adaptive tubal-rank-revealing algorithm for t-product based tensor approximation

Abstract

Color images and video sequences can be modeled as 3-way tensors, which admit low tubal-rank approximations via convex surrogate minimization. This optimization problem is efficiently addressed by tensor singular value thresholding (t-SVT). To mitigate the computational burden of tensor singular value decomposition (t-SVD) at each iteration, this paper introduces an adaptive randomized algorithm for tubal-rank revelation of the data tensor. Our method selectively captures the principal information from frontal slices in the Fourier domain using a predefined threshold, obviating the need for a priori tubal-rank and Fourier-domain singular values estimations while providing an explicit tensor approximation. To enable this adaptive strategy, we first prove that the orthogonal basis captured by matrix randomized SVD with preset target rank k guarantees near-optimality for rank-i approximations (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\le i\le k$$\end{document}). Leveraging this key property, we establish theoretical results to guarantee that the proposed algorithm computes low tubal-rank approximations within constants dependent on data dimensions and the Fourier-domain singular value gap from optimal. Empirical evaluations validate its efficacy for image processing and background modeling tasks.