mlsanityData to 7 Oct 2026

On Tensor Completion via Nuclear Norm Minimization

arXiv 1405.1773 ↗First posted 7 May 2014stat.ML cs.IT cs.NAcited by 32

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 9; 2023: 2; 2024: 3; 2025: 3; 2026: 3.

32 papers.

Sort:

  1. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  2. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  3. 2021Deep Spectrum Cartography: Completing Radio Map Tensors Using Learned Neural Modelscited by 14
  4. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  5. 2022Noisy Tensor Completion via Low-rank Tensor Ringcited by 13
  6. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  7. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  8. 2022Deep Unfolded Tensor Robust PCA with Self-supervised Learningcited by 7
  9. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
  10. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  11. 2021Beyond the Signs: Nonparametric Tensor Completion via Sign Seriescited by 4
  12. 2021Non-Convex Tensor Low-Rank Approximation for Infrared Small Target Detectioncited by 4
20 more
  1. 2021Nonnegative Tensor Completion via Integer Optimizationcited by 4
  2. 2021Multi-version Tensor Completion for Time-delayed Spatio-temporal Datacited by 3
  3. 2022Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeroscited by 3
  4. 2025Theoretical Guarantees for Low-Rank Compression of Deep Neural Networkscited by 3
  5. 2021Convergence bounds for nonlinear least squares and applications to tensor recoverycited by 2
  6. 2022A high-order tensor completion algorithm based on Fully-Connected Tensor Network weighted optimizationcited by 2
  7. 2022Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularizationcited by 1
  8. 2022Convergence bounds for local least squares approximationcited by 1
  9. 2022Accelerated Nonnegative Tensor Completion via Integer Programmingcited by 1
  10. 2023Under-Counted Tensor Completion with Neural Incorporation of Attributescited by 1
  11. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  12. 2021Nonparametric Trace Regression in High Dimensions via Sign Series Representationcited by 0
  13. 2021"Sparse + Low-Rank'' Tensor Completion Approach for Recovering Images and Videoscited by 0
  14. 2024Tensor Completion via Integer Optimizationcited by 0
  15. 2024Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gapscited by 0
  16. 2025Personalized Federated Heat-Kernel Enhanced Multi-View Clustering via Advanced Tensor Decomposition Techniquescited by 0
  17. 2025An Interdisciplinary and Cross-Task Review on Missing Data Imputationcited by 0
  18. 2026StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensingcited by 0
  19. 2026Tensor Completion using Subspace Informationcited by 0
  20. 2026Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descentcited by 0