Cross: Efficient Low-rank Tensor Completion
arXiv:1611.01129
Abstract
The completion of tensors, or high-order arrays, attracts significant attention in recent research. Current literature on tensor completion primarily focuses on recovery from a set of uniformly randomly measured entries, and the required number of measurements to achieve recovery is not guaranteed to be optimal. In addition, the implementation of some previous methods is NP-hard. In this article, we propose a framework for low-rank tensor completion via a novel tensor measurement scheme we name Cross. The proposed procedure is efficient and easy to implement. In particular, we show that a third order tensor of Tucker rank- in -by--by- dimensional space can be recovered from as few as noiseless measurements, which matches the sample complexity lower-bound. In the case of noisy measurements, we also develop a theoretical upper bound and the matching minimax lower bound for recovery error over certain classes of low-rank tensors for the proposed procedure. The results can be further extended to fourth or higher-order tensors. Simulation studies show that the method performs well under a variety of settings. Finally, the procedure is illustrated through a real dataset in neuroimaging.
References in corpus (18)
- A Simpler Approach to Matrix Completion
- Tensor Regression with Applications in Neuroimaging Data Analysis
- Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
- Estimation of high-dimensional low-rank matrices
- Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
- Matrix Completion from a Few Entries
- Matrix Completion via Max-Norm Constrained Optimization
- STORE: Sparse Tensor Response Regression and Neuroimaging Analysis
- Poisson Matrix Recovery and Completion
- Note on sampling without replacing from a finite collection of matrices
- A New Sampling Technique for Tensors
- Tucker Tensor Regression and Neuroimaging Analysis
- Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
- Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
- Semi-supervised Inference: General Theory and Estimation of Means
- On Tensor Completion via Nuclear Norm Minimization
- Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
- Bayesian Tensor Regression