SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Inference for High-dimensional Tensor Data

Anru Zhang,

Date and Time: Sep 13, 2017 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

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.