Learning Tensors From Partial Binary Measurements

We generalize the 1-bit matrix completion problem to higher order tensors. Consider a rank- $r$ order- $d$ tensor $T$ in $\mathbb {R}^{N} \times \cdots \times \mathbb {R}^{N}$ with bounded entries. We show that when $r=O(1)$ , such a tensor can be estimated efficiently from only $m=O_r(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$ . By using a certain atomic M-norm as a convex proxy for rank, we allow for approximately low-rank tensors and give error bounds based on the M-norm of the tensor. We prove that the theoretical bounds are optimal both in the M-norm bound and the size $N$ . Moreover, we show the advantage of directly using the low-rank tensor structure, rather than matricization, both theoretically and numerically. Specifically, we show how the 1-bit measurement model can be used for context-aware recommender systems.