  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$.
  On the technical side, this paper introduces some new techniques for the
analysis of high-dimensional matrix-valued signals. Specific contributions
include a novel extension of the adaptive interpolation method that uses
order-preserving positive semidefinite interpolation paths, and a variance
inequality between the overlap and the free energy that is based on
continuous-time I-MMSE relations.
