How do statistical dependencies in measurement noise influence high-dimensional inference? To answer this, we study the paradigmatic spiked matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We go beyond the usual independence assumption on the noise entries, by drawing the noise from a low-order polynomial orthogonal matrix ensemble. The resulting noise correlations make the setting relevant for applications but analytically challenging. We provide characterization of the Bayes optimal limits of inference in this model. If the spike is rotation invariant, we show that standard spectral PCA is optimal. However, for more general priors, both PCA and the existing approximate message-passing algorithm (AMP) fall short of achieving the information-theoretic limits, which we compute using the replica method from statistical physics. We thus propose an AMP, inspired by the theory of adaptive Thouless–Anderson–Palmer equations, which is empirically observed to saturate the conjectured theoretical limit. This AMP comes with a rigorous state evolution analysis tracking its performance. Although we focus on specific noise distributions, our methodology can be generalized to a wide class of trace matrix ensembles at the cost of more involved expressions. Finally, despite the seemingly strong assumption of rotation-invariant noise, our theory empirically predicts algorithmic performance on real data, pointing at strong universality properties.

The deep Boltzmann machine on the Nishimori line with a finite number of layers is exactly solved by a theorem that expresses its pressure through a finite dimensional variational problem ofmin–maxtype. In the absence of magnetic fields the order parameter is shown to exhibit a phase transition whose dependence on the geometry of the system is investigated.

The Wigner spiked model in a mismatched setting is studied with the finite temperature Statistical Mechanics approach through its representation as a Sherrington-Kirkpatrick model with added Mattis interaction. The exact solution of the model with Ising spins is rigorously proved to be given by a variational principle on two order parameters, the Parisi overlap distribution and the Mattis magnetization. The latter is identified by an ordinary variational principle and turns out to concentrate in the thermodynamic limit. The solution leads to the computation of the Mean Square Error of the mismatched reconstruction. The Gaussian signal distribution case is investigated and the corresponding phase diagram is identified.

Matrix factorization is an inference problem that has acquired importance due to its vast range of applications that go from dictionary learning to recommendation systems and machine learning with deep networks. The study of its fundamental statistical limits represents a true challenge, and despite a decade-long history of efforts in the community, there is still no closed formula able to describe its optimal performances in the case where the rank of the matrix scales linearly with its size. In the present paper, we study this extensive rank problem, extending the alternative ‘decimation’ procedure that was recently introduced by Camilli and Mézard, and carry out a thorough study of its performance. Decimation aims at recovering one column/line of the factors at a time, by mapping the problem into a sequence of neural network models of associative memory at a tunable temperature. The main advantage of decimation is that its theoretical performance can be studied using statistical physics techniques. In this paper we provide the general analysis applying to a large class of compactly supported priors and we show that the replica symmetric free entropy of the neural network models takes a universal form in the low temperature limit. We then study the decimation phase diagrams in two concrete cases, the sparse Ising prior and the uniform prior, for which we show that matrix factorization is theoretically possible when the ration P / N of rank to variable is below a certain threshold. This suggest that a possible route to solving algorithmically the matrix factorization problem could be to find efficient decimation algorithms; in this respect, we show that simple simulated annealing, though being effective for limited signal sizes, is not scalable.

Matrix factorization is an important mathematical problem encountered in the context of dictionary learning, recommendation systems, and machine learning. We introduce a decimation scheme that maps it to neural network models of associative memory and provide a detailed theoretical analysis of its performance, showing that decimation is able to factorize extensive-rank matrices and to denoise them efficiently. In the case of binary prior on the signal components, we introduce a decimation algorithm based on a ground-state search of the neural network, which shows performances that match the theoretical prediction.