# Low-tubal-rank Tensor Completion using Alternating Minimization

arXiv: https://arxiv.org/abs/1610.01690 · HTML: https://mlsanity.com/paper/1610.01690/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2016.

## Built on by (most cited first, 18 of 18)

- [Guaranteed Tensor Recovery Fused Low-rankness and Smoothness](https://mlsanity.com/paper/2302.02155/) (2023)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks](https://mlsanity.com/paper/2303.00196/) (2023)
- [Coarse to Fine Two-Stage Approach to Robust Tensor Completion of Visual Data](https://mlsanity.com/paper/2106.10422/) (2021)
- [H2TF for Hyperspectral Image Denoising: Where Hierarchical Nonlinear Transform Meets Hierarchical Matrix Factorization](https://mlsanity.com/paper/2304.11141/) (2023)
- [Patch Tracking-based Streaming Tensor Ring Completion for Visual Data Recovery](https://mlsanity.com/paper/2105.14620/) (2021)
- [Non-convex approaches for low-rank tensor completion under tubal sampling](https://mlsanity.com/paper/2303.12721/) (2023)
- [A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation](https://mlsanity.com/paper/2305.11458/) (2023)
- [Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion](https://mlsanity.com/paper/2505.11261/) (2025)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- [Convolutional Graph-Tensor Net for Graph Data Completion](https://mlsanity.com/paper/2103.04485/) (2021)
- [Tensor Completion via Leverage Sampling and Tensor QR Decomposition for Network Latency Estimation](https://mlsanity.com/paper/2307.06848/) (2023)
- [Tensor Completion Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees](https://mlsanity.com/paper/2310.02543/) (2023)
- [Under-Sampled High-Dimensional Data Recovery via Symbiotic Multi-Prior Tensor Reconstruction](https://mlsanity.com/paper/2504.05992/) (2025)
- [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025)
- [3DeepRep: 3D Deep Low-rank Tensor Representation for Hyperspectral Image Inpainting](https://mlsanity.com/paper/2506.16735/) (2025)
- [Normalized Iterative Hard Thresholding for Tensor Recovery](https://mlsanity.com/paper/2507.04228/) (2025)
- [Renormalization Group Guided Tensor Network Structure Search](https://mlsanity.com/paper/2512.24663/) (2025)

## Abstract (arXiv)

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called em Tubal-Alt-Min, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-Alt-Min alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Second, the theoretical performance guarantee is challenging since Tubal-Alt-Min is iterative and nonconvex in nature. We prove that 1) Tubal-Alt-Min guarantees exponential convergence to the global optima, and 2) for an n × n × k tensor with tubal-rank r ll n, the required sampling complexity is O(nr2k log3 n) and the computational complexity is O(n2rk2 log2 n). Third, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization (TNN-ADMM), Tubal-Alt-Min improves the recovery error dramatically (by orders of magnitude). It is estimated that Tubal-Alt-Min converges at an exponential rate 10-0.4423 Iter where Iter denotes the number of iterations, which is much faster than TNN-ADMM's 10-0.0332 Iter, and the running time can be accelerated by more than 5 times for a 200 × 200 × 20 tensor.