# Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2018.

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

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Pan-denoising: Guided Hyperspectral Image Denoising via Weighted Represent Coefficient Total Variation](https://mlsanity.com/paper/2407.06064/) (2024)
- [Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizers](https://mlsanity.com/paper/2310.06233/) (2023)
- [Handling The Non-Smooth Challenge in Tensor SVD: A Multi-Objective Tensor Recovery Framework](https://mlsanity.com/paper/2311.13958/) (2023)
- [A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation](https://mlsanity.com/paper/2305.11458/) (2023)
- [Haar Nuclear Norms with Applications to Remote Sensing Imagery Restoration](https://mlsanity.com/paper/2407.08509/) (2024)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- ["Sparse + Low-Rank'' Tensor Completion Approach for Recovering Images and Videos](https://mlsanity.com/paper/2110.09298/) (2021)
- [Robust Data Clustering with Outliers via Transformed Tensor Low-Rank Representation](https://mlsanity.com/paper/2307.09055/) (2023)
- [Color Image Recovery Using Generalized Matrix Completion over Higher-Order Finite Dimensional Algebra](https://mlsanity.com/paper/2308.02621/) (2023)
- [Neural Gradient Regularizer](https://mlsanity.com/paper/2308.16612/) (2023)
- [Online multidimensional dictionary learning](https://mlsanity.com/paper/2503.09337/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [A Spatio-Temporal Online Robust Tensor Recovery Approach for Streaming Traffic Data Imputation](https://mlsanity.com/paper/2511.01267/) (2025)
- [Low-Rank Tensor Completion Based on Fractional Regularization with Ky Fan p-k Norm](https://mlsanity.com/paper/2606.19046/) (2026)

## Abstract (arXiv)

The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011]. It plays a similar role as the matrix nuclear norm which is the convex surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA [Lu et al., 2018a] is an elegant extension of Robust PCA with a similar tight recovery bound, it is natural to solve other low rank tensor recovery problems extended from the matrix cases. However, the extensions and proofs are generally tedious. The general atomic norm provides a unified view of low-complexity structures induced norms, e.g., the ℓ1-norm and nuclear norm. The sharp estimates of the required number of generic measurements for exact recovery based on the atomic norm are known in the literature. In this work, with a careful choice of the atomic set, we prove that TNN is a special atomic norm. Then by computing the Gaussian width of certain cone which is necessary for the sharp estimate, we achieve a simple bound for guaranteed low tubal rank tensor recovery from Gaussian measurements. Specifically, we show that by solving a TNN minimization problem, the underlying tensor of size n1× n2× n3 with tubal rank r can be exactly recovered when the given number of Gaussian measurements is O(r(n1+n2-r)n3). It is order optimal when comparing with the degrees of freedom r(n1+n2-r)n3. Beyond the Gaussian mapping, we also give the recovery guarantee of tensor completion based on the uniform random mapping by TNN minimization. Numerical experiments verify our theoretical results.