Learning tensors from partial binary measurements

In this paper we generalize the 1-bit matrix completion problem to higher order tensors. We prove that when r=O(1) a bounded rank-r, order-d tensor T in ℝN × ℝN × cdots × ℝN can be estimated efficiently by only m=O(Nd) binary measurements by regularizing its max-qnorm and M-norm as surrogates for its rank. We prove that similar to the matrix case, i.e., when d=2, the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is the same as recovering it from unquantized measurements. Moreover, we show the advantage of using 1-bit tensor completion over matricization both theoretically and numerically. Specifically, we show how the 1-bit measurement model can be used for context-aware recommender systems.