Estimation of low-rank tensors via convex optimization

Abstract

In this paper, we propose three approaches for the estimation of the Tucker decomposition of multi-way arrays (tensors) from partial observations. All approaches are formulated as convex minimization problems. Therefore, the minimum is guaranteed to be unique. The proposed approaches can automatically estimate the number of factors (rank) through the optimization. Thus, there is no need to specify the rank beforehand. The key technique we employ is the trace norm regularization, which is a popular approach for the estimation of low-rank matrices. In addition, we propose a simple heuristic to improve the interpretability of the obtained factorization. The advantages and disadvantages of three proposed approaches are demonstrated through numerical experiments on both synthetic and real world datasets. We show that the proposed convex optimization based approaches are more accurate in predictive performance, faster, and more reliable in recovering a known multilinear structure than conventional approaches.

19 pages, 7 figures

References in corpus (1)

• A Singular Value Thresholding Algorithm for Matrix Completion

Cited by in corpus (45)

• Robust Low-rank Tensor Recovery: Models and Algorithms
• Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Rank regularization and Bayesian inference for tensor completion and extrapolation
• Low-rank tensor completion: a Riemannian manifold preconditioning approach
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Online Low-Rank Tensor Subspace Tracking from Incomplete Data by CP Decomposition using Recursive Least Squares
• Canonical Tensor Decomposition for Knowledge Base Completion
• Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm
• Recovery of Future Data via Convolution Nuclear Norm Minimization
• Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization
• Tensor Completion Algorithms in Big Data Analytics
• On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Fast Position-Aided MIMO Beam Training via Noisy Tensor Completion
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Exact Tensor Completion from Sparsely Corrupted Observations via Convex Optimization
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• Tensor train completion: local recovery guarantees via Riemannian optimization
• On Tensor Completion via Nuclear Norm Minimization
• Riemannian preconditioning for tensor completion
• Spectral algorithms for tensor completion
• Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations
• Mixture-based Multiple Imputation Model for Clinical Data with a Temporal Dimension
• Higher order Matching Pursuit for Low Rank Tensor Learning
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Convex Factorization Machine for Regression
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Adaptive Higher-order Spectral Estimators
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Guarantees of Augmented Trace Norm Models in Tensor Recovery
• Bayesian Methods in Tensor Analysis
• Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterion
• Riemannian Tensor Completion with Side Information
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Beyond Unfolding: Exact Recovery of Latent Convex Tensor Decomposition under Reshuffling
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• Convolutional Imputation of Matrix Networks
• Theoretical and Experimental Analyses of Tensor-Based Regression and Classification
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery
• Low-M-Rank Tensor Completion and Robust Tensor PCA
• An Efficient Tensor Completion Method via New Latent Nuclear Norm