Inference for High-dimensional Tensor Data

High-dimensional high-order arrays, or tensors, arise in many modern scientific applications including genomics, brain imaging, and social science. In this talk, we consider two specific problems in tensor data analysis: low-rank tensor completion and tensor SVD.

We first 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 the tensors of Tucker low-rank can be recovered from a limited number of 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.

Then we propose a general framework of tensor singular value decomposition, which focuses on the methodology and theory for extracting the hidden low-rank structure from the high-dimensional tensor data. Comprehensive results on both statistical and computational limits for tensor SVD. The problem exhibits three different phases according to the signal-noise-ratio (SNR). In particular, with strong SNR, the fast spectral power iteration method that achieves the minimax optimal rate of convergence in estimation; with weak SNR, the information-theoretical lower bound shows that it is impossible to have consistent estimation in general; with moderate SNR, we show that the non-convex maximum likelihood estimation provides optimal solution, but with NP-hard computational cost; moreover, under the hardness hypothesis of hypergraphic planted clique detection, there are no polynomial-time algorithms performing consistently in general.