Information-Theoretic Limits for the Matrix Tensor Product
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic Block ModelSimilar Papers 제목 키워드 기반
The Matrix Hilbert Space and Its Application to Matrix Learning
Theoretical studies have proven that the Hilbert space has remarkable performance in many fields of applications. Frames in tensor product of Hilbert spaces were introduced to generalize the inner product to high-order t…
Tensor DecompositionProjected Tensor-Tensor Products for Efficient Computation of Optimal Multiway Data Representations
Tensor decompositions have become essential tools for feature extraction and compression of multiway data. Recent advances in tensor operators have enabled desirable properties of standard matrix algebra to be retained f…
Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm
In this paper, we consider the Tensor Robust Principal Component Analysis (TRPCA) problem, which aims to exactly recover the low-rank and sparse components from their sum. Our model is based on the recently proposed tens…
Tensor-Tensor Product Toolbox
The tensor-tensor product (t-product) [M. E. Kilmer and C. D. Martin, 2011] is a natural generalization of matrix multiplication. Based on t-product, many operations on matrix can be extended to tensor cases, including t…
Covariate-assisted Sparse Tensor Completion
We aim to provably complete a sparse and highly-missing tensor in the presence of covariate information along tensor modes. Our motivation comes from online advertising where users click-through-rates (CTR) on ads over v…