Information-Theoretic Limits for the Matrix Tensor Product

Understand

This paper studies a high-dimensional inference problem involving the matrix tensor product of random matrices.

• This problem generalizes a number of contemporary data science problems including the spiked matrix models used in sparse principal component analysis and covariance estimation and the stochastic block model used in network analysis.
• The main results are single-letter formulas (i.e., analytical expressions that can be approximated numerically) for the mutual information and the minimum mean-squared error (MMSE) in the Bayes optimal setting where the distributions of all random quantities are known.
• We provide non-asymptotic bounds and show that our formulas describe exactly the leading order terms in the mutual information and MMSE in the high-dimensional regime where the number of rows $n$ and number of columns $d$ scale with $d = O(n^\alpha)$ for some $\alpha < 1/20$.