Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion

2016/06/10 by Ming Yuan, Cun‐Hui Zhang, Yuan, Ming +1 · 3 citations
Engineering · Mathematics · #Elasticity and Material Modeling #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1606.03504

openalex publication_date 2016/06/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a kth order tensor of rank r and dimension d×⋯× d can be recovered perfectly from as few as O((r^(k-1)/2d^3/2+r^k-1d)(log(d))²) uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: They not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors.

Citations

• Tensor Decompositions and Applications
• Most Tensor Problems Are NP-Hard
• A Simpler Approach to Matrix Completion

Cited by

• Causal Inference on Sequential Treatments via Tensor Completion
• Solving exact and noisy rank-one tensor completion with semidefinite programming
• Near-Efficient and Non-Asymptotic Multiway Inference

Related

• Scaled Nuclear Norm Minimization for Low-Rank Tensor Completion
• On Tensor Completion via Nuclear Norm Minimization
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery