Fast and Provable Low-Rank High-Order Tensor Completion via Scaled Gradient Descent

This work studies the low-rank high-order tensor completion (HOTC) problem, which aims to exactly recover a low-rank order-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d \geq 4$</tex-math></inline-formula>) tensor from partially observed entries. Leveraging the low-rank structure under the tensor Singular Value Decomposition (t-SVD) decomposition, instead of relying on the computationally expensive tensor nuclear norm (TNN), we propose an efficient algorithm, termed the HOTC-SGD, that directly estimates the high-order tensor factors—starting from a spectral initialization—via scaled gradient descent (SGD). Theoretically, we rigorously establish the recovery guarantee of HOTC-SGD under mild assumptions, demonstrating that it achieves linear convergence to the true low-rank tensor at a constant rate that is independent of the condition number. Numerical experiments on both synthetic and real-world data verify our results and demonstrate the superiority of our method.