A New Convex Relaxation for Tensor Completion

2013/07/17 by Bernardino Romera‐Paredes, Romera-Paredes, Bernardino, Massimiliano Pontil +1 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1307.4653

openalex publication_date 2013/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable.

Cited by

• Solving exact and noisy rank-one tensor completion with semidefinite programming
• Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm

Related

• Trace Norm Regularized Tensor Classification and Its Online Learning Approaches
• Near-optimal sample complexity for convex tensor completion
• Estimation of low-rank tensors via convex optimization
• Revisiting Trace Norm Minimization for Tensor Tucker Completion: A Direct Multilinear Rank Learning Approach
• Theoretical and Experimental Analyses of Tensor-Based Regression and Classification