The decimation scheme for symmetric matrix factorization

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 Mezard, 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.