# On Tensor Completion via Nuclear Norm Minimization

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2014.

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

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Deep Spectrum Cartography: Completing Radio Map Tensors Using Learned Neural Models](https://mlsanity.com/paper/2105.00177/) (2021)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Noisy Tensor Completion via Low-rank Tensor Ring](https://mlsanity.com/paper/2203.08857/) (2022)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Deep Unfolded Tensor Robust PCA with Self-supervised Learning](https://mlsanity.com/paper/2212.11346/) (2022)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Non-Convex Tensor Low-Rank Approximation for Infrared Small Target Detection](https://mlsanity.com/paper/2105.14974/) (2021)
- [Nonnegative Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2111.04580/) (2021)
- [Multi-version Tensor Completion for Time-delayed Spatio-temporal Data](https://mlsanity.com/paper/2105.05326/) (2021)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks](https://mlsanity.com/paper/2502.02766/) (2025)
- [Convergence bounds for nonlinear least squares and applications to tensor recovery](https://mlsanity.com/paper/2108.05237/) (2021)
- [A high-order tensor completion algorithm based on Fully-Connected Tensor Network weighted optimization](https://mlsanity.com/paper/2204.01732/) (2022)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Convergence bounds for local least squares approximation](https://mlsanity.com/paper/2208.10954/) (2022)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gaps](https://mlsanity.com/paper/2410.11225/) (2024)
- [Nonparametric Trace Regression in High Dimensions via Sign Series Representation](https://mlsanity.com/paper/2105.01783/) (2021)
- ["Sparse + Low-Rank'' Tensor Completion Approach for Recovering Images and Videos](https://mlsanity.com/paper/2110.09298/) (2021)
- [Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2402.05141/) (2024)
- [Personalized Federated Heat-Kernel Enhanced Multi-View Clustering via Advanced Tensor Decomposition Techniques](https://mlsanity.com/paper/2509.16101/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensing](https://mlsanity.com/paper/2601.13522/) (2026)

## Abstract (arXiv)

Many problems can be formulated as recovering a low-rank tensor. Although an increasingly common task, tensor recovery remains a challenging problem because of the delicacy associated with the decomposition of higher order tensors. To overcome these difficulties, existing approaches often proceed by unfolding tensors into matrices and then apply techniques for matrix completion. We show here that such matricization fails to exploit the tensor structure and may lead to suboptimal procedure. More specifically, we investigate a convex optimization approach to tensor completion by directly minimizing a tensor nuclear norm and prove that this leads to an improved sample size requirement. To establish our results, we develop a series of algebraic and probabilistic techniques such as characterization of subdifferetial for tensor nuclear norm and concentration inequalities for tensor martingales, which may be of independent interests and could be useful in other tensor related problems.