  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 $\mathbb{R}^{N} \times \mathbb{R}^{N} \times \cdots \times
\mathbb{R}^{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.
