Abstract
We consider the problem of decomposing a higher-order tensor with binary entries. Such data problems arise frequently in applications such as neuroimaging, recommendation systems, topic modeling, and sensor network localization. We propose a multilinear Bernoulli model, develop a rank-constrained likelihood-based estimation method, and obtain theoretical accuracy guarantees. In contrast to continuous-valued problems, the binary tensor problem exhibits an interesting phase transition phenomenon according to the signal-to-noise ratio. The error bound for the parameter tensor estimation is established, and we show that the obtained rate is minimax optimal under the considered model. Furthermore, we develop an alternating optimization algorithm with convergence guarantees. The efficacy of our approach is demonstrated through both simulations and analyses of multiple data sets on the tasks of tensor completion and clustering.
Introduction
In modern data science, complex multi-dimensional relationships are frequently represented as tensors—higher-order arrays that generalize matrices. While classical tensor decomposition methods typically assume data is continuous and follows a Gaussian distribution, real-world observations are often binary. Examples include user-click data in recommendation systems, presence or absence of connectivity in brain regions, and political interactions between nations.
Standard decomposition techniques, such as CANDECOMP/PARAFAC (CP) or Tucker decomposition, are ill-suited for binary data. These methods often predict values outside the valid $[0, 1]$ range and are highly sensitive to how data is encoded (e.g., whether a relationship is coded as 0 or 1). Furthermore, binary data is inherently "information-poor," providing only a single bit per entry. This paper addresses the fundamental statistical and computational challenges of recovering high-dimensional structures from these discrete observations.
The Multilinear Bernoulli Model
The authors introduce a multilinear Bernoulli model to bridge the gap between discrete observations and low-rank structural recovery. They assume an underlying "parameter tensor" $\Theta$ exists, which follows a low-rank CP structure. The observed binary tensor $\mathcal{Y}$ is generated such that each entry $y_{i_1...i_K}$ is a Bernoulli trial with a success probability determined by a link function $f(\theta_{i_1...i_K})$, such as the logistic or probit function.
To estimate $\Theta$, the researchers employ a rank-constrained Maximum Likelihood Estimation (MLE) approach. This probabilistic framework ensures that the estimated probabilities remain within the valid $[0, 1]$ interval and provides invariance to entry flipping ($0 \leftrightarrow 1$), as reversing the coding simply changes the sign of the parameter $\Theta$ without altering the underlying structural decomposition.
Theoretical Insights: The "Noise Helps" Phenomenon
One of the most striking findings of this research is the discovery of a "phase transition" related to the signal-to-noise ratio (SNR). In continuous-valued problems, higher SNR (lower noise) generally leads to better recovery. However, in the binary setting, the authors uncover a phenomenon known as dithering.
In a high-SNR regime with very low noise, binary observations can become "frozen" into a deterministic sign pattern. When this happens, many different underlying signals could produce the exact same binary tensor, making it impossible to distinguish between them. Paradoxically, adding a small amount of stochastic noise "dithers" the signal, allowing the MLE to better resolve the underlying probability levels and improve recovery accuracy.
Furthermore, the paper provides a rigorous theoretical foundation for higher-order tensors. It proves that the estimation error decreases as the order of the tensor ($K$) increases, with the error rate scaling as $d^{-(K-1)/2}$. This demonstrates that the multi-way structure provides a significant "sample size" boost compared to simple matrix decomposition ($K=2$). The authors establish a minimax lower bound, proving that their proposed method achieves the fastest possible convergence rate under the Bernoulli model.
Computational Framework
Because the rank-constrained MLE involves a non-convex optimization problem, the authors developed an Alternating Optimization algorithm. The algorithm decomposes the problem into mode-wise updates. Each step involves solving a series of independent Generalized Linear Models (GLMs), which makes the process computationally efficient and highly parallelizable. The algorithm is shown to have locally linear convergence, meaning it approaches a local maximum at an exponential rate.
Empirical Results
The efficacy of the multilinear Bernoulli model was validated across several diverse real-world datasets:
- Enron Email Dataset: In a tensor completion task involving sender, receiver, and time, the binary model achieved an AUC of 94.3%, significantly outperforming continuous CP decomposition, which struggled with the dataset's extreme sparsity.
- Nations Dataset: The model successfully clustered countries into meaningful geopolitical blocs (Communist, Western, and Neutral) based on latent factors derived from political actions.
- Human Connectome Project (HCP): In neuroimaging analysis, the method identified key brain structures such as the corpus callosum and localized specific association tracts within cerebral hemispheres, demonstrating its utility in biological discovery.
- Kinship Dataset: The model effectively captured social relations within an Australian tribe, represented as a $104 \times 104 \times 26$ tensor.
Conclusion and Future Work
This research provides a robust statistical framework for learning from binary multiway data. By establishing minimax optimality and identifying the dithering phenomenon, the authors have clarified the fundamental limits of discrete tensor recovery.
Future research directions include a full theoretical investigation into rank selection consistency (currently handled via the Bayesian Information Criterion) and exploring the global landscape of the non-convex objective function. Additionally, the framework could be generalized to other exponential family distributions, such as Poisson for count-valued tensors or multinomial for categorical data.
Summary updated