Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality

Tensors of order 3 or greater, known as higher-order tensors, have recently attracted increased attention in many fields. Methods built on tensors provide powerful tools to capture complex structures in data that lower-order methods may fail to exploit. However, extending familiar matrix concepts to higher-order tensors is not straightforward, and indeed it has been shown that most computational problems for tensors are NP-hard. In this talk, I will present some statistical results on binary tensor decomposition. Instead of observing a real-valued higher-order tensor, we observe a binary tensor in which each tensor entry is quantized into a 0-1 measurement. We propose a constrained MLE and give the performance bound under a generalized multilinear model. The obtained rate is optimal in a minimax sense over a class of low-rank tensors. We demonstrate the power of our method on the tasks of tensor completion and clustering, with improved performance over state-of-the-art

https://vimeo.com/298157003