Statistical mechanics of low-rank tensor decomposition
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.
AMP algorithms have a long history dating back to early work on the statistical physics of perceptron learning [7,8] (see [9] for a review). The term AMP was coined by Donoho, Maleki and Montanari in their work on compressed sensing [10] (see also [11,12,13,14,15,16] for replica approaches to compressed sensing and high dimensional regression). AMP approximates belief propagation in graphical models and a rigorous analysis of AMP was carried out in [17]. For a rank-one matrix estimation problem, AMP was first introduced and analyzed in [18]. This framework has been extended in a beautiful body of work by Krzakla and Zdeborova and collaborators to various lowrank matrix factorization problems in [19,20,21,22]). Recently low-rank tensor decomposition through AMP was studied in [21], but their analysis was limited to symmetric tensors which are then necessarily cubic in shape. In [23], a similar approach was used to extend the analysis of order-2 tensors (matrices) to order-3 tensors, which can potentially be further extended to higher orders.
However, tensors that occur naturally in the wild are almost never cubic in shape, nor are they symmetric. The reason is that the p different modes of an order p tensor correspond to measurements across very different modalities, resulting in very different numbers of dimensions across modes, yielding highly irregularly shaped, non-cubic tensors with no symmetry properties. For example in EEG studies 3 different tensor modes could correspond to time, spatial scale, and electrodes [24]. In fMRI studies the modes could span channels, time, and patients [25]. In neurophysiological measurements they could span neurons, time, and conditions [26] or neurons, time, and trials [3]. In studies of visual cortex, modes could span neurons, time and stimuli [27].
Thus, given that tensors in the wild are almost never cubic, nor symmetric, to bridge the gap between theory and experiment, we go beyond prior work to derive and analyze Bayes optimal AMP algorithms for arbitrarily shaped high order and low rank tensor decomposition with different priors for different tensor modes, reflecting their different measurement types. We find that the low-rank decomposition problem admits two phase transitions separating three qualitatively different inference regimes: (1) the easy regime at low noise where AMP works, (2) the hard regime at intermediate noise where AMP fails but the ground truth tensor is still possible to recover, if not in a computationally tractable manner, and (3) the impossible regime at high noise where it is believed no algorithm can recover the ground-truth low rank tensor.
From a theoretical perspective, our analysis reveals several surprises relative to the analysis of symmetric cubic tensors in [21]. First, for symmetric tensors, it was shown that the easy inference regime cannot exist, unless the prior over the low rank factor has non-zero mean. In contrast, for non-symmetric tensors, one tensor mode can have zero mean without destroying the existence of the easy regime, as long as the other modes have non-zero mean. Furthermore, we find that in the space of all possible tensor shapes, the hard regime has the largest width along the noise axis when the shape is cubic, thereby indicating that tensor shape can have a strong effect on inference performance, and that cubic tensors have highly non-generic properties in the space of all possible tensor shapes.
Before continuing, we note some connections to the statistical mechanics literature. Indeed, AMP is closely equivalent to the TAP equations and the cavity method [28,29] in glassy spin systems. Furthermore, the posterior distribution of noisy tensor factorization is equivalent to p-spin magnetic systems [30], as we show below in section 2.2. For Bayes-optimal inference, the phase space of the problem is reduced to the Nishimori line [31]. This ensures that the system does not exhibit replicasymmetry breaking. Working in the Bayes-optimal setting thus significantly simplifies the statistical analysis of the model. Furthermore, it allows theoretical insights into the inference phase-transitions, as we shall see below. In practice, for many applications the prior or underlying rank of the tensors are not known a-priori. The algorithms we present here can also be applied in a non Bayes-optimal setting, where the parametric from of the prior can not be determined. In that case, the theoretical asymptotics we describe here may not hold. However, approximate Bayesian-optimal settings can be recovered through parameter learning using expectation-maximization algorithms [32]. We discuss these consequences in section 4. Importantly,the connection to the statistical physics of magnetic systems allows the adaptation of many tools and intuitions developed extensively in the past few decades, see e.g. [33]. We discuss more connections to statistical mechanics as we proceed below.
Summary: Aim of the paper is to provide a better theoretical understanding of the approximate message passing (AMP) algorithm for low-rank tensor decomposition. For this method, the author show that a mean field approximation may be used to reveal the existence of different regimes (phases) where the inference is easy, hard or impossible. They also extend the AMP algorithm of previous works to the case of non-symmetric tensors.  Strengths: Low-rank tensor decomposition is a widespread and hard problem. Defining regimes where inference is possible/impossible may help obtain one a better high-level interpretation of the task. The analysis proposed by the authors is theoretically sound and connects the tensor factorization task with nice concepts from the physics literature. Such connections have been shown to be useful and inspiring in many other cases in computer science. Finally, the proposed algorithm considerably extends the applicability of the AMP approach.  Weaknesses: It looks complicated to assess the practical impact of the paper. On the one hand, the thermodynamic limit and the Gaussianity assumption may be hard to check in practice and it is not straightforward to extrapolate what happens in the finite dimensional case. The idea of identifying the problem's phase transitions is conceptually clear but it is not explicitly specified in the paper how this can help the practitioner. The paper only compares the AMP approach to alternate least squares without mention, for example, positive results obtained in the spectral method literature. Finally, it is not easy to understand if the obtained results only regard the AMP method or generalize to any inference method.     Questions: - Is the analysis restricted to the AMP inference? In other words, could a tensor that is hard to infer via AMP approach be easily identifiable by other methods (or the other way round)?   - Are the easy-hard-impossible phases be related with conditions on the rank of the tensor?  - In the introduction the authors mention the fact that tensor decomposition is in general harder in the symmetric than in the non-symmetric case. How is this connected with recent findings about the `nice' landscape of the objective function associated with the decomposition of symmetric (orthogonal) order-4 tensors [1]?  - The Gaussian assumption looks crucial for the analysis and seems to be guaranteed in the limit r << N. Is this a typical situation in practice? Is always possible to compute the `effective' variance for non-gaussian outputs? Is there a finite-N expansion that characterize the departure from Gaussianity in the non-ideal case? - For the themodynamic limit to hold, should one require N_alpha / N  =  O(1) for all alpha? - Given an observed tensor, is it possible to determine the particular phase it belongs to?  [1] Rong Ge and Tengyu Ma, 2017, On the Optimization Landscape of Tensor Decompositions