The Decimation Scheme for Symmetric Matrix Factorization
Francesco Camilli Marc Mézard
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
we recently introduced, 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. Though being sub-optimal, decimation has the
advantage of being theoretically analyzable. We extend its scope and analysis
to two families of matrices. For a large class of compactly supported priors,
we show that the replica symmetric free entropy of the neural network models
takes a universal form in the low temperature limit. For sparse Ising prior, we
show that the storage capacity of the neural network models diverges as
sparsity in the patterns increases, and we introduce a simple algorithm based
on a ground state search that implements decimation and performs matrix
factorization, with no need of an informative initialization.