Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Abstract

Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recovering a $K$-way tensor of length $n$ and Tucker rank $r$ from Gaussian measurements requires $\Omega (r{n}^{K-1})$ observations. In contrast, a certain (intractable) nonconvex formulation needs only $O(r^K+nrK)$ observations. We introduce a very simple, new convex relaxation, which partially bridges this gap. Our new formulation succeeds with $O(r^{\lfloor K/2\rfloor }{n}^{\lceil K/2\rceil })$ observations. While these results pertain to Gaussian measurements, simulations strongly suggest that the new norm also outperforms the sum of nuclear norms for tensor completion from a random subset of entries. Our lower bound for the sum-of-nuclear-norms model follows from a new result on recovering signals with multiple sparse structures (e.g. sparse, low rank), which perhaps surprisingly demonstrates the significant suboptimality of the commonly used recovery approach via minimizing the sum of individual sparsity inducing norms (e.g. $l_1$, nuclear norm). Our new formulation for low-rank tensor recovery however opens the possibility in reducing the sample complexity by exploiting several structures jointly.

Slight modifications are made in this second version (mainly, Lemma 5)

References in corpus (3)

• Robust Low-rank Tensor Recovery: Models and Algorithms
• Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
• Parallel matrix factorization for low-rank tensor completion

Cited by in corpus (60)

• Quantum machine learning: a classical perspective
• Parallel matrix factorization for low-rank tensor completion
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Provable Tensor Factorization with Missing Data
• Spectrum Cartography via Coupled Block-Term Tensor Decomposition
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Provable Tensor Ring Completion
• Efficient Tensor Robust PCA under Hybrid Model of Tucker and Tensor Train
• Learning tensors from partial binary measurements
• Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm
• Tensor Regression Using Low-rank and Sparse Tucker Decompositions
• A New Sampling Technique for Tensors
• Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements
• Efficient tensor completion: Low-rank tensor train
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Tensor Completion Algorithms in Big Data Analytics
• Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
• Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
• Exact tensor completion using t-SVD
• Tensor train completion: local recovery guarantees via Riemannian optimization
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• High-Dimensional Low-Rank Tensor Autoregressive Time Series Modeling
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Robust Tensor Completion Using Transformed Tensor SVD
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detection
• Deterministic tensor completion with hypergraph expanders
• Low-rank Tensor Grid for Image Completion
• Fast and Accurate Tensor Completion with Total Variation Regularized Tensor Trains
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Exact Recovery of Tensor Robust Principal Component Analysis under Linear Transforms
• Cross: Efficient Low-rank Tensor Completion
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• Low-Rank Hankel Tensor Completion for Traffic Speed Estimation
• Tensor denoising and completion based on ordinal observations
• Bayesian Methods in Tensor Analysis
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• Hierarchical Tensor Ring Completion
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• FasTer: Fast Tensor Completion with Nonconvex Regularization
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• A Super-Resolution Framework for Tensor Decomposition
• Beyond the Signs: Nonparametric Tensor Completion via Sign Series
• Learning Diagonal Gaussian Mixture Models and Incomplete Tensor Decompositions
• HOSVD-Based Algorithm for Weighted Tensor Completion
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Beyond Unfolding: Exact Recovery of Latent Convex Tensor Decomposition under Reshuffling
• Tensor Completion via Tensor Networks with a Tucker Wrapper
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• Optimal low rank tensor recovery
• Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery
• Multi-modal and frequency-weighted tensor nuclear norm for hyperspectral image denoising
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
• Stochastic Iterative Hard Thresholding for Low-Tucker-Rank Tensor Recovery
• Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexity
• Sturm: Sparse Tubal-Regularized Multilinear Regression for fMRI
• Low-M-Rank Tensor Completion and Robust Tensor PCA