# Learning tensors from partial binary measurements

arXiv: https://arxiv.org/abs/1804.00108 · HTML: https://mlsanity.com/paper/1804.00108/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2018.

## Built on by (most cited first, 13 of 13)

- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Quantized Radio Map Estimation Using Tensor and Deep Generative Models](https://mlsanity.com/paper/2303.01770/) (2023)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion](https://mlsanity.com/paper/2304.13940/) (2023)
- [Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Model](https://mlsanity.com/paper/2405.11377/) (2024)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [A Probit Tensor Factorization Model For Relational Learning](https://mlsanity.com/paper/2111.03943/) (2021)
- [Downlink MIMO Channel Estimation from Bits: Recoverability and Algorithm](https://mlsanity.com/paper/2411.16043/) (2024)
- [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025)
- [Near-Efficient and Non-Asymptotic Multiway Inference](https://mlsanity.com/paper/2511.05368/) (2025)
- [Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularization](https://mlsanity.com/paper/2606.30958/) (2026)

## Abstract (arXiv)

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.