Provable Tensor Ring Completion

Abstract

Tensor completion recovers a multi-dimensional array from a limited number of measurements. Using the recently proposed tensor ring (TR) decomposition, in this paper we show that a d-order tensor of dimensional size n and TR rank r can be exactly recovered with high probability by solving a convex optimization program, given n^{d/2} r^2 ln^7(n^{d/2})samples. The proposed TR incoherence condition under which the result holds is similar to the matrix incoherence condition. The experiments on synthetic data verify the recovery guarantee for TR completion. Moreover, the experiments on real-world data show that our method improves the recovery performance compared with the state-of-the-art methods.

References in corpus (18)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Efficient tensor completion for color image and video recovery: Low-rank tensor train
• Image compression and entanglement
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• A General Analysis of the Convergence of ADMM
• Provable Tensor Ring Completion
• On the method of typical bounded differences
• Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model
• Tensor network ranks
• Learning Efficient Tensor Representations with Ring Structure Networks
• Higher-dimension Tensor Completion via Low-rank Tensor Ring Decomposition
• Tensor-Ring Nuclear Norm Minimization and Application for Visual Data Completion
• Rank Minimization on Tensor Ring: A New Paradigm in Scalable Tensor Decomposition and Completion

Cited by in corpus (8)

• Robust Low-Rank Tensor Ring Completion
• Provable Tensor Ring Completion
• Tensor Train Factorization and Completion under Noisy Data with Prior Analysis and Rank Estimation
• Low-rank Tensor Grid for Image Completion
• A Unified Framework for Coupled Tensor Completion
• Hierarchical Tensor Ring Completion
• Hyperspectral Image Denoising with Partially Orthogonal Matrix Vector Tensor Factorization
• Efficient Tensor Contraction via Fast Count Sketch