Learning tensors from partial binary measurements

Abstract

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.

arXiv comment26 pages

References in corpus (9)

• Matrix estimation by Universal Singular Value Thresholding
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Fast ALS-based tensor factorization for context-aware recommendation from implicit feedback
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Matrix Completion via Max-Norm Constrained Optimization
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• Optimistic Rates for Learning with a Smooth Loss
• A New Low-Rank Tensor Model for Video Completion
• Spectral algorithms for tensor completion

Cited by in corpus (9)

• Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
• Tensor Recovery from Noisy and Multi-Level Quantized Measurements
• Tensor denoising and completion based on ordinal observations
• Beyond the Signs: Nonparametric Tensor Completion via Sign Series
• Downlink MIMO Channel Estimation from Bits: Recoverability and Algorithm
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros
• A Probit Tensor Factorization Model For Relational Learning