# Exact tensor completion using t-SVD

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2015.

## Built on by (most cited first, 30 of 70)

- [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)
- [Low-Rank Hankel Tensor Completion for Traffic Speed Estimation](https://mlsanity.com/paper/2105.11335/) (2021)
- [Self-Supervised Nonlinear Transform-Based Tensor Nuclear Norm for Multi-Dimensional Image Recovery](https://mlsanity.com/paper/2105.14320/) (2021)
- [CausalSim: A Causal Framework for Unbiased Trace-Driven Simulation](https://mlsanity.com/paper/2201.01811/) (2022)
- [Effective Tensor Completion via Element-wise Weighted Low-rank Tensor Train with Overlapping Ket Augmentation](https://mlsanity.com/paper/2109.05736/) (2021)
- [Tensor Recovery Based on A Novel Non-convex Function Minimax Logarithmic Concave Penalty Function](https://mlsanity.com/paper/2206.13506/) (2022)
- [Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation](https://mlsanity.com/paper/2305.11495/) (2023)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [OTLRM: Orthogonal Learning-based Low-Rank Metric for Multi-Dimensional Inverse Problems](https://mlsanity.com/paper/2412.11165/) (2024)
- [T2LR-Net: An unrolling network learning transformed tensor low-rank prior for dynamic MR image reconstruction](https://mlsanity.com/paper/2209.03832/) (2022)
- [Image Denoising Using Green Channel Prior](https://mlsanity.com/paper/2408.05923/) (2024)
- [Coarse to Fine Two-Stage Approach to Robust Tensor Completion of Visual Data](https://mlsanity.com/paper/2106.10422/) (2021)
- [Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizers](https://mlsanity.com/paper/2310.06233/) (2023)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [Patch Tracking-based Streaming Tensor Ring Completion for Visual Data Recovery](https://mlsanity.com/paper/2105.14620/) (2021)
- [Multi-Tensor Network Representation for High-Order Tensor Completion](https://mlsanity.com/paper/2109.04022/) (2021)
- [Spatiotemporal Regularized Tucker Decomposition Approach for Traffic Data Imputation](https://mlsanity.com/paper/2305.06563/) (2023)
- [Causal Imputation for Counterfactual SCMs: Bridging Graphs and Latent Factor Models](https://mlsanity.com/paper/2402.14777/) (2024)
- [Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA](https://mlsanity.com/paper/2501.04565/) (2025)
- [Guaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory](https://mlsanity.com/paper/2501.15388/) (2025)
- [Two New Low Rank Tensor Completion Methods Based on Sum Nuclear Norm](https://mlsanity.com/paper/2108.03002/) (2021)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)
- [Approximation of Images via Generalized Higher Order Singular Value Decomposition over Finite-dimensional Commutative Semisimple Algebra](https://mlsanity.com/paper/2202.00450/) (2022)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [High-Order Multilinear Discriminant Analysis via Order-textitn Tensor Eigendecomposition](https://mlsanity.com/paper/2205.09191/) (2022)
- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [Non-convex approaches for low-rank tensor completion under tubal sampling](https://mlsanity.com/paper/2303.12721/) (2023)
- [Nonnegative Low-Rank Tensor Completion via Dual Formulation with Applications to Image and Video Completion](https://mlsanity.com/paper/2305.07976/) (2023)
- [Image Reconstruction using Superpixel Clustering and Tensor Completion](https://mlsanity.com/paper/2305.09564/) (2023)

## Abstract (arXiv)

In this paper we focus on the problem of completion of multidimensional arrays (also referred to as tensors) from limited sampling. Our approach is based on a recently proposed tensor-Singular Value Decomposition (t-SVD) [1]. Using this factorization one can derive notion of tensor rank, referred to as the tensor tubal rank, which has optimality properties similar to that of matrix rank derived from SVD. As shown in [2] some multidimensional data, such as panning video sequences exhibit low tensor tubal rank and we look at the problem of completing such data under random sampling of the data cube. We show that by solving a convex optimization problem, which minimizes the tensor nuclear norm obtained as the convex relaxation of tensor tubal rank, one can guarantee recovery with overwhelming probability as long as samples in proportion to the degrees of freedom in t-SVD are observed. In this sense our results are order-wise optimal. The conditions under which this result holds are very similar to the incoherency conditions for the matrix completion, albeit we define incoherency under the algebraic set-up of t-SVD. We show the performance of the algorithm on some real data sets and compare it with other existing approaches based on tensor flattening and Tucker decomposition.