Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
复制标题
约束低秩矩阵估计：相变、近似消息传递和应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
L. Zdeborová
中科院分区：
文献类型：
--
作者：
T. Lesieur;Florent Krzakala;L. Zdeborová
本文是 Lesieur 等人之前工作的扩展版本（2015 IEEE Int. Symp. on Information Theory Proc. pp 1635–9 和 2015 年第 53 届 Allerton Conf. on Communication, Control andComputing (IEEE) pp 680–7），在对矩阵分解的因素存在约束的情况下进行低秩矩阵估计。低秩矩阵分解是数据分析中用于相关特征的无监督学习和其他类型的降维的基本方法之一。我们提出了一个框架来研究因素的一般先验的约束低秩矩阵估计，以及观察矩阵的一般输出通道。我们与矢量自旋玻璃模型的研究进行了类比——提出了一种统一的方法来研究先前在单独的统计物理著作中考虑的许多问题。我们针对数据分析中的问题提出了许多应用。我们详细推导了低秩近似消息传递 (Low-RAMP) 算法的一般形式，在统计物理学中称为 TAP 方程。因此，我们统一了谢林顿-柯克帕特里克模型、受限玻尔兹曼机、霍普菲尔德模型或矢量（xy、海森堡和其他）自旋玻璃等不同模型的 TAP 方程的推导。 Low-RAMP算法的状态演化也得到了推导，相当于大类矢量自旋玻璃模型的复制对称解。在专门讨论结果的部分中，我们详细研究了低秩矩阵估计中贝叶斯最优推理的相图和相变。我们提出了相变的类型及其与低 RAMP 或常用光谱方法等算法性能的关系。
This article is an extended version of previous work of Lesieur et al (2015 IEEE Int. Symp. on Information Theory Proc. pp 1635–9 and 2015 53rd Annual Allerton Conf. on Communication, Control and Computing (IEEE) pp 680–7) on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a parallel with the study of vector-spin glass models—presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low-RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as different as the Sherrington–Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayes-optimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods.