Convex Tensor Decomposition via Structured Schatten Norm Regularization

Abstract

We discuss structured Schatten norms for tensor decomposition that includes two recently proposed norms ("overlapped" and "latent") for convex-optimization-based tensor decomposition, and connect tensor decomposition with wider literature on structured sparsity. Based on the properties of the structured Schatten norms, we mathematically analyze the performance of "latent" approach for tensor decomposition, which was empirically found to perform better than the "overlapped" approach in some settings. We show theoretically that this is indeed the case. In particular, when the unknown true tensor is low-rank in a specific mode, this approach performs as good as knowing the mode with the smallest rank. Along the way, we show a novel duality result for structures Schatten norms, establish the consistency, and discuss the identifiability of this approach. We confirm through numerical simulations that our theoretical prediction can precisely predict the scaling behavior of the mean squared error.

12 pages, 3 figures

References in corpus (2)

• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction

Cited by in corpus (18)

• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Provable Tensor Factorization with Missing Data
• Generalized Higher-Order Tensor Decomposition via Parallel ADMM
• Higher order Matching Pursuit for Low Rank Tensor Learning
• Regularized and Smooth Double Core Tensor Factorization for Heterogeneous Data
• Deep Multi-Task Learning via Generalized Tensor Trace Norm
• Adaptive Higher-order Spectral Estimators
• Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
• Structured Low-Rank Matrix Factorization with Missing and Grossly Corrupted Observations
• FasTer: Fast Tensor Completion with Nonconvex Regularization
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Beyond Unfolding: Exact Recovery of Latent Convex Tensor Decomposition under Reshuffling
• Tensor Q-Rank: New Data Dependent Definition of Tensor Rank
• Theoretical and Experimental Analyses of Tensor-Based Regression and Classification
• Trace-Norm Adversarial Examples
• Learning with Optimal Interpolation Norms
• Experimental Analysis of Legendre Decomposition in Machine Learning
• Efficient Tensor Decomposition with Boolean Factors