Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery

Abstract

We consider the problem of recovering a low-multilinear-rank tensor from a small amount of linear measurements. We show that the Riemannian gradient algorithm initialized by one step of iterative hard thresholding can reconstruct an order-$d$ tensor of size $n\times \dots \times n$ and multilinear rank $(r,\dots ,r)$ with high probability from only $O(n{r}^2+r^{d+1})$ measurements, assuming $d$ is a constant. This sampling complexity is optimal in $n$, compared to existing results whose sampling complexities are all unnecessarily large in $n$. The analysis relies on the tensor restricted isometry property (TRIP) and the geometry of the manifold of all tensors with a fixed multilinear rank. High computational efficiency of our algorithm is also achieved by doing higher order singular value decomposition on intermediate small tensors of size only $2r\times \dots \times 2r$ rather than on tensors of size $n\times \dots \times n$ as usual.

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Quantum state tomography via compressed sensing
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Global Optimality in Low-rank Matrix Optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice

Cited by in corpus (3)

• Tensor train completion: local recovery guarantees via Riemannian optimization
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion