Phase Transitions in Semidefinite Relaxations
Adel Javanmard111USC Marshall School of Business, University of Southern California, Andrea Montanari222Department of Electrical Engineering and Department of Statistics, Stanford University and Federico Ricci-Tersenghi333Dipartimento di Fisica, Universitá di Roma, La Sapienza
Abstract
Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large scale datasets.
中文速览
半正定规划（Semidefinite Programming, SDP）松弛是求解高维统计推断中NP难组合优化问题的一类重要方法，但人们对它究竟在什么条件下管用、管到什么程度，一直缺乏精确的理论刻画。本文针对图同步（graph synchronization）和网络社区发现（community detection）这两类经典问题，将对应的SDP松弛映射为统计力学中的向量自旋模型，借助统计物理中的非严格分析手段（replica方法等）精确预测了SDP的相变阈值和阈值以上的估计误差。结果表明，SDP松弛的检测阈值与贝叶斯最优估计器完全吻合，且在信噪比较高时估计精度显著优于主成分分析（PCA），逼近理论最优，兼顾了计算效率与统计性能。这一工作为理解高维统计问题中凸松弛方法的有效性提供了清晰而精确的理论图景，对算法设计与性能评估均具有重要参考价值。
原文 arXiv:1511.08769;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.08769v2