Statistical mechanics of low-rank tensor decomposition
arXiv:1810.10065 · doi:10.1088/1742-5468/ab3216
Abstract
Often, large, high dimensional datasets collected across multiple modalities can be organized as a higher order tensor. Low-rank tensor decomposition then arises as a powerful and widely used tool to discover simple low dimensional structures underlying such data. However, we currently lack a theoretical understanding of the algorithmic behavior of low-rank tensor decompositions. We derive Bayesian approximate message passing (AMP) algorithms for recovering arbitrarily shaped low-rank tensors buried within noise, and we employ dynamic mean field theory to precisely characterize their performance. Our theory reveals the existence of phase transitions between easy, hard and impossible inference regimes, and displays an excellent match with simulations. Moreover, it reveals several qualitative surprises compared to the behavior of symmetric, cubic tensor decomposition. Finally, we compare our AMP algorithm to the most commonly used algorithm, alternating least squares (ALS), and demonstrate that AMP significantly outperforms ALS in the presence of noise.
arXiv comment27 pages, 3 figures
References in corpus (11)
- Message Passing Algorithms for Compressed Sensing
- Tensor Decomposition for Signal Processing and Machine Learning
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Statistical physics of inference: Thresholds and algorithms
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- Statistical mechanics of complex neural systems and high dimensional data
- Statistical and computational phase transitions in spiked tensor estimation
- Phase Transitions in Sparse PCA
- Statistical Mechanics of High-Dimensional Inference