TSP Volume 67 Issue 1

We generalize the 1-bit matrix completion problem to higher order tensors. Consider a rank- r order- d tensorT in RN ×⋯×RN  with bounded entries. We show that when r=O(1) , such a tensor can be estimated efficiently from only m=Or (Nd)  binary measurements. This shows that the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is roughly the same as recovering it from unquantized measurements—a result that had been known only in the matrix case, i.e., when d=2.