We analyse the matrix factorization problem. Given a noisy measurement of a
product of two matrices, the problem is to estimate back the original matrices.
It arises in many applications such as dictionary learning, blind matrix
calibration, sparse principal component analysis, blind source separation, low
rank matrix completion, robust principal component analysis or factor analysis.
It is also important in machine learning: unsupervised representation learning
can often be studied through matrix factorization. We use the tools of
statistical mechanics - the cavity and replica methods - to analyze the
achievability and computational tractability of the inference problems in the
setting of Bayes-optimal inference, which amounts to assuming that the two
matrices have random independent elements generated from some known
distribution, and this information is available to the inference algorithm. In
this setting, we compute the minimal mean-squared-error achievable in principle
in any computational time, and the error that can be achieved by an efficient
approximate message passing algorithm. The computation is based on the
asymptotic state-evolution analysis of the algorithm. The performance that our
analysis predicts, both in terms of the achieved mean-squared-error, and in
terms of sample complexity, is extremely promising and motivating for a further
development of the algorithm.

使用统计力学工具分析了矩阵分解问题的可实现性和计算可处理性，在贝叶斯最优推断设置下计算任意计算时间内可能实现的最小均方误差和有效近似迭代推理算法可以达到的误差。