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 (10)
- Matrix Completion from a Few Entries
- STORE: Sparse Tensor Response Regression and Neuroimaging Analysis
- Poisson Matrix Recovery and Completion
- 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
- Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
- Bayesian Tensor Regression