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.

arXiv comment19 pages, 7 figures

References in corpus (3)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Scalable Tensor Factorizations for Incomplete Data
• A Singular Value Thresholding Algorithm for Matrix Completion

Cited by in corpus (46)

• 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
• Super-Linear Convergence of Dual Augmented-Lagrangian Algorithm for Sparsity Regularized Estimation
• 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
• On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Tensor Completion Algorithms in Big Data Analytics
• 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
• Riemannian preconditioning for tensor completion
• On Tensor Completion via Nuclear Norm Minimization
• Spectral algorithms for tensor completion
• Mixture-based Multiple Imputation Model for Clinical Data with a Temporal Dimension
• Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations
• Higher order Matching Pursuit for Low Rank Tensor Learning
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Convex Factorization Machine for Regression
• Adaptive Higher-order Spectral Estimators
• Bayesian Methods in Tensor Analysis
• Guarantees of Augmented Trace Norm Models in Tensor Recovery
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterion
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Riemannian Tensor Completion with Side Information
• Beyond Unfolding: Exact Recovery of Latent Convex Tensor Decomposition under Reshuffling
• Convolutional Imputation of Matrix Networks
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• 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
• 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