Stochastic Variance Reduced Gradient for Tensor Recovery

Abstract

Low-rank tensor recovery is pivotal in numerous applications, including image and video processing, machine learning, and data analysis. A common approach to this problem involves convex relaxation, where the tensor rank function is minimized by using the tensor nuclear norm. However, this method can be significantly suboptimal. In addition, the stochastic variance reduced gradient (SVRG) method, a variant of stochastic gradient descent, has been applied to matrix recovery problems. 

In this paper, we extend the SVRG method to the tensor framework, introducing the tensor stochastic variance reduced gradient (TSVRG) algorithm for tensor recovery with CP or Tucker rank constraints. TSVRG is designed to achieve higher precision solutions by escaping local minima and identifying superior global optima. Moreover, TSVRG offers reduced computational complexity compared to traditional gradient descent methods. We establish a convergence theorem for TSVRG under the tensor restricted isometry condition when the measurements are linear. Finally, we present numerical results using both synthetic and real data, demonstrating the competitive performance of TSVRG compared to other advanced algorithms.